[C++ algorithm] 미로게임 준비

C++ 알고리즘을 다루기 위해 미로게임을 통해 차근차근 하나씩 쌓아 올릴 예정이다.

가령 미로를 탈출하는 알고리즘을 처음에는 오른손 법칙부터 그걸 개선하고 길 찾기 알고리즘으로 수정하는 식으로 말이다.

환경 설정

Visual Studio 2022으로 진행한다. 콘솔앱으로 진행할 것이기 때문에 어떤 버전으로 해도 상관은 없다. 

일반 algorithm을 공부할 때는 algorithm 프로젝트에, maze는 maze 프로젝트에서 관리를 하겠다.

 

그리고 ConsoleHelper 클래스를 하나 만들겠다. 이는 콘솔에 출력하는 것을 도와주는 클래스 이다.

Maze의 속성에 들어가 미리 선언된 컴파일러 헤더를 '사용'으로 바꿔주고 헤더 파일은 pch.h로 설정한다.

pch 클래스를 만들고 pch.cpp 속성을 들어거 미리 컴파일된 헤더를 만들기로 설정해주면 우리가 공용으로 사용하는 헤더들을 pch.h에 넣으면 된다.

Types 헤더는 다음과 같이 정의한다. __int64 같은 타입명이 긴 키워드들을 짧게 쓰기 위해 따로 정의한 것이다.

콘솔 헬퍼에서는 우리가 콘솔에 그릴때 사용할 색상들을 enum class를 통해 정의 하고 콘솔에 출력을 위해 여러 함수들을 제공한다.

ConsoleHelper.h

#pragma once
#include <Windows.h>
#include "Types.h"
enum class ConsoleColor
{
	BLACK = 0,
	RED = FOREGROUND_RED,
	GREEN = FOREGROUND_GREEN,
	BLUE = FOREGROUND_BLUE,
	YELLOW = RED | GREEN,
	WHITE = RED | GREEN | BLUE,
};
class ConsoleHelper
{
public:
	static void SetCursorPosition(int32 x, int32 y);
	static void SetCursorColor(ConsoleColor color);
	static void ShowConsoleCurosr(bool flag);
};

ConsoleHelper.cpp

#include "ConsoleHelper.h"
#include"pch.h"

void ConsoleHelper::SetCursorPosition(int32 x, int32 y)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	COORD pos = { static_cast<SHORT>(x), static_cast<SHORT>(y) };
	::SetConsoleCursorPosition(output, pos);
}

void ConsoleHelper::SetCursorColor(ConsoleColor color)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	::SetConsoleTextAttribute(output, static_cast<int16>(color));
}

void ConsoleHelper::ShowConsoleCurosr(bool flag)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	CONSOLE_CURSOR_INFO cursorInfo;
	::GetConsoleCursorInfo(output, &cursorInfo);
	cursorInfo.bVisible = flag;
	::GetConsoleCursorInfo(output, &cursorInfo);
}

Maze.cpp

#include "pch.h"
#include "ConsoleHelper.h"
#include <iostream>

int main()
{
	uint64 lastTick = 0;
	while (true)
	{
#pragma region 프레임 관리
		const uint64 currentTick = ::GetTickCount64();
		const uint64 deltaTic = currentTick - lastTick;
		lastTick = currentTick;
#pragma endregion

		// 입력
		
		// 로직
		
		// 렌더링
		
		ConsoleHelper::SetCursorPosition(0, 0);
		ConsoleHelper::ShowConsoleCurosr(false);
		ConsoleHelper::SetCursorColor(ConsoleColor::RED);
		const char* TILE = "■";
		for (int32 y = 0; y < 25; y++)
		{
			for (int32 x = 0; x < 25; x++)
			{
				cout << TILE;
			}
			cout << endl;
		}
	}
}

이것이 미로게임을 사용할 때 쓸 기본적인 맵이다.

 

맵 만들기

메인 함수에서 계속해서 렌더링을 해주는 코드는 좋지 않은 코드 일 것이다. 그렇기 때문에 Board라는 클래스를 하나 생성해 거기서 렌더링을 담당하겠다. 그전에 pch.h에 우리가 추가적으로 사용할 Pos과 Dir을 정의해주겠다.

pch.h

#pragma once

#include <Windows.h>
#include <iostream>
#include <vector>
#include "Types.h"

using namespace std;

