[게임에서의 길찾기] DFS(Depth-First Search)

[본 글은 개인 공부를 위해서 작성하는 글이며, 제공하는 정보에 오류가 있을 수 있습니다.

만약 오류를 발견하신 분은 댓글 작성을 부탁드립니다.]

 

게임에서의 길찾기 포스팅 글들은 게임에서 어떻게 길찾기들이 수행되는 지에 대해 공부하며 작성한 글입니다.

작성자의 능력이 미흡하여 구현된 코드의 수준도 미흡할 수 있는 점 양해부탁드립니다.

 

본 포스팅에서 사용할 미로는 다음과 같습니다.

 

6x6 격자형 미로

6행 6열의 셀들로 구성되어 있는 격자형(Grid) 미로이며 다음과 같은 특징들을 갖습니다.

- 미로의 이동은 상, 하, 좌, 우로만 이동이 가능하며 대각선 이동은 불가능하다고 가정합니다.

- 미로의 셀 사이에서의 이동 비용은 모두 동일하다고 가정합니다.

 

깊이 우선 탐색(Depth-First Search)

 

출처: Wikipedia - Depth-first search(Mre - License: CC BY-SA 3.0)

 

DFS의 장점

- BFS에 비해 필요한 공간 복잡도가 작습니다.

- 노드의 깊이가 깊을 경우, BFS에 비해 빠르게 탐색이 가능합니다.

 

DFS의 단점

- 찾은 경로가 최단 경로가 아닐 수 있습니다.

 

깊이 우선 탐색은 가중치가 없는 간선들로 연결된 그래프에서 사용할 수 있는 탐색 알고리즘입니다.

격자형 미로에서 셀 간의 이동 비용은 전부 동일하므로 가중치 없는 간선들로 연결된 것과 동일합니다.

그러므로 별도로 노드를 생성하지 않고 바로 길찾기를 수행하였습니다.

 

1. 본격적인 탐색에 앞서 먼저 시작 지점과 도착 지점의 셀 정보를 수집합니다.

//bool PathFinding_DFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)

	//	Finding Start Point
	int startX, startY;
	if (!FindingStartPoint(maze_size, maze, startY, startX))
		return false;

	//	Finding Goal Point
	int goalX, goalY;
	if (!FindingGoalPoint(maze_size, maze, goalY, goalX))
		return false;

 

2. 미로를 탐색할 때, 자칫하면 동일한 셀을 계속해서 탐색할 수 있습니다.

그러므로 방문 리스트에 셀 방문 여부 정보를 기록합니다.

초기에는 모든 셀들이 미방문 상태임으로, 방문 리스트의 모든 원소를 -1로 초기화합니다.

//bool PathFinding_DFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)

	//	visit의 -1은 미방문을 의미
	vector<vector<int>> visit;
	visit.resize(maze_size);
	for (size_t i = 0; i < maze_size; ++i)
		visit[i].resize(maze_size, -1);

 

3. 이제 시작 지점의 2차원 인덱스 정보를 활용하여 방문 리스트에 -2를 기록합니다.

방문 리스트에서 -2는 시작 지점임을 뜻합니다.

그리고 시작 지점에서부터 재귀적으로 깊이 우선 탐색을 수행하도록 명령합니다.

//bool PathFinding_DFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)

	visit[startY][startX] = -2;

	if (!Recursive_DFS(maze, maze_size, startX, startY, visit))
		return false;

 

4. 깊이 우선 탐색을 수행합니다.

// 2020.11.30 기준
bool Recursive_DFS(const vector<vector<MAZE_ELEMENT>>& maze, const int maze_size, const int curX, const int curY, vector<vector<int>>& visit)
{
	if (MAZE_ELEMENT::GOAL == maze[curY][curX])
		return true;

	//	상, 하, 좌, 우
	constexpr int value[4][2] = { { 0, -1 },{ 0, 1 },{ -1, 0 },{ 1, 0 } };
	for (int i = 0; i < 4; ++i)
	{
		const int nextX = curX + value[i][0];
		const int nextY = curY + value[i][1];

		if(!CanMove(maze, maze_size, nextX, nextY, visit))
			continue;

		visit[nextY][nextX] = curY * maze_size + curX;

		if (Recursive_DFS(maze, maze_size, nextX, nextY, visit))
			return true;

		visit[nextY][nextX] = -1;
	}
	return false;
}

 

5. 탐색이 종료되면 도착 지점의 방문 리스트 정보를 통해 역순으로 거쳐온 경로를 조사합니다.

//bool PathFinding_DFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)

	while (-2 != visit[goalY][goalX])
	{
		result.path.emplace_front(goalX, goalY);
		const int nextIdx = visit[goalY][goalX];
		goalY = nextIdx / maze_size;
		goalX = nextIdx % maze_size;
	}
	result.path.emplace_front(startX, startY);

 

* 방문 리스트의 원소 의미

방문 리스트의 인덱스는 미로의 셀들이 소유한 2차원 인덱스와 동일하며

방문 리스트 원소에는 -2, -1, 0이상의 수들로 채워져있습니다.

-2는 해당 셀이 시작 지점임을 의미하며 -1은 미방문한 셀임을 뜻합니다.

0 이상의 수들은 해당 셀에 접근하기 직전 셀의 1차원 인덱스 정보를 뜻합니다.

 

최종적으로 깊이 우선 탐색으로 찾아낸 경로는 다음과 같습니다.

 

탐색이 완료된 방문 리스트