Behavior trees arise from the computer game industry as a powerful tool to model the behavior of non-player characters. They have been extensively used in high-profile video games such as Halo and Bioshock. Behavior Trees became popular by being able to create a complex behavior by only programming nodes and then designing a tree structure whose leaf nodes are actions and whose inner nodes determine the decision making.
A behavior tree is graphically represented as a directed tree in which the nodes are classified as root, control flow nodes, or execution nodes. For each pair of connected nodes the outgoing node is called parent and the incoming node is called child. The root has no parent and axactly one child, the control flow nodes have one parent and at least one child, and the execution nodes have one parent and no children. Graphically, the children of a control flow node are placed below it, ordered from left to right.
Some core functionality is common to any type of node in a behaviour tree. This is that they can return one of three statuses.
The first two, as their names suggest, inform their parent that their operation was a success or a failure. The third means that success or failure is not yet determined, and the node is still running. The node will be ticked again next time the tree is ticked, at which point it will again have the opportunity to succeed, fail or continue running. This functionality is the power of behaviour trees, since it allows a node’s processing to persist for many ticks of the game.
There are four diffrent types of nodes.
These are the lowest level node type, and are incapable of having any children. Actions are however the most powerful of node types, as these will be defined and implemented by your game to do the game specific or character specific actions required to make your tree actually do useful stuff.
Conditional nodes test some property of the game. For example in the tree above it tests if the agent has a rigidbody component.
A composite node is a node that can have one or more children. The most commonly used composite node is the Sequence, which simply runs each child in sequence, returning failure at the point any of the children fail, and returning success if every child returned a successful status.
A decorator node, like a composite node, can have a child node. Unlike a composite node, they can specifically only have a single child. Their function is either to transform the result they receive from their child node’s status, to terminate the child, or repeat processing of the child, depending on the type of decorator node.