--- title: "남은 거리를 짐작하면 덜 헤맨다" description: "목표가 하나일 때 탐색을 그쪽으로 기울이는 A 스타(A*) 알고리즘입니다. 휴리스틱이 지켜야 하는 조건, 과대평가하면 무엇이 깨지는지, 격자에서 무엇을 쓰고 동점은 어떻게 처리하는지." author: "유니얼" pubDate: 2026-09-17 updatedDate: 2026-09-18 category: "programming/algorithm/graph" tags: ["탐색", "격자"] canonical: https://blog.unialgames.com/posts/algo-astar/ --- 비용이 가장 적은 후보부터 확정하는 방식은 **사방으로 고르게 퍼집니다.** 목표가 어느 쪽에 있든 상관하지 않습니다. 맵 전체의 거리 지도를 만들 거라면 그게 맞지만, 알고 싶은 것이 **한 지점까지의 길**이라면 반대편으로 퍼진 계산은 전부 버려집니다. 사람은 그렇게 길을 찾지 않습니다. 목적지가 동쪽이면 동쪽부터 봅니다. 그 감각을 알고리즘에 넣은 것이 **A 스타(A*)** 입니다. ## 남은 거리를 더해서 꺼낸다 바꾸는 것은 꺼내는 기준 하나입니다. ``` 다익스트라 f = g A 스타 f = g + h ``` `g` 는 시작점에서 여기까지 실제로 든 비용이고, `h` 는 **여기서 목표까지 얼마나 더 들 것 같은가**라는 짐작입니다. 둘을 더한 값이 작은 것부터 꺼내면, 이미 싸게 온 것과 목표에 가까운 것이 같이 앞으로 옵니다. 같은 그래프, 같은 목표인데 **A 스타는 네 정점만 확정하고 끝냅니다.** 비용만 보는 쪽은 여덟 개를 전부 확정합니다. 답으로 나오는 경로와 비용은 둘이 같습니다. **다른 것은 가는 길이 아니라 들여다본 넓이입니다.** 목표를 확정하는 순간 멈추는 것은 둘 다 같습니다. 그런데 비용만 보면 목표가 큐에서 앞으로 나오기까지 가까운 것들을 전부 확정하게 되고, 그중 상당수는 목표와 반대편입니다. ## 휴리스틱은 넘겨 짚으면 안 된다 `h` 는 짐작이라 아무 값이나 넣어도 돌아갑니다. 다만 **답이 최단이라는 보장은 조건 하나에 걸려 있습니다.** > **h 는 실제 남은 비용보다 크면 안 됩니다.** 이 조건을 허용성(admissibility)이라고 부릅니다. 과대평가하면 무슨 일이 생기는지는 한 줄로 설명됩니다. 실제로는 2면 되는데 `h` 가 9라고 말하면, 그 정점의 `f` 가 부풀어서 **뒤로 밀립니다.** 그 사이에 더 비싼 다른 길이 목표를 먼저 확정해 버리면, 알고리즘은 그걸 답으로 내놓고 멈춥니다. 최단이 아닌 길입니다. 반대로 **과소평가는 안전합니다.** `h` 를 0으로 두면 그냥 다익스트라가 되고, 답은 여전히 최단입니다. 탐색이 넓어질 뿐입니다. 그래서 확신이 없으면 낮춰 잡는 쪽이 맞습니다. 조건이 하나 더 있습니다. **일관성(consistency)** 입니다. 이웃으로 한 칸 갈 때 `h` 가 그 간선 비용보다 더 많이 줄어들면 안 된다는 것입니다. 일관적이면 한 번 확정한 정점을 다시 볼 일이 없어서 구현이 단순해집니다. 아래에서 쓰는 격자용 휴리스틱들은 전부 일관적이라 이 걱정을 안 해도 됩니다. ## 격자에서는 무엇을 쓰나 `h` 는 "장애물이 하나도 없다고 치고 목표까지 가는 비용" 으로 잡으면 자연스럽게 과소평가가 됩니다. 움직일 수 있는 방향에 따라 식이 달라집니다. | 이동 | h | 왜 | | --- | --- | --- | | 네 방향 | 맨해튼 거리. `\|dx\| + \|dy\|` | 대각선으로 못 가니 가로세로 합이 최선입니다 | | 여덟 방향 | 옥타일 거리. `max + (√2 - 1) × min` | 대각선으로 겹치는 만큼 깎아 줍니다 | | 자유 이동 (NavMesh 등) | 유클리드 거리 | 직선이 최선입니다 | **단위를 맞추는 것이 실수하기 쉬운 자리입니다.** 이동 비용이 칸당 10이면 `h` 도 칸 수가 아니라 `칸 수 × 10` 이어야 합니다. 칸 수를 그대로 쓰면 `h` 가 실제보다 열 배 작아서, 틀리지는 않지만 A 스타가 다익스트라처럼 넓게 퍼집니다. 늪처럼 비싼 칸이 섞여 있을 때는 어떨까요. `h` 를 **가장 싼 칸 기준**으로 잡으면 언제나 과소평가라 안전합니다. 평균 비용으로 잡으면 더 빠르지만 과대평가가 생겨서 최단이 깨질 수 있습니다. ## h 를 얼마나 믿을 것인가 같은 코드에서 `h` 에 곱하는 가중치만 바꿔도 성격이 달라집니다. | `f = g + w × h` | 결과 | | --- | --- | | `w = 0` | 다익스트라. 넓게 퍼지지만 최단을 보장합니다 | | `w = 1` | A 스타. 최단을 보장하면서 목표 쪽으로 기울어집니다 | | `w > 1` | 가중 A 스타. 훨씬 빨리 도착하지만 **최단이 아닐 수 있습니다** | | `g` 를 무시 | 탐욕 최우선 탐색. 가장 빠르고 자주 엉뚱합니다 | 모바일에서 유닛이 수십 마리씩 길을 찾는다면 `w` 를 1.2 정도로 두는 선택이 실제로 쓰입니다. 경로가 조금 길어지는 대신 탐색이 확 줄어듭니다. **최단이 아니어도 되는지는 게임이 정할 문제입니다.** ## 동점이 많으면 지그재그가 나온다 격자에서는 `f` 가 같은 후보가 무더기로 생깁니다. 가로세로 비용이 같으면 계단처럼 도는 길과 곧게 가는 길의 `f` 가 똑같습니다. 그러면 알고리즘은 아무거나 고르고, 결과가 **눈에 거슬리는 지그재그**로 나옵니다. 탐색 범위도 쓸데없이 넓어집니다. 동점일 때 순서를 정해 주면 해결됩니다. - **`h` 가 작은 쪽을 먼저.** 같은 `f` 면 목표에 더 가까운 쪽부터 봅니다. 한 줄로 끝나고 효과가 큽니다 - **`h` 에 아주 작은 값을 곱하기.** `h × 1.001` 처럼 미세하게 기울이면 직선 경로가 선호됩니다 - **시작점과 목표를 잇는 직선에서 멀어질수록 조금 손해 주기.** 경로가 더 곧아집니다 셋 다 목적은 같습니다. **답을 바꾸지 않으면서 보기 좋은 쪽을 먼저 고르게 하는 것**입니다. ## 게임에서 부딪히는 자리 - **목표가 여럿일 때.** 가장 가까운 목표까지의 거리를 `h` 로 쓰면 됩니다. 여러 개 중 아무 데나 도착하면 되는 경우입니다 - **목표에 도달할 수 없을 때.** 큐가 빌 때까지 맵 전체를 훑고 실패합니다. 섬처럼 끊긴 구역이 있으면 미리 덩어리를 표시해 두고 시작 전에 거르는 편이 낫습니다 - **여러 유닛이 같은 목표로 갈 때.** 유닛마다 A 스타를 돌리면 같은 계산을 반복합니다. 목표가 하나면 거리 지도를 한 번 만들어 모두가 읽는 쪽이 낫습니다 - **경로가 자주 막힐 때.** 전체를 다시 계산하지 말고 막힌 지점부터 다시 찾거나, 몇 프레임에 나눠 계산합니다 A 스타가 느려지는 것은 대개 알고리즘이 아니라 **한 프레임에 몇 번 부르느냐** 때문입니다. 호출 자체를 줄이는 방법을 먼저 봐야 합니다. ## 정리 A 스타는 다익스트라에 **목표까지의 짐작**을 더한 것입니다. 꺼내는 기준이 `g` 에서 `g + h` 로 바뀐 것이 전부입니다. - 답은 같고 **들여다보는 넓이가 줄어듭니다.** 목표가 하나로 정해져 있을 때만 값을 합니다 - **`h` 는 실제 남은 비용을 넘으면 안 됩니다.** 넘겨 짚으면 더 싼 길을 뒤로 밀어내고 엉뚱한 답을 냅니다 - 격자에서는 네 방향이면 맨해튼, 여덟 방향이면 옥타일입니다. **비용 단위를 맞추는 것**을 잊지 마세요 - `h` 에 1보다 큰 가중치를 곱하면 빨라지지만 최단이 아닐 수 있습니다. 게임이 그걸 허용하는지로 정합니다 - 동점이 많으면 경로가 지그재그로 나옵니다. `h` 가 작은 쪽을 먼저 보게 하면 대부분 해결됩니다