---
title: "통로 안에서 줄을 당긴다"
description: "길찾기가 내놓은 계단 경로와 폴리곤 통로를 사람이 걷는 선으로 펴는 방법입니다. 보이는 점끼리 잇는 스트링 풀링(String Pulling)과, 통로 안 최단을 한 번에 뽑는 깔때기 알고리즘(Funnel Algorithm)."
author: "유니얼"
pubDate: 2026-09-17
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["최적화"]
canonical: https://blog.unialgames.com/posts/algo-path-smoothing/
---
길찾기가 답을 내놨습니다. 그런데 그 답을 그대로 따라 걸으면 이상합니다.
격자에서 나온 경로는 **계단처럼 꺾입니다.** 빈 들판 한가운데서도 45도씩 각 잡고 돕니다.
내비메시에서 나온 것은 더 이상합니다. 삼각형 가운데를 이어 놓으면 **아무 이유 없이 지그재그**입니다.
이유는 하나입니다. **탐색은 칸이나 폴리곤 단위로 답하는데, 유닛은 연속된 공간에서 움직입니다.**
칸 가운데를 지나야 할 이유가 없고, 삼각형 가운데를 지나야 할 이유도 없습니다.
## 보이면 가운데를 버린다
가장 간단한 방법부터 봅니다. **한 점에서 앞쪽 점이 곧장 보이면, 그 사이의 점들은 필요 없습니다.**
격자 길찾기가 내놓은 점 9개. 길이 9.66보이는 점끼리 이어 남은 점 4개. 길이 9.37
점이 아홉 개에서 네 개로 줄었습니다. 길이는 9.66 에서 9.37 로 3% 남짓 줄었을 뿐입니다.
**이 방법의 값어치는 길이보다 점의 수와 모양에 있습니다.** 유닛이 프레임마다 확인할 목표점이 줄고, 계단이 사라집니다.
이것을 **스트링 풀링(String Pulling)** 이라고 부릅니다. 점들을 실로 꿰어 놓고 양 끝을 당기는 그림입니다.
```csharp
List Pull(List path) {
var result = new List { path[0] };
int anchor = 0;
while (anchor < path.Count - 1) {
int far = path.Count - 1;
while (far > anchor + 1 && !LineOfSight(path[anchor], path[far]))
far--; // 안 보이면 한 칸씩 당겨 온다
result.Add(path[far]);
anchor = far;
}
return result;
}
```
**`LineOfSight` 가 이 코드의 전부이고, 함정도 거기 있습니다.**
시야 판정이 **실제 이동 규칙과 같아야** 합니다.
대각선으로 벽 모서리를 스치는 것을 막아 놓고 시야 검사는 선분만 본다면,
다듬은 경로가 유닛이 지나갈 수 없는 자리를 지나갑니다. 길찾기는 맞는데 유닛이 벽에 낍니다.
비용은 시야 검사 횟수입니다. 최악이 `O(n²)` 이고, 검사 하나가 격자 훑기라 싸지 않습니다.
**경로가 길수록 다듬는 값이 찾는 값을 넘어서기도 합니다.**
## 통로가 폴리곤이면 더 잘할 수 있다
내비메시 길찾기가 실제로 내놓는 것은 경로가 아니라 **지나갈 폴리곤의 목록**입니다.
이웃한 두 폴리곤이 맞닿은 변을 **포털(portal)** 이라고 부르고, 통로는 포털의 줄로 표현됩니다.
이 경우에는 시야 검사를 한 번도 안 하고 **그 통로 안에서의 진짜 최단 경로**를 뽑을 수 있습니다.
**깔때기 알고리즘(Funnel Algorithm)** 입니다.
발상은 이렇습니다. 지금 서 있는 점에서 **왼쪽으로 볼 수 있는 한계선**과 **오른쪽 한계선**을 들고 갑니다.
포털을 하나씩 보면서 그 두 선을 좁혀 나갑니다. 좁아지기만 하면 계속 갑니다.
**한쪽이 반대쪽을 넘어가는 순간**, 더는 곧게 갈 수 없다는 뜻이고, 넘긴 쪽 끝점이 꺾이는 자리가 됩니다.
포털 일곱 개를 한 번 훑어서 꺾이는 점 세 개가 나왔습니다. 길이는 655 에서 518 로 **21% 줄었습니다.**
**꺾이는 자리가 전부 포털의 끝점**이라는 데 주목할 만합니다. 당연합니다.
장애물이 없는 곳에서 꺾을 이유가 없으니, 꺾인다면 그 자리는 벽의 모서리입니다.
## 왜 한 번만 훑으면 되나
두 방법의 성질이 꽤 다릅니다.
| | 스트링 풀링 | 깔때기 |
| --- | --- | --- |
| 입력 | 점의 목록 | 포털의 목록 (폴리곤 통로) |
| 필요한 것 | 시야 검사 | 없음. 외적 부호만 봅니다 |
| 비용 | 시야 검사 횟수. 최악 `O(n²)` | 포털 수에 비례. 한 번 훑기 |
| 결과 | 통로 안 최단은 아님 | **그 통로 안에서는 최단** |
| 쓰는 자리 | 격자, 웨이포인트 | 내비메시 |
깔때기가 한 번 훑기로 끝나는 이유는 **버린 것을 다시 볼 일이 없기 때문**입니다.
왼쪽 선이 좁아졌다는 것은 그만큼의 각도가 영영 막혔다는 뜻입니다. 되돌릴 일이 없습니다.
꺾이는 점이 정해지면 거기서 깔때기를 다시 열고, 그 앞부터 다시 봅니다.
되돌아가는 것처럼 보이지만 **이미 확정된 앞부분은 건드리지 않습니다.**
```csharp
// 세 점의 방향을 부호로 본다. 이 함수 하나로 좌우 판정이 끝난다
float Cross(Vector2 a, Vector2 b, Vector2 c)
=> (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
foreach (var portal in portals) {
if (Cross(apex, right, portal.right) >= 0) { // 오른쪽이 안쪽으로
if (apex == right || Cross(apex, left, portal.right) < 0) {
right = portal.right; // 좁힌다
} else {
corners.Add(left); // 왼쪽을 넘었다
apex = left; right = left; // 거기서 다시 연다
RestartFromApex();
continue;
}
}
// 왼쪽도 똑같이, 좌우만 뒤집어서
}
```
**좌우를 뒤집은 같은 코드가 두 번 나오는 것**이 이 알고리즘의 생김새입니다.
한쪽을 짜고 부호와 이름을 뒤집어 복사하면 됩니다.
## 유닛에는 반지름이 있다
여기까지의 경로는 **점 하나가 지나가는 선**입니다. 꺾이는 자리가 벽 모서리에 딱 붙어 있습니다.
반지름이 있는 유닛이 그대로 따라가면 어깨가 벽에 낍니다.
두 가지로 처리합니다.
- **포털을 미리 줄인다.** 포털 양 끝을 반지름만큼 안쪽으로 당겨 놓고 깔때기를 돌립니다. 통로가 반지름보다 좁으면 그 통로는 못 지나간다는 뜻이고, 그 판정도 여기서 나옵니다
- **꺾이는 점을 밀어낸다.** 나온 코너를 모서리에서 반지름만큼 바깥으로 옮깁니다. 간단하지만 두 모서리가 가까우면 밀어낸 점이 다른 벽으로 들어갈 수 있습니다
**앞쪽이 안전합니다.** 통로를 만들 때 이미 유닛 크기를 아는 경우가 대부분입니다.
## 곡선으로 만드는 것은 다른 문제다
꺾인 선이 여전히 각져 보인다고 베지어나 캣멀롬으로 둥글리는 경우가 많습니다.
그건 **보기 좋게 만드는 일**이고, 경로를 짧게 만드는 일과는 다릅니다.
- 곡선은 원래 선보다 **길어집니다.** 코너를 자르는 게 아니라 코너 바깥으로 부풀기 때문입니다
- 부푼 쪽이 벽이면 **벽을 스칩니다.** 곡선을 만든 뒤에 다시 검사해야 합니다
- 유닛이 회전 속도를 가진다면 애초에 곡선이 필요 없습니다. **따라가는 쪽에서 부드러워집니다**
경로를 곡선으로 바꾸는 대신 **유닛의 방향을 서서히 돌리는 쪽**이 대개 더 싸고 덜 깨집니다.
## 다듬어도 안 되는 것
다듬기는 **주어진 통로 안에서만** 일합니다. 통로 바깥으로 나가지 않습니다.
그래서 탐색이 고른 통로가 멀리 돌아가는 것이었다면, 아무리 당겨도 그 길입니다.
구역 단위로 고른 구간이나 점프 포인트로 이은 구간도 마찬가지입니다. 그것들은 전부 **통로를 정하는 단계**입니다.
**경로가 이상하면 다듬기를 의심하기 전에 통로를 먼저 보세요.**
다듬기로 고쳐지는 것은 모양이지 선택이 아닙니다.
## 정리
길찾기의 답은 **지나갈 통로**이고, 걷는 선은 거기서 한 번 더 뽑아내는 것입니다.
- 격자나 웨이포인트에서는 **보이는 점끼리 이어 가운데를 버립니다.** 시야 판정이 이동 규칙과 같아야 합니다
- 내비메시처럼 **포털 목록**이 있으면 깔때기 알고리즘으로 시야 검사 없이 한 번에 뽑습니다. 그 통로 안에서는 최단입니다
- 꺾이는 자리는 언제나 **포털의 끝점**, 즉 벽의 모서리입니다
- 유닛 반지름은 **포털을 미리 줄여** 처리하는 편이 안전합니다
- 곡선으로 만드는 것은 보기 좋게 하는 일이고 경로를 짧게 하는 일이 아닙니다
- 다듬기는 통로 안에서만 일합니다. **통로 선택이 틀렸으면 다듬어도 그 길입니다**