■ Flow Field
Flow Field는 길 찾기 알고리즘의 한 종류로, 객체마다 경로를 따로 구하는 A*와 달리 맵 전체에 방향장을 한 번 깔아 다수가 공유하는 방식이다.
Flow Field는 맵의 모든 칸에 “여기 서 있으면 어디로 가야 하는지” 화살표를 하나씩 미리 꽂아둔 지도이다.
출발지를 신경 쓰지 않고, 목적지에서 거꾸로 맵 전체에 화살표를 한 번 깐다. 이 한 번의 계산 비용을 모든 객체가 공유하므로 “길 찾기 비용이 객체 수와 무관해진다.”
- 플레이어 위치로부터 탐색을 시작해서 플레이어로 가는 방향을 그 타일에 미리 기록해 둔다.
1. 거리 맵 (Integration Field)
플레이어 칸을 0으로 두고, 너비 우선 탐색(BFS) 혹은 각 셀마다 가중치(이동 비용)가 있다면 다익스트라 알고리즘으로 목적지까지 몇 걸음인지를 모든 칸에 채운다.
- 벽은 뚫지 못하므로 물결이 벽을 돌아가고, 그 결과 거리값도 우회 경로를 따라 박힌다.
2. 흐름장(Flow Field)
각 칸에서 이웃 중 거리값이 가장 작은 쪽을 가리키는 화살표를 저장한다.
Vector3 dir = flowField[currentCell].direction; // 내 칸 화살표 읽기
transform.position += dir * speed * Time.deltaTime;
위처럼 적의 이동 로직은 흐름장을 따라 매번 A* 같은 길 찾기 알고리즘을 호출하지 않고, 자기가 있는 칸의 화살표를 읽어 그 방향으로 움직이기만 하면 된다.
🤔 A* 알고리즘과 비교
| A*(개체별 길찾기) | Flow Field(공유) | |
| N마리당 비용 | N번 길찾기 | 1번 굽고 N번 조회 |
| 목표 이동 시 | N번 재계산 | 1번 재계산 |
| 적이 많아질수록 | 선형적으로 폭증 | 굽는 비용은 고정, 조회만 증가 |
다수의 적이 한 명(혹은 소수)의 공통 목표로 향할 때 Flow Field 알고리즘은 효과적이지만, 객체마다 목적지가 제각각이면 무너진다 (흐름장 하나는 목적지 하나에만 유효하므로).
또한 Flow Field는 전역 방향만 제시할 뿐, 객체끼리 겹치는 것이나 자잘한 동적 장애물 회피까지는 처리하지 못한다. 따라서 이런 지역적 회피는 조향(Steering)을 추가로 얹어 구현한다.
- 정리하면 Flow Field는 "어디로 갈지(전역 경로)", 조향은 "어떻게 갈지(지역 회피)"를 맡는다. 둘은 경쟁이 아니라 역할 분담이다.
■ FlowField 구현
1. 노드 구성
FlowField는 2차원 배열로 구성되며, 각 요소에는 "어디로 향하는지"와 "목적지까지의 거리"를 저장한다. 이 두 값을 Node 구조체 하나로 묶어서 그리드 크기만큼 배열로 들고 있는다.
using System.Collections.Generic;
using UnityEngine;
public class FlowField : MonoBehaviour
{
[Header("Components")]
[SerializeField] private Transform playerTf;
private CityLayout _layout;
private int _width = 0;
private int _height = 0;
private Node[,] _flowField;
private Vector2Int _curPlayerCell;
private Vector3 _originCellPos;
private void Start()
{
if (cityGenerator.CityLayout == null)
{
cityGenerator.GenerateCity();
}
_layout = cityGenerator.CityLayout;
_width = _layout.Width;
_height = _layout.Height;
_flowField = new Node[_width, _height];
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
_flowField[x, y] = new Node(int.MaxValue, Vector2Int.zero);
}
}
_originCellPos = _layout.ConvertCellPosToWorld(0,0);
}
}
public struct Node
{
public int Cost;
public Vector2Int Direction;
public Node(int cost, Vector2Int direction)
{
Cost = cost;
Direction = direction;
}
}
여기서 layout은 맵 정보를 저장한 클래스이다. 그리드 형식의 맵이며, 앞서 설명했던 절차적 도심 생성(https://hate-errorlog.tistory.com/61)에 쓰인 맵을 활용 한다.
Start에서 배열을 채울 때 모든 노드를 Cost = int.MaxValue, Direction = Vector2Int.zero로 초기화한다. 비용을 최댓값으로 깔아 두는 건 이후 갱신 단계에서 "아직 도달하지 않은 칸"을 구분하기 위한 초기값이고, 방향이 zero라는 건 "아직 어디로도 향하지 않는다"는 뜻이다.
- 이렇게 초기화된 FlowField를 특정 시점(플레이어가 셀을 옮겼을 때)마다 갱신하여 목표(플레이어)로 향하는 흐름을 만든다.
2. FlowField 갱신
private void Update()
{
var playerIndex = WorldToCell(playerTf.position);
if (playerIndex != _curPlayerCell)
{
_curPlayerCell = playerIndex;
UpdateFlowField();
}
}
private Vector2Int WorldToCell(Vector3 worldPos)
{
var col = Mathf.RoundToInt((worldPos.x - _originCellPos.x) / _layout.CellSize);
var row = Mathf.RoundToInt((worldPos.z - _originCellPos.z) / _layout.CellSize);
return new Vector2Int(col, row);
}
매 프레임 WorldToCell로 플레이어가 현재 속한 셀을 구한다. 이 값이 직전에 저장해 둔 _curPlayerCell과 다를 때만 UpdateFlowField를 호출한다.
플레이어가 같은 셀 안에서 움직이는 동안에는 흐름이 바뀔 이유가 없으므로 재계산을 건너뛰어 갱신 빈도를 줄이는 것이 핵심이다.
각 셀의 이동 비용이 모두 동일하기 때문에 다익스트라가 아닌 BFS로 탐색한다. 비용이 균일한 그리드에서는 BFS가 방문하는 순서 자체가 곧 최단 거리 순서라, 우선순위 큐로 비용을 저울질할 필요가 없다.
여기서 중요한 점은 비용 계산과 방향 계산을 동시에 진행하지 않고, 비용 계산이 모두 끝난 후에 방향 계산을 진행한다는 것이다. 한 칸의 방향을 정하려면 주변 칸들의 최종 비용이 이미 확정되어 있어야 하기 때문이다.
private void UpdateFlowField()
{
ResetNode();
var queue = new Queue<Vector2Int>();
var passable = new List<Vector2Int>();
var visited = new bool[_width * _height];
queue.Enqueue(_curPlayerCell);
visited[_curPlayerCell.x * _height + _curPlayerCell.y] = true;
_flowField[_curPlayerCell.x, _curPlayerCell.y] = new Node(0, Vector2Int.zero);
}
private bool IsPassable(int x, int y)
{
return _layout.Cells[x, y] is ECellType.CatWalk or ECellType.Road;
}
private void ResetNode()
{
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
if (!IsPassable(x,y)) continue;
_flowField[x, y].Cost = int.MaxValue;
_flowField[x, y].Direction = Vector2Int.zero;
}
}
}
[탐색 준비]
탐색에 필요한 큐, 방문 여부를 저장할 1차원 배열, 그리고 나중에 방향을 기록할 통행 가능한 셀들을 모아둘 passable 리스트를 만든다. 그다음 플레이어가 속한 셀을 큐에 넣고 방문 처리한 뒤, 그 셀의 비용을 0으로 설정한다. 플레이어 셀이 비용 0의 출발점이 되고, 여기서부터 비용이 한 칸씩 퍼져나간다.
통행 가능 여부는 IsPassable로 판단하며, 도로(Road)와 인도(CatWalk)만 지나갈 수 있는 칸으로 취급한다.
▶ 비용 갱신
private readonly Vector2Int[] _searchDir = new[]
{
new Vector2Int(0, 1), new Vector2Int(0, -1), // 상, 하
new Vector2Int(-1, 0), new Vector2Int(1, 0), // 좌, 우
new Vector2Int(-1, 1), new Vector2Int(1, 1), // 좌상, 우상
new Vector2Int(-1, -1), new Vector2Int(1, -1) // 좌하, 우하
};
private void UpdateFlowField()
{
//탐색 준비 생략...
while (queue.Count > 0)
{
var node = queue.Dequeue();
var curCost = _flowField[node.x, node.y].Cost;
// 4방향 탐색 먼저
for (var i = 0; i < 4; ++i)
{
var sx = node.x + _searchDir[i].x;
var sy = node.y + _searchDir[i].y;
if (sx < 0 || sx >= _width || sy < 0 || sy >= _height) continue;
if (visited[sx * _height + sy] || IsPassable(sx, sy) == false) continue;
_flowField[sx, sy].Cost = curCost + 1;
queue.Enqueue(new Vector2Int(sx, sy));
passable.Add(new Vector2Int(sx, sy));
visited[sx * _height + sy] = true;
}
}
기본적인 BFS 그대로라 크게 어려운 부분은 없다. 큐에서 셀을 하나 꺼내 _searchDir의 앞 4개 방향(상하좌우)을 탐색한다. 범위를 벗어나거나, 이미 방문했거나, 통행 불가능한 셀이면 건너뛰고, 아니라면 비용을 갱신한 뒤 큐와 passable에 넣고 방문 처리한다.
비용을 갱신하는 방식은 단순하다. 꺼낸 셀에서 한 칸 떨어진 이웃이므로, 그 이웃의 비용은 꺼낸 셀의 비용(curCost)에 1을 더한 값이 된다. 플레이어 셀에서 시작해 바깥으로 퍼져나갈수록 비용이 1씩 커지는 구조라, 결국 각 셀의 Cost는 플레이어로부터 몇 칸 떨어져 있는지를 나타내게 된다.
visited 배열은 2차원 좌표를 sx * _height + sy 형태로 1차원 인덱스로 바꿔서 접근한다.
- [x, y] 2차원 배열 대신 1차원 bool 배열을 쓰는 방식인데, 방문 여부처럼 매 갱신마다 새로 만드는 단순 플래그에는 이쪽이 가볍다.
▶ 방향 갱신
private void UpdateFlowField()
{
// 탐색 준비 생략..
// 비용 갱신 생략..
foreach (var pNode in passable)
{
var min = _flowField[pNode.x, pNode.y].Cost;
foreach (var s in _searchDir)
{
var dx = pNode.x + s.x;
var dy = pNode.y + s.y;
if(dx < 0 || dx >= _width || dy < 0 || dy >= _height)
continue;
if (s.x != 0 && s.y != 0)
{
if(!IsPassable(dx, pNode.y) || !IsPassable(pNode.x, dy))
continue;
}
if (min > _flowField[dx, dy].Cost)
{
min = _flowField[dx, dy].Cost;
_flowField[pNode.x, pNode.y].Direction = s;
}
}
}
}
비용 전파가 끝나면 passable에 모아둔 통행 가능한 셀만 순회하며 방향을 정한다. 핵심은 각 셀에서 주변 8방향을 살펴 비용이 가장 낮은 이웃을 가리키게 하는 것이다.
시작할 때 min을 자기 자신의 비용으로 두고, 8방향 이웃 중 이보다 비용이 낮은 칸이 나올 때마다 그 방향으로 Direction을 갱신한다. 각 셀의 비용은 플레이어로부터의 거리이므로, 자기보다 비용이 낮은 이웃은 곧 플레이어에 한 칸 더 가까운 칸이다. 모든 셀이 이렇게 "거리가 줄어드는 쪽"을 가리키게 되면, 그 방향을 따라 계속 이동했을 때 플레이어에게 최단 거리로 도달하는 흐름이 완성된다.
여기서 비용 전파는 4방향으로만 했지만 방향 할당은 8방향을 본다. 비용은 상하좌우로만 퍼져 직교 거리로 계산되고, 실제로 에이전트가 향할 방향은 대각선까지 허용해 더 자연스러운 이동을 만드는 것이다.
if (s.x != 0 && s.y != 0)
{
if(!IsPassable(dx, pNode.y) || !IsPassable(pNode.x, dy))
continue;
}
대각선 방향을 고를 때는 유의할 점이 하나 있다. 대각선으로 이동하려면 그 사이에 낀 가로·세로 두 칸이 모두 통행 가능해야 한다. 예를 들어 우상단으로 가려면 오른쪽 칸과 위쪽 칸이 둘 다 뚫려 있어야 하며, 한쪽이라도 막혀 있으면 건물 모서리를 대각선으로 뚫고 지나가는 부자연스러운 이동이 된다.
_searchDir의 한 요소에서 x와 y가 모두 0이 아닌 경우가 대각선이므로, 이 조건일 때만 양옆 칸을 검사한다. IsPassable(dx, pNode.y)는 가로 이웃, IsPassable(pNode.x, dy)는 세로 이웃을 확인하는 것이고, 둘 중 하나라도 막혀 있으면 이 대각선 방향은 후보에서 제외한다.
대각선 이웃의 비용을 함께 비교한다는 점
비용 전파를 8방향으로 확장하면 대각선을 1로 세면서 거리가 왜곡되고, 이를 바로잡으려면 대각선 비용을 √2로 주어야 하는데 그 순간 비용이 균일하지 않아 BFS 대신 다익스트라가 필요해진다.
4방향 비용 전파에 8방향 방향 할당을 얹은 이 구조는, BFS의 단순함과 속도를 유지하면서 자연스러운 대각선 이동만 취하기 위한 선택이다. 수백 단위 이상의 대규모 군중을 매번 갱신해야 하는 상황에서, 다익스트라 대비 체감 차이는 작으면서 비용은 훨씬 낮다.
■ 기즈모 디버깅
private void OnDrawGizmos()
{
if (drawGizmos == false || _flowField == null) return;
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
if (_flowField[x, y].Direction == Vector2Int.zero) continue;
var center = _layout.ConvertCellPosToWorld(x, y);
var dir = _flowField[x, y].Direction;
var worldDir = new Vector3(dir.x, 0f, dir.y).normalized;
var tip = center + worldDir * (_layout.CellSize * 0.4f);
Gizmos.color = Color.cyan;
Gizmos.DrawLine(center, tip);
var back1 = Quaternion.Euler(0, 150f, 0) * worldDir;
var back2 = Quaternion.Euler(0, -150f, 0) * worldDir;
Gizmos.DrawLine(tip, tip + back1 * (_layout.CellSize * 0.15f));
Gizmos.DrawLine(tip, tip + back2 * (_layout.CellSize * 0.15f));
}
}
}
완성된 FlowField를 순회하며 각 셀에 저장된 Direction을 따라 화살표를 그린다. 방향이 Vector2Int.zero인 셀은 아직 방향이 정해지지 않았거나 흐름에서 제외된 칸이므로 건너뛴다.
화살표는 셀 중심(center)에서 방향 쪽으로 뻗은 몸통 하나와, 화살촉을 이루는 짧은 선 두 개로 그린다. 먼저 그리드 좌표의 방향 dir을 월드 공간의 worldDir로 바꾸고, 중심에서 이 방향으로 셀 크기의 0.4배만큼 나아간 지점을 화살표 끝(tip)으로 삼아 몸통을 그린다. 화살촉은 이 tip에서 그리는데, worldDir을 Y축 기준으로 ±150도 회전시키면 진행 방향과 거의 반대로 벌어진 두 방향이 나온다. 이 두 방향으로 짧은 선을 그으면 끝에 > 모양의 화살촉이 완성된다.
■ 최종 결과
using UnityEngine;
public class DummyEnemy : MonoBehaviour
{
[HideInInspector] public FlowField FlowField;
[SerializeField] private CharacterController cc;
[SerializeField] private float speed = 5f;
private void Update()
{
var cellDir = FlowField.GetCurrentCellDirection(transform.position);
var dir = new Vector3(cellDir.x, 0f, cellDir.y).normalized;
cc.Move(dir * (speed * Time.deltaTime));
}
}
[적 이동 코드]
위 결과처럼 적들이 자신이 서 있는 칸의 화살표를 따라 플레이어의 위치로 이동하는 모습을 확인할 수 있다. 각 적은 매 프레임 GetCurrentCellDirection으로 자기 위치의 흐름 방향을 받아와, 그 방향으로 speed만큼 이동할 뿐이다. 개별적으로 경로를 계산하지 않고 미리 만들어둔 FlowField를 참조하기만 하므로, 적이 수백 마리로 늘어나도 이동 비용은 거의 그대로다.
하지만 이 코드만으로는 두 가지 문제가 있다.
- FlowField는 큰 흐름일 뿐, 같은 칸 안에서 서로 겹치는 것까지는 막지 못한다. 서로를 밀어내는 힘이 없기 때문에 적들이 한 덩어리로 뭉친 채 이동한다.
- CharacterController는 벽 같은 지형과는 충돌하지만 CharacterController끼리는 서로를 밀어내지 못하므로, CC에 기대는 것만으로는 적끼리 겹치는 문제가 해결되지 않음.
그렇다고 매 프레임 모든 적을 서로 비교해 밀어내면(혹은 OverlapSphere로 주변을 검사하면) 적 수가 늘어날수록 연산량이 급격히 커져 대규모 처리라는 목적이 무너진다. 그래서 다음에는 공간 해싱 그리드(Spatial Hash)를 사용해, 주변에 있을 법한 적만 추려서 밀어내는 조향 기능을 추가한다.
■ 전체 코드
using System.Collections.Generic;
using UnityEngine;
public class FlowField : MonoBehaviour
{
[SerializeField] private bool drawGizmos = true;
[Header("Components")]
[SerializeField] private CityGenerator cityGenerator;
[SerializeField] private Transform playerTf;
private CityLayout _layout;
private int _width = 0;
private int _height = 0;
private Node[,] _flowField;
private Vector2Int _curPlayerCell;
private Vector3 _originCellPos;
private void Start()
{
if (cityGenerator.CityLayout == null)
{
cityGenerator.GenerateCity();
}
_layout = cityGenerator.CityLayout;
_width = _layout.Width;
_height = _layout.Height;
_flowField = new Node[_width, _height];
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
_flowField[x, y] = new Node(int.MaxValue, Vector2Int.zero);
}
}
_originCellPos = _layout.ConvertCellPosToWorld(0,0);
}
public Vector2Int GetCurrentCellDirection(Vector3 pos)
{
if(_flowField == null) return Vector2Int.zero;
var index = WorldToCell(pos);
return (index.x < 0 || index.x >= _width || index.y < 0 || index.y >= _height)
? Vector2Int.zero
: _flowField[index.x, index.y].Direction;
}
public bool IsBlocked(Vector3 worldPos)
{
var c = WorldToCell(worldPos);
if (c.x < 0 || c.x >= _width || c.y < 0 || c.y >= _height) return true;
return !IsPassable(c.x, c.y);
}
private void Update()
{
var playerIndex = WorldToCell(playerTf.position);
if (playerIndex != _curPlayerCell)
{
_curPlayerCell = playerIndex;
UpdateFlowField();
}
}
private void UpdateFlowField()
{
ResetNode();
var queue = new Queue<Vector2Int>();
var passable = new List<Vector2Int>();
var visited = new bool[_width * _height];
queue.Enqueue(_curPlayerCell);
visited[_curPlayerCell.x * _height + _curPlayerCell.y] = true;
_flowField[_curPlayerCell.x, _curPlayerCell.y] = new Node(0, Vector2Int.zero);
while (queue.Count > 0)
{
var node = queue.Dequeue();
var curCost = _flowField[node.x, node.y].Cost;
for (var i = 0; i < 4; ++i)
{
var sx = node.x + _searchDir[i].x;
var sy = node.y + _searchDir[i].y;
if (sx < 0 || sx >= _width || sy < 0 || sy >= _height) continue;
if (visited[sx * _height + sy] || IsPassable(sx, sy) == false) continue;
_flowField[sx, sy].Cost = curCost + 1;
queue.Enqueue(new Vector2Int(sx, sy));
passable.Add(new Vector2Int(sx, sy));
visited[sx * _height + sy] = true;
}
}
foreach (var pNode in passable)
{
var min = _flowField[pNode.x, pNode.y].Cost;
foreach (var s in _searchDir)
{
var dx = pNode.x + s.x;
var dy = pNode.y + s.y;
if(dx < 0 || dx >= _width || dy < 0 || dy >= _height)
continue;
if (s.x != 0 && s.y != 0)
{
if(!IsPassable(dx, pNode.y) || !IsPassable(pNode.x, dy))
continue;
}
if (min > _flowField[dx, dy].Cost)
{
min = _flowField[dx, dy].Cost;
_flowField[pNode.x, pNode.y].Direction = s;
}
}
}
}
private void OnDrawGizmos()
{
if (drawGizmos == false || _flowField == null) return;
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
if (_flowField[x, y].Direction == Vector2Int.zero) continue;
var center = _layout.ConvertCellPosToWorld(x, y);
var dir = _flowField[x, y].Direction;
var worldDir = new Vector3(dir.x, 0f, dir.y).normalized;
var tip = center + worldDir * (_layout.CellSize * 0.4f);
Gizmos.color = Color.cyan;
Gizmos.DrawLine(center, tip);
var back1 = Quaternion.Euler(0, 150f, 0) * worldDir;
var back2 = Quaternion.Euler(0, -150f, 0) * worldDir;
Gizmos.DrawLine(tip, tip + back1 * (_layout.CellSize * 0.15f));
Gizmos.DrawLine(tip, tip + back2 * (_layout.CellSize * 0.15f));
}
}
}
private Vector2Int WorldToCell(Vector3 worldPos)
{
var col = Mathf.RoundToInt((worldPos.x - _originCellPos.x) / _layout.CellSize);
var row = Mathf.RoundToInt((worldPos.z - _originCellPos.z) / _layout.CellSize);
return new Vector2Int(col, row);
}
private bool IsPassable(int x, int y)
{
return _layout.Cells[x, y] is ECellType.CatWalk or ECellType.Road;
}
private void ResetNode()
{
for (var x = 0; x < _width; ++x)
{
for (var y = 0; y < _height; ++y)
{
if (!IsPassable(x,y)) continue;
_flowField[x, y].Cost = int.MaxValue;
_flowField[x, y].Direction = Vector2Int.zero;
}
}
}
private readonly Vector2Int[] _searchDir = new[]
{
new Vector2Int(0, 1), new Vector2Int(0, -1), // 상, 하
new Vector2Int(-1, 0), new Vector2Int(1, 0), // 좌, 우
new Vector2Int(-1, 1), new Vector2Int(1, 1), // 좌상, 우상
new Vector2Int(-1, -1), new Vector2Int(1, -1) // 좌하, 우하
};
}
public struct Node
{
public int Cost;
public Vector2Int Direction;
public Node(int cost, Vector2Int direction)
{
Cost = cost;
Direction = direction;
}
}
'Unity,C# > Unity 정보' 카테고리의 다른 글
| [Unity] 다수의 적을 어떻게 움직일까(2) - 공간 해시 그리드 (0) | 2026.08.03 |
|---|---|
| [Unity] 이동 정리 - 벡터 개념부터 물리 이동까지(Transform, Rigidbody, CharacterController) (1) | 2026.06.23 |
| [Unity] 총알 시스템으로 알아보는 Object Pool (1) | 2026.05.07 |
| [Unity, C#] 델리게이트에 대한 모든것(Action, Func, Lambda) (0) | 2026.05.07 |
| [Unity, C#] SOLID 원칙 (1) | 2025.11.21 |