Skip to content

About

A C++11 implementation of the Behaviour Tree data structure/design pattern

Topics

Resources

Stars

3 stars

Watchers

0 watching

Forks

Latest commit

 

History

23 Commits

Folders and files

Repository files navigation

A C++11 implementation of the Behaviour Tree data structure/design pattern.

The behaviour tree design pattern fills the same niche as state machines, but it has several advantages over them:

  • it is easier to maintain and understand
  • it can be multithreaded

The Behaviour tree (BT) is a decision tree where branching decisions are
based on user defined environment variables. A BT is comparable in some ways to an abstract syntax tree. Because it features nodes that allow branching, loops, delays and actions, it is Turing complete. This particular implementation allows to run subtrees in a separate thread in a fashion similar to futures.

The main disadvantage of BT compared to state machines is they can be less responsive than state machines because the tree needs to be constantly traversed. This reason makes it generally suitable for soft real time only.

This implementation is header-only: src/BehaviourTree.h plus the thread-safe stack it uses, src/ConcurrentStack.h, making it very easy to integrate.

Each node starts with a NOTRUN status, and has a run() method that returns to its parent node a final status. The final status can be either SUCCESS, FAILURE, or ERROR. Additionally, asynchronous nodes can have an intermediate RUNNING status indicating to their parent nodes that they cannot return a final state as yet.

BehaviourTree::tick() runs the tree once and may return RUNNING; BehaviourTree::run() ticks until the status is no longer RUNNING. A node that returned a final status is marked completed: when a RUNNING branch is ticked again, its completed children are not run again and their last status is reused. Nodes created with dontSkip = true run on every tick. Call BehaviourTree::reset() to run a completed tree again from scratch.

Every node has a name (getName()), which defaults to its type ("Sequence", "Repeat"…) and can be passed as the last constructor argument. The name is particularly useful when you need to trace the running of the Behaviour Tree.

Building a tree

Nodes can be declared by the caller, who must keep them alive while the tree is used:

BehaviourTree tree;
BehaviourTree::Sequence sequence;
BehaviourTree::Condition ready([&]() { return robot.ready(); });
BehaviourTree::Action work([&]() { return robot.work(); });
sequence.addChildren({ &ready, &work });
tree.setRootChild(&sequence);

or created by the tree's builders. The tree then owns them, and they live as long as it does:

BehaviourTree tree;
tree.setRootChild(tree.repeat(10, tree.sequence({
    tree.condition([&]() { return robot.ready(); }, "ready"),
    tree.action([&]() { return robot.work(); }, "work"),
    tree.compute(count, [&]() { return count + 1; })
})));

There is one builder per node type: sequence, select, invert, succeed, fail, repeat, repeatUntil, async, sleep, condition, isTrue (a Condition on a bool variable), action, set (fixed value), compute (value computed when the node runs), isNull, push, pop, stackIsEmpty and getStack; make<NodeType>(args…) creates any other node type, including your own. Both styles can be mixed in the same tree.

Debugging a tree

validate() checks the structure of a tree and returns one message per problem, prefixed with the path of the node (an empty list means the tree is well formed). It reports a missing root child, null children, empty composites, decorators without a child, a Sleep with a child (it ignores it), cycles, and nodes placed under several parents (they would share their state):

for (const std::string& problem : tree.validate())
    std::cerr << problem << '\n';   // e.g. "game cycle/charge: composite node has no children"

print(out) writes the tree structure with each node's last status, for instance after a tick():

choose [RUNNING]
├── no [FAILURE, completed]
├── busy [RUNNING]
└── never reached [NOTRUN]

The tree is drawn with UTF-8 box-drawing characters.

setTracer(tracer) calls tracer(node, status, depth) after every node execution. BehaviourTree::streamTracer(out) is a ready-made, thread-safe tracer that writes one indented name -> STATUS line per execution; children are reported before their parent, and completed nodes that are skipped do not appear. Call setTracer once the tree is assembled. Nodes run by Async report from another thread, so a custom tracer must be thread-safe if the tree uses Async. Give nodes meaningful names to get readable traces. Statuses can be written to a stream (std::cout << status) or converted with BehaviourTree::toString(status).

