A flow field

since 0.4.1 or earlier Simulation, audio and XR

Open the live demo · Read the source · View on GitHub

When every agent in a level chases the same target, running one path search per agent recomputes most of the same tree over and over. A flow field turns that around: it sweeps once from the goal, and every cell ends up holding the direction that leads there. Steering an agent is then one array lookup.

Step 1: A grid to sweep over #

An open floor, ten metres on a side.

final grid = NavGrid.bake(<Brush>[
  Brush(centre: Vector3(5, 0, 5), size: Vector3(10, 1, 10)),
], cellSize: 0.5);

Step 2: Sweep towards a goal #

FlowField wraps a grid, and rebuild runs the sweep towards a world position. It only needs re-running when the goal moves to a different cell, or when the level itself changes.

final field = FlowField(grid);
field.rebuild(Vector3(9.0, 0.0, 9.0));

Step 3: Ask which way to walk #

descend writes the direction to walk from any point, as a flat unit vector. walkingDistanceTo reports how far it is to the goal along the field, which the sweep already knows for free.

final from = Vector3(1.0, 0.0, 1.0);
final direction = Vector3.zero();
final found = field.descend(from, direction);
final distance = field.walkingDistanceTo(from);

A point in the near corner of the floor is told to walk towards the far corner, where the goal sits.

Step 4: Sixteen agents, one table #

The floor on this page has two walls across it, each with a gap at one end, and sixteen agents that start on the left. There is one FlowField: rebuilt when the goal moves, and read by every agent every frame. Each agent asks it for a direction from wherever it stands and takes a step, and they all snake round the walls to the gold post, however far apart they started. Move the goal and the whole crowd turns at once, off a single rebuild.

// A floor with two walls across it, each leaving a gap at one end: an
// agent has to snake round them, and the field knows how.
_grid = NavGrid.bake(<Brush>[
  Brush(centre: Vector3(10, 0, 10), size: Vector3(20, 1, 20)),
  Brush(centre: Vector3(7, 2, 6), size: Vector3(1, 4, 12)),
  Brush(centre: Vector3(13, 2, 14), size: Vector3(1, 4, 12)),
], cellSize: 0.5);
_field = FlowField(_grid);

// A new goal is one rebuild; every agent then follows the same table.
_field.rebuild(Vector3(gx, 0.5, gz));

// One step down the table from wherever the agent stands.
if (_field.descend(at, direction)) {
  // A long frame (a tab left in the background) must not fling an agent
  // out of the level in one step.
  at.addScaled(direction, 3.0 * math.min(dt, 0.05));
} else {
  // Not on the floor any more: back to where it started.
  at.setFrom(_starts[i]);
}