[C++] A* 알고리즘을 이용한 '미로찾기 알고리즘'

참고: https://powerclabman.tistory.com/26

[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘'

참고: https://powerclabman.tistory.com/27

[C++/이론] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

이 포스팅을 보려면 위 2개의 포스팅에 대한 완벽한 이해가 필요합니다.

개요

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘입니다.

'다익스트라 알고리즘'은 '목적지' 개념을 가지지 않고, 그저 전체 그래프를 탐색하여 최소 이동 경로를 계산합니다. 그렇기에, 계산 오버헤드가 많다는 단점이 있습니다.

 

방대한 네트워크나 사람이 사는 공간등 정보량이 매우 많을 때

최단 경로를 찾는 알고리즘으로 '다익스트라 알고리즘'을 많이 활용되지 않는 이유가

너무나도 많은 계산량 때문이죠.

 

A* 알고리즘은 '목적'을 가지고 최단 경로를 탐색합니다.

'현재 노드까지 오는 비용' + '사용자 지정 함수'를 계산하여, 이 값이 최소가 되는 쪽으로 경로를 탐색합니다.

 

저는 이를 마치 '페널티 점수를 부과한다.'라고 여깁니다.

페널티 점수가 높은 곳은 굳이 탐색하지 않고, 페널티 점수가 낮은 곳을 위주로 탐색하는 것이죠.

 

만약, 미로찾기 알고리즘으로 A* 알고리즘을 이용할 때, 페널티를 어떻게 부과하면 좋을까요?

아무래도 목적지에서 멀어질수록 높은 페널티를 부과하면 되겠죠.

그러면 자연스럽게 목적지와 가까운 노드를 위주로 탐색하게 될 것입니다.

 

이러면 연산량의 유의미하게 줄어듭니다.

 

개념

다익스트라 알고리즘의 확장이기 때문에, 의사코드 자체는 '다익스트라 알고리즘'과 매우 유사합니다.

새로 추가되는 것은 '휴리스틱 함수'입니다.

 

특정 수학적 공식을 이용해 각 블록으로 가는 비용을 구하고,

비용이 최소가 되는 노드에 방문하는 것이 A* 알고리즘의 핵심 동작입니다.

 

f(n) = g(n) + h(n)

 

g(n): 출발 노드에서 노드 n까지 도달하기 위한 최단 비용

h(n): 현재 노드 n에서 도착지까지의 예상 이동비용 (휴리스틱 함수)

f(n): g(n) + h(n)의 값

 

f(n) 값이 작은 노드를 방문하여 목적지까지의 최소 비용 경로를 찾아내며

휴리스틱 함수 h(n)을 어떻게 정의하냐에 따라 A* 알고리즘의 성능이 결정됩니다.

즉, g(n) + h(n) 통해 '페널티 값'을 매기고, '페널티 값'이 적은 쪽으로 경로를 결정한다고 보시면 되겠습니다.

 

미로 찾기 알고리즘에서는

g(n)을 유클리디안 거리(Euclidean distance)를 사용합니다.

유클리디안 거리는

상하좌우 이동 비용을 10

대각선 이동 비용을 14

로 정의합니다.

 

h(n)는 맨해튼 거리(Manhattan distance)를 사용합니다.

h(n) = |현재위치 x - 도착지 x| + |현재위치 y - 도착지 y|

로 정의됩니다.

 

h(n)의 함수를 어떻게 정의하냐는 매우 중요하며,

어떤 상황에서 A*를 사용하는지에 따라 그 정의가 달라집니다.

의사 코드

// distance 배열에는 (y, x) 좌표로 가기위한 최소 f 값이 저장되어 있습니다.
// closedlist 배열에는 (y, x) 좌표에 방문했는지 여부를 체크합니다.
// pq는 우선순위 큐이며, f 값에 대해서 '최소 힙' 형태로 구현됩니다.

Astar(시작정점) :
	f(시작정점) = g(시작정점) + h(시작정점)
    pq <- push(f)
    distance[시작정점] = 0
    
    while(pq가 비어있지 않다면)
    	pq에서 here를 pop
        
        if(만약 closedlist[here]를 방문했다면?)
        	continue;
            
        closedlist[here] <- true
        
        for(주변 정점 방문)
        	다음정점의 f값 계산
            if(distance[다음정점] > 다음정점의 f)
            	distance[다음정점] <- f
                pq <- push(f)

 

A* 알고리즘은 기본적으로 '우선순위 큐 다익스트라 알고리즘'을 기반으로 생각하면 쉽게 구현할 수 있습니다.

(관련 코드는 '참고' 부분에 가면 볼 수 있습니다.)

 

사실 우선순위 큐 다익스트라 알고리즘을 제대로 이해했고, 구현할 수 있다면 따로 이해할 것이 없습니다.

A*의 알고리즘은 그저 '페널티 값'을 이용해서 최단 경로를 탐색하는 '확장'일뿐이니까요.

 

한 가지 다른 점이라면, A* 알고리즘의 휴리스틱 함숫값에 따라 '중복 방문'이 발생할 수 있기 때문에

방문한 노드를 기록하는 closedlist를 사용한다는 것입니다.

 

일단 의사코드를 이용해서 '미로 찾기 알고리즘'을 구현한 코드는 다음과 같습니다.

 

struct Node
{
	Node(int f, int g, Pos pos)
		: f(f), g(g), pos(pos) {}

	bool operator<(const Node& other) const { return f < other.f; }
	bool operator>(const Node& other) const { return f > other.f; }

	int f;
	int g;
	Pos pos;
};

int GetHulistic(Pos here, Pos dest)
{
	int h = 10 * (abs(here._x - dest._x) + abs(here._y - dest._y));
	return h;
}

void PathFinder_Astar()
{
	Pos start = player;
	Pos dest = DestPos;

	Pos move[8] =
	{
	{0,1},
	{0,-1},
	{1,0},
	{-1,0},
	{-1,1},
	{1,-1},
	{1,1},
	{-1,-1},
	};

	int cost[8] =
	{
	10,
	10,
	10,
	10,
	14,
	14,
	14,
	14
	};

	const int INF = 9999;

	vector<vector<int>> distance(height, vector<int>(width, INF));
	vector<vector<bool>> closedlist(height, vector<bool>(width, false));

	priority_queue<Node, vector<Node>, greater<Node>> pq;

	{
		//초기화
		int g = 0;
		int h = GetHulistic(start, dest);

		Node node(g + h, g, start);

		pq.push(node);

		distance[start._y][start._x] = 0;
	}

	while (!pq.empty())
	{
		Node node = pq.top();
		Pos here = node.pos;
		pq.pop();

		if (closedlist[here._y][here._x] == true)
			continue;

		if (here == dest)
			break;

		closedlist[here._y][here._x] = true;

		for (int dir = 0; dir < 8; dir++)
		{
			Pos NextPos = move[dir] + here;

			//발견한 좌표면 패스
			if (closedlist[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			int g = node.g + cost[dir];
			int h = GetHulistic(NextPos, dest);

			if (distance[NextPos._y][NextPos._x] > g + h)
			{
				Node NextNode(g + h, g, NextPos);
				pq.push(NextNode);
				distance[NextPos._y][NextPos._x] = g + h;
			}
		}
	}
}

 

찬찬히 뜯어보도록 하겠습니다.

 

struct Node
{
	Node(int f, int g, Pos pos)
		: f(f), g(g), pos(pos) {}

	bool operator<(const Node& other) const { return f < other.f; }
	bool operator>(const Node& other) const { return f > other.f; }

	int f;
	int g;
	Pos pos;
};

int GetHulistic(Pos here, Pos dest)
{
	int h = 10 * (abs(here._x - dest._x) + abs(here._y - dest._y));
	return h;
}

먼저 '우선순위 큐'에 넣어줄 구조체입니다.

해당 구조체는 f, g, pos를 가지고 있습니다.

f는 우선순위 큐가 활용하는 '페널티 값'

g는 f를 계산하기 위해 누적 g 값을 계산하는 변수

pos는 해당 좌표를 뜻합니다.

 

아래

GetHulistic 함수는

앞서 말한 '맨해튼 거리'를 이용해서 '휴리스틱 함수'를 계산한 것입니다.

 

	Pos move[8] =
	{
	{0,1},
	{0,-1},
	{1,0},
	{-1,0},
	{-1,1},
	{1,-1},
	{1,1},
	{-1,-1},
	};

	int cost[8] =
	{
	10,
	10,
	10,
	10,
	14,
	14,
	14,
	14
	};

이 코드는 플레이어의 이동을 담당하는 move 배열과 g값 결정을 위한 cost 배열입니다.

move는 상하좌우, 대각선 4방향 총 8방향을 움직이며

cost는 상하좌우에는 10점, 대각선 이동에는 14점을 부여합니다.

 

	vector<vector<int>> distance(height, vector<int>(width, INF));
	vector<vector<bool>> closedlist(height, vector<bool>(width, false));

	priority_queue<Node, vector<Node>, greater<Node>> pq;

A* 구현에 필요한 자료구조입니다.

closedlist는 굳이 필요 없긴 한데, 많은 인터넷 자료들이 closedlist를 사용하고 있길래 저도 사용해 봤습니다.

사실 distance 배열만으로도 '중복 방문'을 체크할 수 있습니다.

 

	{
		//초기화
		int g = 0;
		int h = GetHulistic(start, dest);

		Node node(g + h, g, start);

		pq.push(node);
        
		distance[start._y][start._x] = 0;
	}

 

본격적인 루프에 들어가기 전 초기화 부분입니다.

 

while (!pq.empty())
	{
		Node node = pq.top();
		Pos here = node.pos;
		pq.pop();

		if (closedlist[here._y][here._x] == true)
			continue;

		if (here == dest)
			break;

		closedlist[here._y][here._x] = true;

		for (int dir = 0; dir < 8; dir++)
		{
			Pos NextPos = move[dir] + here;

			//발견한 좌표면 패스
			if (closedlist[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			int g = node.g + cost[dir];
			int h = GetHulistic(NextPos, dest);

			if (distance[NextPos._y][NextPos._x] > g + h)
			{
				Node NextNode(g + h, g, NextPos);
				pq.push(NextNode);
				distance[NextPos._y][NextPos._x] = g + h;
			}
		}
	}

 

우선순위 큐 top부분 노드를 빼서 알고리즘을 수행하는데,

f = g+h 를 계산하는 것을 빼면, 다익스트라의 구현과 동일합니다.

아마 다익스트라의 구현을 할 수 있고, BFS 미로 찾기 알고리즘을 구현할 수 있다면,

무난하게 구현할 거라고 생각합니다.

 

이제 이러면 최단경로를 찾아냈을 것이고, 마지막으로 BFS 미로 찾기 알고리즘에서 했던 것과

동일하게 '경로 역추적'을 해주면 끝입니다.

 

경로 역추적을 위해 record 벡터를 추가하였고, 자세한 코드는 다음과 같습니다.

 

stack<Pos> PathFinder_Astar()
{
	Pos start = player;
	Pos dest = DestPos;

	Pos move[8] =
	{
	{0,1},
	{0,-1},
	{1,0},
	{-1,0},
	{-1,1},
	{1,-1},
	{1,1},
	{-1,-1},
	};

	int cost[8] =
	{
	10,
	10,
	10,
	10,
	14,
	14,
	14,
	14
	};

	const int INF = 9999;

	vector<vector<int>> distance(height, vector<int>(width, INF));
	vector<vector<bool>> closedlist(height, vector<bool>(width, false));
	vector<vector<Pos>> record(height, vector<Pos>(width, Pos(0, 0)));

	priority_queue<Node, vector<Node>, greater<Node>> pq;

	{
		//초기화
		int g = 0;
		int h = GetHulistic(start, dest);

		Node node(g + h, g, start);

		pq.push(node);

		record[start._y][start._x] = start;
		distance[start._y][start._x] = 0;
	}

	while (!pq.empty())
	{
		Node node = pq.top();
		Pos here = node.pos;
		pq.pop();

		if (closedlist[here._y][here._x] == true)
			continue;

		if (here == dest)
			break;

		closedlist[here._y][here._x] = true;

		for (int dir = 0; dir < 8; dir++)
		{
			Pos NextPos = move[dir] + here;

			//발견한 좌표면 패스
			if (closedlist[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			int g = node.g + cost[dir];
			int h = GetHulistic(NextPos, dest);

			if (distance[NextPos._y][NextPos._x] > g + h)
			{
				Node NextNode(g + h, g, NextPos);
				pq.push(NextNode);
				record[NextPos._y][NextPos._x] = here;
				distance[NextPos._y][NextPos._x] = g + h;
			}
		}
	}

	stack<Pos> st;

	Pos temp = dest;

	while (temp != start)
	{
		st.push(temp);
		temp = record[temp._y][temp._x];
	}

	return st;
}

 

<전체 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <Windows.h>
using namespace std;

#pragma region 좌표 클래스
class Pos
{
public:
	Pos() {}
	Pos(int y, int x)
		: _y(y)
		, _x(x)
	{}

	Pos operator+(const Pos& other)
	{
		int newy = _y + other._y;
		int newx = _x + other._x;

		return Pos(newy, newx);
	}

	Pos operator-(const Pos& other)
	{
		int newy = _y - other._y;
		int newx = _x - other._x;

		return Pos(newy, newx);
	}

	void operator+=(const Pos& other)
	{
		_y += other._y;
		_x += other._x;
	}

	void operator-=(const Pos& other)
	{
		_y -= other._y;
		_x -= other._x;
	}

	bool operator==(const Pos& other) const
	{
		return _x == other._x && _y == other._y;
	}
	bool operator!=(const Pos& other) const
	{
		return _x != other._x || _y != other._y;
	}

public:
	int _y = 0;
	int _x = 0;
};
#pragma endregion

#pragma region 버퍼 컨트롤 함수
enum class SystemColor {
	BLACK = 0,
	LIGHTBLUE = 9,
	LIGHTRED = 12,
	YELLOW = 14,
	WHITE = 15
};

void gotoxy(const Pos& point)
{
	COORD pos = { point._x, point._y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void gotoxy(int y, int x)
{
	COORD pos = { x, y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void CursorView(bool triger)
{
	CONSOLE_CURSOR_INFO cursorInfo = { 0, };
	cursorInfo.dwSize = 1; //커서 굵기 (1 ~ 100)
	cursorInfo.bVisible = triger; //커서 Visible TRUE(보임) FALSE(숨김)
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursorInfo);
}

void textcolor(SystemColor foreground, SystemColor background = SystemColor::BLACK)
{
	int color = static_cast<int>(foreground) + static_cast<int>(background) * 16;
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
#pragma endregion

#pragma region 미로 관련 코드
//false: 빈공간, true: 벽
vector<vector<bool>> maze =
{
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1},
{1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1},
{1,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1},
{1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1},
{1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1},
{1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,0,1},
{1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,0,1},
{1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,1},
{1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1},
{1,0,1,1,0,1,1,1,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,1},
{1,0,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,1,1},
{1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1},
{1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};
int height = maze.size();
int width = maze[0].size();
Pos DestPos(0, 0);

void InitMaze()
{
	do
	{
		DestPos = Pos(rand() % height, rand() % width);
	} while (maze[DestPos._y][DestPos._x] == 1);
}

void RenderMaze()
{
	gotoxy(0, 0);

	for (int y = 0; y < height; y++)
	{
		for (int x = 0; x < width; x++)
		{
			if (Pos(y, x) == DestPos)
			{
				textcolor(SystemColor::YELLOW);
				cout << "★";
				continue;
			}

			if (maze[y][x])
			{
				textcolor(SystemColor::LIGHTBLUE, SystemColor::LIGHTBLUE);
				cout << " ";
			}
			else
			{
				textcolor(SystemColor::BLACK);
				cout << " ";
			}
		}
		cout << "\n";
	}
}
#pragma endregion

#pragma region Player
Pos player;
stack<Pos> PathFinder_Astar();

void InitPlayer()
{
	//플레이어 위치 잡기
	do
	{
		player = Pos(rand() % height, rand() % width);
	} while (maze[player._y][player._x] == 1);
}

void UpdatePlayer()
{
	static stack<Pos> st;
	if (GetAsyncKeyState(VK_SPACE) & 0x8000)
	{
		st = PathFinder_Astar();
	}

	if (!st.empty())
	{
		player = st.top();
		st.pop();
	}
}

void RenderPlayer()
{
	gotoxy(player);
	textcolor(SystemColor::LIGHTRED);
	cout << "■";
}

struct Node
{
	Node(int f, int g, Pos pos)
		: f(f), g(g), pos(pos) {}

	bool operator<(const Node& other) const { return f < other.f; }
	bool operator>(const Node& other) const { return f > other.f; }

	int f;
	int g;
	Pos pos;
};

int GetHulistic(Pos here, Pos dest)
{
	int h = 10 * (abs(here._x - dest._x) + abs(here._y - dest._y));
	return h;
}

stack<Pos> PathFinder_Astar()
{
	Pos start = player;
	Pos dest = DestPos;

	Pos move[8] =
	{
	{0,1},
	{0,-1},
	{1,0},
	{-1,0},
	{-1,1},
	{1,-1},
	{1,1},
	{-1,-1},
	};

	int cost[8] =
	{
	10,
	10,
	10,
	10,
	14,
	14,
	14,
	14
	};

	const int INF = 9999;

	vector<vector<int>> distance(height, vector<int>(width, INF));
	vector<vector<bool>> closedlist(height, vector<bool>(width, false));
	vector<vector<Pos>> record(height, vector<Pos>(width, Pos(0, 0)));

	priority_queue<Node, vector<Node>, greater<Node>> pq;

	{
		//초기화
		int g = 0;
		int h = GetHulistic(start, dest);

		Node node(g + h, g, start);

		pq.push(node);

		record[start._y][start._x] = start;
		distance[start._y][start._x] = 0;
	}

	while (!pq.empty())
	{
		Node node = pq.top();
		Pos here = node.pos;
		pq.pop();

		if (closedlist[here._y][here._x] == true)
			continue;

		if (here == dest)
			break;

		closedlist[here._y][here._x] = true;

		for (int dir = 0; dir < 8; dir++)
		{
			Pos NextPos = move[dir] + here;

			//발견한 좌표면 패스
			if (closedlist[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			int g = node.g + cost[dir];
			int h = GetHulistic(NextPos, dest);

			if (distance[NextPos._y][NextPos._x] > g + h)
			{
				Node NextNode(g + h, g, NextPos);
				pq.push(NextNode);
				record[NextPos._y][NextPos._x] = here;
				distance[NextPos._y][NextPos._x] = g + h;
			}
		}
	}

	stack<Pos> st;

	Pos temp = dest;

	while (temp != start)
	{
		st.push(temp);
		temp = record[temp._y][temp._x];
	}

	return st;
}

#pragma endregion



#pragma region 프로그램 초기화 및 랜더링

void ProgramInit()
{
	srand(time(NULL));
	gotoxy(0, 0);
	CursorView(false);
	textcolor(SystemColor::WHITE, SystemColor::BLACK);
	InitMaze();
	InitPlayer();
}

void ProgramRender()
{
	RenderMaze();
	RenderPlayer();
}

void ProgramUpdate()
{
	UpdatePlayer();
}
#pragma endregion



int main()
{
	ProgramInit();

	while (true)
	{
		ProgramUpdate();
		ProgramRender();
	}

}

 

 

<시연 영상>

 

콘솔 버전이 안 맞아서 랜더링이 어색하게 되는 부분 양해 부탁드립니다.

 

마치며

A* 알고리즘에 대한 포스팅을 다루기 위해서, 상당히 많은 선수 포스팅을 다뤘습니다.

앞선 포스팅 '그래프 개론', 'BFS/DFS', '경로 역추적', '다익스트라 알고리즘'을 이해하지 못하면, 해당 포스팅을 이해하는 것이 상당히 힘들었을 것입니다.

 

A*를 이용한 미로 찾기 알고리즘은 

경로 역추적, 다익스트라 알고리즘을 잘 응용한 것이기에, 제대로 구현하지 못했다면

이전 포스팅에 대한 지식을 더 쌓고 다시 구현해 보시길 바랍니다.

 

해당 포스팅에서는 미로 찾기를 위한 A* 알고리즘을 선보였지만

상당히 많은 부분에서 A* 알고리즘을 사용할 수 있고

어떤 상황에서 사용하느냐에 따라서 휴리스틱 함수를 잘 정의해야겠죠.

 

A* 또한 상당히 오래된 알고리즘이고

현재는 속도를 더 높이거나, 목적에 따라 개량하여 사용하기도 합니다.

A*을 바탕으로 발달한 무수히 많은 알고리즘이 있기에 관심있다면 한 번 찾아보시길 바랍니다.