Custom nodes only implement run(). Their parents call execute(), which runs the node and reports it to the tracer. A custom composite or decorator should call execute() on its children and override childNodes(), so that tracing, print() and validate() can see them.

Detailed description

Branching type nodes

Composite: This type of Node follows the Composite Pattern, containing a list of 1...n children Nodes.

Sequence: Composite node. If one child fails, then the entire sequence fails and quits immediately.
The Status is SUCCESS only if all children succeed. Equivalent of a logical AND. A child returning RUNNING or ERROR also stops the sequence, which returns that status.

Select: Composite Node. If one child succeeds, the Select succeeds and quits immediately. The status is FAILURE only if all children fail. Equivalent of a logical OR. A child returning RUNNING or ERROR also stops the select, which returns that status.

DecoratorNode: A DecoratorNode adds a functionality to its child node. Function is either to transform the Status it receives from the child, to terminate the child, or repeat the processing of the child.

Root: A Decorator at the root of the Behaviour Tree.

Invert: A Decorator that swaps SUCCESS and FAILURE from its child. RUNNING and ERROR are passed through.

Succeed: A Decorator that returns SUCCESS whether the child succeeds or fails (RUNNING and ERROR are passed through). These are useful in cases where you want to process a branch of a tree where a Status::FAILURE is expected or anticipated, but you don’t want to abandon the processing of a sequence that branch sits on.

Fail: A Decorator that is the opposite of a Succeed node, returning FAILURE whether the child succeeds or fails (RUNNING and ERROR are passed through).

A decorator without a child returns ERROR.

Repeat: This Decorator will reprocess its child node each time its child returns SUCCESS or FAILURE. These are often used at the root of the tree, to make the tree run continuously. Repeat(n) runs its child n times, then returns the child's last status; with a negative count (the default) it never terminates. RUNNING and ERROR from the child are returned immediately, and the iteration count is kept until the next tick.

RepeatUntil: This Decorator will continue to reprocess its child until the child finally returns the expected status, at which point the repeater will return the status to its parent. The expected status must be either SUCCESS or FAILURE; the constructor throws std::invalid_argument otherwise.

Async: This Decorator executes its child asynchronously in a separate thread, yielding RUNNING until it gets a final Status.

Sleep: Inserts a delay in msec (1 msec by default) and returns Status SUCCESS. It derives from DecoratorNode but ignores any child.

Memory type nodes

These nodes persist data between node runs. There are two sorts of memory: a thread safe stack and variables.

SetVar: assign a value to a variable, optionally computing the value when run

IsNull: return SUCCESS if the object passed in argument is nullptr.

StackNode: base class of the stack nodes below. It holds a reference to a ConcurrentStack<T*> owned by the caller, so several nodes can share the same stack.

Push: push a pointer on the stack.

Pop: pop a pointer from the stack into a variable; return FAILURE if the stack is empty.

StackIsEmpty: return SUCCESS if the stack is empty, FAILURE otherwise.

GetStack: replace the stack with a copy of another stack, optionally pushing an extra pointer on top.

Function leaves

Condition: return SUCCESS when a user predicate (std::function<bool()>) holds, FAILURE otherwise.

Action: return the Status computed by a user function (std::function<Status()>).

Tests

make test

or, with CMake:

cmake -S . -B build && cmake --build build && (cd build && ctest)

src/Nodes_test is the test suite of BehaviourTree.h: every node type, the completion and dontSkip semantics, reset(), RUNNING propagation, Async threading and the stack nodes. It has no external dependency; pass a substring to run only the matching tests, e.g. ./src/Nodes_test Repeat. The other programs are described below.

Coffee shop example

The executable src/CoffeeShop_test serves a queue of two customers with one behaviour tree, and demonstrates the debugging tools. The shop has filter coffee and tea, its espresso machine is broken, and only one portion of milk is left:

  • customer 1 asks for a coffee with milk, and gets a coffee with milk;
  • customer 2 asks for an espresso with milk. The espresso is unavailable, so the shop prepares tea instead; the milk has run out, so the tea is served without milk.
