Behavior trees (BTs) have been gaining popularity among game developers very steadily. Over the last decade, BTs have become the pattern of choice for many AAA studios when it comes to implementing AI for their agents. Games like Halo and Gears of War are among the more famous franchises to make extensive use of BTs. An abundance of computing power in PCs, gaming consoles, and mobile devices has made them a good option for implementing AI in games of all types and scopes.
In this chapter, we will cover the following topics:
- The basics of a behavior tree
- The benefits of using existing behavior tree solutions
- How to implement our own behavior tree framework
- How to implement a basic tree using our framework
It is called a tree because it is a hierarchical, branching system of nodes with a common parent, known as the root. As you've surely learned from reading this book, by now, behavior trees, too, mimic the real thing they are named after—in this case, trees. If we were to visualize a behavior tree, it would look something like the following figure:
A basic tree structure
Of course, behavior trees can be made up of any number of nodes and children nodes. The nodes at the very end of the hierarchy are referred to as leaf nodes, just like a tree. Nodes can represent behaviors or tests. Unlike state machines, which rely on transition rules to traverse through it, a BT's flow is defined strictly by each node's order within the larger hierarchy. A BT begins evaluating from the top (based on the preceding visualization) of the tree, then continues through each child, which, in turn, runs through each of its children until a condition is met or the leaf node is reached. BTs always begin evaluating from the root node.
The names of the different types of nodes may vary depending on who you ask, and even nodes themselves are sometimes referred to as tasks. While the complexity of a tree is dependent entirely upon the needs of the AI, the high-level concepts about how BTs work are fairly easy to understand if we look at each component individually. The following is true for each node regardless of what type of node we're referring to. A node will always return one of the following states:
Due to the potential complexity of a BT, most implementations are asynchronous, which, at least for Unity, means that evaluating a tree will not block the game from continuing other operations. The evaluation process of the various nodes in a BT can take several frames, if necessary. If you had to evaluate several trees on any number of agents at a time, you can imagine how it would negatively affect the performance of the program to have to wait for each of them to return a true or false to the root node. This is why the "running" state is important.
Composite nodes are called so as they have one or more children. Their state is based entirely upon the result of evaluating its children, and while its children are being evaluated, it will be in a "running" state. There are a couple of composite node types, which are mostly defined by how their children are evaluated:
- Sequences: The defining characteristic of a sequence is that the entire sequence of children needs to complete successfully in order for it to evaluate as a success itself. If any of the children at any step of the sequence return false, the sequence itself will report a failure. It is important to note that, in general, sequences are executed from left to right. The following figures show a successful sequence and a failed sequence, respectively:
A successful sequence node
An unsuccessful sequence node
- Selectors: By comparison, selectors are much more forgiving parents to their children nodes. If any one of the children nodes in a selector sequence returns true, the selector says, "eh, good enough!" and returns true immediately, without evaluating any more of its children. The only way a selector node will return false is if all of its children are evaluated and none of them return a success.
Of course, each composite node type has its use depending on the situation. You can think of the different types of sequence nodes as "and" and "or" conditionals.
The biggest difference between a composite node and a decorator node is that a decorator can have exactly one child and one child only. At first, this may seem unnecessary as you would, in theory, be able to get the same functionality by containing the condition in the node itself rather than relying on its child, but the decorator node is special in that it essentially takes the state returned by the child and evaluates the response based on its own parameters. A decorator can even specify how its children are evaluated and how often they are. These are some common decorator types:
- Inverter: Think of the inverter as a NOT modifier. It takes the opposite of the state returned by its child. For example, if the child returns TRUE, the decorator evaluates as FALSE, and vice versa. This is the equivalent of having the
!operator in front of a Boolean in C#. - Repeater: This repeats the evaluation of the child a specified (or infinite) number of times until it evaluates as either TRUE or FALSE as determined by the decorator. For example, you may want to wait indefinitely until a certain condition is met, such as "having enough energy" before a character uses an attack.
- Limiter: This simply limits the number of times a node will be evaluated to avoid getting an agent stuck in an awkward infinite behavior loop. This decorator, in contrast to the repeater, can be used to make sure a character only tries to, for example, kick the door open so many times before giving up and trying something else.
Some decorator nodes can be used for debugging and testing your trees. For example:
- Fake state: This always evaluates true or false as specified by the decorator. This is very helpful for asserting certain behavior in your agent. You can also have the decorator maintain a fake "running" state indefinitely to see how other agents around it will behave, for example.
- Breakpoint: Just like a breakpoint in code, you can have this node fire off logic to notify you via debug logs or other methods that the node has been reached.
These types are not monolithic archetypes that are mutually exclusive. You can combine these types of nodes to suit your needs. Just be careful not to combine too much functionality into one decorator to the point where it may be more efficient or convenient to use a sequence node instead.
We briefly covered leaf nodes earlier in the chapter to make a point about the structure of a BT, but leaf nodes, in reality, can be just about any sort of behavior. They are magical in the sense that they can be used to describe any sort of logic your agent can have. A leaf node can specify a walk function, shoot command, or kick action. It doesn't matter what it does or how you decide to have it evaluate its states, it just has to be the last node in its own hierarchy and return any of the three states a node can return.