칸이 아니라 구역 사이를 먼저 잇는다

한 칸씩 이웃을 보는 길찾기는 맵이 커지면 그만큼 더 훑습니다. 훑는 양이 맵 넓이를 따라갑니다.

방 여덟 칸짜리가 격자로 늘어서 있고 방과 방 사이에 문이 하나씩 뚫린 맵을 만들어 한쪽 끝에서 반대쪽 끝까지 재 봤습니다.

맵 한 변이 여덟 배가 되는 동안 훑는 양은 여든 배가 됐습니다. 유닛 하나가 한 번 길을 찾는 값으로는 너무 큽니다.

사람은 방 단위로 길을 찾는다

낯선 건물에서 길을 찾을 때 바닥 타일을 하나씩 세지 않습니다. “이 방에서 저 문으로, 그 복도를 지나 저쪽 문으로” 로 먼저 정하고, 방 안에서 어떻게 걸을지는 그때 정합니다.

계층형 길찾기(HPA, Hierarchical Pathfinding A)** 가 그대로 그 순서입니다. 맵을 일정한 크기의 구역으로 자르고, 구역과 구역을 잇는 문만 모아 작은 그래프를 하나 만들어 둡니다. 길찾기는 그 작은 그래프에서 먼저 하고, 칸 단위 경로는 정해진 구간 안에서만 채웁니다.

여기서 구역은 방이 아닙니다. 맵 위에 그냥 격자로 그은 선입니다. 방 모양을 분석하지 않아도 되고, 어떤 맵에나 똑같이 적용됩니다.

경계에서 뚫린 자리마다 노드를 놓는다

구역을 자르고 나면 경계에서 양쪽이 다 뚫려 있는 구간을 찾습니다. 그 자리가 문입니다. 구간마다 전이 노드(transition node) 를 놓습니다. 경계를 사이에 둔 두 칸이 한 쌍입니다.

구간이 길면 양 끝에 하나씩 둡니다. 가운데 하나만 두면 벽에 바짝 붙어 도는 길이 나올 수 있어서입니다. 짧은 구간은 가운데 하나로 충분합니다.

