강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)
A* 알고리즘 이란?
다익스트라에서 조금 더 추가된 내용인데
그 조금이 바로 출구를 알고 있다는 점이다.
즉 출구(목적지)에 가까워질수록 가산점이 있다는 점이있다.
결국에는 입구에서 부터 얼마나 이동을 하는지도 중요하지만
출구에서 부터 얼마나 떨어져있는지도 같이 생각을 하여서
가산점을 줘서 점수를 줘서 정한다는 점이 추가 되것이고
그 외에 점은 다익스트라랑 비슷하다고 볼 수 있다.
A* 알고리즘을 사용하는 이유는
BFS와 다익스트라에는 목적지의 개념이 없기떄문이다.
점수를 줄 때 우리는
- 입구에서부터 얼마나 떨어져 있는지?
- 출구에서부터 얼마나 떨어져 있는지?
그래서 점수를 매기는 공식을 보자면
F = G + H
F = 최종 점수(작을 수록 좋음)
G = 시작점에서 해당 좌표까지 이동하는데 드는 비용
H = 목적지에서 해당 좌표까지 이동하는데 드는 비용
이런식으로 점수를 매긴다.
하지만 공식은 유동적으로 바꿀 수 있기 때문에 공식에 목을 매달 필요는 없다고 본다.
그럼 구현을 해보자
A* 알고리즘 구현
일단 우선순위 큐에 넣을 PQNode라는 것을 만들어준다.
struct PQNode
{
PQNode(int32 f, int32 g, Pos pos) : f(f), g(g), pos(pos) { }
bool operator<(const PQNode& other) const { return f < other.f; }
bool operator>(const PQNode& other) const { return f > other.f; }
int32 f; // f = g + h
int32 g;
Pos pos;
};그리고 일단 기본적인 코드를 만들어준다.
// F = G + H
// F = 최종 점수(작을 수록 좋음)
// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용
// H = 목적지에서 해당 좌표까지 이동하는데 드는 비용
Pos start = _pos;
Pos dest = _board->GetExitPos(); // 목적지
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
};여기서 cost같은 것을 추가해서 이동할 때 코스트를 넣어줄 수 있다.
int32 cost[] =
{
10,
10,
10,
10,
14,
14,
14,
14
};이런식으로 만들어주는데 1로 만들면 대각선 거리가 1.4가 되어버리기 때문에
10으로 만들어서 14로 만들어 주는게 더 빠르다. (정수 연산이 실수 연산보다 빠름)
그다음으로 맵의 사이즈를 받아와준다.
const int32 size = _board->GetSize();또 다익스트라에서 했었던 best(베스트 케이스)를 y,x 기준으로 만들어야 하기 때문에
// best[y][x] -> 지금까지 (y,x)에 댛나 가장 좋은 비용 (작을 수록 좋음)
vector<vector<int32>> best(size, vector<int32>(size, INT32_MAX));이 부분은 나중에 map을 배운다면 map으로 구현가능하다.
그리고 CloseList라는 것을
// ClosedList -> closed[y][x] -> (y, x)에 방문을 했는지 여부
// Option) 사실 best만으로 판별 가능
vector<vector<bool>> closed(size, vector<bool>(size, false));이런식으로 만들어서 closed[y][x]가 true라면 그 지역에 방문을 했었다는 것을 알고 방문을 하지 않게 만들어 준다.
그리고 우리가 항상 만들었던 것 처럼 parent로 추적할 수 있게 만들어준다.
// 부모 추적 용도
vector<vector<Pos>> parent(size, vector<Pos>(size, Pos(-1, -1)));그리고 우리는 예약시스템으로 구현을 하고
뒤늦게 더 좋은 경로가 발견될 수 있기 때문에 예외 처리를 해줘야 한다.
그럼 OpenList 즉 우선순위 큐를 만들어준다.
// 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.y][start.x] = start;
}일단 g는 시작점부터 현재 위치인데 시작점이니 0을 넣어준다.
그리고 h는 목적지에서 현재 위치까지 이동하는데 얼마나 노력을 하는가? 이기 때문에
우리는 h를 목적지의 y,x의 값에서 현재 위치의 y,x를 빼주고 둘을 더하고 10을 곱해주는 공식을 만들 것이다.
그리고 F는 G+H이기 때문에 실질적으로 우선순위 큐에 넣어줄 때는 g+h를 넣어주면 된다.
그리고 best[start.y][start.x]에는 g + h를 넣어준다.
또 parent[start.y][start.x]에는 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 < 8; 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 * (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.y][nextPos.x] = node.pos;
}
}그리고 항상 하였던 것처럼
우선순위 큐가 빌때까지 작동하는 while문을 만들어주고
그리고 여기서 제일 좋은 후보를 찾아주면 된다.
일단 pq.top()으로 값을 뽑아주고 pop으로 내보낸다.
그 다음에 동일한 좌표를 여려 경로로 찾아서
더 빠른 경로로 인해서 이미 방문(closed)된 경우 스킵을 해준다.
그 후에 나보다 더 우수한 후보가 있다면 스킵을 해준다.
다음에는 방문을 해준다.
즉, closed를 true로 해준다.
그리고 목적지에 도착했으면 종료하는 코드를 만든다.
그리고 for문으로 상하좌우를 움직여 준다.
nextPos에 node의 위치와 방향에 따른 위치의 좌표를 더해줘서 다음 좌표를 구한다.
그리고 만들어둔 CanGo함수를 통하여 간선이 연결되있는가?를 구해 갈 수 있는 지역이 맞는지 확인을 한다.
그리고 다시 한 번 방문이 된 곳인지 체크를 한다.
그 다음에는 다음 좌표까지 가는 비용을 계산해보고 체크를 해서 이전에 더 빠른 경로가 있었다면 스킵을 하고 그게 아니라면 그곳으로 가능 기능을 만들어준다.
일단 g를 계산하는데 node.g즉 이전에 좌표까지의 이동값에다가 cost[dir] 즉
위에서 cost로 방향에 따른 비용을 관리하고 있기 때문에 그것을 이용해서 새로운 g를 계산해준다.
그 다음에는 h를 구해주는데 위에서 말했던 공식을 사용하여서 목적지의 y,x에서 다음 좌표의 y,x를 빼주고 더한후에 10을 곱해서 h를 구해준다.
그리고 우리는 다른 경로에서 더 빠른 길을 찾았으면 스킵을 해줘야 한다.
best[nextPos.y][nextPos.x] <= g + h이렇다면 스킵을 해준다.
여기까지 통과를 했다면 예약을 해주면 된다.
하지만 이것은 최종적인 예약은 아니고 갱신이 될 수 있다.
그 후에 BFS와 시작점 구하고 뒤바꾸는 것은 똑같기 때문에 이런식으로 코드를 짜준다.
_path.clear();
Pos pos = dest;
while (true)
{
_path.push_back(pos);
// 시작점
if (pos == parent[pos.y][pos.x])
break;
pos = parent[pos.y][pos.x];
}
/*vector<Pos> temp(_path.size());
for (int i = 0; i < _path.size(); i++)
temp[i] = _path[_path.size() - 1 - i];
_path = temp;*/
std::reverse(_path.begin(), _path.end());
그러면 이런식으로 길찾기를 하는 것을 볼 수 있다.
정리
일단 길찾기를 하기 위한 긴 여정이 끝났다.
여기서 우리가 알고 가야할 것은 적어도 개념을 알고가자! 이다.
코드는 구현을 못해도 우리가 언제가 이 개념을 기억하고 가져간다면 분명 나중에 도움되는 일이 많을 것이다.
결국 A* -> Dijkstra -> BFS -> Graph (PQ)
라고 볼 수 있는 것이다.
이걸 전체적으로 설명을 해보자면
일단 그래프는 정점과 간선이 연결되어 있는 것을 그래프라고 하고
그 그래프를 탐색(서치)하는 방법이 여러가지가 있는데
전체 순회를 할 때
우리는 깊이를 우선으로 할 것인가 너비를 우선으로 할 것인가에 따라서
DFS와 BFS로 나뉘는데
여기서 BFS는 너비 우선 탐색이다.
그리고 BFS를 구현할 때는 큐로 구현하는 것이 일반적이다.
왜냐하면 BFS는 발견한 순서대로 방문하는 것이기 때문에 큐를 사용하는 것이 합리적이고
내가 발견한 순서대로 방문을 하기 때문에 길찾기와 밀접하게 관련 있는 것을 확인 할 수 있다.
즉, 내가 목적지를 발견했다고 한다면 그 경로를 추적해서 어떻게 왔는지 알 수 있을 것이고 그게 바로 최단거리 일 것이다.
다만 단점으로는 애가 목적지라는 개념이 없이 아무곳이나 스캔하다 보니 필요없는 곳을 스캔하는 것이 마음에 안들 수가 있다.
그리고 가중치라는 개념이 없어서 어디길이 더 좋은지 판별을 할 수가 없었다.
여기서 BFS에 가중치라는 개념을 집어넣은 것이 다익스트라이다.
다익스트라는 가중치라는 개념을 가지고 가산점을 줘서 나중에 라도 더 좋은 길을 선택할 수 있도록 유도를 해줄 수 있고
가중치가 생김으로써 게임에서 온갖 상황을 다 묘사할 수 있게된다.
하지만 다익스트라도 목적지라는 개념을 두고 특정 방향으로 가는것이 아니기 때문에
A*로 업그레이드가 된다.
A*같은 경우는 현재 내 좌표를 기준으로 목적지를 바라보고 가려는 시도를 하기 때문에 BFS나 다익스트라보다는 확률적으로 좀 더 옳은 방향으로 갈 확율이 높을 것이다.
왜냐하면 A*는 목적지 기준으로 서칭을 하기위해 노력할 것이기 때문에 결과는 비슷하게 보여도 불필요한 움직임이 덜 할 것이다.
꼭 위에 개념을 알아두고 나중에 한 번더 복습을 하자
다음에는 STL에 관련해서 공부할 것이다.
