[C++/STL] Ranking System 소개 및 구현

프로젝트 소개

프로젝트 내용: 플레이어 랭킹 관리 프로그램 작성

프로그램 요구사항

• STL Container, Iterator, Algorithm을 사용한다.
• 플레이어는 다른 플레이어와 구분되는 고유ID를 갖는다.
• 플레이어는 챔피언스리그 / 떼탈출에서 얻은 점수를 멤버변수로 갖는다.

초기화

100,000 명의 플레이어를 생성한다. 랜덤엔진을 사용하여 플레이어의 점수를 생성한다.

 

게임진행 - 한 번 진행할 때마다 게임 한 시즌이 끝났다고 가정한다. 

전체 100,000 플레이어 중 임의의 50,000 명의 플레이어가 떼탈출을 플레이한다. 또 다른 임의의 50,000 명의 플레이어가 챔피언스리그를 플레이한다.

 

떼탈출에서 획득한 점수는 0~2,905,887,026점 사이의 정규분포값을 갖도록 설정한다. 챔피언스리그에서 점수는 0~1,112,670,384점 사이의 정규분포값을 갖도록 설정한다.

 

플레이어가 얻은 점수가 이전 점수보다 높으면 높은 점수를 저장한다. 프로그램은 찾고자 하는 플레이어의 정보를 확인하여 존재하는 플레이어라면 떼탈출과 챔피언스리그에서 얻은 점수를 다른 플레이어의 점수와 비교하여

• 내 등수, 상위 몇 %인가, 내 점수는 얼마인가를 표시한다.
• 내 순위 기준으로 내 위와 아래 순위 플레이어의 id와 점수를 표시한다.

---

프로젝트 구현

랭킹 시스템 프로젝트를 구현하고, 컨테이너 별 성능을 비교하여 적합한 STL 컨테이너를 선택합니다.

 

▶ 랭킹시스템 프로젝트 특징 - 검색기능

• 한 번 진행할 때마다 게임 한 시즌이 끝났다고 가정한다.
• 내 정보를 알아야 하고, 내 순위 기준으로 위 아래 순위 플레이어 정보를 알아내야한다.

▶ 모든 플레이어들을 관리할 컨테이너 목록 (어뎁터 컨테이너는 제외하겠습니다.)

• 시퀀스 컨테이너
  • vector
  • deque
  • list / Forward list
• 연관 컨테이너
  • map / multi, unordered
  • set / multi, unordered

▶ 성능분석

• 시퀀스 컨테이너 vs 연관 컨테이너
• 시퀀스 컨테이너가 더 빠르다면?
  • Sequential access(순차 접근) vs Random access(비순차 접근)

▶ 구현내용

<파라미터>

- 플레이어 클래스

#pragma once

class Player
{
private:
	string m_ID;
	unsigned int m_Breakout;			// 떼탈출 점수
	unsigned int m_ChampionsLeague;	// 챔피언스리그 점수

public:
	string GetID() const;

	void SetBreakoutScore(unsigned int score);
	unsigned int GetBreakoutScore() const;

	void SetChampionsLeagueScore(unsigned int score);
	unsigned int GetChampionsLeagueScore() const;

public:
	void UpdateBreakout(unsigned int breakout);
	void UpdateChampionsLeague(unsigned int championsLeague);

public:
	explicit Player(std::string id);
	virtual ~Player();
};

#include "stdafx.h"
#include "Player.h"

Player::Player(std::string id) : m_ID(id),
	m_Breakout(0), m_ChampionsLeague(0)
{
}

Player::~Player()
{
}

string Player::GetID() const
{
	return m_ID;
}

void Player::SetBreakoutScore(unsigned int score)
{
	m_Breakout = score;
}

unsigned int Player::GetBreakoutScore() const
{
	return m_Breakout;
}

void Player::SetChampionsLeagueScore(unsigned int score)
{
	m_ChampionsLeague = score;
}

unsigned int Player::GetChampionsLeagueScore() const
{
	return m_ChampionsLeague;
}

void Player::UpdateBreakout(unsigned int breakout)
{
	// 갱신된 점수가 기존점수보다 높을경우만 업데이트를한다.
	if(breakout > m_Breakout)
		m_Breakout = breakout;
}

void Player::UpdateChampionsLeague(unsigned int championsLeague)
{
	// 갱신된 점수가 기존점수보다 높을경우만 업데이트를한다.
	if (championsLeague > m_ChampionsLeague)
		m_ChampionsLeague = championsLeague;
}

- 전역변수

#define VERSION_SEQUENCE 0xFF1
//#define VERSION_ASSOCIATE 0xFF2

