[게임에서의 길찾기] BFS(Breath-First Search)

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

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

 

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

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

 

 

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

 

6x6 격자형 미로

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

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

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

 

너비 우선 탐색(Breath-First Search)

 

출처: Wikipedia - Breadth-first search(Blake Matheny - License: CC BY-SA 3.0)

 

BFS의 장점

- 찾은 경로가 최단 경로임을 보장합니다.

- 노드의 깊이가 얕을 경우, DFS보다 빠르게 탐색이 가능합니다.

 

BFS의 단점

- DFS에 비해 필요한 공간 복잡도가 큽니다.

 

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

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

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

 

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

// bool PathFinding_BFS(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_BFS(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. 이제 시작 지점에서부터 탐색을 시작하기 위해 큐(Queue)에 시작 지점 셀의 2차원 인덱스 정보를 추가합니다.

그리고 방문 리스트에 시작 지점 셀의 2차원 인덱스 정보로 접근하여 -2를 기록합니다.

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

// bool PathFinding_BFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)
    
    //	visit의 -2는 시작 지점을 의미
	queue<pair<int, int>>	que;
	que.emplace(startX, startY);
	visit[startY][startX] = -2;

 

4. 너비 우선 탐색을 수행합니다.

이 탐색은 큐에 원소가 없을 때까지 반복되며 다음 명령들을 수행합니다.

4-1. 큐에서 탐색을 진행할 셀의 2차원 인덱스 정보를 가져옵니다.

4-2. 탐색을 진행할 원소가 도착 지점이면 탐색을 종료합니다.

4-3. 상, 하, 좌, 우 순으로 탐색 셀의 인방 셀들을 조사합니다.

      이동 불가 구역이 아니면 큐에 2차원 인덱스 정보를 기록합니다.

      그리고 접근 가능한 인방 셀들의 방문 리스트에 현재 탐색 중인 셀의 2차원 인덱스 정보를

      1차원 인덱스 정보로 변환하여 기록합니다.

 

// bool PathFinding_BFS(const vector<vector<MAZE_ELEMENT>>& maze, Result& result) 일부분 (2020.11.30 기준)
    
    while (!que.empty())
	{
		pair<int, int> element = que.front();
		que.pop();

		if (MAZE_ELEMENT::GOAL == maze[element.second][element.first])
			break;
		
		const int curIdx = maze_size * element.second + element.first;

		//	상, 하, 좌, 우
		constexpr int value[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

		for (int i = 0; i < 4; ++i)
		{
			const int nextX = element.first + value[i][0];
			const int nextY = element.second + value[i][1];

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

			visit[nextY][nextX] = curIdx;
			que.emplace(nextX, nextY);
		}
	}

 

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

// bool PathFinding_BFS(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차원 인덱스 정보를 뜻합니다.

 

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

 

탐색이 완료된 방문 리스트