Introduction

My name is Szabolcs, and I work as a game programmer at SYNAPSE STUDIO.

In my previous job, I was working on a big AAA game’s NPC AI using Behavior Trees. It was the first time for me to dig into this topic. I learned a lot during this project and enjoyed working on it. With this article, I would like to give a quick introduction to one of the most used game AI solutions: behavior trees.

What is a Behavior Tree

As its name suggests, a behavior tree (let’s shorten it to BT from now on) is a tree of hierarchical nodes that control the decision flow of an AI entity. The leaves of the tree are the actual commands, and the branches are utility nodes that control which commands are going to be executed for the current situation. The trees can be really deep and complex, with nodes that are calling subtrees. Development with BTs is highly iterative; you can start with very simple behavior, then add new branches when you want to deal with specific cases, alternative approaches to achieve a goal, and fallback tactics.

Execution of Behavior Trees

In a simple BT implementation, the system will traverse down the tree every frame from the root, testing each node in its way down to see which is active and needs to be ticked (an action at a leaf node could take multiple frames to finish). This is not an efficient way to do it, but it is easier to explain the flow in this way. Modern game engines such as Unreal Engine have implemented a BT system in a way that it can store the currently processed nodes and can tick them directly, rather than traverse the entire tree at all frames.

Nodes of the BT can have three statuses: Success, Fail and Running. The first two probably need no explanation; these statuses basically report to the parent nodes that the child is finished with their operation with either success or failure. Running means the node is still processing, the result is not yet decided, and it has to be ticked in the next frame again. Let’s see an example that probably many games have: a MoveTo node, which calculates a path and then starts moving the NPC to the desired position while playing an animation. If the pathfinding fails, or during the movement something stops the NPC from reaching the target position, the node reports Fail. If everything goes well, the node will report Running on every tick during the movement and Success when reaching the target position.

There are three main types of BT nodes: Composite, Decorator and Leaf.

Composite

Composites can have one or more child nodes and execute them in order (from left to right). Their status depends entirely on the return value of their child nodes. The most common composite nodes are Sequence and Selector.

Sequence is simply executing each child one after the other. It could execute all of them and return Success or stop when one of the children returns with Fail.

foreach child do
   status = Tick(child)
   if status is Running
                    return Running
   else if status is Fail
                    return Fail
end
return Success

Selector is the opposite, as it executes until only the first child that returns with Success. The selector node reports Fail if all of their child’s executions failed and Success when any of the child succeed.

foreach child do
   status = Tick(child)
   if status is Running
                    return Running
   else if status is Success
                    return Success
end
return Fail

Decorator

Decorator nodes can have exactly one child node. Their function is to either transform the child node’s result, repeat the processing of the child (like a loop) or terminate it. The most common decorator node is an Inverter, that simply inverts the child node’s result: return Success when the child Fails and Fail when the child Succeeds.

Leaf

While Composite and Decorator nodes are used to make decisions, Leaf nodes represent the actual actions. As they are the lowest-level node types, they cannot have any child nodes. Leaf nodes are game- and character-specific actions that make your BT actually do something. An example of a Leaf node would be the MoveTo node that I described earlier.

Blackboard

Blackboards can be imagined as the memory of the AI. Basically, it is a collection of variables that the BT can read from and write to during execution.

We can use our imaginary MoveTo node again as an example. When executing, first it checks if there is any path already generated. If not, do pathfinding and save it; otherwise, start moving. The path points are stored on the Blackboard so it doesn’t have to do pathfinding on every tick. Or we can think bigger and use Blackboard variables to make decisions on the tree: if an AttackTarget variable is set, the BT will control the character to go close to the target and start attacking it. Otherwise, walk on the patrol path. When the player is perceived during patrol, AttackTarget gets set, and on next the BT tick, it will be attacked. When line of sight to the player is lost or the player defeated, the variable gets cleared and the patrol continues.

Conclusion

Being able to create complex behaviors by only implementing the NPC’s actions and designing the tree structure made behavior trees popular. Game engines such as Unreal Engine usually have a graph editor for BT with dragging and dropping nodes, which makes it visually intuitive and easy to design, test, and debug. With the possibility to have sub-trees, this behavior creation method becomes even more modular and reusable.