struct  Pos
{
	bool operator==(Pos& other)
	{
		return y == other.y && x == other.x;
	}
	bool operator!=(Pos & other)
	{
		return !(*this == other);
	}
	Pos operator+(Pos& other)
	{
		Pos ret;
		ret.y = y + other.y;
		ret.x = x + other.x;
		return ret;
	}
	Pos& operator+=(Pos& other)
	{
		y += other.y;
		x += other.x;
		return *this;
	}
	int32 y = 0;
	int32 x = 0;
};
enum Dir
{
	DIR_UP = 0,
	DIR_LEFT = 1,
	DIR_DOWN = 2,
	DIR_RIGHT = 3,

	DIR_COUNT = 4,
};

그리고 실제 렌더링을 할 Board 클래스와 Player 클래스를 생성한다.

Board.h

#pragma once
#include "ConsoleHelper.h"
class Player;
enum 
{
	BOARD_MAX_SIZE = 100
};
enum class TileType
{
	NONE = 0,
	EMPTY,
	WALL,
};
class Board
{
public:
	Board();
	~Board();

	void Init(int32 size, Player* player);
	void Render();
	TileType GetTileType(Pos pos);
	ConsoleColor GetTileColor(Pos pos);
	Pos GetEnterPos() { return Pos{ 1,1 }; }
	Pos GetExitPos() { return Pos{ _size - 2, _size - 2 }; }
	void GenerateMap();
private:
	TileType	_tile[BOARD_MAX_SIZE][BOARD_MAX_SIZE] = {};
	int32		_size = 0;
	Player*		_player;
};

Board.cpp

#include "pch.h"
#include "Player.h"
#include "Board.h"
#include "ConsoleHelper.h"
const char* TILE = "■";

Board::Board()
{
}

Board::~Board()
{
}

void Board::Init(int32 size, Player* player)
{
	_size = size;
	_player = player;
	GenerateMap();
}

void Board::Render()
{
	ConsoleHelper::SetCursorPosition(0, 0);
	ConsoleHelper::ShowConsoleCurosr(false);
	ConsoleHelper::SetCursorColor(ConsoleColor::RED);
	
	for (int32 y = 0; y < 25; y++)
	{
		for (int32 x = 0; x < 25; x++)
		{
			ConsoleColor color = GetTileColor(Pos{y, x});
			ConsoleHelper::SetCursorColor(color);

			cout << TILE;
		}
		cout << endl;
	}
}

TileType Board::GetTileType(Pos pos)
{
	if(pos.x < 0 || pos.x >= _size)
		return TileType::NONE;

	if (pos.y < 0 || pos.y >= _size)
		return TileType::NONE;

	return _tile[pos.y][pos.x];
}

ConsoleColor Board::GetTileColor(Pos pos)
{
	if (_player && _player->GetPos() == pos)
		return ConsoleColor::YELLOW;
	if (GetExitPos() == pos)
	{
		return ConsoleColor::BLUE;
	}
	TileType tileType = GetTileType(pos);

	switch (tileType)
	{
	case TileType::EMPTY:
		return ConsoleColor::GREEN;
	case TileType::NONE:
		break;
	case TileType::WALL:
		return ConsoleColor::RED;
	}

	return ConsoleColor::WHITE;
}

// Binary Tree 미리 생성 알고리즘
// - Mazes For Programmers
void Board::GenerateMap()
{
	for (int32 y = 0;  y < _size;  y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
			{
				_tile[y][x] = TileType::WALL;
			}
			else
			{
				_tile[y][x] = TileType::EMPTY;
			}
		}
	}
	// 랜덤으로 우측 혹은 아래로 길을 뚫어주기.
	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
				continue;
			if (y == _size - 2 && x == _size - 2)
				continue;
			if (y == _size - 2)
			{
				_tile[y][x + 1] = TileType::EMPTY;
				continue;
			}
			if (x == _size - 2)
			{
				_tile[y + 1][x] = TileType::EMPTY;
				continue;
			}
			const int32 randValue = ::rand() % 2;
			if (randValue == 0)
			{
				_tile[y][x + 1] = TileType::EMPTY;
			}
			else
			{
				_tile[y + 1][x] = TileType::EMPTY;
			}
		}
	}
}

Player.h

#pragma once
class Board;

class Player
{
public:
	void Init(Board* board);
	void Update(uint64 deltaTick);
	void SetPos(Pos pos) { _pos = pos; }
	Pos GetPos() { return _pos; }
private:
	Pos _pos = {};
	int32 _dir = DIR_UP;
	Board* _board = nullptr;
};

