Navigation meshes and crowds: the source
Open the live demo · Read the guide · View on GitHub
Regions the guide quotes: avoid (line 40), level (line 136), bake (line 153), jumps (line 165), route (line 181), hole (line 255), check (line 377).
1/// A navigation mesh baked from a small level: a route round a wall pulled
2/// tight by the funnel, a jump up onto a ledge the walk cannot reach, the
3/// wall broken and only its tiles baked again, and a crowd crossing a
4/// circle without touching.
5///
6/// Quoted by `navmesh_crowds.md` and shown whole in the Source tab.
7library;
9import 'dart:math' as math;
11import 'package:flutter3d/flutter3d.dart';
12import 'package:flutter3d_matter/flutter3d_matter.dart';
13import 'package:flutter3d_showcase/src/demo/demo.dart';
14import 'package:flutter3d_sim/flutter3d_sim.dart';
16/// Bodies on an open floor stepped by velocity alone, each wanting to walk
17/// straight to the far side of the circle it starts on.
18final class _Crowd {
19 _Crowd(this.count, this.centerX, this.circle) {
20 for (var i = 0; i < count; i++) {
21 final double a = i * 2.0 * math.pi / count;
22 x.add(centerX + circle * math.cos(a));
23 z.add(circle * math.sin(a));
24 goalX.add(centerX - circle * math.cos(a));
25 goalZ.add(-circle * math.sin(a));
26 }
27 }
29 final int count;
30 final double centerX, circle;
31 final List<double> x = <double>[], z = <double>[];
32 final List<double> goalX = <double>[], goalZ = <double>[];
33 late final List<double> vx = List<double>.filled(count, 0.0);
34 late final List<double> vz = List<double>.filled(count, 0.0);
36 static const double radius = 0.35;
37 static const double speed = 1.5;
38 static const Avoidance _avoidance = Avoidance();
40 /// One step: every body asks ORCA for the velocity nearest the one it
41 /// wants that meets no neighbour within the horizon, all from where they
42 /// all were, and only then do they all move.
43 void step(double dt) {
44 final List<AvoidanceVelocity> picked = <AvoidanceVelocity>[
45 for (var i = 0; i < count; i++)
46 _avoidance.velocity(
47 x: x[i],
48 z: z[i],
49 vx: vx[i],
50 vz: vz[i],
51 radius: radius,
52 maxSpeed: speed,
53 prefX: _wish(goalX[i] - x[i], goalZ[i] - z[i]).$1,
54 prefZ: _wish(goalX[i] - x[i], goalZ[i] - z[i]).$2,
55 neighbors: <AvoidanceNeighbor>[
56 for (var j = 0; j < count; j++)
57 if (j != i)
58 AvoidanceNeighbor(
59 x: x[j],
60 z: z[j],
61 vx: vx[j],
62 vz: vz[j],
63 radius: radius,
64 ),
65 ],
66 dt: dt,
67 ),
68 ];
69 for (final (int i, AvoidanceVelocity(x: px, z: pz)) in picked.indexed) {
70 vx[i] = px;
71 vz[i] = pz;
72 x[i] += px * dt;
73 z[i] += pz * dt;
74 }
75 }
77 /// Straight at the goal, at walking speed, slowing on the last metre.
78 static (double, double) _wish(double dx, double dz) {
79 final double d = math.sqrt(dx * dx + dz * dz);
80 if (d <= speed) return (dx, dz);
81 return (dx * speed / d, dz * speed / d);
82 }
84 /// The nearest any two came, centre to centre.
85 double closest() {
86 var least = double.infinity;
87 for (var i = 0; i < count; i++) {
88 for (var j = i + 1; j < count; j++) {
89 final double dx = x[i] - x[j], dz = z[i] - z[j];
90 least = math.min(least, math.sqrt(dx * dx + dz * dz));
91 }
92 }
93 return least;
94 }
95}
97/// The `navmesh-crowds` page: a navigation mesh baked from a small level, a
98/// route round a wall, a jump onto a ledge, and a crowd crossing a circle.
99/// Its check is the route round the wall, the jump, the hole once the wall is
100/// broken, and rebaked tiles equal to a whole bake.
101final class NavmeshCrowdsDemo extends ShowcaseDemo {
102 late NavMesh _mesh;
103 late final NavMesh _jumpMesh;
104 late NavMeshRoute _route;
105 late final NavMeshRoute _jump;
106 late _Crowd _crowd;
107 late final Scene _scene;
108 late final MeshNode _door;
109 Registration? _lines;
111 final List<MeshNode> _people = <MeshNode>[];
112 late final MeshNode _walker;
114 /// Whether the wall is broken, which rebakes only its tiles.
115 bool broken = false;
117 /// Whether the mesh's polygons are drawn.
118 bool showMesh = true;
119 double _along = 0.0;
120 double _crowdAge = 0.0;
122 static Vector3 get _start => Vector3(-10.0, 0.0, 0.0);
123 static Vector3 get _goal => Vector3(-2.0, 0.0, 0.0);
124 static Vector3 get _below => Vector3(-9.0, 0.0, 1.5);
125 static Vector3 get _onLedge => Vector3(-9.0, 0.9, 5.0);
128 void configureView(DemoContext context) {
129 context.orbit
130 ..distance = 22.0
131 ..pitch = 0.85
132 ..yaw = 0.0;
133 context.orbit.target.setValues(-1.0, 0.0, 0.0);
134 }
136 /// A floor, a wall across the left half with a middle piece that can be
137 /// broken, and a ledge 0.9 m up: higher than a step, lower than a jump.
138 static List<Brush> _brushes({required bool broken}) => <Brush>[
139 Brush(
140 center: WorldPosition(0.0, -0.5, 0.0),
141 size: Vector3(24.0, 1.0, 12.0),
142 ),
143 Brush(center: WorldPosition(-6.0, 1.5, -2.5), size: Vector3(0.6, 3.0, 3.0)),
144 if (!broken)
145 Brush(
146 center: WorldPosition(-6.0, 1.5, 0.0),
147 size: Vector3(0.6, 3.0, 2.0),
148 ),
149 Brush(center: WorldPosition(-6.0, 1.5, 2.5), size: Vector3(0.6, 3.0, 3.0)),
150 Brush(center: WorldPosition(-9.0, 0.45, 4.5), size: Vector3(4.0, 0.9, 3.0)),
151 ];
153 /// Quarter-metre cells in tiles of sixteen. A tiled mesh keeps its
154 /// outlines within half a cell, which is what lets a tile be baked again
155 /// on its own and still meet its neighbours.
156 static const NavMeshSettings _config = NavMeshSettings(
157 cellSize: 0.25,
158 tileSize: 16,
159 maxEdgeError: 0.4,
160 );
162 static NavMesh _bake({required bool broken}) =>
163 NavMesh.bake(_brushes(broken: broken), settings: _config);
165 /// A body that leaves the ground at 5 m/s reaches 1.27 m up, under the
166 /// Earth's gravity: the page has no world of its own to ask. Baked with
167 /// that reach, the mesh keeps links where a gap, a ledge or a drop can be
168 /// jumped, and a route given the same reach may take them.
169 static const JumpReach _reach = JumpReach(
170 jumpSpeed: 5.0,
171 gravity: standardGravity,
172 runSpeed: 4.0,
173 );
175 static NavMesh _bakeWithJumps() => NavMesh.bake(
176 _brushes(broken: false),
177 settings: const NavMeshSettings(cellSize: 0.25),
178 jumps: _reach,
179 );
181 /// A* over the polygons, then the funnel through the edges they share:
182 /// a list of corners a body walks straight between.
183 NavMeshRoute _routeAcross() => _mesh.route(_start, _goal)!;
186 Scene build(DemoContext context) {
187 _mesh = _bake(broken: false);
188 _jumpMesh = _bakeWithJumps();
189 _route = _routeAcross();
190 _jump = _jumpMesh.route(_below, _onLedge, jumps: _reach)!;
191 _crowd = _Crowd(8, 6.0, 4.0);
193 MeshNode box(Brush b, Vector4 color, String name) => MeshNode(
194 DeviceMesh.upload(context.device, CuboidShape(size: b.size).build()),
195 RenderMaterial(name: name, baseColor: _fromSrgb(color)),
196 name: name,
197 )..setPosition(b.center.x, b.center.y, b.center.z);
199 _scene = Scene()
200 ..ambientIntensity = 0.35 * LightNode.legacyUnit
201 ..add(
202 LightNode(name: 'sun', intensity: 2.5 * LightNode.legacyUnit)
203 ..setLocalForward(Vector3(-0.3, -0.8, -0.4)),
204 );
205 final List<Brush> brushes = _brushes(broken: false);
206 for (final (int i, Brush b) in brushes.indexed) {
207 final MeshNode node = box(
208 b,
209 i == 0 ? Vector4(0.36, 0.38, 0.42, 1.0) : Vector4(0.62, 0.58, 0.5, 1.0),
210 'brush $i',
211 );
212 _scene.add(node);
213 if (i == 2) _door = node;
214 }
215 final DeviceMesh ball = DeviceMesh.upload(
216 context.device,
217 SphereShape(segments: 12).build(),
218 );
219 _walker = MeshNode(
220 ball,
221 RenderMaterial(
222 name: 'walker',
223 baseColor: LinearColor.fromSrgb(0.95, 0.8, 0.2, 1.0),
224 ),
225 name: 'walker',
226 )..setScale(0.35, 0.35, 0.35);
227 _scene.add(_walker);
228 for (var i = 0; i < _crowd.count; i++) {
229 final MeshNode person = MeshNode(
230 ball,
231 RenderMaterial(
232 name: 'person $i',
233 baseColor: LinearColor.fromSrgb(
234 0.3 + 0.6 * (i % 2),
235 0.4 + 0.07 * i,
236 0.9 - 0.08 * i,
237 1.0,
238 ),
239 ),
240 name: 'person $i',
241 )..setScale(_Crowd.radius, _Crowd.radius, _Crowd.radius);
242 _people.add(person);
243 _scene.add(person);
244 }
245 _lines = context.renderer.addDebugLines(_draw);
246 _place();
247 return _scene;
248 }
251 void dispose() {
252 _lines?.cancel();
253 }
255 /// The middle of the wall goes. Only the tiles its box reaches, widened by
256 /// the body's erosion, are baked again; the polygons are cut again from
257 /// every outline, and the mesh is the one a whole bake would give.
258 void _breakWall() {
259 _mesh = _mesh.rebake(
260 _brushes(broken: true),
261 minX: -6.3,
262 minZ: -1.0,
263 maxX: -5.7,
264 maxZ: 1.0,
265 );
266 _route = _routeAcross();
267 }
269 void _mendWall() {
270 _mesh = _bake(broken: false);
271 _route = _routeAcross();
272 }
274 void _draw(DebugDraw lines) {
275 final Vector3 a = Vector3.zero(), b = Vector3.zero();
276 if (showMesh) {
277 final LinearColor edge = LinearColor.fromSrgb(0.3, 0.85, 0.5);
278 for (var p = 0; p < _mesh.polygonCount; p++) {
279 final int n = _mesh.polygonVertexCount(p);
280 for (var k = 0; k < n; k++) {
281 _mesh.vertexAt(_mesh.polygonVertex(p, k), a);
282 _mesh.vertexAt(_mesh.polygonVertex(p, (k + 1) % n), b);
283 lines.addLine(
284 a + Vector3(0.0, 0.03, 0.0),
285 b + Vector3(0.0, 0.03, 0.0),
286 edge,
287 );
288 }
289 }
290 }
291 final Vector3 lift = Vector3(0.0, 0.1, 0.0);
292 final List<Vector3> path = _route.points;
293 for (var i = 0; i + 1 < path.length; i++) {
294 lines.addLine(
295 path[i] + lift,
296 path[i + 1] + lift,
297 LinearColor.fromSrgb(1, 0.85, 0.2),
298 );
299 }
300 final List<Vector3> hop = _jump.points;
301 for (var i = 0; i + 1 < hop.length; i++) {
302 lines.addLine(
303 hop[i] + lift,
304 hop[i + 1] + lift,
305 _jump.jumps.contains(i)
306 ? LinearColor.fromSrgb(1.0, 0.35, 0.2)
307 : LinearColor.fromSrgb(1.0, 0.6, 0.3),
308 );
309 }
310 }
312 /// Where along [_route] the walker is after [distance] metres.
313 Vector3 _pointAlong(double distance) {
314 var left = distance;
315 final List<Vector3> p = _route.points;
316 for (var i = 0; i + 1 < p.length; i++) {
317 final double leg = p[i].distanceTo(p[i + 1]);
318 if (left <= leg) {
319 return p[i] + (p[i + 1] - p[i]) * (leg == 0.0 ? 0.0 : left / leg);
320 }
321 left -= leg;
322 }
323 return p.last.clone();
324 }
326 void _place() {
327 final Vector3 at = _pointAlong(_along);
328 _walker.setPosition(at.x, at.y + 0.35, at.z);
329 for (var i = 0; i < _crowd.count; i++) {
330 _people[i].setPosition(_crowd.x[i], _Crowd.radius, _crowd.z[i]);
331 }
332 }
335 void update(DemoContext context, double dt) {
336 final double step = math.min(dt, 1 / 30);
337 _along += 2.0 * step;
338 if (_along > _route.length + 1.0) _along = 0.0;
339 _crowd.step(step);
340 _crowdAge += step;
341 if (_crowdAge > 12.0) {
342 _crowd = _Crowd(8, 6.0, 4.0);
343 _crowdAge = 0.0;
344 }
345 _place();
346 }
349 List<DemoControl> controls(DemoContext context) => <DemoControl>[
350 ToggleControl(
351 'Break the wall (rebake its tiles)',
352 value: () => broken,
353 onChanged: (bool v) {
354 broken = v;
355 if (v) {
356 _breakWall();
357 _scene.remove(_door);
358 } else {
359 _mendWall();
360 _scene.add(_door);
361 }
362 _along = 0.0;
363 },
364 ),
365 ToggleControl(
366 'Show the polygons',
367 value: () => showMesh,
368 onChanged: (bool v) => showMesh = v,
369 ),
370 ];
373 void verify(Scene scene, FrameResult frame) {
374 if (frame.drawCalls < 1 || frame.debugLines < 1) {
375 throw StateError('the level or its mesh did not reach the frame');
376 }
377 // Round the wall: complete, bending past its end, longer than straight.
378 final NavMeshRoute round = _bake(broken: false).route(_start, _goal)!;
379 if (!round.complete ||
380 !round.points.any((Vector3 p) => p.z.abs() > 4.0) ||
381 round.length <= _start.distanceTo(_goal) + 1.0) {
382 throw StateError('the route does not go round the wall');
383 }
384 // A hole baked tile by tile is the hole baked whole, and walked through.
385 final NavMesh mended = _bake(broken: false);
386 final NavMesh holed = mended.rebake(
387 _brushes(broken: true),
388 minX: -6.3,
389 minZ: -1.0,
390 maxX: -5.7,
391 maxZ: 1.0,
392 );
393 final NavMesh whole = NavMesh.bake(
394 _brushes(broken: true),
395 settings: _config,
396 lattice: mended.lattice,
397 );
398 if (holed.digest != whole.digest) {
399 throw StateError('the rebaked tiles differ from a whole bake');
400 }
401 if (holed.route(_start, _goal)!.points.length != 2) {
402 throw StateError('the route does not take the hole');
403 }
404 // The ledge is reached by a jump, and not at all on foot.
405 if (_jump.jumps.isEmpty || !_jump.complete) {
406 throw StateError('no jump onto the ledge');
407 }
408 if (_jumpMesh.route(_below, _onLedge)!.complete) {
409 throw StateError('the ledge should not be walked onto');
410 }
411 // Eight bodies crossing for ten seconds never come closer than two
412 // radii, give or take a centimetre.
413 final _Crowd crowd = _Crowd(8, 6.0, 4.0);
414 var least = double.infinity;
415 for (var i = 0; i < 600; i++) {
416 crowd.step(1 / 60);
417 least = math.min(least, crowd.closest());
418 }
419 if (least < 2.0 * _Crowd.radius - 0.01) {
420 throw StateError('two of the crowd overlapped: $least m apart');
421 }
422 }
423}
425/// A `Vector4` holding a colour sRGB-encoded, as the linear colour it names.
426LinearColor _fromSrgb(Vector4 c) => LinearColor.fromSrgb(c.x, c.y, c.z, c.w);