최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로 현재 상태의 비용을 g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)라고 할 때, 둘을 더한 f(x) = g(x) + h(x)가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.
f(x)가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.
"NavMesh가 있는데 굳이?" 라고 생각할 수 있다. 하지만 NavMesh는 만능이 아니다.
NavMesh가 어색한 상황들이 분명히 있다. 타일맵 기반의 전략 게임, 절차적으로 생성되는 던전, 2D 격자 이동이 필요한 퍼즐 게임 — 이런 경우엔 NavMesh보다 A*를 직접 구현하는 것이 훨씬 자연스럽다.
커스텀 로직이 필요할 때도 마찬가지다. "적이 불 타일은 피해서 이동", "체력이 낮으면 전투를 우회하는 경로 선택" 같은 조건은 NavMesh의 비용 시스템만으로는 표현하기 어렵다. 원리를 알아야 자유롭게 응용할 수 있다.
디버깅할 때도 원리가 필요하다. NavMesh를 쓰다가 경로가 이상하게 나올 때, 내부 동작을 모르면 원인을 찾기 어렵다. A*의 휴리스틱과 비용 계산 방식을 이해하면 문제를 훨씬 빠르게 파악할 수 있다.
NavMesh는 도구고, A*는 지식이다. 도구는 상황에 따라 바뀌지만, 원리를 알면 어떤 도구든 제대로 쓸 수 있다.
Dijkstra는 "지금까지 비용 g(n)"만 본다.
A*는 "지금까지 비용 g(n) + 목적지까지 예상 비용 h(n)"을 함께 본다.
f(n) = g(n) + h(n)
- g(n): 시작점에서 n까지 실제 비용(Dijkstra의 distance와 동일)
- h(n): n에서 목적지까지 추정 비용 - 휴리스틱(heuristic)
우선순위 큐에 f(n)을 우선순위로 넣어 "실제로 가까운 + 목적지를 향해 있는" 노드가 먼저 나오게 된다
Admissible(허용 가능): h(n) ≤ 실제 n→goal 비용. 과소평가여야 최적 보장.
격자에서 많이 쓰는 것:
- Manhattan 거리:
|dx| + |dy| — 상하좌우 이동만 가능한 4방향 격자에 적합. 이 프로젝트가 사용.
- Euclidean 거리:
sqrt(dx² + dy²) — 대각선도 가능할 때.
- Chebyshev 거리:
max(|dx|, |dy|) — 8방향 격자.
pQueue.Enqueue(adjacent, newDistance);
pQueue.Enqueue(adjacent, newDistance + Heuristic(adjacent, goal));
즉 A는 Dijkstra + 휴리스틱이다.

*Dijkstra는 등고선처럼 사방으로 퍼지고, A**는 목적지를 향해 "길죽하게" 탐색한다.