길찾기2 BFS 를 이용하기

일단 최단거리가 보장이 된다.

 

미로가 있을 때, 해당 미로의 각 POS를 정점으로 생각하면 그래프를 만들수 있다.

아래 그림에서 초록색을 길, 빨간색을 벽으로 생각하면, 모든 초록색 빨간색 POS를 각각 정점으로 생각할 수 있고, 초록색이 연속으로 있으면 인접(간선이 연결 되어있다.)라고 말하고 초록색과 빨간색이 붙어있으면 초록색 노드와 빨간색 노드는 인접해 있지 않은것이다.

 

 

BFS 로 파란색 도착노드와 좌상단 시작 노드를 parent 노드를 찾는 역추적 방식으로 BFS 길찾기를 진행할것이다.

시작노드와 도착노드 사이의 역추적을 통해 최적의 경로를 찾아서 저장하고 해당 경로로 플레이어가 이동하게 만들것이다.

 

pch.h

map 변수 parent 를 사용할 것인데 map 이 Pos 라는 구조체를 비교하여 자동정렬을 할 것이다.

이를 위해서 map 이 각각의 Pos 중 무엇이 우선인지 확인시키기위해서 비교연산자 < 를 오버라이딩한다.

 

struct Pos
{
...

bool operator<(const Pos& other) const
	{
		if (y != other.y)
			return y < other.y;
		return x < other.x;
	}


...

};

 

 

player 클래스의 헤더에서 BFS() 선언하고 Init() 함수에서 사용한다.

void Player::Init(Board* board)
{
	_pos = board->GetEnterPos();
	_board = board;

	Bfs();
	//RightHand();
}

void Player::Bfs()
{
	Pos pos = _pos;
	
	// 목적지 도착하기 전에는 계속 실행
	Pos dest = _board->GetExitPos();

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

	const int32 size = _board->GetSize();
	// int[size][size] 만들고 초기화 한다. 다만, 동적임
	vector<vector<bool>> discovered(size, vector<bool>(size,false));

	// 도착점에서부터 시작점까지의 역추적을 위한 저장 공간
	//vector<vector<Pos>> parent; 이거 써도 되고
	// 이것도 됨
	// parent[A] = B; 이면 A는 B로 인해 발견함! A 의 인접 직전노드가 B
	map<Pos, Pos> parent;

	// 발견한 점들을 넣어줄것이다.
	queue<Pos> q;
	// 시작좌표 발견한거 넣어주기
	q.push(pos);
	// 맨처음 노드 발견함을 알려주기
	discovered[pos.y][pos.x] = true;

	// 맨처음 노드를 발견한 것은 자기자신이다!
	parent[pos] = pos;

	while (q.empty() == false)
	{
		pos = q.front();
		q.pop();

		// 탐색!
		if (pos == dest)
		{
			break;
		}

		// 상하좌우 4방향으로 이동
		for (int32 dir = 0; dir < 4; ++dir)
		{
			Pos nextPos = pos + front[dir];
			// 갈 수 있는지 확인
			if (CanGo(nextPos) == false)
			{
				continue;
			}
			// 이미 발견한 지역인가? 맞으면 continue 로 넘어감
			if (discovered[nextPos.y][nextPos.x] == true)
			{
				continue;
			}

			// 갈 수 있고 처음 발견한 지역이니 발견한 지역을 q에 저장
			// 처음 발견한 지역 이제 발견했다고 true 로 만들기
			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());

}