[Algorithm/Shortest Path] A* 알고리즘 - 구현C++
스터디에서 A* 알고리즘을 한 번 작성해보고 간단하게 콘솔로 띄어보고.. 유니티로 적용해보기로 하였다. 유니티로 옮기는 작업 벌써부터 걱정이 된다. 일단 A*알고리즘이 뭔지 정리를 해보자 ..
A* 알고리즘은 다익스트라 알고리즘을 확장하여 만들어진 알고리즘으로 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.
주로 게임에서 몬스터가 플레이어를 목표지점으로 이동하거나 자동 사냥 게임에서 플레이어가 타겟(몬스터나 다른 PC)을 향해 이동시킬 때 사용하는 알고리즘이다.
| 알고리즘 | 다익스트라 알고리즘 | A* 알고리즘 |
| 목표점 | 시작점 -> 나머지 모든 정점들까지의 최단 거리 | 시작점 -> 목표점까지의 최단 거리 |
| 차후 경로 도출을 위한 함수 f(n) |
현재 노드에서 가까운 노드부터 순차적으로 방문 f(n) = g(n) |
현재 노드와 휴리스틱 함수를 통해 점수를 매기고 가장 좋은(가장 가까운) 점수 노드를 방문 f(n) = g(n) + h(n) (* h(n)=0 이면, 다익스트라) |
| 속도 | 다익스트라 < A* | |
A* 알고리즘 방문 노드 탐색 기준 공식
$ f\big(n\big) = g\big(n\big)+h\big(n\big) $
- g(x): 시작 노드부터 현재 노드까지의 최단 거리(비용)
- h(x)/heuristic : 현재 노드에서 도착 노드까지의 추정된 남은 거리(비용)
heuristic 휴리스틱 중 대표적인 함수
(1). 맨해튼 거리(Manhattan Distance) 함수 : L1 Distance라고 불리는 공식
2차원 : |x1 - x2| + |y1 - y2|
3차원: |x1 - x2| + |y1 - y2| + |z1 - z2|
(2). 유클리디안 거리 함수(Euclidean Distance) : L2 Distance라고 불리는 공식 (아래 코드는 유클리디안 사용.)
2차원: $$\sqrt{ \big(x2 - x1\big) ^{2}+ \big(y2-y1\big) ^{2}}$$
3차원: $$\sqrt{ \big(x2 - x1\big) ^{2}+ \big(y2-y1\big) ^{2} + \big(z2-z1\big) ^{2}}$$
그림으로 A*알고리즘 흐름보기
1. P = 시작점
2. P에 f, g, h 할당
3. Open 리스트에 P 넣기
4. B = Open 리스트에서 가장 낮은 f 값을 가진 노드
a. B가 목표점이면, 경로 완성
b. Open 리스트가 비었으면, 목표점까지 경로가 존재하지 않음
5. C = B에 연결된 노드
a. C에 f, g, h 값 할당
b. Open/Close 리스트에서 C가 있는지 체크
1. 있으면, 더 낮은 f 값으로 경로 업데이트
2. 없으면, C를 Open 리스트에 넣기
c. 5번으로 돌아가서 B에 연결된 모든 노드를 대상으로 진행
6. 4번으로 돌아감
[pseudo 코드 출처]
A* 알고리즘의 구현 – 게임 개발 블로그/유니티/언리얼/스토리/팁/프로그래밍 (lunchballer.com)
- 시작 노드 7번을 close에 담는다.
- 7번과 연결된 6번 5번을 open에 담는다.
- 추정거리가 가장 짧은 6번 노드를 close에 담는다.
- 6번과 연결된 2번 1번을 open에 담는다.
- 추정거리가 가장 짧은 2번 노드를 close에 담는다.
- 6번과 연결된 2번 1번을 open에 담는다.
- 추정거리가 가장 짧은 2번 노드를 close에 담는다.
구현 (C++)