Path-finding

since 0.4.1 Simulation, audio and XR

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

Before anything can path across a level, something has to say where standing is possible at all. NavGrid bakes that once from the level's brushes into a lattice of cells, so a step asks "can I stand here" and "can I move from here to there" as array lookups instead of geometry queries.

Step 1: Build a small level #

Two floor slabs with a narrow bridge between them, and open air everywhere else.

/// Two floor slabs joined by a narrow bridge, so most of the gap between
/// them is not walkable but the bridge is.
static List<Brush> _brushes() => <Brush>[
  Brush(centre: Vector3(2, 0, 2), size: Vector3(4, 1, 4)),
  Brush(centre: Vector3(5.5, 0, 3.5), size: Vector3(3, 1, 1)),
  Brush(centre: Vector3(9, 0, 2), size: Vector3(4, 1, 4)),
];

Step 2: Bake the grid #

NavGrid.bake rasterises the solid brushes into cells at a chosen size, finding the floor height and the headroom above it for each one.

static NavGrid _bake() => NavGrid.bake(_brushes(), cellSize: 0.5);

Step 3: Ask it questions #

cellAtPoint finds which cell a world position falls in, and isWalkable says whether anything can stand there.

final onFirstSlab = _grid.isWalkable(_grid.cellAtPoint(2.0, 2.0));
final inTheGap = _grid.isWalkable(_grid.cellAtPoint(4.5, 0.5));
final onBridge = _grid.isWalkable(_grid.cellAtPoint(5.0, 3.5));

Both slabs and the bridge between them answer walkable; the open gap on either side of the bridge does not, because no brush covers it.

Step 4: Probe it #

The grid is drawn from above, blue where an agent could stand. The dot is a probe that sweeps across both slabs, the bridge and the gap: each frame it asks the grid which cell it is in and whether that cell is walkable, and turns green or red. Tap the map to put it somewhere yourself; the answer is one array lookup either way.

// Asking the baked grid about one point: which cell it falls in, and
// whether an agent could stand there.
final int cell = _grid.cellAtPoint(_probe.x, _probe.y);
final bool walkable = _grid.isWalkable(cell);