A-Star 알고리즘이란?
A*는 시작점에서 목표까지의 최단 경로를 찾기 위해
현재까지의 비용(g(n)) + 목표까지의 예상 비용(h(n)) 를기준으로 탐색하는 알고리즘 입니다.
g(n) : 시작점에서 현재 노드까지 가는데 드는 비용
h(n) : 현재 노드에서 목표 노드까지 가는데 드는 비용
f(n) : 총 예상 비용 ( g(n) + f(n) )
A-Star 알고리즘 동작 과정
1. 해당 노드 주변의 열린 노드의 g(n), h(n), f(n) 비용 구하기
- 열린노드(Open Node)는 현재 위치 노드에 인접한 노드들을 의미합니다.
- g(n)의 비용을 구하는 방식은 바로 유클리디안 거리(점과 점사이의 거리)을 사용하여 나타낸다.
- h(n)의 비용을 구하는 방식은 휴리스틱 거리 측정값을 통해 이동 비용을 구한다.
(격자에서는 가로, 세로 Manhattan 거리 방식을 이용하며, 그 외는 점과 점 사이의 거리 공식을 이용해 표현)
- f(n)의 비용 = g(n) + h(n) 이다.
2. 경로 탐색
현재 노드의 오픈 노드를 모아둔 오픈 리스트에서 가장 낮은 f(n)을 우선 방문합니다.
따라서 현재 그림상에서는 오른쪽 대각선 위 f(n) = 44인 노드를 방문합니다.
방문한 후에는 ClosedList에 해당 노드를 넣고 재방문을 하지 않도록 합니다.
(하늘색 윤곽선으로 그려진 노드는 ClosedList에 들어간 것입니다.)
3. 1,2번 반복 하여 Best_Route 구하기
A*가 왜 최적의 루트를 제공하는가?
해당 알고리즘을 공부하면서 의문이 들기도 했습니다.
이거 BFS와 마찬가지고 queue를 이용하여 모든 경로를 다 탐색하는거 아니야? 라는 생각을 처음에는 가졌습니다.
하지만 A* 알고리즘과 BFS의 탐색범위에 차이가 있습니다.
A* 알고리즘은 무작정 모든 방향을 탐색하는 것이 아니라, 목표 지점에 더 가까워 보이는 노드를 우선적으로 확장합니다.
탐색 도중 장애물을 만나거나 비효율적인 경로임이 판단되면, Open list에 저장된 다른 후보 노드를 선택해 탐색을 이어갑니다.
이러한 방식 덕분에 BFS보다 불필요한 탐색을 줄이고, 더 빠르게 최적 경로를 찾을 수 있습니다.
코드 구현
bool CNavigation::Make_Route(int iStartIndex, int iGoalIndex)
{
priority_queue<NodeInfo, vector<NodeInfo>,PQCompare> OpenQueue;
NodeInfo node;
node.index = iStartIndex;
node.g_Cost.x = 0;
node.g_Cost.y = 0;
node.Cost = 0;
OpenQueue.push(node);
m_ClosedList.clear();
while(!OpenQueue.empty())
{
// 여기서 계산하고 맨 위에거 가져온거
int CurIndex = OpenQueue.top().index;
int Cur_gCoost_x = OpenQueue.top().g_Cost.x;
int Cur_gCoost_y = OpenQueue.top().g_Cost.y;
OpenQueue.pop();
if (CheckClose(CurIndex))
continue;
if (CurIndex == iGoalIndex)
return true;
m_ClosedList.push_back(CurIndex);
//여기서 이제 다시 오픈리스트에 넣고 계산하기
for (auto& pCell : m_vecCellAbj[CurIndex])
{
if (!CheckClose(pCell->Get_Index()) && pCell->Get_Option() != 1) // 장애물 체크
{
//여기서 계산하기 (나중에 함수화하기)
int gCost_x = abs(m_vecCell[CurIndex]->Get_Position().x - pCell->Get_Position().x) + Cur_gCoost_x;
int gCost_y = abs(m_vecCell[CurIndex]->Get_Position().y - pCell->Get_Position().y) + Cur_gCoost_y;
int hCost_x = abs(m_vecCell[iGoalIndex]->Get_Position().x - pCell->Get_Position().x);
int hCost_y = abs(m_vecCell[iGoalIndex]->Get_Position().y - pCell->Get_Position().y);
// 여기서도 g_value가 더 낮다면을 가정해야함
if ((gCost_x + gCost_y) < pCell->Get_gValue())
{
pCell->Set_ParentIndex(CurIndex);
pCell->Set_gValue(gCost_x + gCost_y);
int fResult = gCost_x + gCost_y + hCost_x + hCost_y;
NodeInfo node;
node.index = pCell->Get_Index();
node.Cost = fResult;
node.g_Cost.x = gCost_x;
node.g_Cost.y = gCost_y;
OpenQueue.push(node);
}
}
}
}
return false;
}
구현 결과
