게임 맵에서 최단 경로는 유지하면서 Dijkstra보다 탐색 범위를 줄이려 합니다. A*의 휴리스틱은 어떤 역할을 하며 어떤 조건을 만족해야 하나요?

Dijkstra는 출발점에서 현재까지의 누적 비용이 작은 노드를 우선 확장하지만, A는 여기에 목적지까지 남은 비용의 추정치를 더해 목표 방향의 후보를 먼저 봅니다. 노드의 우선순위를 f(n) = g(n) + h(n)으로 두며 g는 실제 누적 비용, h는 휴리스틱 추정치입니다. 휴리스틱이 실제 남은 비용을 넘지 않으면 최단 경로를 유지하면서 보통 탐색 범위를 줄일 수 있습니다. 이 조건을 허용적 휴리스틱(admissible heuristic)이라고 부릅니다. h=0이면 A의 우선순위가 Dijkstra와 같아집니다.

이동 규칙과 최적성

먼저 그래프의 이동 규칙과 비용을 고정해야 합니다. 네 방향으로 한 칸씩 같은 비용이면 맨해튼 거리가 자연스럽고, 대각 이동을 같은 비용으로 허용하면 체비셰프 거리, 직교 비용과 대각 비용이 다르면 그 조합에 맞는 옥타일 거리처럼 실제 가능한 경로의 하한을 사용해야 합니다. 벽을 모서리로 통과하지 못하게 하는 규칙이나 지형별 가중치가 있는데 단순한 직선거리를 쓰면 추정치가 실제 비용보다 큰지 다시 증명해야 합니다. 허용적이지만 값이 들쭉날쭉한 휴리스틱은 최적성을 위해 닫힌 노드를 다시 열어야 할 수 있습니다. 인접한 두 노드에서 h(a) <= cost(a,b)+h(b)가 성립하는 일관성(consistency)까지 만족하면, 일반적인 비음수 비용 탐색에서 닫힌 노드를 재오픈하지 않는 구현을 단순화할 수 있습니다. 예를 들어 평면 격자에서 벽을 피해 멀리 돌아가는 경로의 실제 남은 비용이 12인데 휴리스틱이 8이면 안전한 하한입니다.

반대로 휴리스틱을 20으로 과대 추정하면 목표에 가까워 보이는 길을 먼저 따라가므로 빠를 수 있지만, 비용 12 경로보다 실제로는 15인 경로를 먼저 반환해 최단 보장이 깨질 수 있습니다. 실시간 게임에서 Weighted A*처럼 g + w*h를 사용하는 근사 탐색을 택할 수는 있지만, 그때는 정확한 최단 경로가 아니라 허용 가능한 비용 상한을 가진 경로라는 계약으로 바꿔야 합니다.

검증과 운영 선택

작은 맵에서는 휴리스틱을 0으로 둔 결과와 비용·도달성을 비교하고, 대각 모서리·가중 지형·좁은 통로를 포함해 실제 규칙과 맞는지 확인하겠습니다. 탐색 노드 수만 줄고 휴리스틱 계산이나 우선순위 큐 비용이 커질 수 있으므로 전체 경과 시간, p99 탐색 시간, 메모리, 경로 비용을 함께 봅니다. 동점 우선순위를 목표에 가까운 순으로 둘 수 있지만 경로 모양과 탐색량을 바꾸는 최적화일 뿐 최적성 조건 자체를 대신하지는 않습니다. 또한 맵 버전이 바뀌면 휴리스틱이 여전히 같은 그래프의 하한인지 재검증하고, 근사 모드와 정확 모드를 사용자 경험상 명확히 구분하겠습니다. 결국 휴리스틱은 “그럴듯한 방향”이 아니라 실제 비용의 하한이라는 최적성 조건(optimality condition)으로 판단해야 합니다. 휴리스틱의 품질은 0과 최적 하한 사이에서 단순히 큰 값이 좋은 것으로 판단하지 않습니다.

같은 비용을 유지하면서 더 큰 하한을 주는 휴리스틱이 보통 노드를 덜 열지만, 계산 자체가 비싸거나 캐시를 망치면 전체 시간이 늘 수 있습니다. 각각이 실제 비용의 하한인 휴리스틱을 결합할 때 최대값을 취하면 하한으로 남지만, 값을 더하거나 가중치를 곱하는 방식은 과대 추정 여부를 다시 확인해야 합니다. 탐색 종료 조건도 최적성의 일부입니다. 목표를 처음 발견한 즉시 반환하는지, open의 최솟값이 목표 비용 이상이 될 때까지 확인하는지에 따라 허용적 휴리스틱에서의 보장이 달라집니다. 지형 비용이 바뀌는 게임에서는 휴리스틱뿐 아니라 간선 비용과 목표 도달 조건도 같은 맵 스냅샷을 봐야 합니다. 근사 모드라면 시간 상한에 도달했을 때 반환할 후보의 품질과 실패 시 대체 경로를 명확히 하겠습니다.