A* 알고리즘

파란 칸 = 다익스트라가 확정한 칸 - 목적지(E) 반대쪽 왼쪽 끝까지

다익스트라를 사용할 경우, 목적지를 찾기 위해 사방을 전부 뒤져야 한다.
목적지(E)는 오른쪽에 있는데, 출발지(S)에서 왼쪽까지 찾게 된다.

빈칸 217개 중 185칸을 확정해서 16걸음짜리 경로 하나를 얻은 셈이다.

하지만 게임에서는 이는 비효율적이다.
- RTS 장르: 유닛 100명을 움직이면 길찾기를 100번 수행한다.
- 추격하는 적: 플레이어가 움직일 때마다 경로를 재계산한다.

일반적으로 길을 찾을때는, "목적지가 동쪽이면 일단 동쪽으로" 간다.
이러한 대략의 감을 수치화하여 다익스트라에 추가한 것이 A*(에이스타) 이다.

※ A*: 1968년도, 거의 모든 게임 길찾기의 표준 알고리즘.

A*의 원리

다익스트라는 "출발점에서 가까운 순서로만" 확정하니 목적지 방향과 관계없이 사방으로 퍼진다.

다익스트라의 확정 기준은 "미확정 중 g가 가장 작은 칸"
: 목적지는 없음. 뒤(온 거리)는 알지만, 앞(남은 거리)은 보지 않음.

"남은 비용"을 정확히 알면 이미 최단경로를 아는 것 (즉, 불가능함)

하지만 어림은 할 수 있다. 이 어림값이 이름이 휴리스틱(heuristic), 기호로 h이다.

h = "이 칸에서 목적지까지, 대략 얼마나 남았나"의 추정값.

뉴욕 맨해튼의 바둑판 도로에서 딴 이름 - 대각선 없이 가로·세로로만 걸을 때의 거리이다.
(칸 안 숫자 = n에서부터의 걸음)

h = |세로 차이| + |가로 차이| = 2 + 4 = 6

n에서 E까지: 아래로 2칸, 오른쪽으로 4칸, 벽이 있든 없든 이 계산은 똑같다. (장애물 무시)