길찾기4 A* 알고리즘

BFS, 다익스트라는 시작점은 있지만 목적지를 향해서 가는 것은 아니다.

break 로 어느 지점에서 멈추라고는 했지만 목적지를 정해놓는 알고리즘은 아니었다.

 

A* 는 시작점과 더불어 도착점까지 완벽하게 설정하고 길찾기를 시작한다.

사실 이 차이점 외에는 다익스트라와 큰 차이가 없다.

 

A* 는 출발점에서 내가 가고 있는 길이 얼마나 떨어져있는지(비용) 뿐 만 아니라 도착점과 얼마나 가까워지고 있는지도 판단할 것 이다.

 

2가지 고려함

최적의 경로를 위해 비용을 계산하는 것은 다익스트라와 비슷하지만 비용을 2가지 방식으로 계산한다는 것이다.

 

struct PQNode
{
	// 우선순위 큐에다가 정보를 넣어서 비교를 할 때에는 f 를 기준으로 비교할것
	bool operator<(const PQNode& other) const { return f < other.f; }
	bool operator>(const PQNode& other) const { return f > other.f; }
	int32 f;
	int32 g;
	Pos pos;
};
void Player::AStar()
{
	// 점수 매기기
	// F = G + H
	// F = 최종 점수 (작을 수록 좋은걸로 만들거임, 경로에 따라 달라짐)
	// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을 수록 좋음. 경로에 따라 다름)
	// H = 목적지에서 얼마나 가까운지 ( 작을 수록 좋음. 고정)

	Pos start = _pos;

	// 목적지 도착하기 전에는 계속 실행
	Pos dest = _board->GetExitPos();

	enum
	{
		// 요게 4이면 4방향, 8이면 8방향
		DIR_COUNT = 8
	};

	Pos front[] =
	{
	Pos {-1,0},	// UP
	Pos {0,-1},	// LEFT
	Pos {1,0},	// DOWN
	Pos {0,1},	// RIGHT
	Pos {-1,-1}, // UP_LEFT
	Pos { 1, -1}, // DOWN_LEFT
	Pos {1, 1}, // DOWN_RIGHT
	Pos { -1,1} // UP_RIGHT
	};

	int32 cost[]
	{
		10, // UP
		10, // LEFT
		10, // DOWN
		10, // RIGHT
		14, // UP_LEFT
		14, // DOWN_LEFT
		14,
		14
	};

	const int32 size = _board->GetSize();

	// 1) 예약 (발견) 시스템 구현
	// 정점을 방문할 때 마다 인접한 정점을 발견해서 그 정점들에 대한
	// 비용을 계산해서 예약해줄것. 예약 되면 나중에 루프 돌면서 
	// 예약 중에 제일 좋은 걸로 갈거임.
	// 
	// 2) 근데 뒤늦게 더 좋은 후보가 발견될수있어서 예외처리 꼭 해야함

	// 좌표가 어떤 비용을 가지는지 알아야한다.

	//CloseList
	// close[y][x] 에 방문했는지 여부
	// 방문한 친구들 여기서 하ㅘㄱ인 가능
	vector<vector<bool>> closed(size, vector<bool>(size, false));

	// best[y][x] -> 지금까지 {y,x} 에 대한 가장 좋은 비용 ( 작은 거 )
	// f
	vector<vector<int32>> best(size, vector<int32>(size, INT32_MAX));

	// 부모 추적 용도
	map<Pos, Pos> parent;

	// 예약 시스템 구현 OpenList 에 해당함 예약된 애들 관리하는거
	// 방문은 하지 않았고 발견만한 친구들
	priority_queue<PQNode, vector<PQNode>, greater<PQNode>> pq;


	// 초기값
	{
		int32 g = 0;
		// 이 공식은 효율적으로 연산량 적게해서 임의로 계산식 만든거고
		// 피타고라스 해도 됨..
		int32 h = 10 * (abs(dest.y - start.y) + abs(dest.x - start.x));
		pq.push(PQNode{ g + h, g, start });
		best[start.y][start.x] = g + h;
		parent[start] = start;
		// closed 이거 true 안한다. 아직 방문 아니다. top 하면 방문이다.
	}


	while (pq.empty() == false)
	{
		// 제일 좋은 후보를 찾기
		// f 값이 제일 작은 node
		// 방문 시작 단계 여기서부터 방문하는 걸 뜯함
		PQNode node = pq.top();
		pq.pop();

		// 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서
		// 이미 방문된 경우 스킵

		// 선택 CloseList
		if (closed[node.pos.y][node.pos.x])
			continue;

		// 선택 best
		if (best[node.pos.y][node.pos.x] < node.f)
			continue;

		// 방문
		// 방문 후에 더 우수한 경로를 찾는것은 불가능한가?
		// 수학적으로 이미 증명되었다. 방문 이후에 더 우수한 경로를 찾는것은
		// 불가능하다. A* 에서는
		closed[node.pos.y][node.pos.x] = true;

		// 목적지에 도착했으면 바로 종료
		if (node.pos == dest)
			break;

		for (int32 dir = 0; dir < DIR_COUNT; dir++)
		{
			// 갈 방향 정하기
			Pos nextPos = node.pos + front[dir];
			// 막혔으면 continue;
			if (CanGo(nextPos) == false)
				continue;

			// [선택] 이미 방문한 곳 스킵
			// if (closed[node.pos.y][node.pos.x])
			//     continue;
			// 이거 있어서 쓸지 말지 정해도 됨 어짜피 위에서 continue 로 걸러짐
			if (closed[nextPos.y][nextPos.x])
				continue;

			// 비용 계산
			// 이전 좌표 node.g 에서 현재 좌표 cost[dir]로 가는 비용 
			// 
			int32 g = node.g + cost[dir];
			int32 h = 10 * (abs(dest.y - nextPos.y) + abs(dest.x - nextPos.x));

			// 다른 경로에서 더 빠른 길을 찾았으면 스킵
			// 방문은 안했지만 예약은 되었있다면
			if (best[nextPos.y][nextPos.x] <= g + h)
				continue;

			// 예약 진행
			best[nextPos.y][nextPos.x] = g + h;
			pq.push(PQNode{ g + h,g,nextPos });
			parent[nextPos] = node.pos;

		}
		int a = 3;
	}
	// 거꾸로 넣어준다.
	Pos pos = dest;

	_path.clear();
	_pathIndex = 0;


	while (true)
	{
		_path.push_back(pos);

		// 시작점은 자신이 곧 부모이다.
		if (parent[pos] == pos)
			break;

		pos = parent[pos];
	}

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

}