Astar

Dijkstra, BFS는 시작점은 있지만 목적지가 뚜렷하게 없다.

그냥 싹다 탐색을 하다가 목적지가 얻어 걸리는거임.

다익스트라 잠깐 생각해보면은

BFS의 가중치가 있을 경우의 한계를 보완하기 위해 다익스트라 썼는데

다익스트라는 간선마다 가중치가 있어가지고 발견한 경로 중에서 누적된 가중치가 가장 작은 녀석을 선택을 해가지고 그녀석을 방문하는 식으로 진행함.

Astar의 경우 출발점으로 부터 얼마나 가까이 떨어져있는지 뿐만 아니라 출구로부터 얼마나 가까워 지는지도 고려를 한다.

중간에 특정알고리즘을 통해서 점수를 매겨서 => 가장 좋은 후보를 고른다.

1. 점과 점 사이의 거리

Mangantten Distance

https://rebro.kr/60

2. 중간 팁

알고리즘을 구현을 할 때, best가 지금 이차원 배열인데 어떤 자료구조를 쓰는게 핵심이 아니라 알고리즘의 핵심을 이해하는게 핵심임.

자료구조는 아무거나 써도 상관없다.

3. 이해안가는 부분 ❗❗❗

struct PQNode
{
	bool operator < (const PQNode& other) { return f < other.f; }
	bool operator > (const PQNode& other) { return f > other.f; }

	int32 f;
	int32 g;
	POS pos;
};

priority_queue<PQNode, std::vector<PQNode>, std::greater<PQNode>> pq;

우선순위 큐만들때 기본 container = vector에 Predicate는 greater로 top()을 하면은 가장 작은 값부터 나오는거 알겠는데,

PQNode의 뭘 비교를 해서 우선순위 큐의 힙트리 구조를 만들겠다는 거임..???

이 에러 계속뜸...

여기에 const안 붙여주어서 그럼.

greater보면은 const_Ty& Left, const _Ty& right 다음에 const보이나? 이유는 모르겠는데 이거 때문에 그런듯

그래서 붙여주자.

4. 분석

struct PQNode
{
	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
	
	POS start = _pos;
	POS dest = p_board->GetExitPos();

	enum
	{
		DIR_COUNT = 4
	};

	POS front[] =
	{
		POS {0, -1},
		POS {-1, 0},
		POS {0, 1},
		POS {1, 0},

		POS {-1, -1},
		POS {1, -1},
		POS {1, 1},
		POS {-1, 1}
	};

	int32 cost[] =
	{
		10, 10, 10, 10,
		14, 14, 14, 14
	};

	const int32 size = p_board->GetSize();

	// ClosedList (옵션임)
	// closed[y][x] -> (y, x)에 방문을 했는지 여부 (방문을 끝낸애들)
	vector<vector<bool>> closed(size, vector<bool>(size, false));

	// best[y][x] -> 지금까지 (y, x)에 대한 가장 좋은 비용 (작을 수록 좋음)
	vector<vector<int32>> best(size, vector<int32>(size, INT32_MAX));

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

	// OpenList (에약된 애들 관리하는 자료구조)
	// 발견한 상태인 녀석들을 OpenList로 관리할 것임. (절반의 성공 느낌)
	priority_queue<PQNode, std::vector<PQNode>, std::greater<PQNode>> pq;

	// 1) 예약(발견) 시스템 구현
	// 2) 뒤늦게 더 좋은 경로가 발견될 수 있음 -> 예외 처리 필수
	
	// 초기값
	{
		int32 g = 0; // 시작점 -> 시작점이라 0.
		int32 h = 10 * (std::abs(dest.y - start.y) + std::abs(dest.x - start.x));
		pq.push(PQNode{g + h, g, start});
		best[start.y][start.x] = g + h;
		parent[start] = start;
	}
	
	while (pq.empty() == false)
	{
		// 제일 좋은 후보를 찾는다.
		PQNode node = pq.top();
		pq.pop();

		// 동일한 좌표를 여러 경로로 찾아서 
		// 더 빠른 경로로 인해서 이미 방문(closed)된 경우 스킵. ( 이부분 누락하면 드라군이 왼쪽갔다 오른쪽갔다 와리가리침)
		
		// [선택] (중복된 부분 선택할 수 있는 방법 두가지)
		if (closed[node.pos.y][node.pos.x])
			continue;
		if (best[node.pos.y][node.pos.x] < node.f)
			continue;

		// 방문
		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];
			if (Cango(nextPos) == false)
				continue;
			// [선택] 이미 방문한 곳이라면 스킵
			if (closed[nextPos.y][nextPos.x])
				continue;

			// 비용계산
			int32 g = node.g + cost[dir]; // 이전 좌표에서 현재 좌표로 이동하는데 드는 비용 => 시작점을 기준으로 이동하는데 드는 비용.
			int32 h = 10 * (std::abs(dest.y - nextPos.y) + std::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;
		}
	}

	// 거꾸로 거슬러 올라간다
	POS pos = dest;
	
	_path.clear();
	_pathIdx = 0;

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

		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

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

5. 정리

Dijkstra는 뭐랄까... BFS의 한계점을 보완한 알고리즘이고 BFS는 DFS의 무식한 방법을 보완한 알고리즘같음.

다익, BFS는 목적지가 없고 우연찮게 목적지를 발견해서 break하여 종료한 느낌이고

Astar는 출발점과 목적지가 있고

F = G + H 라는 비용 계산을 통해서 목적지 까지 가는데 가장 효율적인 방법으로 가는 알고리즘이라고 생각하면 될거같다.

best라는 이차원 배열을 통해서 최소비용 거리찾게하고 (갱신하는 부분)

우선순위 큐를 통해서 PQNode의 f의 가장 최소값을 O(log n)으로 얻어옴.