serve every customer               Repeat(2)
└── serve one customer             Sequence
    ├── take next customer
    ├── prepare a drink            Select
    │   ├── requested drink        (a custom Node subclass)
    │   └── tea instead
    ├── milk                       Select
    │   ├── no milk wanted?
    │   ├── add milk
    │   └── without milk
    └── serve

The program runs the scenario, then validates and prints the tree, then runs the scenario again with streamTracer. The trace shows, for instance, how the second customer gets tea:

[espresso] unavailable, trying tea
      requested drink -> FAILURE
[tea] prepared
      tea instead -> SUCCESS
    prepare a drink -> SUCCESS

Run it with:

make
./src/CoffeeShop_test

Robot enclosure game

src/RealtimeRobot is a small keyboard-controlled game backed by a behavior tree. The arena is 40 columns wide by 20 rows high, including the # boundary. The three-cell opening is in the middle of the south wall; groups of # inside the arena are obstacles. The robot is shown as o.

Build and run it with:

make
./src/RealtimeRobot

Use i, j, k, l or the arrow keys to move north, west, south, and east. The robot moves one cell every 100 ms and loses one battery percentage point per cell. s stops it; obstacles and walls stop it automatically. At 0%, press c to recharge, then press a direction to move again. Escape through the opening in the south wall to win, or press q to quit. When several keys are typed within the same 100 ms cycle, only the latest one is applied.

The game logic is written as a behavior tree, not as C++ control flow or an external state machine. C++ code is limited to the leaves: reading the terminal, drawing, and the arena geometry (isExit, isObstacle). Every decision is a Condition, and every state change is a SetVar. The tree is assembled with the builders described above, so it owns all of its nodes:

RepeatUntil(SUCCESS)                         one iteration per game cycle
└── Sequence
    ├── Async → Succeed → RepeatUntil(FAILURE)          reader thread
    │                     └── Sequence: Action(read one key) → Push(key)
    ├── Succeed → Sequence                               handle the command
    │   ├── Pop(key)                                     FAILURE: no key
    │   ├── GetStack(empty)                              the latest key wins
    │   └── Select
    │       ├── key q? → SetVar(quit)
    │       ├── key s? → SetVar(stopped) → SetVar(message)
    │       ├── key c? → Select(battery 0? → SetVar(charge requested) | SetVar(message))
    │       ├── battery 0? → SetVar(stopped) → SetVar(message)
    │       └── key i/j/k/l? → SetVar(dx, dy) → SetVar(moving) → SetVar(message)
    ├── Succeed → Select                                 prioritized behavior
    │   ├── charge requested?
    │   │   → Repeat(100) → Sequence(SetVar(battery + 1) → Action(draw) → Sleep(10 ms))
    │   │   → SetVar(charge done) → SetVar(message)
    │   └── moving? → Select
    │       ├── exit ahead? → SetVar(position) → SetVar(finished) → SetVar(message)
    │       ├── obstacle ahead? → SetVar(stopped) → SetVar(message)
    │       └── SetVar(battery - 1) → SetVar(position) → SetVar(steps + 1)
    │           → Succeed(every 10 steps? → SetVar(message))
    │           → Succeed(battery 0? → SetVar(stopped) → SetVar(message))
    ├── Action(draw arena)
    ├── Sleep(100 ms)
    └── Select(finished? | quit?)

RepeatUntil runs game cycles until the exit condition succeeds. The selectors express priorities rather than transitions between named states, and Succeed marks branches where "nothing to do" is not a failure. Async reads the keyboard in a separate thread; the commands it decodes reach the game through a ConcurrentStack with Push and Pop. Repeat(100) charges the battery one percentage point at a time, redrawing the gauge, so the keyboard is not read during the one-second recharge. This is a real-time-style demonstration, not a hard real-time guarantee.

Other options:

  • ./src/RealtimeRobot --self-test validates the tree structure and checks the game logic without a terminal;
  • ./src/RealtimeRobot --print-tree prints the complete game tree;
  • ./src/RealtimeRobot --trace trace.log plays while writing the execution trace to trace.log (follow it from another terminal with tail -f trace.log).

Published under MIT License.

About

A C++11 implementation of the Behaviour Tree data structure/design pattern

Topics

Resources

Stars

3 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages