--- title: "칸이 아니라 구역 사이를 먼저 잇는다" description: "맵이 커지면 한 칸씩 훑는 길찾기는 넓이만큼 헤맵니다. 맵을 구역으로 나누고 구역 사이만 미리 이어 두는 계층형 길찾기(HPA*, Hierarchical Pathfinding A*)의 구조와, 전처리·경로 품질·구역 크기의 거래." author: "유니얼" pubDate: 2026-09-17 updatedDate: 2026-09-18 category: "programming/algorithm/graph" tags: ["최적화"] canonical: https://blog.unialgames.com/posts/algo-hpa-star/ --- 한 칸씩 이웃을 보는 길찾기는 **맵이 커지면 그만큼 더 훑습니다.** 훑는 양이 맵 넓이를 따라갑니다. 방 여덟 칸짜리가 격자로 늘어서 있고 방과 방 사이에 문이 하나씩 뚫린 맵을 만들어 한쪽 끝에서 반대쪽 끝까지 재 봤습니다. | 맵 크기 | 큐에서 꺼낸 칸 | | --- | --- | | 32×32 | 177 | | 64×64 | 977 | | 128×128 | 2,427 | | 256×256 | 14,087 | 맵 한 변이 여덟 배가 되는 동안 훑는 양은 여든 배가 됐습니다. 유닛 하나가 한 번 길을 찾는 값으로는 너무 큽니다. ## 사람은 방 단위로 길을 찾는다 낯선 건물에서 길을 찾을 때 바닥 타일을 하나씩 세지 않습니다. **"이 방에서 저 문으로, 그 복도를 지나 저쪽 문으로"** 로 먼저 정하고, 방 안에서 어떻게 걸을지는 그때 정합니다. **계층형 길찾기(HPA*, Hierarchical Pathfinding A*)** 가 그대로 그 순서입니다. 맵을 일정한 크기의 구역으로 자르고, **구역과 구역을 잇는 문**만 모아 작은 그래프를 하나 만들어 둡니다. 길찾기는 그 작은 그래프에서 먼저 하고, 칸 단위 경로는 정해진 구간 안에서만 채웁니다. 여기서 구역은 방이 아닙니다. **맵 위에 그냥 격자로 그은 선**입니다. 방 모양을 분석하지 않아도 되고, 어떤 맵에나 똑같이 적용됩니다. ## 경계에서 뚫린 자리마다 노드를 놓는다 구역을 자르고 나면 경계에서 **양쪽이 다 뚫려 있는 구간**을 찾습니다. 그 자리가 문입니다. 구간마다 **전이 노드(transition node)** 를 놓습니다. 경계를 사이에 둔 두 칸이 한 쌍입니다.

경계에서 양쪽이 다 뚫린 구간마다 전이 노드를 놓는다. 노드는 경계를 사이에 둔 두 칸이 한 쌍이다.

구역 안의 노드끼리는 실제로 재 본 거리로, 경계를 사이에 둔 쌍은 1로 잇는다. 이것이 추상 그래프의 전부다.

