2-4. BFS를 이용한 길 찾기 구현

0. 회상

BFS를 만들 때 인접한 항목을 배열 리스트로 가졌음(adjacent)

이를 만들 필요도 없이 기존에 가진 정보를 이용해서 유추할 수 있음.

 

1. BFS로 길 찾기

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

	_path.clear();
	_path.push_back(pos);

	// 목적지 도달 전까지 계속 실행
	Pos dest = _board->GetExitPos();

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

	const int32 size = _board->GetSize();
	vector<vector<bool>> discovered(size, vector<bool>(size, false));
	// size 개수의 요소를 vector(size, false)로 초기화
	// 100x100, 초기값 false
	queue<Pos> q; // 발견한 정점{ y, x }을 넣을 예정

	q.push(pos); // 시작 좌표
	discovered[pos.y][pos.x] = true; // 시작점 발견함

	while (q.empty() == false) // 큐가 텅 빌 때까지
	{
		pos = q.front(); // 점을 pos에 대입
		q.pop(); // 그 점을 pop해서 제거

		// 목적지에 도달하면
		if (pos == dest)
			break;

		for (int32 dir = 0; dir < 4; dir++)
		{
			Pos nextPos = pos + front[dir]; // 다음 좌표
			// 진행 가능한지 확인
			if (CanGo(nextPos) == false) // 갈 수 없는 지역인가
				continue;
			// 이미 발견된 지역(큐에 들어간 점)인지 확인
			if (discovered[nextPos.y][nextPos.x])
				continue;

			q.push(nextPos);
			discovered[nextPos.y][nextPos.x] = true;
		}
	}



	_path.clear();
	_path.push_back(pos);
}

(1) discovered ; 방문했는지 확인

size by size 2차원 행렬로 구성한다. 초기값을 false로 지정하고 시작 좌표를 큐에 넣는다.

그리고 시작지점의 discovered 행렬을 true로 만들어준 후에 반복문을 시작한다.

 

(2) BFS

처음 코드를 실행하면 큐에는 시작 좌표의 pos값 만이 들어있다.

이 값을 pop해서 큐에서 제거한 후에 진행이 불가능한 조건들을 체크한다.

pos 값이 목적지라면 break로 루프문을 탈출한다.

기존에 만들었던 배열 Pos 타입의 nextPos를 만들고 지금 좌표와 바라보고 있는 방향의 좌표를 더한다.

이 nextPos가 벽으로 막혀있는지 체크하고, 이미 방문한 점인지 체크한다.

이후 문제가 없으면 큐에 밀어넣고 discovered를 true로 표시한다.

 

(3) 데이터 추적

반복문 이전에 코드를 작성한다.

	map<Pos, Pos> parent;

그리고 결과값은 이렇게 해석한다.

	parent[A] = B; // A는 B에 의해 발견됨

즉, 이동하는 플레이어가 A 바로 이전인 B 지점에서 왔다는 것을 뜻한다.

	parent[pos] = pos;

초기에는 자기 자신을 부모로 설정한다.

이후는 반복문 내에 작성한다.

		for (int32 dir = 0; dir < 4; dir++)
		{ //~~~~

			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];
	}

	reverse(_path.begin(), _path.end());

};

도착점에서 시작점으로 거슬러 올라가 역으로 작성된 _path를 한 번 뒤집어주면 최적 경로를 저장한 셈이 된다.

 

- 오류 제거

맵을 사용하며 발생한 오류는 pch.h 내의 Pos 구조체에서 해결한다.

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

 

2. BFS로 길을 찾을 때 단점

(1) 시작점을 기준으로 가까운 모든 점을 탐색

(2) 아래로 내려간다는 것은 좀 더 가중을 줄 수 있어야 함