flutter3d
Showcase Changelog 62 packages API reference

Behaviour trees

since 1.0.0-rc.1 Simulation, audio and XR

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 parallel node: 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.