Navigation meshes and crowds
Open the live demo · Read the source · View on GitHub
A grid tells an agent which cells it can stand in. A navigation mesh does the
same job with convex polygons: fewer of them, any shape, and stacked where a
walkway crosses over a floor. NavMesh.bake makes one from a level's brushes,
a route over it is a short list of corners, and Avoidance keeps bodies
walking those routes from walking into each other.
This page has a floor with a wall across its left half and a ledge in one corner. The yellow ball walks the route round the wall, the orange line climbs onto the ledge by a jump, and on the right eight bodies swap places across a circle. The green lines are the mesh's polygons.
Step 1: A level #
Brushes are boxes, and the mesh is made from them, not from the collision world. The collision world has doors in it, and a mesh baked with a door shut has a wall where the door is. The wall is three brushes so that its middle can be broken later. The ledge is 0.9 m up, too high to step onto.
/// A floor, a wall across the left half with a middle piece that can be
/// broken, and a ledge 0.9 m up: higher than a step, lower than a jump.
static List<Brush> _brushes({required bool broken}) => <Brush>[
Brush(
center: WorldPosition(0.0, -0.5, 0.0),
size: Vector3(24.0, 1.0, 12.0),
),
Brush(center: WorldPosition(-6.0, 1.5, -2.5), size: Vector3(0.6, 3.0, 3.0)),
if (!broken)
Brush(
center: WorldPosition(-6.0, 1.5, 0.0),
size: Vector3(0.6, 3.0, 2.0),
),
Brush(center: WorldPosition(-6.0, 1.5, 2.5), size: Vector3(0.6, 3.0, 3.0)),
Brush(center: WorldPosition(-9.0, 0.45, 4.5), size: Vector3(4.0, 0.9, 3.0)),
];
Step 2: Bake #
The bake voxelises the brushes, keeps the floors a body of the config's
height and radius fits on and can step between, erodes them by the radius,
cuts them into regions and outlines, and cuts the outlines into convex
polygons that know their neighbours. Everything from the voxeliser on is in
whole numbers, so NavMesh.digest is the same on every platform.
tileSize cuts the lattice into tiles of sixteen cells, and a region never
crosses a tile's edge. That is what step 5 needs. A tiled mesh has to keep
maxEdgeError under half a cell, and the config refuses one that does not.
/// Quarter-metre cells in tiles of sixteen. A tiled mesh keeps its
/// outlines within half a cell, which is what lets a tile be baked again
/// on its own and still meet its neighbours.
static const NavMeshSettings _config = NavMeshSettings(
cellSize: 0.25,
tileSize: 16,
maxEdgeError: 0.4,
);
static NavMesh _bake({required bool broken}) =>
NavMesh.bake(_brushes(broken: broken), settings: _config);
Step 3: A route round the wall #
route runs A* over the polygons, entering each at the middle of the edge it
came through, and then pulls a string through the shared edges, the funnel.
What comes back is the start, each corner the string bends round, and the end.
Inside the corridor every polygon is convex, so walking straight from corner to
corner stays on the mesh. Costs are counted in whole millimetres and ties go
by the mesh's own order, so two machines find the same route. A goal nobody can
reach gives a route marked incomplete, ending at the nearest point there is.
/// A* over the polygons, then the funnel through the edges they share:
/// a list of corners a body walks straight between.
NavMeshRoute _routeAcross() => _mesh.route(_start, _goal)!;
Step 4: Jumps #
Baked with a JumpReach, the mesh also looks for gaps, ledges and drops a
body with that reach can jump, and keeps the shortest link between each pair
of polygons. A route given the reach may take those links, and jumps says
which legs are flights. Without a reach the same route ends at the foot of the
ledge, incomplete. Bake with the most capable body a level has, and let each
route filter by its own.
/// A body that leaves the ground at 5 m/s reaches 1.27 m up, under the
/// Earth's gravity: the page has no world of its own to ask. Baked with
/// that reach, the mesh keeps links where a gap, a ledge or a drop can be
/// jumped, and a route given the same reach may take them.
static const JumpReach _reach = JumpReach(
jumpSpeed: 5.0,
gravity: standardGravity,
runSpeed: 4.0,
);
static NavMesh _bakeWithJumps() => NavMesh.bake(
_brushes(broken: false),
settings: const NavMeshSettings(cellSize: 0.25),
jumps: _reach,
);
Step 5: Break the wall and bake its tiles again #
Switch on Break the wall. The middle brush is gone, and rebake bakes
again only the tiles its box reaches, widened by the erosion. It outlines the
ring of tiles round them again and cuts the polygons again from every outline.
The result is, digest for digest, the changed level baked whole on the same
lattice, in a fraction of the time on a real level. The route now goes
straight through.
/// The middle of the wall goes. Only the tiles its box reaches, widened by
/// the body's erosion, are baked again; the polygons are cut again from
/// every outline, and the mesh is the one a whole bake would give.
void _breakWall() {
_mesh = _mesh.rebake(
_brushes(broken: true),
minX: -6.3,
minZ: -1.0,
maxX: -5.7,
maxZ: 1.0,
);
_route = _routeAcross();
}
Step 6: A crowd #
Avoidance is ORCA. Each neighbour rules out the velocities that would meet
it within the time horizon, each body takes half of the turning, and the
velocity picked is the one nearest the wanted one that every neighbour allows.
Every body picks from where all of them were before any of them moves, and
nothing is kept between steps. In a game, ActorSystem.avoidance does this for
every actor on the ground, after its route has said where it wants to go.
/// One step: every body asks ORCA for the velocity nearest the one it
/// wants that meets no neighbour within the horizon, all from where they
/// all were, and only then do they all move.
void step(double dt) {
final List<AvoidanceVelocity> picked = <AvoidanceVelocity>[
for (var i = 0; i < count; i++)
_avoidance.velocity(
x: x[i],
z: z[i],
vx: vx[i],
vz: vz[i],
radius: radius,
maxSpeed: speed,
prefX: _wish(goalX[i] - x[i], goalZ[i] - z[i]).$1,
prefZ: _wish(goalX[i] - x[i], goalZ[i] - z[i]).$2,
neighbors: <AvoidanceNeighbor>[
for (var j = 0; j < count; j++)
if (j != i)
AvoidanceNeighbor(
x: x[j],
z: z[j],
vx: vx[j],
vz: vz[j],
radius: radius,
),
],
dt: dt,
),
];
for (final (int i, AvoidanceVelocity(x: px, z: pz)) in picked.indexed) {
vx[i] = px;
vz[i] = pz;
x[i] += px * dt;
z[i] += pz * dt;
}
}
Step 7: What has to hold #
The route has to be complete, pass the wall's end and be longer than the straight line. The broken wall baked tile by tile has to have the same digest as the broken level baked whole, and the route through it has to be a straight line. The ledge has to be reached by a jump and not on foot. Eight bodies crossing for ten seconds must never come closer than two radii, give or take a centimetre.
// Round the wall: complete, bending past its end, longer than straight.
final NavMeshRoute round = _bake(broken: false).route(_start, _goal)!;
if (!round.complete ||
!round.points.any((Vector3 p) => p.z.abs() > 4.0) ||
round.length <= _start.distanceTo(_goal) + 1.0) {
throw StateError('the route does not go round the wall');
}
// A hole baked tile by tile is the hole baked whole, and walked through.
final NavMesh mended = _bake(broken: false);
final NavMesh holed = mended.rebake(
_brushes(broken: true),
minX: -6.3,
minZ: -1.0,
maxX: -5.7,
maxZ: 1.0,
);
final NavMesh whole = NavMesh.bake(
_brushes(broken: true),
settings: _config,
lattice: mended.lattice,
);
if (holed.digest != whole.digest) {
throw StateError('the rebaked tiles differ from a whole bake');
}
if (holed.route(_start, _goal)!.points.length != 2) {
throw StateError('the route does not take the hole');
}
// The ledge is reached by a jump, and not at all on foot.
if (_jump.jumps.isEmpty || !_jump.complete) {
throw StateError('no jump onto the ledge');
}
if (_jumpMesh.route(_below, _onLedge)!.complete) {
throw StateError('the ledge should not be walked onto');
}
// Eight bodies crossing for ten seconds never come closer than two
// radii, give or take a centimetre.
final _Crowd crowd = _Crowd(8, 6.0, 4.0);
var least = double.infinity;
for (var i = 0; i < 600; i++) {
crowd.step(1 / 60);
least = math.min(least, crowd.closest());
}
if (least < 2.0 * _Crowd.radius - 0.01) {
throw StateError('two of the crowd overlapped: $least m apart');
}
Note. A mesh baked with jumps, or with small islands dropped, is not baked again by tiles:
rebakerefuses it and it is baked whole. Avoidance knows nothing of walls. The route keeps a body off them and the character controller slides it along them, which is why the crowd here stands on open floor and walks straight. A crowd stepped by exact velocities, as here, keeps its distance; actors moved by a character controller keep about 94% of two radii, since the controller only approaches the velocity it is given. A goal nobody can reach searches the whole of the start's part of the mesh before giving up.