1. A* 알고리즘이란?
시작 노드에서부터 목표 노드까지의 최단 경로를 찾는 그래프 탐색 알고리즘.
2. 탐색 과정
0. 각 노드에서 f(n), g(n), h(n) 값을 계산한다.
g(n) : 시작 노드에서 현재 노드까지의 비용
h(n) : 현재 노드에서 목표 노드까지의 추정 비용
f(n) : g(n) + h(n) (최종 비용)
* h(n)값을 구하는 방법에는 여러 가지가 있다. (이 경우에는 맨하탄 거리(Manhattan Distance)를 사용한다)
* 맨하탄 거리 : | 현재 좌표 x값 - 목표 좌표 x값 | + | 현재 좌표 y값 - 목표 좌표 y값 |
1. 현재 노드에서 이동할 수 있는 노드들을 열린 목록(Open List)에 넣는다.
2. 열린 목록의 노드 중 f(n)값이 최소인 노드로 이동한다. (f(n)값이 같다면 h(n)값이 더 작은 노드로 이동한다)
(좌측 하단 - g(n), 우측 하단 - h(n), 우측 상단 - f(n))
3. 탐색이 끝난 노드를 닫힌 목록(Closed List)에 넣는다.
4. 목표 노드에 도달할 때 까지 위 과정을 반복한다.
