[C++] 미로게임 | 미로 생성 알고리즘-프림 알고리즘

미로 게임 프로젝트의 미로 생성 방식을 변경했습니다.

 

최종 결과인 Prim알고리즘으로 생성한 미로를 먼저 보여드리고 시작하겠습니다.

 

[사진 1] Prim 알고리즘

 

기존에 만들었던 미로 생성 방식인 SideWinder 알고리즘으로 생성한 미로를 확인해보면,

 

[사진 2] SideWinder 알고리즘

 

[사진 2]을 보면 알 수 있듯이 SideWinder 알고리즘 특성상 마지막 행과 마지막 열에는 벽이 전혀 없는 구조를 만들어냅니다. 이 알고리즘의 한계를 보완하기 위해, 더 다양하고 복잡한 미로 생성 방법을 모색했습니다. 그 결과, Hunt and Kill과 Prim 알고리즘을 새로운 미로 생성 기법으로 선정하여 개발에 적용하게 됐습니다.

 

먼저 Hunt and Kill 알고리즘을 사용하여 미로를 구현했으나, 결과적으로 미로의 형태가 만족스럽지 않았습니다. 더 복잡한 형태의 미로를 위해 prim 알고리즘으로 전환하여 개발을 다시 진행했습니다.

 

간단하게 prim 알고리즘에 대해 설명하면, 최소 신장 트리(Minimum Spanning Tree, MST)를 만드는 알고리즘 중 하나입니다. prim 알고리즘은 priority queue를 활용하며, O(NlogN)의 시간 복잡도를 가지고 있습니다.

Kruskal과 prim 알고리즘에 대한 자세한 설명은 나중에 시간이 되면 정리하겠습니다.

 

*MST는 모든 노드를 가장 적은 수의 간선과 비용으로 연결한 트리입니다. 즉, 모든 노드는 서로 연결되어 있습니다.

 

---

 

Prim 알고리즘을 미로 생성에 어떻게 적용 할 수 있는지 고민해본 결과, MST와 미로의 공통점을 찾았습니다. MST는 모든 노드가 연결되어 있으며, 미로는 모든 장소에서 도착지까지 도달할 수 있어야 합니다.

즉, 미로의 모든 장소가 연결되어 있어야 하기 때문에 MST와 같은 형태를 보이게 됩니다.

 

미로 생성 흐름을 간단하게 정리했습니다. 

1. 초기에 벽이 아닌 공간(길)을 설정한다.
2. 길을 각각 노드라고 생각하며 간선으로 연결한다.
3. 비용이 적은 간선을 기준으로 모든 길을 연결한다.

 

[미로 생성 흐름을 자세히 보기]

[사진 3] 초기 상태의 미로

 

1. 초기에 벽이 아닌 공간(길)을 설정한다.

- 홀수 행/열을 길로 설정한다.

2. 길을 각각 노드라고 생각하며 간선으로 연결한다.

- 이웃 상태의 길을 간선으로 연결한다.

- 이때 각 간선의 비용은 랜덤으로 설정하며, 양방향 간선으로 만든다.

3. 비용이 적은 간선을 기준으로 모든 길을 연결한다. (Prim 알고리즘)

- 1. 시작 노드(길)를 정해 우선 순위 큐에 넣는다.

- 2. 우선 순위 큐에서 하나를 꺼낸다.

   *방문하지 않은 노드가 나올 때까지 2번을 반복한다.

- 3. 현재 선택된 노드를 방문 표시 해준다.

- 4. 현재 노드와 연결할 노드 사이의 벽을 없앤다. 즉, 두 노드는 이어진 길이 된다.  

- 5. 노드와 연결된 모든 간선을 우선순위 큐에 넣는다. 

- 6. 모든 노드를 방문할 때까지 2~5번을 반복한다.

 

---

 

[결과 보기]

[사진 4] Prim 알고리즘을 적용한 미로 생성

 

---

 

코드는 아래 블로그를 참고했습니다.

https://choi-dan-di.github.io/algorithm/prim-algorithm/

[Algorithm] 프림(Prim) 알고리즘

 

