Behaviour trees
Open the live demo · Read the source · View on GitHub
A brain written in Dart is quick to start with and hard to change later: every
new idea means another branch in code that only a programmer can edit. A
behaviour tree puts the decisions in a document. BehaviorTree.read turns
JSON into a tree, BehaviorBrain runs it for an actor, and everything the
tree remembers lives on the actor's entity, where a save or a rewind finds it.
On this page a red guard walks between two posts on the far side of a wall. The blue target drifts along the near side. While the wall hides it, the guard patrols. When the target comes out past the wall's end, the guard sees it and gives chase. The coloured strokes over the guard are the path the tree took, one per node, and the line runs to where its leaf is heading.
Step 1: The tree as a document #
Composites are the tree's own: sequence, selector, utility, invert,
alwaysSucceed and cooldown. A selector asks its children in order, from
the top, every time it is ticked, so the chase is asked about first on every
step. A sequence resumes where it was, so the patrol keeps its place: after
waiting at post a, it walks to b rather than starting over. A utility
node scores its options instead of taking them in order, each score being a
weight times its considerations, and gives the running option a little
inertia so it does not flicker between two near ties.
/// A selector asks its children in order, from the top, every time it is
/// ticked: chase if the target can be seen, otherwise patrol. A sequence
/// resumes where it was, so the patrol keeps its place between ticks.
static const Map<String, Object?> document = <String, Object?>{
'kind': 'selector',
'name': 'guard',
'children': <Object?>[
<String, Object?>{
'kind': 'sequence',
'name': 'chase',
'children': <Object?>[
<String, Object?>{'kind': 'seesFocus'},
<String, Object?>{'kind': 'goToFocus', 'within': 1.2},
],
},
<String, Object?>{
'kind': 'sequence',
'name': 'patrol',
'children': <Object?>[
<String, Object?>{'kind': 'goTo', 'key': 'a'},
<String, Object?>{'kind': 'wait', 'seconds': 0.5},
<String, Object?>{'kind': 'goTo', 'key': 'b'},
<String, Object?>{'kind': 'wait', 'seconds': 0.5},
],
},
],
};
Step 2: Read it #
Leaves and considerations are looked up by kind in BehaviorKinds. The
standard ones are what an actor's Mind can already do: goTo a point on the
board, goToFocus, wait, seesFocus, check and set a board value, and
a few more. A game registers its own kinds next to them. A document that does
not read gives no tree. It gives every problem instead, each with where it is,
such as root.children[2]: no leaf kind "fly", so it can be fixed in one pass.
/// Leaves are found by kind in `BehaviorKinds`; the standard ones are
/// what an actor's `Mind` already does. A document with problems gives no
/// tree and every problem with where it is.
static BehaviorTree readTree() {
final BehaviorTreeRead read = BehaviorTree.read(document, BehaviorKinds());
final BehaviorTree? tree = read.tree;
if (tree == null) throw FormatException(read.problems.join('\n'));
return tree;
}
Step 3: An actor that runs it #
BehaviorBrain is the brain, and it keeps nothing. The running path, each
node's memory, cooldowns, the tree's clock and what the actor last heard or
felt are on a Blackboard component of its entity. Here the board is given
the two posts before the first step. Because the board is a component, a
snapshot taken halfway through a wait brings back the same wait, half done. A
board left by a different tree, told apart by the tree's digest, starts again
instead of resuming at node numbers that now mean something else.
/// A floor, a wall the guard cannot see through, and the guard on the far
/// side of it. What the tree knows lives on a `Blackboard` component of
/// the guard's entity, here its two posts; the brain keeps nothing.
static (ActorSystem, Actor) _world() {
final world = CollisionWorld()
..addBox(Vector3(0.0, -0.5, 0.0), Vector3(30.0, 1.0, 20.0))
..addBox(Vector3(0.0, 1.0, 0.0), Vector3(10.0, 2.0, 0.4))
..update();
final system = ActorSystem(world: world, random: GameRandom(1));
final Actor guard = system.spawn(
body: CharacterController(world: world, position: Vector3(-4, 0.9, -3)),
brain: BehaviorBrain(readTree()),
name: 'guard',
);
system.entities.set(
guard.entity,
Blackboard(
values: <String, Object?>{
'a': <double>[-4.0, 0.9, -3.0],
'b': <double>[4.0, 0.9, -3.0],
},
),
);
return (system, guard);
}
Step 4: Step #
The tree is ticked in the fixed step, through ActorSystem.step. The focus is
the point the actors pay attention to, here the target. seesFocus asks for a
clear line from the guard's eyes to it, against the level only.
/// One fixed step: the system thinks for every actor, the tree ticks from
/// its root, and the leaf it reaches acts.
static void _stepOnce(ActorSystem system, Vector3 target) {
system
..beginStep()
..step(_step, focus: target);
}
Step 5: The overlay #
BehaviorOverlay reads every actor's board and hands lines to the renderer
through addDebugLines. Amber is a node still running, green one that
succeeded, red one that failed. describe() gives the same path by name, as in
guard: guard › chase › goToFocus (running). The overlay never makes a board,
so turning it on cannot change what the next snapshot holds. The dungeon draws
it, names and all, on the B key.
// The overlay reads the boards and never makes one, so turning it on
// cannot change what a snapshot holds.
_lines = context.renderer.addDebugLines((DebugDraw lines) {
if (overlay) BehaviorOverlay(_system).draw(lines);
});
Step 6: What has to hold #
A fresh guard, with the target hidden behind the wall for a second, has to be
on the patrol branch, at a goTo or a wait. Five steps after the target
appears past the wall's end, the selector has to have picked the chase, with
goToFocus as the leaf. The overlay has to draw one stroke for each node on
that path and one line to the goal.
final (ActorSystem system, Actor guard) = _world();
String leaf() => BehaviorBrain.pathOf(guard).last.kind;
String branch() => BehaviorBrain.pathOf(guard)[1].label;
// Hidden behind the wall: the guard patrols.
final Vector3 hidden = Vector3(0.0, 0.9, 4.0);
for (var i = 0; i < 60; i++) {
_stepOnce(system, hidden);
}
if (branch() != 'patrol' || !<String>{'goTo', 'wait'}.contains(leaf())) {
throw StateError('not patrolling: ${BehaviorOverlay(system).describe()}');
}
// Out past the wall's end, in sight from anywhere on the patrol: from
// post a, at x = −4, the line to a point four metres behind the wall
// still crosses it, so the point stands a metre behind it, where the
// line from either post passes the wall's end at x = 5.
final Vector3 seen = Vector3(9.0, 0.9, 1.0);
for (var i = 0; i < 5; i++) {
_stepOnce(system, seen);
}
if (branch() != 'chase' || leaf() != 'goToFocus') {
throw StateError('not chasing: ${BehaviorOverlay(system).describe()}');
}
// The overlay draws a stroke per node on the path and a line to the goal.
final DebugDraw lines = DebugDraw();
BehaviorOverlay(system).draw(lines);
if (lines.lineCount != BehaviorBrain.pathOf(guard).length + 1) {
throw StateError('the overlay drew ${lines.lineCount} lines');
}
Note. There is no
parallelnode: one body steers one way, so two leaves that both move it would fight. The names are not printed in this page's viewport, only drawn as strokes;describe()is the way to read them, and the check uses it in its messages. A 600-step trace of a tree's digests agrees across a restore in the tests, but it has been measured on one operating system so far.