지도 한 장을 모두가 읽는다

유닛 200마리가 같은 깃발로 달려갑니다. 유닛마다 길찾기를 한 번씩 돌리면 200번입니다.

그런데 그 200번은 거의 같은 계산입니다. 출발점만 다르고 목표가 같으니, 목표 근처의 지형은 200번 다시 계산됩니다. 128×128 맵에서 재 보면 한 마리당 평균 983칸을 확정하고, 200마리면 196,659칸입니다.

목표에서 거꾸로 센다

방향을 뒤집으면 이 반복이 통째로 사라집니다.

출발점에서 목표로 재는 대신 목표에서 시작해 맵 전체로 번져 나가면, 한 번에 모든 칸의 “목표까지 얼마” 가 나옵니다. 맵의 걸을 수 있는 칸이 13,249개인데, 그 한 번이 13,249칸입니다. 한 마리당 983칸씩 200번 하는 것보다 훨씬 쌉니다.

유닛은 이제 길을 찾지 않습니다. 발밑 칸의 값과 이웃 칸의 값을 견줘 더 낮은 쪽으로 가면 됩니다. 골짜기로 굴러떨어지는 것과 같습니다. 이 지도를 흐름 필드(Flow Field) 라고 부릅니다.

세 겹으로 나눠 둔다

흐름 필드는 보통 세 겹으로 만들어 둡니다. 겹마다 바뀌는 시점이 다르기 때문입니다.

비용 필드는 맵이 안 바뀌면 그대로 두고, 목표만 바뀌면 뒤의 두 겹만 다시 만듭니다. 마지막 겹이 방향 하나뿐이라는 것이 중요합니다. 유닛이 실제로 읽는 것은 이것뿐이고, 칸당 1바이트면 됩니다.

만들어지는 것을 보면 이렇다

숫자를 보면 물결이 목표에서 바깥으로 번져 나갑니다. 가로세로는 10, 대각선은 14 로 셉니다. 루트 2를 1.4로 친 것이고, 정수라 칸에 적어 두기 좋고 나눗셈이 없습니다.

물결이 끝나면 칸마다 화살표가 하나씩 답니다. 그 화살표가 지도의 전부입니다. 유닛 다섯이 각자 다른 곳에서 출발하지만 아무도 길을 찾지 않습니다. 발밑 화살표만 보고 한 칸씩 갑니다.

// 1. 목표에서 거꾸로. 칸마다 목표까지의 비용을 채운다
void BuildIntegration(Vector2Int goal) {
    Array.Fill(cost, int.MaxValue);
    cost[Index(goal)] = 0;

    var open = new MinHeap();
    open.Push(goal, 0);

    while (open.Count > 0) {
        var cur = open.Pop();

        foreach (var d in Dirs8) {
            var next = cur + d;
            if (!Walkable(next)) continue;

            int n = cost[Index(cur)] + StepCost(d) * Terrain(next);
            if (n >= cost[Index(next)]) continue;

            cost[Index(next)] = n;
            open.Push(next, n);
        }
    }
}

// 2. 칸마다 가장 싼 이웃 하나를 가리키게 한다
void BuildFlow() {
    for (int i = 0; i < cellCount; i++) {
        int best = cost[i];
        byte dir = NONE;

        for (byte d = 0; d < 8; d++) {
            int n = NeighborIndex(i, d);
            if (n < 0 || cost[n] >= best) continue;
            best = cost[n];
            dir = d;
        }

        flow[i] = dir;          // 칸 하나에 1바이트
    }
}

유닛 쪽 코드는 이렇게 끝납니다.

void Update() {
    byte d = flow[Index(CellOf(transform.position))];
    if (d == NONE) return;

    transform.position += (Vector3)Dirs8[d] * speed * Time.deltaTime;
}

길찾기 호출이 없습니다. 배열 조회 하나입니다. 유닛이 몇 마리든 한 마리당 비용이 같습니다.

몇 마리부터 값을 하나

지도 한 장을 만드는 값은 유닛이 하나든 천이든 똑같습니다. 그래서 유닛이 적으면 손해입니다. 128×128 맵에서 유닛 수만 바꿔 재 봤습니다.

열다섯 마리 근처가 손익분기입니다. 64×64 맵에서 재도 같은 자리가 나왔습니다. 지도 한 장 값을 한 마리당 길찾기 값으로 나눈 것이라, 맵이 커지면 둘 다 같이 커져서 분기점은 잘 안 움직입니다.

유닛 서넛이 각자 다른 곳으로 가는 게임에는 쓸 이유가 없습니다. 떼로 몰려가는 장면이 있는 게임의 도구입니다.

방향 하나로 줄여 두면 생기는 것

마지막 겹이 칸당 1바이트라는 데서 따라오는 것들이 있습니다.