Map을 활용한 구현 방식이 있으며, map이 익숙지 않은 분들을 위해 map을 사용하지 않은 방식이 있습니다.

만약 map에 대해 잘 모르시면, map을 사용하지 않은 방법을 확인해도 무방합니다.

 

Map 사용 방식과 Map을 사용하면서 발생한 시행착오를 정리했으니 원하시는 분은 보시면 됩니다.

 

https://end-of-code.tistory.com/entry/C-map%EA%B3%BC-unorderedmap%EC%9D%B4%EB%9E%80

[C++] map과 unordered_map이란?

 

[Map을 사용한 방식]

[Board.h]

#pragma once
#ifndef __BOARD_H__
#define __BOARD_H__
#define RandomMod 100
#define AI_MOVE_SECOND 125

#include <iostream>
#include <queue>
#include <map>
#include <climits>
#include <vector>
#include <algorithm>
#include <ctime>
#include <Windows.h>

using namespace std;

class Board
{
private:
	enum class EWallType
	{
		Road,
		Wall
	};

	struct Pos {
		int row, col;

		Pos() { row = -1, col = -1; }
		Pos(int row, int col) : row(row), col(col) {}

		bool operator<(const Pos& o) const {
			if (row == o.row) return col < o.col;
			return row < o.row;
		}
	};

	struct EdgeInfo
	{
		Pos pos;
		int cost;

		EdgeInfo(Pos pos, int cost) : pos(pos), cost(cost) {}

		bool operator<(const EdgeInfo& o) const { return cost > o.cost; }
	};

	struct Path {
		int _row, _col, _vis;

		Path(int row, int col, int vis) {
			_row = row;
			_col = col;
			_vis = vis;
		}
	};

	int* dx, * dy;
	int _size, endRow, endCol, _count;
	bool** _wall, ** _vis;
	int** autoPath;
	map<Pos, bool> _visRoad;
	map<Pos, int> _minCost;
	map<Pos, vector<EdgeInfo>> _edge;

	void Initialize();
	void makeEdge();
	void makeRoad();
	void setStartPos();
	void setExit();

	void findPath(int, int, int);
	void ini_vis();
	void ini_autoPath();
	
	int getRand(int r = RandomMod);

public:
	Board(int size);

	void Draw(bool empty,int curRow = 0, int curCol = 0);
	int getSize();
	bool** getWall();
	int getEndRow();
	int getEndCol();
	int getBFSCount();
	int bfs(int row, int col, bool printDis = false);
	bool search(bool isAI = false, int row = 0, int col = 0, int count = 0, int startRow = 0, int startCol = 0, int startCount = 0);
	void AIEscape();
	void ini_for_search();
	void print_player(int after_color= 15);
	void print_exit(int after_color = 15);
	void print_wall(int after_color = 15);
	void print_color_str(string, int, int after_color = 15);
	~Board();
};

#endif // !__BOARD_H__

 

[Board.cpp]

#include "Board.h"

Board::Board(int size)
{
	_size = size;
	
	srand((unsigned int)time(NULL));
	Initialize();

	cout << endl;
	Draw(false);
}

void Board::Initialize()
{
	endRow = -1;
	endCol = -1;
	_count = 0;

	dx = new int[4]{ -1, 1, 0, 0 };
	dy = new int[4]{ 0, 0, -1, 1 };

	_wall = new bool* [_size];
	for (int i = 0; i < _size; i++) {
		_wall[i] = new bool[_size];
		fill_n(_wall[i], _size, static_cast<bool>(EWallType::Wall));

		if (i % 2 == 0) continue;

		for (int j = 1; j < _size; j += 2) _wall[i][j] = static_cast<bool>(EWallType::Road);
	}

	for (int i = 1; i < _size; i += 2) {
		for (int j = 1; j < _size; j += 2) {
			_visRoad[Pos(i, j)] = false;
			_minCost[Pos(i, j)] = INT_MAX;
		}
	}

	makeEdge();
	makeRoad();

	setStartPos();
	setExit();
}