구간이 길면 양 끝에 하나씩 둡니다. 가운데 하나만 두면 벽에 바짝 붙어 도는 길이 나올 수 있어서입니다. 짧은 구간은 가운데 하나로 충분합니다. ```csharp // 오른쪽 경계에서 양쪽이 다 뚫린 구간을 찾는다 void BuildEntrances(int cx, int cy) { int bx = cx * size + size - 1; var span = new List(); for (int y = top; y <= bottom + 1; y++) { bool open = y <= bottom && Walkable(bx, y) && Walkable(bx + 1, y); if (open) { span.Add(y); continue; } if (span.Count > 0) { PlaceNodes(bx, span); span.Clear(); } } } void PlaceNodes(int bx, List span) { // 길면 양 끝, 짧으면 가운데 하나 var picks = span.Count > 3 ? new[] { span[0], span[^1] } : new[] { span[span.Count / 2] }; foreach (int y in picks) { var a = new Vector2Int(bx, y); var b = new Vector2Int(bx + 1, y); AddNode(a); AddNode(b); AddEdge(a, b, 1f); // 경계를 넘는 값은 언제나 1 } } ``` 노드를 다 놓으면 **같은 구역 안의 노드끼리 실제 거리를 재서** 이어 둡니다. 구역 하나 안에서만 도는 A 스타라 한 번이 싸고, 이때 나온 경로도 같이 저장해 둡니다. 나중에 그 구간을 지나게 되면 다시 찾지 않고 읽기만 하면 됩니다. 여기까지가 전처리입니다. 맵을 불러올 때 한 번 합니다. ## 질의는 세 단계다 만들어 둔 그래프에는 시작 칸도 목표 칸도 없습니다. 그래서 질의가 세 단계가 됩니다. 1. **끼워 넣기.** 시작과 목표를 제 구역 안에서만 재서 그 구역의 전이 노드에 이어 붙입니다 2. **구간 정하기.** 전이 노드만 있는 그래프에서 A 스타를 돌립니다. 칸이 아니라 노드를 꺼냅니다 3. **채우기.** 정해진 구간마다 저장해 둔 경로를 읽어 잇습니다 ```csharp List Find(Vector2Int start, Vector2Int goal) { InsertTemp(start); // 1. 이번 질의에만 쓰는 임시 노드 InsertTemp(goal); var hops = AStarOnGraph(start, goal); // 2. 노드 단위로 찾는다 var cells = new List { start }; for (int i = 1; i < hops.Count; i++) // 3. 구간을 읽어 잇는다 cells.AddRange(StoredPath(hops[i - 1], hops[i]).Skip(1)); RemoveTemp(start); RemoveTemp(goal); return cells; } ``` **임시 노드를 지우는 것을 잊으면 그래프가 질의할 때마다 자랍니다.** 처음 만들 때 한 번은 꼭 밟는 자리입니다. 같은 맵을 두 방식으로 돌려 보면 꺼내는 것이 무엇인지가 눈에 들어옵니다. 24×12 맵을 여섯 칸짜리 구역으로 잘랐습니다. 전이 노드는 28개, 구간은 9개로 정해졌습니다. | | 큐에서 꺼낸 것 | 들여다본 칸 | 경로 비용 | | --- | --- | --- | --- | | 한 칸씩 (A 스타) | 25칸 | 74 | 27.56 | | 구역 단위로 (HPA 스타) | 13노드 | 42 | 28.14 | **꺼내는 것이 칸에서 노드로 바뀌었습니다.** 지나갈 구역이 정해지고 나면 그 구역 밖은 쳐다보지도 않습니다. 대신 **경로가 2.1% 길어졌습니다.** 이것이 이 방법이 치르는 값입니다. ## 맵이 커질수록 벌어진다 이 정도 맵에서는 차이가 크지 않습니다. 이 방법이 값을 하는 자리는 맵이 커질 때입니다. 앞의 방 격자 맵을 여덟 칸짜리 구역으로 잘라 재 봤습니다. 질의 합은 끼워 넣기와 구간 정하기와 채우기를 더한 것입니다. | 맵 | A 스타가 꺼낸 칸 | 추상 노드 수 | 꺼냄 | 끼워 넣기 | 채우기 | 질의 합 | 최적 대비 | | --- | --- | --- | --- | --- | --- | --- | --- | | 32×32 | 177 | 46 | 18 | 24 | 43 | 85 | 103.6% | | 64×64 | 977 | 221 | 118 | 32 | 91 | 241 | 104.7% | | 128×128 | 2,427 | 953 | 360 | 24 | 170 | 554 | 105.8% | | 256×256 | 14,087 | 3,944 | 1,610 | 32 | 349 | 1,991 | 104.7% | 두 배씩 커지는 동안 차이가 2.1배에서 7.1배로 벌어집니다. 눈여겨볼 열은 **끼워 넣기**입니다. 맵이 예순네 배로 커지는 동안 이 값은 24와 32 사이에서 움직이지 않습니다. 시작 칸을 그래프에 잇는 일은 **제 구역 안에서만** 하는 것이라, 맵이 아무리 커져도 구역 하나 크기에 갇혀 있습니다. **맵 크기에 딸려 가는 부분을 구역 크기에 가둬 두는 것**이 이 방법의 핵심입니다. 반대로 꺼냄은 여전히 맵을 따라 커집니다. 추상 그래프 자체가 맵 넓이에 비례해 커지기 때문입니다. 그래서 정말 큰 맵에서는 **구역을 다시 묶어 한 층 더 쌓습니다.** 구역의 구역을 만드는 것이고, 절차는 똑같습니다. ## 구역을 얼마나 크게 잡을 것인가 구역을 키우면 추상 그래프가 작아집니다. 대신 끼워 넣기가 커집니다. 128×128 맵에서 구역 크기만 바꿔 봤습니다. | 구역 한 변 | 추상 노드 수 | 전처리에서 꺼낸 칸 | 꺼냄 | 끼워 넣기 | 채우기 | 질의 합 | 최적 대비 | | --- | --- | --- | --- | --- | --- | --- | --- | | 8 | 953 | 8,589 | 360 | 24 | 170 | 554 | 105.8% | | 16 | 448 | 40,074 | 136 | 348 | 161 | 645 | 103.0% | | 32 | 192 | 96,571 | 52 | 2,339 | 155 | 2,546 | 101.2% | | 64 | 64 | 89,950 | 20 | 15,401 | 153 | 15,574 | 100.6% | 구역을 키울수록 **경로는 좋아지고 질의는 나빠집니다.** 끼워 넣기가 구역 넓이를 따라가기 때문입니다. 구역 한 변이 여덟 배가 되면 넓이는 예순네 배가 되고, 끼워 넣기 값이 그대로 그 곡선을 그립니다. 전처리도 같이 커집니다. 한 구역 안의 노드가 늘면 노드 쌍의 수가 제곱으로 늘고, 쌍마다 A 스타를 한 번씩 돌려야 합니다. **맵 크기가 아니라 구역 크기가 저울입니다.** 여덟에서 열여섯 사이가 흔히 쓰이는 값인 이유가 이 표에 있습니다. ## 최단이 아니다 나오는 경로는 최단이 아닙니다. 위 표에서 3~6% 길었습니다. 이유는 **문을 몇 개로 줄여 놨기** 때문입니다. 실제 최단 경로가 지나가야 할 자리가 전이 노드 사이에 있으면, 그 자리를 못 씁니다. 구간이 길 때 양 끝에 노드를 두 개 두는 것도 이 손해를 줄이려는 것입니다. 줄이는 방법이 몇 가지 있습니다. - **노드를 더 촘촘히.** 구간마다 두 개가 아니라 몇 칸마다 하나씩 둡니다. 그래프가 커지는 만큼 질의가 느려집니다 - **이어 붙인 경로를 직선으로 펴기.** 구간을 이으면 문마다 꺾인 자국이 남습니다. 막힌 것이 없는 구간을 직선으로 바꾸면 상당 부분이 회수됩니다 - **가까우면 그냥 한 칸씩.** 시작과 목표가 같은 구역이거나 이웃 구역이면 구역 안에서 A 스타를 한 번 돌리는 편이 빠르고 정확합니다 마지막 줄이 실무에서 제일 값을 합니다. **가까운 길찾기에는 아예 이 구조를 안 타는 것**이 맞습니다. ## 맵이 바뀌면 그 구역만 다시 짓는다 전처리를 해 두는 방식은 보통 맵이 바뀌면 통째로 무너집니다. 이 구조는 그렇지 않습니다. 칸 하나가 막히거나 뚫리면 **그 칸이 든 구역 하나만** 다시 지으면 됩니다. 그 구역의 경계를 다시 훑어 전이 노드를 다시 놓고, 그 구역 안의 노드 쌍만 다시 재면 끝입니다. 다른 구역의 값은 하나도 건드리지 않습니다. 구역 안의 거리는 **구역 안에서만 정해지기** 때문입니다. 건물이 세워지고 부서지는 맵, 문이 열리고 닫히는 던전에서 이 성질이 값을 합니다. 128×128 맵의 전처리가 8,589칸이었지만, 구역 하나를 다시 짓는 것은 그 중 백분의 일도 안 됩니다. ## 조심할 자리 - **구역 경계가 맵 구조와 어긋나도 됩니다.** 오히려 그게 보통입니다. 다만 구역이 방보다 훨씬 작으면 문이 지나치게 많아져서 추상 그래프가 안 작아집니다 - **한 구역이 벽으로 두 조각 나 있으면** 그 조각들 사이에는 간선이 안 생깁니다. 노드 쌍마다 실제로 재 보기 때문에 저절로 처리되지만, 구역 안이 이어져 있다고 가정한 코드를 짜면 여기서 틀립니다 - **끼워 넣기는 매 질의마다 냅니다.** 같은 목표로 여러 유닛이 갈 때는 목표 쪽 끼워 넣기를 한 번만 하고 돌려 쓰면 그만큼 아낍니다 - **칸마다 비용이 다른 맵에서도 됩니다.** 구역 안 거리를 실제로 재서 저장하는 구조라, 늪이든 도로든 그 값이 그대로 들어갑니다 ## 정리 계층형 길찾기는 **길 하나를 두 단계로 나눠 찾는 방법**입니다. - 맵을 구역으로 자르고, 경계에서 뚫린 구간마다 전이 노드를 놓고, **구역 안 거리를 미리 재 둡니다** - 질의는 끼워 넣기, 구간 정하기, 채우기의 세 단계입니다. 임시 노드를 지우는 것을 잊으면 그래프가 자랍니다 - **끼워 넣기 값이 구역 크기에 갇혀 있다는 것**이 전부입니다. 맵이 커져도 그 부분은 안 커집니다 - 경로는 최단이 아닙니다. 3~6% 정도이고, 노드를 촘촘히 두거나 이어 붙인 경로를 펴서 줄입니다 - 맵이 바뀌면 **그 구역 하나만** 다시 지으면 됩니다. 동적인 맵에서 이 성질이 값을 합니다