Why steer a crowd of thousands sharing one goal with a flow field instead of one path per agent, and how is the field built?
answer
- one search per goal, not per agent
- cost, integration, direction
- a wavefront spreading from the goal
- constant-time lookup per agent
- still needs local avoidance
basics
~20 sA flow field is built once per goal: a wavefront from the goal gives each cell its cost-to-goal and a downhill direction. Any number of agents then read their cell in constant time instead of each running its own search.
solid answer
~50 sA flow field is three grids. The **cost field** holds each cell's traversal cost, with walls impassable. The **integration field** holds each cell's cheapest cost to the goal, filled by a uniform-cost wavefront spreading out from the goal cells, which is Dijkstra's algorithm run backwards from the goal. The **direction field** stores, per cell, the step toward the neighbour with the lowest integration value. One build costs about one search over the grid, whatever the number of agents, and each agent then reads its cell in constant time; per-agent paths cost one search per agent. It pays when many agents share few goals, and loses for many distinct goals or a handful of agents. The field ignores other agents, so its direction becomes each agent's preferred velocity and local avoidance still prevents collisions; dynamic obstacles force a rebuild of the affected area.
code
pseudocode · 22 lines// 8-connected grid; cost[c] = INF for walls
function buildFlowField(cost, goalCells):
integration = fill(INF)
open = priorityQueue()
for g in goalCells:
integration[g] = 0
open.push(g, 0)
while open is not empty:
(c, d) = open.popMin()
if d > integration[c]:
continue // stale queue entry
for n in neighbours8(c):
if cost[n] == INF or cutsBlockedCorner(c, n):
continue
stepCost = cost[n] * (if isDiagonal(c, n) then 1.414 else 1.0)
if integration[c] + stepCost < integration[n]:
integration[n] = integration[c] + stepCost
open.push(n, integration[n])
direction = fill(NONE)
for c in cells where integration[c] < INF and c not in goalCells:
direction[c] = the allowed neighbour n of c with the lowest integration[n]
return directiongo deeper
Recall the three layers, cost, integration and direction, and that agents read the direction of the cell they stand in.
Explain how the integration field is filled from the goal, why one build serves every agent, and why local avoidance is still needed on top.
Judge when a flow field beats per-agent paths, design multi-goal seeding and sector rebuilds, and fix lane artefacts with interpolation.
Weigh field memory and rebuild cost against crowd size and goal count when choosing a crowd navigation approach for a whole game.
## The problem with one path per agent Picture a crowd of several thousand spectators leaving a stadium through one gate. With a path per agent: - Every agent runs its own route search, so the cost grows with the number of agents, and most of those searches explore nearly the same cells. - Every path has to be stored and followed, and every one has to be repaired when something changes. - Agents following near-identical paths line up in single file along the same polygon edges or cell centres. All the agents want the same thing: the cheapest way from wherever they stand to one goal. A **flow field** answers that question once for every cell. ## Building the field The grid convention here is an 8-connected grid: straight moves cost 1 times the cell's cost, diagonal moves about 1.414 times, and a diagonal may not cut past a blocked corner. 1. **Cost field.** Each cell gets a traversal cost: 1 for open ground, more for mud or stairs, impassable for walls. 2. **Integration field.** Seed every goal cell with 0 and spread a uniform-cost wavefront outward, always expanding the cheapest frontier cell next. This is Dijkstra's algorithm from the goal; when every move costs the same, a breadth-first search is enough. Each cell ends with its cheapest cost to the goal. 3. **Direction field.** Each reachable cell points to the neighbour with the lowest integration value. With positive costs, every reachable cell except a goal has such a downhill neighbour, so agents cannot get stuck in a local minimum. For a stadium gate, seed **all** the cells across the gate's width as goals. Agents then head for the nearest part of the opening rather than its centre. The wavefront visits each reachable cell, so its cost depends on the size of the map, not on how many agents will read the result. ## What it costs On a 512 x 512 grid there are 262,144 cells. One build expands each cell about once. The integration field as 32-bit values takes 1 MiB and the direction field at one byte per cell takes 256 KiB, about 1.25 MiB per goal, plus a shared cost field. | Approach | Search work | Per-agent runtime cost | Best for | |---|---|---|---| | Path per agent | one search per agent | follow its own path | few agents, many different goals | | Flow field | one search per goal | read one cell | many agents, few shared goals | Agents that each choose their nearest exit can share a single field seeded with every exit's cells; agents assigned to specific exits need one field per exit. ## Reading the field at runtime - **Preferred velocity.** An agent reads the direction at its position and scales it to its preferred speed. That is a wish, not a move. - **Interpolation.** Snapping to a cell's single arrow produces motion in 45-degree steps and visible lanes. Blending the directions of the surrounding cells, weighted by position, gives smooth curves. - **Line of sight near the goal.** Where an agent can see the goal directly, steering straight at it avoids grid artefacts in the last stretch. - **Unreachable cells.** An agent pushed into a cell the wavefront never reached finds no direction there; give it a fallback, such as steering to the nearest reachable cell. - **Local avoidance.** The field knows walls, not other agents. Separation or reciprocal velocity avoidance still has to keep agents from overlapping, especially where the field funnels them together. ## Limits and extensions - **One field per goal.** Many unique goals make per-agent paths cheaper again. - **Dynamic obstacles** invalidate the integration field. Splitting the map into sectors and rebuilding only affected sectors, or building fields on demand for the sectors a route passes through, keeps updates affordable. - **Memory** grows with map area times the number of live goals, so caches of fields need eviction. - **Crowd density.** Adding a density term to the cost, as continuum-crowd methods do, makes agents spread to less crowded routes instead of all taking the same cheapest one. ## Common mistakes - Pointing each cell straight at the goal, which walks agents into walls. - Treating the field as collision avoidance between agents. - Rebuilding the whole map every tick when one door closes. - Using breadth-first search on a grid with diagonal or varied costs, which counts steps instead of cost.
- Agents may leave through whichever of three exits is closest; how many fields do you build?One. Seed the cells of all three exits with cost 0 and run a single wavefront; every cell ends up holding its cost to the nearest exit and pointing toward it. Separate fields per exit are needed only when agents are assigned a specific exit, or when you want to weigh exits differently per group.
- A door closes in the middle of a large map; how do you update a flow field without rebuilding everything?Mark the door's cells impassable and rebuild only what depends on them. With the map split into sectors and a coarse graph of sector portals, recompute the portal costs, then rebuild the fine fields only for sectors whose routes changed. Agents keep using their old directions until the new sectors are ready, which a short delay usually hides.
- A flow field is A* run once per agent and cached.
- A flow field also stops agents from colliding with each other.
- Flow fields beat per-agent paths even for a few agents with different goals.
- Each cell should simply point straight at the goal.
- Breadth-first search gives correct costs on any grid, diagonals included.