개요
길 찾기 알고리즘으로 유명한 A* 알고리즘이다.
게임에서 많이 사용된다.
기본적으로 다익스트라 알고리즘의 변형이다.
A*알고리즘은 휴리스틱 이론을 사용한다.
휴리스틱 이론은 정확한 값이 아닌 어림짐작을 통해 값을 추정하는 방법이다.
A*알고리즘은 목표까지의 거리를 정확하게 측정하지 않고 어림짐작하여 연산 시간을 줄이는 것이 핵심이다.
A*알고리즘을 통해 최단 거리를 찾기 위해 목표까지의 경로를 분할해야 하며, 이때 분할된 구역들이 노드가 된다.
초록색 노드가 시작노드, 빨간색 노드가 목표노드이며, 파란색은 지나갈 수 없는 장애물이다.
시작노드에 인접한 노드들 부터 확인하며, 비용이 작은 노드부터 탐색하게 되는데, 비용은 다음과 같이 정해진다.
비용 = (시작노드-현재노드 사이의 가중치) + (현재노드-목표노드 사이의 가중치)
이때 현재노드와 목표노드 사이의 가중치는 장애물을 무시한 단순 거리로 추정한다.
각 노드가 기억해야할 정보는 다음의 2가지 이다.
- 부모노드
- 비용
과정
A*알고리즘은 다음의 순서로 길 찾기를 한다.
1. 시작 노드를 열린목록(open list)에 넣는다. 열린목록에 있는 노드들은 다음 순번에 탐색할 후보노드들이 된다.
2. 열린목록에서 비용이 가장 작은 노드를 탐색한다. 처음에는 시작 노드만 들어있으므로 탐색노드는 시작노드가 된다.탐색한 노드는 다시 볼 필요가 없으므로 열린목록에서 제거하고 닫힌목록(closed list)에 추가한다.
3. 탐색노드와 인접한 노드들 중 닫힌목록과 갈 수 없는 노드들을 제외하고 열린목록에 넣는다. 또, 이 노드들의 비용을 측정한다.
좌하단의 값이 현재노드와의 가중치
우하단의 값이 목표노드와의 가중 추정치
좌상단의 값이 비용이다.
4. 목표에 도달할 때 까지 2번 부터 반복한다. 탐색중 가중치가 더 낮아지는 경우가 있다면, 가중치를 수정하고 부모노드를 변경한다.
시작노드의 2칸 아래 있는 노드는 처음에는 가중치가 88이었으나, 탐색중 80으로 낮아지면서, 경로가 수정되었다.
빨간 점이 찍힌 길이 최단거리가 된다.
+ 2019.09.25 추가
유니티 에이스타 구현 : https://github.com/dongb94/A-Star-Pathfinding
dongb94/A-Star-Pathfinding
Contribute to dongb94/A-Star-Pathfinding development by creating an account on GitHub.
github.com