Flow fields: pathfinding para multitudes
Comparte path con miles de agentes sin recalcular nada. Lo que mueve los enjambres de Supreme Commander y Planetary Annihilation.
Publicado: · Por Juanjo "Banyo" López
0. Introducción
Imagina un RTS con 2000 unidades del mismo bando, todas marchando al mismo punto. Si cada una corre su propio A*, son 2000 búsquedas por orden. En un mapa de 256×256 con A* eficiente, son ~10 millones de operaciones. Tu CPU te odia.
La idea del flow field: en vez de “cada agente sabe su path”, el mapa sabe a dónde ir. Calculas un campo direccional una sola vez desde el goal; cada agente solo lee la dirección de su celda actual y se mueve hacia allá. Costo por agente: O(1).
Supreme Commander (2007) y Planetary Annihilation lo popularizaron en RTS. Cualquier juego con miles de agentes hacia un destino común (zombies, hordas, multitudes en general) lo usa.
¿Cuándo usar flow field?
- Cientos o miles de agentes hacia el mismo destino.
- El destino cambia poco (recalcular el flow field es caro).
- Te conformas con un path óptimo en costo total (Dijkstra back) pero no necesariamente con avoidance entre agentes (eso lo añades aparte, ej: separation steering encima del flow field).
¿Cuándo NO?
- Pocos agentes con goals distintos: un A* por agente cuesta menos que recalcular el flow field para cada uno.
- Mapas dinámicos que cambian rápido: el flow field se invalida.
- Agentes con personalidades o velocidades muy distintas: el flow field asume comportamiento homogéneo.
1. Generación del flow field
Un flow field tiene dos capas:
- Integration field (a veces llamado cost field): la distancia desde el goal a cada celda. Es exactamente un Dijkstra map desde el goal.
- Flow vectors: la dirección de cada celda hacia el vecino con menor distancia integrada.
El integration field (heatmap) es la distancia desde el goal a cada celda — un Dijkstra back. La dirección de cada flecha apunta al vecino con menor distancia. Junto, eso es un flow field. Cualquier agente en cualquier celda solo necesita leer su flecha.
Figura 1 — El heatmap es el integration field (azul = cerca del goal, rojo = lejos). Las flechas blancas son los vectores: cada celda apunta al vecino con menor distancia. Click para muros, Shift+click mueve el goal.
1.1 Paso a paso
function buildFlowField(grid, goal):
# Capa 1: integration (Dijkstra back desde el goal)
distance = Map.fillWith(Infinity)
distance[goal] = 0
pq = MinPriorityQueue()
pq.push(goal, 0)
while pq not empty:
cur = pq.popMin()
for each neighbor of walkableNeighbors(cur):
tentative = distance[cur] + cost(neighbor)
if tentative < distance[neighbor]:
distance[neighbor] = tentative
pq.push(neighbor, tentative)
# Capa 2: dirección a vecino con menor distance
direction = Map()
for each cell c in grid:
if not walkable(c): continue
bestNeighbor = argmin(distance[n] for n in neighbors8(c))
direction[c] = angle(c -> bestNeighbor)
return { distance, direction }
Costo total: O(N log N) donde N es el número de celdas (un Dijkstra). Una sola vez. Después, cualquier agente lee direction[cell] en O(1).
1.2 Por qué Dijkstra y no BFS
BFS daría distancia uniforme (en pasos). Si tu mapa tiene terrenos con costos distintos (barro, agua), BFS te miente — los agentes elegirían “rodear el barro o cruzarlo” según pasos, no costos. Dijkstra respeta los costos. Si tu mapa es uniforme, BFS es equivalente y más rápido.
1.3 Diagonales: ¿8-conexo o 4-conexo?
8-conexo se ve más natural (los agentes pueden moverse en diagonales). Pero ojo: si el costo diagonal no es √2 sino 1 (Chebyshev), el flow field puede preferir diagonales innecesarias. Asegúrate de que el costo de mover diagonal sea consistente.
2. Navegación: cientos de agentes, un solo cálculo
Una vez generado el flow field, los agentes no piensan: cada frame, leen la dirección de su celda y se mueven en esa dirección.
Un flow field calculado una sola vez guía a centenares de agentes simultáneamente. Cada agente solo lee la dirección de su celda — no calcula path. Sube el slider y mira el FPS: aguanta miles de agentes sin pestañear.
Figura 2 — Cientos de agentes salen de la izquierda hacia el goal en la derecha. Sube el slider hasta 2000 — el FPS se mantiene porque cada agente solo hace un lookup O(1). El flow field se calculó una sola vez al generar el mapa.
2.1 El movimiento básico
function moveAgent(agent, flowField, dt):
cell = floor(agent.position)
angle = flowField.direction[cell]
if angle is finite:
agent.velocity.x = cos(angle) * agent.maxSpeed
agent.velocity.y = sin(angle) * agent.maxSpeed
agent.position += agent.velocity * dt
Es trivial. Toda la inteligencia está en el field, no en el agente.
2.2 Capas que necesitas añadir encima
Flow field puro tiene un problema: los agentes se atraviesan. Para que se sientan como una multitud realista, sumas:
- Separation (de Flocking): cada agente empuja suavemente a sus vecinos cercanos. Le da “cuerpo” a la multitud.
- Avoidance local: si dos agentes van en direcciones casi opuestas, uno cede.
- LOS smoothing: si el agente puede ir directo a un punto del flow N celdas adelante, salta intermedios. Es el equivalente de Theta* para flow fields.
El flow field marca la dirección general; las capas locales evitan choques. Suma de fuerzas con prioridades: avoidance > flow.
3. El número que importa: A* vs Flow field
A\* es O(agentes × tamaño-mapa): cada agente paga su propia búsqueda. Flow field es O(tamaño-mapa) + O(agentes): un cálculo, lookup O(1) por agente. Sube el slider y mira el ratio: con muchos agentes hacia el mismo goal, flow field gana por dos órdenes de magnitud.
Figura 3 — Sube el slider de cantidad de agentes. A* paga búsqueda por agente (lineal en N agentes); flow field paga una vez y luego es lineal trivial. Con 2000 agentes hacia el mismo goal, flow field gana por ~2 órdenes de magnitud.
3.1 Cuándo cambia la balanza
- 1 agente, 1 goal: A* gana cómodo. Flow field es overkill.
- 10 agentes, 1 goal: A* sigue ganando si los agentes calculan en paralelo.
- 100+ agentes, 1 goal: flow field empieza a ganar.
- 1000+ agentes, 1 goal: flow field domina. A* deja de ser viable en hardware modesto.
- N agentes, N goals distintos: flow field no aplica directamente. Volvés a A*.
3.2 Múltiples flow fields para múltiples goals
Si tienes 5 destinos típicos (la base, las minas, los puntos de control), pre-computas 5 flow fields. Cada agente lee el que corresponde a su orden actual. Cambio de destino = cambio de campo. Cada cálculo es de O(N log N), pero amortizado entre cientos de agentes.
4. Pseudocódigo completo
class FlowField
cols, rows: int
distance: Float[] # Dijkstra map desde goal
direction: Float[] # ángulo (radianes) hacia el vecino con menor distance
function buildFlowField(grid, goal) -> FlowField
distance = array(grid.cols * grid.rows, fill = Infinity)
distance[idx(goal)] = 0
pq = MinPriorityQueue()
pq.push(idx(goal), 0)
while pq not empty
cur = pq.popMin()
for each n in walkableNeighbors8(cur)
stepCost = cost(n) * (n.diagonal ? sqrt(2) : 1)
cand = distance[cur] + stepCost
if cand < distance[n]
distance[n] = cand
pq.push(n, cand)
direction = array(grid.cols * grid.rows, fill = NaN)
for each cell c in grid
if not walkable(c) or distance[c] = Infinity: continue
best = c
for each n in neighbors8(c)
if walkable(n) and distance[n] < distance[best]
best = n
if best != c
direction[c] = atan2(best.y - c.y, best.x - c.x)
return { distance, direction }
function moveAgents(agents, flowField, dt)
for each agent in agents
cell = floor(agent.position)
if flowField.direction[cell] is finite
agent.velocity = vec2(cos(angle), sin(angle)) * maxSpeed
agent.position += agent.velocity * dt
5. Implementación en Unity / C#
Snippet representativo. El asset trae un sistema completo con multi-target, recalculo incremental cuando cambia el mapa, y particle-system rendering para visualizar el field.
using System.Collections.Generic;
using UnityEngine;
public class FlowField {
public int Cols, Rows;
public float[] Distance;
public float[] Direction; // ángulo en radianes; NaN si no hay flujo
public static FlowField Build(bool[,] walkable, float[] cost, Vector2Int goal) {
int W = walkable.GetLength(0), H = walkable.GetLength(1), N = W * H;
var ff = new FlowField { Cols = W, Rows = H, Distance = new float[N], Direction = new float[N] };
for (int i = 0; i < N; i++) { ff.Distance[i] = float.PositiveInfinity; ff.Direction[i] = float.NaN; }
ff.Distance[goal.y * W + goal.x] = 0;
var pq = new PriorityQueue<int, float>();
pq.Enqueue(goal.y * W + goal.x, 0);
var dirs8 = new[] { (1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1) };
while (pq.Count > 0) {
int cur = pq.Dequeue();
int cx = cur % W, cy = cur / W;
foreach (var d in dirs8) {
int nx = cx + d.Item1, ny = cy + d.Item2;
if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
if (!walkable[nx, ny]) continue;
int ni = ny * W + nx;
float step = (d.Item1 != 0 && d.Item2 != 0) ? Mathf.Sqrt(2f) : 1f;
float cand = ff.Distance[cur] + cost[ni] * step;
if (cand < ff.Distance[ni]) {
ff.Distance[ni] = cand;
pq.Enqueue(ni, cand);
}
}
}
// capa de direcciones
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
int ci = y * W + x;
if (!walkable[x, y] || float.IsInfinity(ff.Distance[ci])) continue;
float best = ff.Distance[ci]; int bdx = 0, bdy = 0;
foreach (var d in dirs8) {
int nx = x + d.Item1, ny = y + d.Item2;
if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
if (!walkable[nx, ny]) continue;
if (ff.Distance[ny * W + nx] < best) {
best = ff.Distance[ny * W + nx];
bdx = d.Item1; bdy = d.Item2;
}
}
if (bdx != 0 || bdy != 0) ff.Direction[ci] = Mathf.Atan2(bdy, bdx);
}
}
return ff;
}
public Vector2 SampleDirection(Vector2 worldPos) {
int cx = Mathf.Clamp((int)worldPos.x, 0, Cols - 1);
int cy = Mathf.Clamp((int)worldPos.y, 0, Rows - 1);
float a = Direction[cy * Cols + cx];
return float.IsNaN(a) ? Vector2.zero : new Vector2(Mathf.Cos(a), Mathf.Sin(a));
}
}
6. En otros engines
- Godot: no trae flow fields nativos; lo escribís sobre
TileMapoGridMap. Es directo con la API. - Unreal: el plugin Detour Crowd es un equivalente conceptual (avoidance multi-agente sobre NavMesh), pero no es flow field puro. Para RTS masivo en Unreal, custom es la opción.
- JavaScript / TypeScript: la lib del sitio implementa
buildFlowField()directamente sobre la grilla.
7. Quiz
Pon a prueba lo que entendiste
Responde una por una. La explicación aparece al elegir, correcta o no.
Tienes un RTS con 1500 unidades del mismo bando hacia el mismo punto. ¿Por qué flow field gana sobre A* por agente?
Tu juego es un puzzle con 4 unidades, cada una con goal distinto. ¿Flow field o A*?
El flow field marca la dirección general pero los agentes se atraviesan visualmente. ¿Cómo lo solucionas?
Cambias el goal del flow field cada 10 segundos en una partida de RTS. ¿Cuál es el costo crítico?
El integration field es Dijkstra desde el goal hacia atrás. ¿Por qué Dijkstra y no BFS?