Player.cpp

#include "pch.h"
#include "Player.h"
#include "Board.h"

void Player::Init(Board* board)
{
	_pos = board->GetEnterPos();
	_board = board;
}

void Player::Update(uint64 deltaTick)
{
	// 여기에서 여러 길 찾기 알고리즘 도입 예정
}

Maze.cpp

#include "pch.h"
#include "ConsoleHelper.h"
#include <iostream>
#include "Board.h"
#include "Player.h"

Board board;
Player player;
int main()
{
	::srand(static_cast<unsigned int>(time(nullptr)));
	uint64 lastTick = 0;
	board.Init(25, &player);
	player.Init(&board);
	while (true)
	{
#pragma region 프레임 관리
		const uint64 currentTick = ::GetTickCount64();
		const uint64 deltaTic = currentTick - lastTick;
		lastTick = currentTick;
#pragma endregion

		// 입력
		
		// 로직
		
		// 렌더링
		board.Render();
		
	}
}

 

이로써 여러 길찾기 알고리즘을 공부하기 위한 미로를 만들었다.

오른손 법칙

가장 간단한 우수법(오른손 법칙)을 코딩해보겠다. 우수법은 무조건 오른쪽 벽을 따라서 가다보면 출구에 도달할 수 있다는 법칙이다. 이는 매번 유효한게 아니고 순환 구조가 아니고 모든 길이 이어져있다고 가정하면 유효하다.

제일 무식한 방법이지만 한번 해보겠다.

Player.h

#pragma once
class Board;

class Player
{
	enum 
	{
		MOVE_TICK = 100
	};
public:
	void Init(Board* board);
	void Update(uint64 deltaTick);

	void SetPos(Pos pos) { _pos = pos; }
	Pos GetPos() { return _pos; }

	bool CanGo(Pos pos);
private:
	Pos _pos = {};
	int32 _dir = DIR_UP;
	Board* _board = nullptr;

	vector<Pos> _path;
	uint32 _pathIndex = 0;
	uint64 _sumTick = 0;
};

Player.cpp

#include "pch.h"
#include "Player.h"
#include "Board.h"

void Player::Init(Board* board)
{
	_pos = board->GetEnterPos();
	_board = board;

	Pos pos = _pos;	// 임시

	_path.clear();
	_path.push_back(pos);
	//목적지 도착하기 전에는 계속 실행
	Pos dest = board->GetExitPos();
	
	Pos front[4] = {
		Pos {-1, 0},	// up
		Pos {0 , -1},	// left
		Pos {1, 0},		// down
		Pos {0, 1},		// right
	};
	while (pos != dest)
	{
		// 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인
		int32 newDir = (_dir - 1 + DIR_COUNT) % DIR_COUNT;
		if (CanGo(pos + front[newDir]))
		{
			// 오른쪽 방향으로 90 회전.
			_dir = newDir;
			// 앞으로 한 보 전진
			pos += front[_dir];
			_path.push_back(pos);
		}
		// 2. 현재 바라보는 방향으로 기준으로 전진할 수 있는지 확인.
		else if (CanGo(pos + front[_dir]))
		{
			// 앞으로 한보 전진.
			pos += front[_dir];
			_path.push_back(pos);
		}
		else
		{	
			// 왼쪽 방향으로 90도 회전.
			_dir = (_dir + 1) % DIR_COUNT;
		}
	}
}

void Player::Update(uint64 deltaTick)
{
	if (_pathIndex >= _path.size())
		return;
	_sumTick += deltaTick;
	if (_sumTick >= MOVE_TICK)
	{
		_sumTick = 0;

		_pos = _path[_pathIndex];
		_pathIndex++;
	}
}

bool Player::CanGo(Pos pos)
{
	TileType tileType = _board->GetTileType(pos);
	return tileType == TileType::EMPTY;
}

우수법을 계산하는거는 Player가 생성되고 Init 될때 미리 계산을 한후 Update에서 매 프레임 마다 미리 계산된 판을 한칸씩 이동하는 식으로 구현했다. 물론 실시간으로 계산해도 전혀 문제가 되지 않는다.

 

여기서 중요한 점은 우리가 방향과 앞으로 한칸 전진을 하는 방식이 switch-case 문이 아니라 배열과 enum 값으로 해결을 했다 이부분의 코드를 유의깊게 보자. 알고리즘 코테 문제에서 유용하게 사용할 수 있을 것이다.

 

결과