---
title: "건너뛰어도 되는 칸은 건너뛴다"
description: "균일한 격자에서는 같은 비용의 길이 수십 개라서 탐색이 그만큼 넓어집니다. 그중 하나만 보게 만드는 점프 포인트 서치(JPS, Jump Point Search)의 규칙과, 이 방법이 통하지 않는 자리."
author: "유니얼"
pubDate: 2026-09-17
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["최적화", "격자"]
canonical: https://blog.unialgames.com/posts/algo-jps/
---
벽이 하나도 없는 빈 타일맵에서 길찾기를 돌려 보면, 목표 쪽으로 기울여 놨는데도 탐색이 꽤 넓게 퍼집니다.
막힌 곳이 없으니 헤맬 이유가 없어 보이는데도 그렇습니다.
이유는 벽이 아니라 **같은 값이 너무 많아서**입니다.
## 격자에서는 같은 길이 스무 개다
오른쪽으로 세 칸, 아래로 세 칸 떨어진 칸으로 갑니다. 가로세로로만 움직이면 어떤 순서로 가든 여섯 걸음입니다.
`R R R D D D` 를 섞는 가짓수는 스무 가지고, **그 스무 가지의 비용이 전부 같습니다.**
어떤 순서로 가든 여섯 걸음이다. 우선순위 큐는 이 셋을 구별하지 못한다.
대각선을 허용해도 마찬가지입니다. 대각선 몇 번과 가로세로 몇 번을 어떤 순서로 섞든 값이 같습니다.
오히려 같은 값의 길이 더 늘어납니다.
우선순위 큐는 이 스무 개 사이에서 우열을 가릴 수 없습니다. 값이 같으니까요.
그래서 하나를 붙잡고 끝까지 가 보는 대신, 스무 개를 조금씩 다 펼쳐 놓고 번갈아 봅니다.
칸 하나가 여러 경로에 동시에 들어가고, 큐에 넣었다 빼는 일이 그만큼 늘어납니다.
같은 비용의 길이 여러 개 존재하는 이 성질을 **경로 대칭(path symmetry)** 이라고 부릅니다.
동점일 때 목표에 가까운 쪽을 먼저 꺼내게 해 두면 꽤 줄어들지만, 대칭 자체가 사라지지는 않습니다.
**줄 세우기를 바꾸는 것으로는 한계가 있습니다. 애초에 만들지 않는 편이 낫습니다.**
## 스무 개 중 하나만 만든다
**점프 포인트 서치(JPS, Jump Point Search)** 는 그 스무 개 중 **하나만** 만들도록 규칙을 정합니다.
나머지 열아홉 개는 탐색 중에 아예 생기지 않습니다.
방법은 이렇습니다. 이웃 한 칸씩 큐에 넣는 대신,
**한 방향으로 계속 나아가다가 「여기서 다시 판단해야 한다」 는 칸이 나올 때만 큐에 넣습니다.**
지나온 칸들은 큐에 들어가지 않습니다. 어차피 그 칸들에서 갈라질 이유가 없었기 때문입니다.
큐에 넣는 그 칸을 **점프 포인트(jump point)** 라고 부릅니다.
## 다시 판단해야 하는 칸은 벽이 만든다
빈 들판에서는 갈라질 이유가 없습니다. 어느 칸에서 꺾든 값이 같으니까요.
**갈라질 이유는 벽이 만듭니다.** 벽 때문에 「이 칸을 지나야만 닿는 칸」 이 생기면, 거기서는 판단이 필요합니다.
그런 이웃을 **강제 이웃(forced neighbor)** 이라고 부릅니다.
p 에서 오른쪽으로 갈 때. n 에서 새로 열리는 칸이 없다n 위가 벽일 때. 물음표 칸은 n 을 지나야만 닿는다
규칙으로 적으면 세 줄입니다.
- **가로세로로 나아갈 때.** 진행 방향의 옆이 벽이고 그 벽 너머 대각선 칸이 뚫려 있으면, 지금 칸이 점프 포인트입니다
- **대각선으로 나아갈 때.** 한 칸 갈 때마다 **가로와 세로로 먼저 훑어 봅니다.** 그쪽에서 점프 포인트가 나오면 지금 칸이 점프 포인트입니다
- **목표 칸.** 무조건 점프 포인트입니다. 그냥 지나쳐 버리면 안 되니까요
대각선이 가로세로를 먼저 보는 이유는 순서 때문입니다.
대각선으로 쭉 가다가 옆으로 꺾어야 하는 상황이라면, 꺾을 자리를 대각선 위에서 미리 찾아 둬야 합니다.
그래서 대각선 한 칸마다 가로 한 줄과 세로 한 줄을 확인합니다. **비용이 가장 많이 드는 부분도 여기입니다.**
## 같은 격자에서 얼마나 줄어드는가
벽 한 줄만 세워 둔 14×8 격자입니다. 두 방식 모두 여덟 방향으로 움직이고 대각선 비용은 루트 2,
꺼내는 기준도 똑같이 `g + h` 입니다. 다른 것은 이웃을 보는 방식 하나뿐입니다.
한 칸씩 보는 쪽은 큐에서 **26개**를 꺼냅니다. 건너뛰는 쪽은 **6개**입니다.
꺼낸 칸이 곧 힙에서 값을 빼고 다시 정렬하는 횟수이고, 길찾기 시간의 큰 몫을 차지하는 부분입니다.
길의 **비용**은 둘 다 14.66 입니다. 지나는 칸이 서로 다른데 값이 같은 것이 바로 경로 대칭입니다.
**답을 나쁘게 만들지 않으면서 큐 작업만 줄이는 것**이 이 방법의 전부입니다.
## 코드는 재귀 한 덩어리다
바뀌는 곳은 이웃을 만드는 자리 하나입니다. 큐도, `f = g + h` 도 그대로 씁니다.
```csharp
// (x, y) 에서 (dx, dy) 방향으로 나아가며 점프 포인트를 찾는다. 없으면 null
Vector2Int? Jump(int x, int y, int dx, int dy) {
int nx = x + dx, ny = y + dy;
if (!Walkable(nx, ny)) return null; // 벽이나 맵 밖
if (nx == goal.x && ny == goal.y) return new Vector2Int(nx, ny);
if (HasForced(nx, ny, dx, dy)) return new Vector2Int(nx, ny);
if (dx != 0 && dy != 0) { // 대각선이면 가로세로를 먼저 본다
if (Jump(nx, ny, dx, 0) != null) return new Vector2Int(nx, ny);
if (Jump(nx, ny, 0, dy) != null) return new Vector2Int(nx, ny);
}
return Jump(nx, ny, dx, dy); // 같은 방향으로 계속
}
// 진행 방향 옆이 벽인데 그 너머 대각선 칸이 뚫려 있으면 여기서 갈라진다
bool HasForced(int x, int y, int dx, int dy) {
if (dy == 0)
return (!Walkable(x, y - 1) && Walkable(x + dx, y - 1))
|| (!Walkable(x, y + 1) && Walkable(x + dx, y + 1));
if (dx == 0)
return (!Walkable(x - 1, y) && Walkable(x - 1, y + dy))
|| (!Walkable(x + 1, y) && Walkable(x + 1, y + dy));
return (!Walkable(x - dx, y) && Walkable(x - dx, y + dy))
|| (!Walkable(x, y - dy) && Walkable(x + dx, y - dy));
}
```
큐에 넣을 때는 건너뛴 거리를 한 번에 더합니다.
```csharp
foreach (var (dx, dy) in DirectionsFrom(cur, parent[cur])) {
var jp = Jump(cur.x, cur.y, dx, dy);
if (jp == null) continue;
float ng = g[cur] + Octile(cur, jp.Value); // 한 칸이 아니라 건너뛴 만큼
if (ng >= Best(jp.Value)) continue;
Push(jp.Value, ng + Heuristic(jp.Value));
}
```
`DirectionsFrom` 은 어디서 왔는지를 보고 볼 필요 없는 방향을 미리 걷어내는 부분입니다.
오른쪽에서 온 칸이면 왼쪽으로 되돌아갈 이유가 없고, 대각선으로 온 칸이면 뒤쪽 세 방향이 통째로 빠집니다.
이 걷어내기가 없으면 점프 포인트를 찾아 놓고도 같은 곳을 여러 번 훑게 됩니다.
재귀가 부담이면 가로세로 방향은 `while` 로 펴도 됩니다. 재귀가 꼭 필요한 쪽은 대각선뿐입니다.
## 들여다본 칸은 오히려 늘어난다
값을 치르는 곳이 있습니다. 위 격자에서 **실제로 읽어 본 칸**을 세어 보면 반대가 나옵니다.
| | 큐에서 꺼낸 칸 | 들여다본 칸 |
| --- | --- | --- |
| 한 칸씩 (A 스타) | 26 | 57 |
| 건너뛰며 (JPS) | 6 | 102 |
빈 칸이 108개인 맵에서 102개를 읽었습니다. **거의 전부입니다.**
건너뛴다는 말이 안 본다는 뜻이 아니기 때문입니다. 한 방향으로 끝까지 훑어 보고 나서야 「여기엔 아무것도 없다」 를 알 수 있습니다.
그런데도 빠른 이유는 두 일의 단가가 다르기 때문입니다.
- **큐에서 꺼내는 일은 비쌉니다.** 힙을 다시 정렬하고, 노드마다 부모와 비용을 기록하고, 메모리를 잡습니다
- **한 방향으로 훑는 일은 쌉니다.** 배열을 차례로 읽는 것이라 캐시에 잘 맞고 분기도 적습니다. 한 줄을 비트로 묶어 한 번에 검사하는 구현도 있습니다
**그래서 이득은 맵에 따라 다릅니다.** 벽이 거의 없는 열린 맵은 훑는 거리가 길어져서 이득이 줄고,
방과 복도가 많은 맵은 금방 벽에 걸려 멈추기 때문에 이득이 큽니다. 실제 맵으로 재 보지 않으면 모릅니다.
## 통하지 않는 자리
조건이 꽤 까다롭습니다. 하나라도 어긋나면 답이 틀리거나 아예 적용이 안 됩니다.
| 조건 | 어긋나면 |
| --- | --- |
| 칸마다 이동 비용이 같아야 한다 | 늪이나 도로처럼 비용이 다르면 **쓸 수 없습니다.** 건너뛴 칸의 비용을 모르니 더할 수가 없습니다 |
| 격자여야 한다 | 내비메시나 웨이포인트 그래프에는 해당이 없습니다. 「한 방향으로 계속」 이 정의되지 않습니다 |
| 이동 규칙이 고정이어야 한다 | 유닛마다 지나갈 수 있는 칸이 다르면 점프 포인트도 달라집니다 |
**대각선으로 벽 모서리를 스칠 수 있게 할 것인지**도 미리 정해야 합니다.
흔히 보는 강제 이웃 규칙은 모서리 통과를 허용한다는 전제로 만들어져 있습니다.
많은 게임이 그걸 막는데, 막는 쪽으로 가려면 강제 이웃 판정을 그 규칙에 맞게 다시 써야 합니다.
**규칙만 그대로 두고 이동만 막으면 길을 못 찾습니다.** 큐에 넣은 점프 포인트로 갈 방법이 없어지기 때문입니다.
비용이 다른 칸이 필요하다면 그냥 A 스타를 씁니다. 격자를 균일하게 유지할 수 있는 맵에서만 꺼내는 카드입니다.
## 나오는 경로는 점이 몇 개뿐이다
결과로 받는 것은 칸의 목록이 아니라 점프 포인트의 목록입니다. 위 격자에서는 여섯 점입니다.
칸 단위로 움직여야 한다면 점과 점 사이를 직선으로 채우면 되고, 채우는 비용은 한 칸씩 훑는 것과 같습니다.
점이 적다는 것 자체가 쓸모 있을 때도 있습니다.
유닛이 따라갈 목표점이 여섯 개면 프레임마다 확인할 것도 여섯 개고, 직선 구간은 이미 하나로 합쳐져 있습니다.
## 정리
균일한 격자에서 탐색이 넓어지는 원인은 벽이 아니라 **같은 비용의 길이 여러 개**라는 사실입니다.
- 점프 포인트 서치는 그 대칭인 길들 중 **하나만 만들도록** 규칙을 정한 방법입니다. 답은 그대로고 큐 작업만 줄어듭니다
- 멈추는 자리는 **벽이 만드는 강제 이웃**입니다. 빈 들판에서는 갈라질 이유가 없으니 계속 지나칩니다
- 대각선으로 갈 때는 한 칸마다 가로세로를 먼저 훑습니다. 여기가 가장 비쌉니다
- **읽는 칸은 오히려 늘어납니다.** 대신 비싼 큐 작업이 줄어드는 거래입니다. 이득은 맵 모양에 따라 달라집니다
- **칸마다 비용이 다르면 쓸 수 없습니다.** 균일한 격자라는 조건이 이 방법의 전부를 떠받치고 있습니다