미로 - BFS

미로 - BFS

• 우리는 오른손 법칙을 개선하여 막다른 길에서 되돌아가는 루트를 줄여 조금 더 짧은 길찾기 루트를 알아낼 수 있었다.

• 하지만 오른손 법칙 개선은 "되돌아가는" 루트만 제거했다뿐이지 최단루트를 보장하는 알고리즘은 아니다.

• 최단루트를 알아내는 알고리즘은 대표적으로 BFS를 사용한 알고리즘이 있다.

void Player::Bfs()
{
	Pos pos = _pos;


	// 목적지 도착 전엔 계속 실행
	Pos dest = _board->GetExitPos();
	int32 size = _board->GetSize();
	vector<vector<bool>> discovered(size, vector<bool>(size, false));
	map<Pos, Pos> parent;
	parent[pos] = pos;


	Pos front[4] =
	{
		Pos{-1,0},// UP
		Pos{0,-1},// LEFT
		Pos{1,0},// DOWN
		Pos{0,1}// RIGHT
	};


	queue<Pos> q;
	q.push(pos);
	discovered[pos.y][pos.x] = true;

	while (q.empty() == false)
	{
		pos = q.front();
		q.pop();
        	// 목적지에 도착한 순간 break
		if (pos == dest)
			break;
            
		for (int32 dir = 0;dir < 4;dir++)
		{
			Pos nextPos = pos + front[dir];
			// 갈 수 없는 길이면 검사대상 X
			if (CanGo(nextPos)==false)
				continue;
              		// 이미 발견한 길이면 검사대장에 추가 X
			if (discovered[nextPos.y][nextPos.x] == true)
				continue;

			q.push(nextPos);
            
			discovered[nextPos.y][nextPos.x] = true;
            
            		// 방금전 길을 부모로 저장하여 길찾는데 사용
			parent[nextPos] = pos;
		}
	}
	_path.clear();

	pos = dest;
	while (true)
	{
		_path.push_back(pos);
        
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

	std::reverse(_path.begin(), _path.end());
}

• 시작점으로 부터 길을 가까운 길부터 검사하며 목적지를 찾아 나간다.

• 그 동시에 바로 전 길을 parent에 저장하여 추후에 길찾기 용도로 사용한다.

• 목적지를 찾았다면 break를 한다. 이때 BFS를 활용했으므로 지금 찾은 길이 가장 빨리 도달할 수 있는 최단 루트이다.

• 실제 루트를 저장하는 _path에 도착지의 parent부터 시작하여 거꾸로 저장한다.

• 맨 마지막에 시작점이 저장되었으므로 reverse를 통해 _path를 정방향으로 만들어 준다.

결과

• BFS를 통해 Player는 최단 루트로 길을 찾을 수 있다.