void Board::makeEdge()
{
	for (int row = 1; row < _size; row += 2) {
		for (int col = 1; col < _size; col += 2) {
			if (row < _size - 2) {
				int r = getRand();
				Pos u(row, col);
				Pos v(row + 2, col);
				_edge[u].push_back(EdgeInfo(v, r));
				_edge[v].push_back(EdgeInfo(u, r));
			}

			if (col < _size - 2) {
				int r = getRand();
				Pos u(row, col);
				Pos v(row, col + 2);
				_edge[u].push_back(EdgeInfo(v, r));
				_edge[v].push_back(EdgeInfo(u, r));
			}
		}
	}
}

void Board::makeRoad()
{
	priority_queue<EdgeInfo> PQ;
	PQ.push(EdgeInfo(Pos(1, 1), 0));
	_minCost[Pos(1, 1)] = 0;

	map<Pos, Pos> parent;
	parent[Pos(1, 1)] = Pos(1, 1);

	while (!PQ.empty()) {
		EdgeInfo node = PQ.top();
		PQ.pop();

		Pos curPos = node.pos;
		int curCost = node.cost;

		if (_visRoad[curPos]) continue;
		_visRoad[curPos] = true;

		int row = (parent[curPos].row + curPos.row) / 2;
		int col = (parent[curPos].col + curPos.col) / 2;
		_wall[row][col] = static_cast<bool>(EWallType::Road);

		for (const EdgeInfo& next : _edge[curPos]) {
			Pos nextPos = next.pos;
			int nextCost = next.cost;

			if (_visRoad[nextPos] || _minCost[nextPos] < nextCost) continue;

			parent[nextPos] = curPos;
			_minCost[nextPos] = nextCost;

			PQ.push(next);
		}
	}
}

void Board::setStartPos() {
	_wall[0][0] = static_cast<bool>(EWallType::Road);
	_wall[0][1] = static_cast<bool>(EWallType::Road);
}

void Board::setExit() {
	while (true) {
		endRow = getRand(_size);
		endCol = getRand(_size);

		if (_wall[endRow][endCol] == static_cast<bool>(EWallType::Road) && (_count = bfs(0, 0)) > _size) break;
	}
}

int Board::getRand(int r)
{
	return rand() % r;
}

 

[Map을 사용하지 않은 방식]

[TestBoard.h]

#pragma once
#ifndef __TESTBOARD_H__
#define __TESTBOARD_H__
#define TestRandomMod 100

#include <iostream>
#include <ctime>
#include <queue>
#include <climits>
#include <algorithm>
#include <vector>

using namespace std;

class TestBoard {
	enum class ERoadType
	{
		Wall,
		Road
	};

	struct EdgeInfo
	{
		int row, col, cost;

		EdgeInfo(int row, int col, int cost) : row(row), col(col), cost(cost) {}

		bool operator<(const EdgeInfo& o) const { return cost > o.cost; }
	};

private:
	int _size, ** _minCost;
	bool** _road, ** _visRoad;
	vector<EdgeInfo>** _edge;

	void Initialize();
	void makeEdge();
	void makeRoad();
	int getRand(int r = TestRandomMod);

public:
	TestBoard(int);
	~TestBoard();
	void Draw();
};

#endif __TESTBOARD_H__

 

[TestBoard.cpp]

#include "TestBoard.h"

TestBoard::TestBoard(int size)
{
	_size = size;

	srand((unsigned int)time(NULL));
	Initialize();

	cout << "\n";
	Draw();
	cout << "\n";
}

void TestBoard::Initialize()
{
	_road = new bool* [_size];
	_visRoad = new bool* [_size];
	_minCost = new int* [_size];
	_edge = new vector<EdgeInfo>* [_size];

	for (int i = 0; i < _size; i++) {
		_road[i] = new bool[_size] {static_cast<bool>(ERoadType::Wall)};
		_visRoad[i] = new bool[_size] {false};

		_minCost[i] = new int[_size];
		fill_n(_minCost[i], _size, INT_MAX);

		_edge[i] = new vector<EdgeInfo>[_size];

		if (i % 2 == 0) continue;

		for (int j = 1; j < _size; j += 2) _road[i][j] = static_cast<bool>(ERoadType::Road);
	}

	makeEdge();
	makeRoad();
}

