[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)

[왼쪽]  각 노드간의 거리 (g(x)) ,  [오른쪽] 도착지점까지의 추정거리 (h(x))

시작노드 : 7번

- 시작 노드 7번을 close에 담는다.
- 7번과 연결된 6번 5번을 open에 담는다.
- 추정거리가 가장 짧은 6번 노드를 close에 담는다.

 

- 6번과 연결된 2번 1번을 open에 담는다.
- 추정거리가 가장 짧은 2번 노드를 close에 담는다.

 

 

- 6번과 연결된 2번 1번을 open에 담는다.
- 추정거리가 가장 짧은 2번 노드를 close에 담는다.

 

 

---

구현 (C++)