• 메모리가 작습니다. 128×128 이면 흐름 필드가 16KB 입니다. 유닛마다 경로 배열을 들고 있는 것보다 훨씬 쌉니다
• 유닛을 더 넣어도 공짜입니다. 새로 들어온 유닛이 자기 발밑을 읽으면 그만입니다. 길찾기 요청 큐가 필요 없습니다
• 경로를 저장할 필요가 없습니다. 유닛이 밀려나거나 넉백을 당해도, 그 자리의 화살표를 읽으면 됩니다. 경로를 들고 있는 방식은 이럴 때 다시 찾아야 합니다
• 비용 필드에 무엇을 넣느냐가 부대 성격이 됩니다. 적 포탑 주변 칸을 비싸게 매기면 부대가 알아서 돌아갑니다. 유닛 코드는 하나도 안 바뀝니다

목표가 바뀌면 통째로 다시 만든다

값을 치르는 곳입니다. 통합 필드는 목표 하나에 한 장입니다.

• 플레이어가 깃발을 옮기면 13,249칸을 다시 채워야 합니다
• 목표가 여럿이면 지도도 여러 장입니다. 부대가 셋이고 목적지가 다 다르면 세 장을 따로 만듭니다
• 쫓는 대상이 움직이면 매 프레임 다시 만들어야 합니다. 이건 감당이 안 됩니다

그래서 실제로는 이렇게 씁니다.

• 목표를 칸 단위로 반올림합니다. 쫓는 대상이 같은 칸 안에서 움직이는 동안은 다시 안 만듭니다
• 몇 프레임에 나눠 채웁니다. 한 프레임에 다 하지 말고 물결을 몇 번에 나눠 밀어냅니다. 그동안 유닛은 낡은 지도를 봅니다. 한두 프레임 낡은 방향은 눈에 안 띕니다
• 지도를 낮은 해상도로 만듭니다. 칸 하나를 두 배 크게 잡으면 칸 수가 사분의 일입니다. 방향이 거칠어지는 만큼 유닛 쪽에서 보간합니다

유닛끼리는 여전히 겹친다

흐름 필드는 지형만 봅니다. 유닛이 어디 있는지는 모릅니다. 그래서 좁은 문 앞에서 같은 화살표를 읽은 유닛들이 그대로 겹쳐 서고, 서로를 밀고 들어갑니다.

여기는 길찾기의 몫이 아닙니다. 흐름 필드가 준 방향에 유닛끼리 밀어내는 힘을 더해서 실제 이동 방향을 만듭니다.

Vector2 desired = Dirs8[flow[Index(cell)]];
Vector2 separation = SeparationFrom(neighborsWithinRadius);

Vector2 move = (desired * flowWeight + separation * separationWeight).normalized;

이 두 힘의 비율이 부대가 뭉쳐 보이느냐 흩어져 보이느냐를 정합니다. 둘을 한 곳에서 섞는다는 것만 알면 됩니다. 흐름 필드를 고칠 일이 아닙니다.

조심할 자리

• 대각선으로 벽 모서리를 스치는 것을 막을 거면 흐름 필드를 만들 때도 막아야 합니다. 통합 필드만 막고 방향은 그대로 두면 화살표가 벽을 뚫습니다
• 10과 14는 근사값입니다. 긴 대각선 경로에서 실제 거리와 조금씩 어긋납니다. 최단 거리 자체가 필요한 계산에 이 값을 그대로 쓰면 안 됩니다
• 막힌 칸은 방향이 없습니다. 벽에 둘러싸인 구역에서 출발한 유닛은 화살표가 없어 제자리에 섭니다. 그 상태를 유닛 쪽에서 따로 처리해야 합니다
• 통합 필드를 int 로 두면 128×128 에 64KB 입니다. 맵이 커지면 ushort 로 줄이는 것이 흔합니다. 비용 상한만 확인하면 됩니다

정리

흐름 필드는 목표에서 거꾸로 한 번 채워 두고 모두가 읽는 방법입니다.

• 유닛마다 길을 찾는 대신 지도를 한 장 만듭니다. 유닛 코드에는 길찾기 호출이 없고 배열 조회만 남습니다
• 세 겹으로 나눠 둡니다. 지형이 바뀌면 첫 겹, 목표가 바뀌면 뒤의 두 겹입니다
• 유닛 열다섯 마리 근처가 손익분기입니다. 그보다 적으면 각자 찾는 편이 쌉니다
• 목표 하나에 지도 한 장입니다. 목표가 자주 바뀌면 이 방법의 전제가 무너집니다
• 유닛끼리 겹치는 것은 흐름 필드가 풀어 주지 않습니다. 밀어내는 힘을 따로 얹습니다