void TestBoard::makeEdge()
{
	for (int row = 1; row < _size; row += 2) {
		for (int col = 1; col < _size; col += 2) {
			if (row < _size - 2) {
				int r = getRand();

				_edge[row][col].push_back(EdgeInfo(row + 2, col, r));
				_edge[row + 2][col].push_back(EdgeInfo(row, col, r));
			}

			if (col < _size - 2) {
				int r = getRand();

				_edge[row][col].push_back(EdgeInfo(row, col + 2, r));
				_edge[row][col + 2].push_back(EdgeInfo(row, col, r));
			}
		}
	}
}

void TestBoard::makeRoad()
{
	priority_queue<EdgeInfo> PQ;
	PQ.push(EdgeInfo(1, 1, 0));
	_minCost[1][1] = 0;

	pair<int, int>** parent = new pair<int, int>*[_size];
	for (int i = 0; i < _size; i++) parent[i] = new pair<int, int>[_size];

	parent[1][1] = { 1, 1 };

	while (!PQ.empty()) {
		EdgeInfo node = PQ.top();
		PQ.pop();

		int curRow = node.row, curCol = node.col, curCost = node.cost;

		if (_visRoad[curRow][curCol]) continue;
		_visRoad[curRow][curCol] = true;

		int row = (parent[curRow][curCol].first + curRow) / 2;
		int col = (parent[curRow][curCol].second + curCol) / 2;
		_road[row][col] = static_cast<bool>(ERoadType::Road);

		for (const EdgeInfo& next : _edge[curRow][curCol]) {
			int nextRow = next.row, nextCol = next.col, nextCost = next.cost;

			if (_visRoad[nextRow][nextCol] || _minCost[nextRow][nextCol] < nextCost) continue;

			parent[nextRow][nextCol] = { curRow, curCol };
			_minCost[nextRow][nextCol] = nextCost;

			PQ.push(next);
		}
	}

	for (int i = 0; i < _size; i++) delete[] parent[i];
	delete[] parent;
}

int TestBoard::getRand(int r)
{
	return rand() % r;
}

 

코드를 간단히 설명하겠습니다.

1. 초기에 벽이 아닌 공간(길)을 설정한다 : Initialize() 함수에서 수행
2. 길을 각각 노드라고 생각하며 간선으로 연결한다 : makeEdge() 함수에서 수행
3. 비용이 적은 간선을 기준으로 모든 길을 연결한다 : makeRoad() 함수에서 수행, Prim 알고리즘

여기서 주의할 점은 벽을 없애는 방법입니다.

int row = (parent[curPos].row + curPos.row) / 2;
int col = (parent[curPos].col + curPos.col) / 2;
_wall[row][col] = static_cast<bool>(EWallType::Road);

연결할 노드의 위치와 현재 노드의 위치를 더하고 2를 나누면, 사이에 있는 벽의 좌표가 됩니다.
벽의 좌표를 길이라고 표시해주면 벽이 없어집니다.

 

---

 

Prim 알고리즘을 적용하면서 간선의 가중치의 역할이 궁금했습니다.

TestRandomMod의 값을 변경해도 비슷한 결과가 나왔습니다.

 

고민 끝에 낸 결론은, "간선의 가중치는 크게 중요하지 않다" 입니다.

 

그 이유에 대해서 설명하자면,

Prim 알고리즘은 가중치에 따라 MST의 모양이 결정됩니다.

미로의 모양은 랜덤한 모양을 가져야하며, 가중치가 크든 작든 결국 모든 노드가 연결된다는 점에서,

"간선의 가중치로 인한 연결 모양과 순서는 미로 생성에 중요하지 않다"라고 결론을 내렸습니다.

 

이러한 이유로 다익스트라, 크루스탈 알고리즘으로 구현해도 프림 알고리즘과 비슷한 효과를 낼 것 같습니다.

 

---

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!