[TIL] A* 알고리즘 개념 정리

A* 알고리즘이란?

최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로 현재 상태의 비용을 g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)라고 할 때, 둘을 더한 f(x) = g(x) + h(x)가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.

f(x)가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.

유니티 개발자가 A Star 알고리즘을 배워야하는 이유

"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방향 격자.

Dijkstra와의 차이 - 코드상 한줄

// Dijkstra
pQueue.Enqueue(adjacent, newDistance);

// A*
pQueue.Enqueue(adjacent, newDistance + Heuristic(adjacent, goal));

즉 A는 Dijkstra + 휴리스틱이다.

Dijkstra vs A Star 시각적 비교

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