Behaviour trees: the source
Open the live demo · Read the guide · View on GitHub
Regions the guide quotes: tree (line 44), read (line 72), spawn (line 82), overlay (line 131), step (line 174), check (line 220).
1/// A guard whose mind is a JSON document: patrol between two posts until
2/// the target comes out from behind the wall, then chase it. The overlay
3/// draws the path the tree took, one stroke a node, and a line to where
4/// its leaf is going.
5///
6/// Quoted by `behaviour_trees.md` and shown whole in the Source tab.
7library;
9import 'dart:math' as math;
11import 'package:flutter/foundation.dart' show visibleForTesting;
12import 'package:flutter3d_game/flutter3d_game.dart';
13import 'package:flutter3d_showcase/src/demo/demo.dart';
15/// The `behaviour-trees` page: a guard run by a behaviour tree read from
16/// JSON, and a target behind a wall. Its check is that the guard patrols,
17/// then chases once the target shows, and that the overlay drew the path.
18final class BehaviourTreesDemo extends ShowcaseDemo {
19 late (ActorSystem, Actor) _run;
20 ActorSystem get _system => _run.$1;
21 Actor get _guard => _run.$2;
22 late final MeshNode _guardMesh;
23 late final MeshNode _targetMesh;
24 Registration? _lines;
26 final Vector3 _target = Vector3(0.0, 0.9, 4.0);
27 double _clock = 0.0;
28 double _carry = 0.0;
30 /// Whether the overlay draws the path the tree took this step.
31 bool overlay = true;
33 static const double _step = 1 / 60;
36 void configureView(DemoContext context) {
37 context.orbit
38 ..distance = 18.0
39 ..pitch = 0.8
40 ..yaw = 0.0;
41 context.orbit.target.setValues(0.0, 0.0, 0.0);
42 }
44 /// A selector asks its children in order, from the top, every time it is
45 /// ticked: chase if the target can be seen, otherwise patrol. A sequence
46 /// resumes where it was, so the patrol keeps its place between ticks.
47 static const Map<String, Object?> document = <String, Object?>{
48 'kind': 'selector',
49 'name': 'guard',
50 'children': <Object?>[
51 <String, Object?>{
52 'kind': 'sequence',
53 'name': 'chase',
54 'children': <Object?>[
55 <String, Object?>{'kind': 'seesFocus'},
56 <String, Object?>{'kind': 'goToFocus', 'within': 1.2},
57 ],
58 },
59 <String, Object?>{
60 'kind': 'sequence',
61 'name': 'patrol',
62 'children': <Object?>[
63 <String, Object?>{'kind': 'goTo', 'key': 'a'},
64 <String, Object?>{'kind': 'wait', 'seconds': 0.5},
65 <String, Object?>{'kind': 'goTo', 'key': 'b'},
66 <String, Object?>{'kind': 'wait', 'seconds': 0.5},
67 ],
68 },
69 ],
70 };
72 /// Leaves are found by kind in `BehaviorKinds`; the standard ones are
73 /// what an actor's `Mind` already does. A document with problems gives no
74 /// tree and every problem with where it is.
75 static BehaviorTree readTree() {
76 final BehaviorTreeRead read = BehaviorTree.read(document, BehaviorKinds());
77 final BehaviorTree? tree = read.tree;
78 if (tree == null) throw FormatException(read.problems.join('\n'));
79 return tree;
80 }
82 /// A floor, a wall the guard cannot see through, and the guard on the far
83 /// side of it. What the tree knows lives on a `Blackboard` component of
84 /// the guard's entity, here its two posts; the brain keeps nothing.
85 static (ActorSystem, Actor) _world() {
86 final world = CollisionWorld()
87 ..addBox(Vector3(0.0, -0.5, 0.0), Vector3(30.0, 1.0, 20.0))
88 ..addBox(Vector3(0.0, 1.0, 0.0), Vector3(10.0, 2.0, 0.4))
89 ..update();
90 final system = ActorSystem(world: world, random: GameRandom(1));
91 final Actor guard = system.spawn(
92 body: CharacterController(world: world, position: Vector3(-4, 0.9, -3)),
93 brain: BehaviorBrain(readTree()),
94 name: 'guard',
95 );
96 system.entities.set(
97 guard.entity,
98 Blackboard(
99 values: <String, Object?>{
100 'a': <double>[-4.0, 0.9, -3.0],
101 'b': <double>[4.0, 0.9, -3.0],
102 },
103 ),
104 );
105 return (system, guard);
106 }
109 Scene build(DemoContext context) {
110 _run = _world();
111 MeshNode box(Vector3 at, Vector3 size, Vector4 color, String name) =>
112 MeshNode(
113 DeviceMesh.upload(context.device, CuboidShape(size: size).build()),
114 RenderMaterial(name: name, baseColor: _fromSrgb(color)),
115 name: name,
116 )..setPosition(at.x, at.y, at.z);
117 _guardMesh = box(
118 Vector3.zero(),
119 Vector3(0.7, 1.8, 0.7),
120 Vector4(0.85, 0.3, 0.25, 1.0),
121 'guard',
122 );
123 _targetMesh = MeshNode(
124 DeviceMesh.upload(context.device, SphereShape(segments: 12).build()),
125 RenderMaterial(
126 name: 'target',
127 baseColor: LinearColor.fromSrgb(0.3, 0.6, 0.95, 1.0),
128 ),
129 name: 'target',
130 )..setScale(0.4, 0.4, 0.4);
131 // The overlay reads the boards and never makes one, so turning it on
132 // cannot change what a snapshot holds.
133 _lines = context.renderer.addDebugLines((DebugDraw lines) {
134 if (overlay) BehaviorOverlay(_system).draw(lines);
135 });
136 _place();
137 return Scene()
138 ..ambientIntensity = 0.35 * LightNode.legacyUnit
139 ..add(
140 LightNode(name: 'sun', intensity: 2.5 * LightNode.legacyUnit)
141 ..setLocalForward(Vector3(-0.3, -0.8, -0.4)),
142 )
143 ..add(
144 box(
145 Vector3(0.0, -0.5, 0.0),
146 Vector3(30.0, 1.0, 20.0),
147 Vector4(0.38, 0.4, 0.44, 1.0),
148 'floor',
149 ),
150 )
151 ..add(
152 box(
153 Vector3(0.0, 1.0, 0.0),
154 Vector3(10.0, 2.0, 0.4),
155 Vector4(0.62, 0.58, 0.5, 1.0),
156 'wall',
157 ),
158 )
159 ..add(_guardMesh)
160 ..add(_targetMesh);
161 }
164 void dispose() {
165 _lines?.cancel();
166 }
168 void _place() {
169 final Vector3 at = _guard.position ?? Vector3.zero();
170 _guardMesh.setPosition(at.x, at.y, at.z);
171 _targetMesh.setPosition(_target.x, _target.y, _target.z);
172 }
174 /// One fixed step: the system thinks for every actor, the tree ticks from
175 /// its root, and the leaf it reaches acts.
176 static void _stepOnce(ActorSystem system, Vector3 target) {
177 system
178 ..beginStep()
179 ..step(_step, focus: target);
180 }
183 void update(DemoContext context, double dt) {
184 _clock += dt;
185 // Behind the wall for most of the cycle, out past its end for a while.
186 _target.x = 9.0 * math.sin(_clock * 0.35);
187 _carry += math.min(dt, 0.1);
188 while (_carry >= _step) {
189 _carry -= _step;
190 _stepOnce(_system, _target);
191 }
192 _place();
193 }
196 List<DemoControl> controls(DemoContext context) => <DemoControl>[
197 ToggleControl(
198 'Draw the path the tree took',
199 value: () => overlay,
200 onChanged: (bool v) => overlay = v,
201 ),
202 ToggleControl(
203 'Start again',
204 value: () => false,
205 onChanged: (bool v) {
206 if (!v) return;
207 _run = _world();
208 _clock = 0.0;
209 },
210 ),
211 ];
213 /// The path the guard took last, by name, for a test.
215 List<String> get described => BehaviorOverlay(_system).describe();
218 void verify(Scene scene, FrameResult frame) {
219 if (frame.drawCalls < 1) throw StateError('nothing reached the frame');
220 final (ActorSystem system, Actor guard) = _world();
221 String leaf() => BehaviorBrain.pathOf(guard).last.kind;
222 String branch() => BehaviorBrain.pathOf(guard)[1].label;
224 // Hidden behind the wall: the guard patrols.
225 final Vector3 hidden = Vector3(0.0, 0.9, 4.0);
226 for (var i = 0; i < 60; i++) {
227 _stepOnce(system, hidden);
228 }
229 if (branch() != 'patrol' || !<String>{'goTo', 'wait'}.contains(leaf())) {
230 throw StateError('not patrolling: ${BehaviorOverlay(system).describe()}');
231 }
232 // Out past the wall's end, in sight from anywhere on the patrol: from
233 // post a, at x = −4, the line to a point four metres behind the wall
234 // still crosses it, so the point stands a metre behind it, where the
235 // line from either post passes the wall's end at x = 5.
236 final Vector3 seen = Vector3(9.0, 0.9, 1.0);
237 for (var i = 0; i < 5; i++) {
238 _stepOnce(system, seen);
239 }
240 if (branch() != 'chase' || leaf() != 'goToFocus') {
241 throw StateError('not chasing: ${BehaviorOverlay(system).describe()}');
242 }
243 // The overlay draws a stroke per node on the path and a line to the goal.
244 final DebugDraw lines = DebugDraw();
245 BehaviorOverlay(system).draw(lines);
246 if (lines.lineCount != BehaviorBrain.pathOf(guard).length + 1) {
247 throw StateError('the overlay drew ${lines.lineCount} lines');
248 }
249 }
250}
252/// A `Vector4` holding a colour sRGB-encoded, as the linear colour it names.
253LinearColor _fromSrgb(Vector4 c) => LinearColor.fromSrgb(c.x, c.y, c.z, c.w);