// 오른쪽 경계에서 양쪽이 다 뚫린 구간을 찾는다
void BuildEntrances(int cx, int cy) {
    int bx = cx * size + size - 1;
    var span = new List<int>();

    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<int> 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. 채우기. 정해진 구간마다 저장해 둔 경로를 읽어 잇습니다

List<Vector2Int> Find(Vector2Int start, Vector2Int goal) {
    InsertTemp(start);                  // 1. 이번 질의에만 쓰는 임시 노드
    InsertTemp(goal);

    var hops = AStarOnGraph(start, goal);   // 2. 노드 단위로 찾는다

    var cells = new List<Vector2Int> { 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개로 정해졌습니다.

꺼내는 것이 칸에서 노드로 바뀌었습니다. 지나갈 구역이 정해지고 나면 그 구역 밖은 쳐다보지도 않습니다. 대신 경로가 2.1% 길어졌습니다. 이것이 이 방법이 치르는 값입니다.

맵이 커질수록 벌어진다

이 정도 맵에서는 차이가 크지 않습니다. 이 방법이 값을 하는 자리는 맵이 커질 때입니다. 앞의 방 격자 맵을 여덟 칸짜리 구역으로 잘라 재 봤습니다. 질의 합은 끼워 넣기와 구간 정하기와 채우기를 더한 것입니다.

두 배씩 커지는 동안 차이가 2.1배에서 7.1배로 벌어집니다.

눈여겨볼 열은 끼워 넣기입니다. 맵이 예순네 배로 커지는 동안 이 값은 24와 32 사이에서 움직이지 않습니다. 시작 칸을 그래프에 잇는 일은 제 구역 안에서만 하는 것이라, 맵이 아무리 커져도 구역 하나 크기에 갇혀 있습니다. 맵 크기에 딸려 가는 부분을 구역 크기에 가둬 두는 것이 이 방법의 핵심입니다.

반대로 꺼냄은 여전히 맵을 따라 커집니다. 추상 그래프 자체가 맵 넓이에 비례해 커지기 때문입니다. 그래서 정말 큰 맵에서는 구역을 다시 묶어 한 층 더 쌓습니다. 구역의 구역을 만드는 것이고, 절차는 똑같습니다.

구역을 얼마나 크게 잡을 것인가

구역을 키우면 추상 그래프가 작아집니다. 대신 끼워 넣기가 커집니다. 128×128 맵에서 구역 크기만 바꿔 봤습니다.

구역을 키울수록 경로는 좋아지고 질의는 나빠집니다. 끼워 넣기가 구역 넓이를 따라가기 때문입니다. 구역 한 변이 여덟 배가 되면 넓이는 예순네 배가 되고, 끼워 넣기 값이 그대로 그 곡선을 그립니다.

전처리도 같이 커집니다. 한 구역 안의 노드가 늘면 노드 쌍의 수가 제곱으로 늘고, 쌍마다 A 스타를 한 번씩 돌려야 합니다.

맵 크기가 아니라 구역 크기가 저울입니다. 여덟에서 열여섯 사이가 흔히 쓰이는 값인 이유가 이 표에 있습니다.

최단이 아니다

나오는 경로는 최단이 아닙니다. 위 표에서 3~6% 길었습니다.

이유는 문을 몇 개로 줄여 놨기 때문입니다. 실제 최단 경로가 지나가야 할 자리가 전이 노드 사이에 있으면, 그 자리를 못 씁니다. 구간이 길 때 양 끝에 노드를 두 개 두는 것도 이 손해를 줄이려는 것입니다.

줄이는 방법이 몇 가지 있습니다.

• 노드를 더 촘촘히. 구간마다 두 개가 아니라 몇 칸마다 하나씩 둡니다. 그래프가 커지는 만큼 질의가 느려집니다
• 이어 붙인 경로를 직선으로 펴기. 구간을 이으면 문마다 꺾인 자국이 남습니다. 막힌 것이 없는 구간을 직선으로 바꾸면 상당 부분이 회수됩니다
• 가까우면 그냥 한 칸씩. 시작과 목표가 같은 구역이거나 이웃 구역이면 구역 안에서 A 스타를 한 번 돌리는 편이 빠르고 정확합니다

마지막 줄이 실무에서 제일 값을 합니다. 가까운 길찾기에는 아예 이 구조를 안 타는 것이 맞습니다.

맵이 바뀌면 그 구역만 다시 짓는다

전처리를 해 두는 방식은 보통 맵이 바뀌면 통째로 무너집니다. 이 구조는 그렇지 않습니다.

칸 하나가 막히거나 뚫리면 그 칸이 든 구역 하나만 다시 지으면 됩니다. 그 구역의 경계를 다시 훑어 전이 노드를 다시 놓고, 그 구역 안의 노드 쌍만 다시 재면 끝입니다. 다른 구역의 값은 하나도 건드리지 않습니다. 구역 안의 거리는 구역 안에서만 정해지기 때문입니다.

건물이 세워지고 부서지는 맵, 문이 열리고 닫히는 던전에서 이 성질이 값을 합니다. 128×128 맵의 전처리가 8,589칸이었지만, 구역 하나를 다시 짓는 것은 그 중 백분의 일도 안 됩니다.

조심할 자리

• 구역 경계가 맵 구조와 어긋나도 됩니다. 오히려 그게 보통입니다. 다만 구역이 방보다 훨씬 작으면 문이 지나치게 많아져서 추상 그래프가 안 작아집니다
• 한 구역이 벽으로 두 조각 나 있으면 그 조각들 사이에는 간선이 안 생깁니다. 노드 쌍마다 실제로 재 보기 때문에 저절로 처리되지만, 구역 안이 이어져 있다고 가정한 코드를 짜면 여기서 틀립니다
• 끼워 넣기는 매 질의마다 냅니다. 같은 목표로 여러 유닛이 갈 때는 목표 쪽 끼워 넣기를 한 번만 하고 돌려 쓰면 그만큼 아낍니다
• 칸마다 비용이 다른 맵에서도 됩니다. 구역 안 거리를 실제로 재서 저장하는 구조라, 늪이든 도로든 그 값이 그대로 들어갑니다

정리

계층형 길찾기는 길 하나를 두 단계로 나눠 찾는 방법입니다.

• 맵을 구역으로 자르고, 경계에서 뚫린 구간마다 전이 노드를 놓고, 구역 안 거리를 미리 재 둡니다
• 질의는 끼워 넣기, 구간 정하기, 채우기의 세 단계입니다. 임시 노드를 지우는 것을 잊으면 그래프가 자랍니다
• 끼워 넣기 값이 구역 크기에 갇혀 있다는 것이 전부입니다. 맵이 커져도 그 부분은 안 커집니다
• 경로는 최단이 아닙니다. 3~6% 정도이고, 노드를 촘촘히 두거나 이어 붙인 경로를 펴서 줄입니다
• 맵이 바뀌면 그 구역 하나만 다시 지으면 됩니다. 동적인 맵에서 이 성질이 값을 합니다