--- title: "지도 한 장을 모두가 읽는다" description: "유닛 수백 마리가 같은 곳으로 갈 때 각자 길을 찾는 대신, 목표에서 거꾸로 채운 지도를 한 장 만들어 모두가 읽는 방법입니다. 흐름 필드(Flow Field)의 세 겹 구조와 손익분기점, 목표가 바뀔 때 치르는 값." author: "유니얼" pubDate: 2026-09-17 updatedDate: 2026-09-18 category: "programming/algorithm/graph" tags: ["최적화", "격자"] canonical: https://blog.unialgames.com/posts/algo-flow-field/ --- 유닛 200마리가 같은 깃발로 달려갑니다. 유닛마다 길찾기를 한 번씩 돌리면 200번입니다. 그런데 그 200번은 **거의 같은 계산**입니다. 출발점만 다르고 목표가 같으니, 목표 근처의 지형은 200번 다시 계산됩니다. 128×128 맵에서 재 보면 한 마리당 평균 983칸을 확정하고, 200마리면 196,659칸입니다. ## 목표에서 거꾸로 센다 방향을 뒤집으면 이 반복이 통째로 사라집니다. 출발점에서 목표로 재는 대신 **목표에서 시작해 맵 전체로 번져 나가면**, 한 번에 모든 칸의 "목표까지 얼마" 가 나옵니다. 맵의 걸을 수 있는 칸이 13,249개인데, 그 한 번이 13,249칸입니다. 한 마리당 983칸씩 200번 하는 것보다 훨씬 쌉니다. 유닛은 이제 길을 찾지 않습니다. **발밑 칸의 값과 이웃 칸의 값을 견줘 더 낮은 쪽으로 가면** 됩니다. 골짜기로 굴러떨어지는 것과 같습니다. 이 지도를 **흐름 필드(Flow Field)** 라고 부릅니다. ## 세 겹으로 나눠 둔다 흐름 필드는 보통 세 겹으로 만들어 둡니다. 겹마다 바뀌는 시점이 다르기 때문입니다. | 겹 | 무엇이 들었나 | 언제 바뀌나 | | --- | --- | --- | | **비용 필드(cost field)** | 칸 하나를 밟는 값. 벽은 못 감, 늪은 비쌈 | 지형이 바뀔 때만 | | **통합 필드(integration field)** | 그 칸에서 목표까지의 누적 비용 | 목표가 바뀔 때마다 | | **흐름 필드(flow field)** | 가장 싼 이웃을 가리키는 방향 하나 | 통합 필드를 다시 만들 때 | 비용 필드는 맵이 안 바뀌면 그대로 두고, 목표만 바뀌면 뒤의 두 겹만 다시 만듭니다. **마지막 겹이 방향 하나뿐**이라는 것이 중요합니다. 유닛이 실제로 읽는 것은 이것뿐이고, 칸당 1바이트면 됩니다. ## 만들어지는 것을 보면 이렇다 숫자를 보면 물결이 목표에서 바깥으로 번져 나갑니다. 가로세로는 10, 대각선은 14 로 셉니다. 루트 2를 1.4로 친 것이고, 정수라 칸에 적어 두기 좋고 나눗셈이 없습니다. 물결이 끝나면 칸마다 화살표가 하나씩 답니다. **그 화살표가 지도의 전부입니다.** 유닛 다섯이 각자 다른 곳에서 출발하지만 아무도 길을 찾지 않습니다. 발밑 화살표만 보고 한 칸씩 갑니다. ```csharp // 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바이트 } } ``` 유닛 쪽 코드는 이렇게 끝납니다. ```csharp void Update() { byte d = flow[Index(CellOf(transform.position))]; if (d == NONE) return; transform.position += (Vector3)Dirs8[d] * speed * Time.deltaTime; } ``` **길찾기 호출이 없습니다.** 배열 조회 하나입니다. 유닛이 몇 마리든 한 마리당 비용이 같습니다. ## 몇 마리부터 값을 하나 지도 한 장을 만드는 값은 유닛이 하나든 천이든 똑같습니다. 그래서 유닛이 적으면 손해입니다. 128×128 맵에서 유닛 수만 바꿔 재 봤습니다. | 유닛 | 각자 길찾기 | 흐름 필드 (지도 한 장 + 걷기) | | | --- | --- | --- | --- | | 1 | 983 | 13,339 | 열세 배 손해 | | 5 | 4,916 | 13,698 | 아직 손해 | | 15 | 14,745 | 14,599 | 여기서 뒤집힌다 | | 50 | 49,165 | 17,738 | 2.8배 | | 200 | 196,659 | 31,204 | 6.3배 | | 1,000 | 983,295 | 103,024 | 9.5배 | **열다섯 마리 근처가 손익분기**입니다. 64×64 맵에서 재도 같은 자리가 나왔습니다. 지도 한 장 값을 한 마리당 길찾기 값으로 나눈 것이라, 맵이 커지면 둘 다 같이 커져서 분기점은 잘 안 움직입니다. **유닛 서넛이 각자 다른 곳으로 가는 게임에는 쓸 이유가 없습니다.** 떼로 몰려가는 장면이 있는 게임의 도구입니다. ## 방향 하나로 줄여 두면 생기는 것 마지막 겹이 칸당 1바이트라는 데서 따라오는 것들이 있습니다. - **메모리가 작습니다.** 128×128 이면 흐름 필드가 16KB 입니다. 유닛마다 경로 배열을 들고 있는 것보다 훨씬 쌉니다 - **유닛을 더 넣어도 공짜입니다.** 새로 들어온 유닛이 자기 발밑을 읽으면 그만입니다. 길찾기 요청 큐가 필요 없습니다 - **경로를 저장할 필요가 없습니다.** 유닛이 밀려나거나 넉백을 당해도, 그 자리의 화살표를 읽으면 됩니다. 경로를 들고 있는 방식은 이럴 때 다시 찾아야 합니다 - **비용 필드에 무엇을 넣느냐가 부대 성격이 됩니다.** 적 포탑 주변 칸을 비싸게 매기면 부대가 알아서 돌아갑니다. 유닛 코드는 하나도 안 바뀝니다 ## 목표가 바뀌면 통째로 다시 만든다 값을 치르는 곳입니다. **통합 필드는 목표 하나에 한 장입니다.** - 플레이어가 깃발을 옮기면 13,249칸을 다시 채워야 합니다 - 목표가 여럿이면 지도도 여러 장입니다. 부대가 셋이고 목적지가 다 다르면 세 장을 따로 만듭니다 - 쫓는 대상이 움직이면 매 프레임 다시 만들어야 합니다. 이건 감당이 안 됩니다 그래서 실제로는 이렇게 씁니다. - **목표를 칸 단위로 반올림합니다.** 쫓는 대상이 같은 칸 안에서 움직이는 동안은 다시 안 만듭니다 - **몇 프레임에 나눠 채웁니다.** 한 프레임에 다 하지 말고 물결을 몇 번에 나눠 밀어냅니다. 그동안 유닛은 낡은 지도를 봅니다. 한두 프레임 낡은 방향은 눈에 안 띕니다 - **지도를 낮은 해상도로 만듭니다.** 칸 하나를 두 배 크게 잡으면 칸 수가 사분의 일입니다. 방향이 거칠어지는 만큼 유닛 쪽에서 보간합니다 ## 유닛끼리는 여전히 겹친다 흐름 필드는 **지형만** 봅니다. 유닛이 어디 있는지는 모릅니다. 그래서 좁은 문 앞에서 같은 화살표를 읽은 유닛들이 그대로 겹쳐 서고, 서로를 밀고 들어갑니다. 여기는 길찾기의 몫이 아닙니다. 흐름 필드가 준 방향에 **유닛끼리 밀어내는 힘**을 더해서 실제 이동 방향을 만듭니다. ```csharp Vector2 desired = Dirs8[flow[Index(cell)]]; Vector2 separation = SeparationFrom(neighborsWithinRadius); Vector2 move = (desired * flowWeight + separation * separationWeight).normalized; ``` 이 두 힘의 비율이 부대가 뭉쳐 보이느냐 흩어져 보이느냐를 정합니다. **둘을 한 곳에서 섞는다는 것**만 알면 됩니다. 흐름 필드를 고칠 일이 아닙니다. ## 조심할 자리 - **대각선으로 벽 모서리를 스치는 것**을 막을 거면 흐름 필드를 만들 때도 막아야 합니다. 통합 필드만 막고 방향은 그대로 두면 화살표가 벽을 뚫습니다 - **10과 14는 근사값입니다.** 긴 대각선 경로에서 실제 거리와 조금씩 어긋납니다. 최단 거리 자체가 필요한 계산에 이 값을 그대로 쓰면 안 됩니다 - **막힌 칸은 방향이 없습니다.** 벽에 둘러싸인 구역에서 출발한 유닛은 화살표가 없어 제자리에 섭니다. 그 상태를 유닛 쪽에서 따로 처리해야 합니다 - **통합 필드를 `int` 로 두면 128×128 에 64KB 입니다.** 맵이 커지면 `ushort` 로 줄이는 것이 흔합니다. 비용 상한만 확인하면 됩니다 ## 정리 흐름 필드는 **목표에서 거꾸로 한 번 채워 두고 모두가 읽는** 방법입니다. - 유닛마다 길을 찾는 대신 **지도를 한 장** 만듭니다. 유닛 코드에는 길찾기 호출이 없고 배열 조회만 남습니다 - 세 겹으로 나눠 둡니다. 지형이 바뀌면 첫 겹, 목표가 바뀌면 뒤의 두 겹입니다 - **유닛 열다섯 마리 근처가 손익분기**입니다. 그보다 적으면 각자 찾는 편이 쌉니다 - **목표 하나에 지도 한 장**입니다. 목표가 자주 바뀌면 이 방법의 전제가 무너집니다 - 유닛끼리 겹치는 것은 흐름 필드가 풀어 주지 않습니다. 밀어내는 힘을 따로 얹습니다