constexpr int TOTAL_PLAYER_COUNT = 10'0000;
enum GAMETYPE {BREAKOUT = 0, CHAMPIONS_LEAGUE};

namespace SharedRandomValue
{
	default_random_engine dre;
	uniform_int_distribution<> randomNameLen(3, 7);
	uniform_int_distribution<> randomName('a', 'z');

	normal_distribution<double> breakoutDistribution(0.0f, 1.0f);
	normal_distribution<double> championsLeagueDistribution(0.0f, 1.0f);
	normal_distribution<double> chooseDistribution(0.0f, 1.0f);
}

// 전체플레이어를 담고있는 컨테이너
std::vector<Player*> g_AllPlayers;
// 플레이어가 존재하는지 여부를 알기위한 컨테이너
std::set<string> g_IsPlayer;

<유틸메서드>

- Util

namespace Util
{
	double CalcNormalDistribScore(GAMETYPE gameType)
	{
		double score = 0;

		if (gameType == GAMETYPE::BREAKOUT)
		{
			score = SharedRandomValue::breakoutDistribution(SharedRandomValue::dre);
			score = clamp(score, -5.0, 5.0);
			score += 5.0;
			score *= 2905'8870'2.6;
		}
		else if (gameType == GAMETYPE::CHAMPIONS_LEAGUE)
		{
			score = SharedRandomValue::championsLeagueDistribution(SharedRandomValue::dre);
			score = clamp(score, -5.0, 5.0);
			score += 5.0;
			score *= 1112'6703'8.4;
		}

		return score;
	}
}

- GameUtil

namespace GameUtil
{
	void CreatePlayers()
	{
		g_AllPlayers.resize(TOTAL_PLAYER_COUNT);

		// 저장한 파일이 없다면 100,000 명의 플레이어를 생성한다.
		for (int i = 0; i < TOTAL_PLAYER_COUNT; ++i)
		{
			// 이름생성
			string id;
			for (int i = 0; i < SharedRandomValue::randomNameLen(SharedRandomValue::dre); ++i) id += SharedRandomValue::randomName(SharedRandomValue::dre);

			// 정규분포값 생성 (breakout, championsLeague)
			double breakout_Distribution = Util::CalcNormalDistribScore(GAMETYPE::BREAKOUT);
			double championsLeague_Distribution = Util::CalcNormalDistribScore(GAMETYPE::CHAMPIONS_LEAGUE);

			Player* player = new Player(id);
			player->SetBreakoutScore(breakout_Distribution);
			player->SetChampionsLeagueScore(championsLeague_Distribution);

			// 모든 플레이어를 담는 vector
			g_AllPlayers[i] = player;
			// 플레이어 존재여부를 위한 컨테이너 set
			g_IsPlayer.emplace(id);
		}
	}

	void ShowRanking(const int index, GAMETYPE gameType)
	{
		if (index < 0) return;

#ifdef VERSION_SEQUENCE
		if (gameType == GAMETYPE::BREAKOUT)
			cout << g_AllPlayers[index]->GetID() << " " << index << "등 " << "상위 " << (index) * 100.f / TOTAL_PLAYER_COUNT << "%" << " 점수 " << g_AllPlayers[index]->GetBreakoutScore() << endl;
		else
			cout << g_AllPlayers[index]->GetID() << " " << index << "등 " << "상위 " << (index) * 100.f / TOTAL_PLAYER_COUNT << "%" << " 점수 " << g_AllPlayers[index]->GetChampionsLeagueScore() << endl;
#endif
	}
}

<프로젝트 프로세스>

- main

int main()
{
	/*[초기화]*/
	// 저장한 파일이 없다면 100,000 명의 플레이어를 생성한다.
	// 랜덤엔진을 사용하여 플레이어의 점수를 생성한다. (normal_distribution을 사용할 것)
	// 닉네임 받아오기
	GameUtil::CreatePlayers();

	cout << "My Player ID: " << g_AllPlayers[0]->GetID() << endl;

	// While loop
	/*[게임진행] - 한 번 진행할 때마다 게임 한 시즌이 끝났다고 가정한다.*/
	while (true)
	{
		string id;
		cout << "ID를 입력하세요: ";
		cin >> id;
		
		// 플레이어 여부 체크
		if (g_IsPlayer.count(id) == 0) {
			cout << "존재하지 않는 ID입니다." << endl << endl;
		}
		else Process(id);
	}
}

- Process

