Scripting, Part 5: Behaviour Tree Builder - Language Design

Today I'd like to showcase another use of scripting: data driven object creation. So today, we are designing a language that creates behaviour trees.

Behaviour trees

This post is not really about how behaviour trees work or how to use them. If you are interested, I highly recommend reading this article by Chris Simpson, developer of Project Zomboid.

To summarize, behaviour trees are a data structures that control the behaviour of a game entity. They are a very powerful tool, as they naturally encourage divide-and-conquer-style problem solving, back-up plans and prioritization.

Trees are traversed from top to bottom; internal nodes control traversal, while leafs determine actions.
While the available actions will vary with your game, there is a set of basic internal nodes that most behaviour trees will use:

• Sequence nodes execute their children in order, until one of them fails.
• Selector nodes execute their childrem in order, until one of them succeeds.
• Inverter nodes execute their child and invert its result, i.e. they fail if their child succeeds and succeed if their child fails.
• Succeeder nodes execute their child and ignore its result, succeeding when the child finishes.
• Repeater nodes execute their child over and over again.
• Repeat-until-failure nodes execute their child again and again, until it fails.

Finally, there is one type of leaf that is reusable: The Run behaviour node, which allows behaviour trees to recursively call themselves or other trees.

Tree markup

When describing a tree structure, there are essentially three different types of representation: breadth-first, prefix notation, or postfix notation.
Breadth-first is the most intuitive to humans, but also rather inconvenient to generate from an existing tree (it involves a queue and a loop, whereas the other two can be generated with simple recursive functions).
Prefix and postfix are quiet similar to each other, but interpreting prefix notation involves more management code, so we'll be using postfix.

Postfix notation means that a node's children are described before the node itself. When applied to an entire tree, this, in turn, means that a tree's leafs are described before the root, so the tree is discribed bottom-up.
For example, if you want to describe a sequence of three actions, that might look something like this:

 Action A
 Action B
 Action C
 Sequence 3

This already hints at what kind of commands our language will use:

• The Action command creates a leaf node. Let's assume there is a finite set of actions that can be adressed by an integer, so the action command will take an integer as an argument.
• The RunBehaviour command creates a run-behaviour node. Again, we'll assume that all defined behaviour trees can be id'd by an integer, so this will take an integer argument as well.
• The Sequence command will take the length of the sequence as an argument and combine the nodes described last into a sequence node.
• The Selector command will also take the number of children as an argument and combine the apropriate number of nodes into a selector node.
• The Inverter, Succeeder, Repeater and RepeatUntilFail commands do not take any arguments. They just create the respective node with the previous node as a child.

Additionally, the End command aborts execution and returns the node that was defined last as the root node of the tree. As the descriptions imply, we're going to use a last-in-first-out data structure to store previously defined nodes, i.e. a stack.

In the next post I'll walk you through implementing a concrete interpreter for this language.