건너뛰어도 되는 칸은 건너뛴다

벽이 하나도 없는 빈 타일맵에서 길찾기를 돌려 보면, 목표 쪽으로 기울여 놨는데도 탐색이 꽤 넓게 퍼집니다. 막힌 곳이 없으니 헤맬 이유가 없어 보이는데도 그렇습니다.

이유는 벽이 아니라 같은 값이 너무 많아서입니다.

격자에서는 같은 길이 스무 개다

오른쪽으로 세 칸, 아래로 세 칸 떨어진 칸으로 갑니다. 가로세로로만 움직이면 어떤 순서로 가든 여섯 걸음입니다. R R R D D D 를 섞는 가짓수는 스무 가지고, 그 스무 가지의 비용이 전부 같습니다.

대각선을 허용해도 마찬가지입니다. 대각선 몇 번과 가로세로 몇 번을 어떤 순서로 섞든 값이 같습니다. 오히려 같은 값의 길이 더 늘어납니다.

우선순위 큐는 이 스무 개 사이에서 우열을 가릴 수 없습니다. 값이 같으니까요. 그래서 하나를 붙잡고 끝까지 가 보는 대신, 스무 개를 조금씩 다 펼쳐 놓고 번갈아 봅니다. 칸 하나가 여러 경로에 동시에 들어가고, 큐에 넣었다 빼는 일이 그만큼 늘어납니다.

같은 비용의 길이 여러 개 존재하는 이 성질을 경로 대칭(path symmetry) 이라고 부릅니다. 동점일 때 목표에 가까운 쪽을 먼저 꺼내게 해 두면 꽤 줄어들지만, 대칭 자체가 사라지지는 않습니다. 줄 세우기를 바꾸는 것으로는 한계가 있습니다. 애초에 만들지 않는 편이 낫습니다.

스무 개 중 하나만 만든다

점프 포인트 서치(JPS, Jump Point Search) 는 그 스무 개 중 하나만 만들도록 규칙을 정합니다. 나머지 열아홉 개는 탐색 중에 아예 생기지 않습니다.

방법은 이렇습니다. 이웃 한 칸씩 큐에 넣는 대신, 한 방향으로 계속 나아가다가 「여기서 다시 판단해야 한다」 는 칸이 나올 때만 큐에 넣습니다. 지나온 칸들은 큐에 들어가지 않습니다. 어차피 그 칸들에서 갈라질 이유가 없었기 때문입니다.

큐에 넣는 그 칸을 점프 포인트(jump point) 라고 부릅니다.

다시 판단해야 하는 칸은 벽이 만든다

빈 들판에서는 갈라질 이유가 없습니다. 어느 칸에서 꺾든 값이 같으니까요. 갈라질 이유는 벽이 만듭니다. 벽 때문에 「이 칸을 지나야만 닿는 칸」 이 생기면, 거기서는 판단이 필요합니다. 그런 이웃을 강제 이웃(forced neighbor) 이라고 부릅니다.

규칙으로 적으면 세 줄입니다.

• 가로세로로 나아갈 때. 진행 방향의 옆이 벽이고 그 벽 너머 대각선 칸이 뚫려 있으면, 지금 칸이 점프 포인트입니다
• 대각선으로 나아갈 때. 한 칸 갈 때마다 가로와 세로로 먼저 훑어 봅니다. 그쪽에서 점프 포인트가 나오면 지금 칸이 점프 포인트입니다
• 목표 칸. 무조건 점프 포인트입니다. 그냥 지나쳐 버리면 안 되니까요

대각선이 가로세로를 먼저 보는 이유는 순서 때문입니다. 대각선으로 쭉 가다가 옆으로 꺾어야 하는 상황이라면, 꺾을 자리를 대각선 위에서 미리 찾아 둬야 합니다. 그래서 대각선 한 칸마다 가로 한 줄과 세로 한 줄을 확인합니다. 비용이 가장 많이 드는 부분도 여기입니다.

같은 격자에서 얼마나 줄어드는가

벽 한 줄만 세워 둔 14×8 격자입니다. 두 방식 모두 여덟 방향으로 움직이고 대각선 비용은 루트 2, 꺼내는 기준도 똑같이 g + h 입니다. 다른 것은 이웃을 보는 방식 하나뿐입니다.

한 칸씩 보는 쪽은 큐에서 26개를 꺼냅니다. 건너뛰는 쪽은 6개입니다. 꺼낸 칸이 곧 힙에서 값을 빼고 다시 정렬하는 횟수이고, 길찾기 시간의 큰 몫을 차지하는 부분입니다.

길의 비용은 둘 다 14.66 입니다. 지나는 칸이 서로 다른데 값이 같은 것이 바로 경로 대칭입니다. 답을 나쁘게 만들지 않으면서 큐 작업만 줄이는 것이 이 방법의 전부입니다.

코드는 재귀 한 덩어리다

바뀌는 곳은 이웃을 만드는 자리 하나입니다. 큐도, f = g + h 도 그대로 씁니다.

// (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));
}

큐에 넣을 때는 건너뛴 거리를 한 번에 더합니다.

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 로 펴도 됩니다. 재귀가 꼭 필요한 쪽은 대각선뿐입니다.

들여다본 칸은 오히려 늘어난다

값을 치르는 곳이 있습니다. 위 격자에서 실제로 읽어 본 칸을 세어 보면 반대가 나옵니다.

빈 칸이 108개인 맵에서 102개를 읽었습니다. 거의 전부입니다. 건너뛴다는 말이 안 본다는 뜻이 아니기 때문입니다. 한 방향으로 끝까지 훑어 보고 나서야 「여기엔 아무것도 없다」 를 알 수 있습니다.

그런데도 빠른 이유는 두 일의 단가가 다르기 때문입니다.

• 큐에서 꺼내는 일은 비쌉니다. 힙을 다시 정렬하고, 노드마다 부모와 비용을 기록하고, 메모리를 잡습니다
• 한 방향으로 훑는 일은 쌉니다. 배열을 차례로 읽는 것이라 캐시에 잘 맞고 분기도 적습니다. 한 줄을 비트로 묶어 한 번에 검사하는 구현도 있습니다

그래서 이득은 맵에 따라 다릅니다. 벽이 거의 없는 열린 맵은 훑는 거리가 길어져서 이득이 줄고, 방과 복도가 많은 맵은 금방 벽에 걸려 멈추기 때문에 이득이 큽니다. 실제 맵으로 재 보지 않으면 모릅니다.

통하지 않는 자리

조건이 꽤 까다롭습니다. 하나라도 어긋나면 답이 틀리거나 아예 적용이 안 됩니다.

대각선으로 벽 모서리를 스칠 수 있게 할 것인지도 미리 정해야 합니다. 흔히 보는 강제 이웃 규칙은 모서리 통과를 허용한다는 전제로 만들어져 있습니다. 많은 게임이 그걸 막는데, 막는 쪽으로 가려면 강제 이웃 판정을 그 규칙에 맞게 다시 써야 합니다. 규칙만 그대로 두고 이동만 막으면 길을 못 찾습니다. 큐에 넣은 점프 포인트로 갈 방법이 없어지기 때문입니다.

비용이 다른 칸이 필요하다면 그냥 A 스타를 씁니다. 격자를 균일하게 유지할 수 있는 맵에서만 꺼내는 카드입니다.

나오는 경로는 점이 몇 개뿐이다

결과로 받는 것은 칸의 목록이 아니라 점프 포인트의 목록입니다. 위 격자에서는 여섯 점입니다. 칸 단위로 움직여야 한다면 점과 점 사이를 직선으로 채우면 되고, 채우는 비용은 한 칸씩 훑는 것과 같습니다.

점이 적다는 것 자체가 쓸모 있을 때도 있습니다. 유닛이 따라갈 목표점이 여섯 개면 프레임마다 확인할 것도 여섯 개고, 직선 구간은 이미 하나로 합쳐져 있습니다.

정리

균일한 격자에서 탐색이 넓어지는 원인은 벽이 아니라 같은 비용의 길이 여러 개라는 사실입니다.

• 점프 포인트 서치는 그 대칭인 길들 중 하나만 만들도록 규칙을 정한 방법입니다. 답은 그대로고 큐 작업만 줄어듭니다
• 멈추는 자리는 벽이 만드는 강제 이웃입니다. 빈 들판에서는 갈라질 이유가 없으니 계속 지나칩니다
• 대각선으로 갈 때는 한 칸마다 가로세로를 먼저 훑습니다. 여기가 가장 비쌉니다
• 읽는 칸은 오히려 늘어납니다. 대신 비싼 큐 작업이 줄어드는 거래입니다. 이득은 맵 모양에 따라 달라집니다
• 칸마다 비용이 다르면 쓸 수 없습니다. 균일한 격자라는 조건이 이 방법의 전부를 떠받치고 있습니다