void Process(string id)
{
	cout << "------------------------------------------------------------------------" << endl;
	// 스코어 정규분포값 구하기
	double breakout_Distribution = Util::CalcNormalDistribScore(GAMETYPE::BREAKOUT);
	double championsLeague_Distribution = Util::CalcNormalDistribScore(GAMETYPE::CHAMPIONS_LEAGUE);

	// 점수 업데이트
	// 임의의 50, 000 명의 플레이어가 떼탈출을 플레이한다.
	// 또 다른 임의의 50, 000 명의 플레이어가 챔피언스리그를 플레이한다.
	for (auto& p : g_AllPlayers)
	{
		if (SharedRandomValue::chooseDistribution(SharedRandomValue::dre) < 0)
			p->UpdateBreakout(breakout_Distribution);
		else
			p->UpdateChampionsLeague(championsLeague_Distribution);
	}

	// chrono 시간측정 시작
	auto start_t = high_resolution_clock::now();
#ifdef VERSION_SEQUENCE
	/* Breakout Score */
	// Breakout 기준으로 내림차순 정렬
	// TimeComplex :  quicksort (nlogN ~ n^2)
	sort(g_AllPlayers.begin(), g_AllPlayers.end(), [](const Player* player1, const Player* player2) {
		return player1->GetBreakoutScore() > player2->GetBreakoutScore();
		});

	// Breakout Score 검색 
	// TimeComplex :  순차탐색(N)
	auto iter = find_if(g_AllPlayers.begin(), g_AllPlayers.end(), [&](const Player* player1) {
		return player1->GetID() == id;
		});

	int index = iter - g_AllPlayers.begin();

	// ShowScreen
	cout << "[ 때탈출 ]" << endl;
	GameUtil::ShowRanking( index - 1, GAMETYPE::BREAKOUT);
	GameUtil::ShowRanking(index, GAMETYPE::BREAKOUT);
	GameUtil::ShowRanking(index + 1, GAMETYPE::BREAKOUT);
	cout << endl;

	//////////////////////////////////////////////////////////
	/* Champions-League Score */
	sort(g_AllPlayers.begin(), g_AllPlayers.end(), [](const Player* player1, const Player* player2) {
		return player1->GetChampionsLeagueScore() > player2->GetChampionsLeagueScore();
		});

	iter = find_if(g_AllPlayers.begin(), g_AllPlayers.end(), [&](const Player* player1) {
		return player1->GetID() == id;
		});
	index = iter - g_AllPlayers.begin();

	cout << "[ 챔피언스리그 ]" << endl;
	GameUtil::ShowRanking(index - 1,GAMETYPE::CHAMPIONS_LEAGUE);
	GameUtil::ShowRanking(index, GAMETYPE::CHAMPIONS_LEAGUE);
	GameUtil::ShowRanking(index + 1, GAMETYPE::CHAMPIONS_LEAGUE);
	cout << endl;
#elif VERSION_ASSOCIATE
	// 정렬을 위해 각 분야마다 multimap 생성
	map<int, Player*> breakoutMap;
	map<int, Player*> championsLeagueMap;

	for (auto& p : g_AllPlayers) {
		breakoutMap.emplace(p->GetBreakoutScore(), p);
		championsLeagueMap.emplace(p->GetChampionsLeagueScore(), p);
	}

	map<int, Player*>::iterator breakoutIter;
	for (auto iter = breakoutMap.begin(); iter != breakoutMap.end(); ++iter)
	{
		if (iter->second->GetID() == id) {
			breakoutIter = iter;
			break;
		}
	}

	auto previter = breakoutIter;
	auto preiter = breakoutIter;

	cout << "[ 때탈출 ]" << endl;
	cout << (--previter)->second->GetID() << " 점수" << (--previter)->first << endl;
	cout << breakoutIter->second->GetID() << " 점수" << breakoutIter->first << endl;
	cout << (++preiter)->second->GetID() << " 점수" << (++preiter)->first << endl;
	cout << endl;

	map<int, Player*>::iterator champMap;
	for (auto iter = championsLeagueMap.begin(); iter != championsLeagueMap.end(); ++iter)
	{
		if (iter->second->GetID() == id) {
			champMap = iter;
			break;
		}
	}

	previter = champMap;
	preiter = champMap;

	cout << "[ 챔피언스리그 ]" << endl;
	cout << (--previter)->second->GetID() << " 점수" << (--previter)->first << endl;
	cout << champMap->second->GetID() << " 점수" << champMap->first << endl;
	cout << (++preiter)->second->GetID() << " 점수" << (++preiter)->first << endl;
	cout << endl;
#endif

	auto end_t = high_resolution_clock::now();
	auto exec_time = end_t - start_t;
	cout << "Exec Time = " << duration_cast<milliseconds>(exec_time).count() << "ms" << endl;
	cout << "------------------------------------------------------------------------" << endl;
}

---

프로젝트 출처

한국산업기술대학교 게임공학부 윤정현교수님 STL 수업 과제