Behavior trees (BTs) have been gaining popularity among game developers very steadily.  Games such as 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 tutorial, we will look at the basics of a behavior tree and its implementation.  Over the last decade, BTs have become the pattern of choice for many developers when it comes to implementing behavioral rules for their AI agents.

This tutorial is an excerpt taken from the book 'Unity 2017 Game AI programming - Third Edition' written by Raymundo Barrera, Aung Sithu Kyaw, and Thet Naing Swe.

Note: You need to have Unity 2017 installed on a system that has either Windows 7 SP1+, 8, 10, 64-bit versions or Mac OS X 10.9+.

Let's first have a look at the basics of behavior trees.

Learning the basics of behavior trees

Behavior trees got their name from their hierarchical, branching system of nodes with a common parent, known as the root. Behavior trees mimic the real thing they are named after—in this case, trees, and their branching structure. If we were to visualize a behavior tree, it would look something like the following figure:

Of course, behavior trees can be made up of any number of nodes and child 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 them, a BT's flow is defined strictly by each node's order within the larger hierarchy. A BT begins evaluating from the top of the tree (based on the preceding visualization), 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.

Evaluating the existing solutions - Unity Asset store and others

The Unity asset store is an excellent resource for developers. Not only are you able to purchase art, audio, and other kinds of assets, but it is also populated with a large number of plugins and frameworks. Most relevant to our purposes, there are a number of behavior tree plugins available on the asset store, ranging from free to a few hundred dollars. Most, if not all, provide some sort of GUI to make visualizing and arranging a fairly painless experience.

There are many advantages of going with an off-the-shelf solution from the asset store. Many of the frameworks include advanced functionality such as runtime (and often visual) debugging, robust APIs, serialization, and data-oriented tree support. Many even include sample leaf logic nodes to use in your game, minimizing the amount of coding you have to do to get up and running.

Some other alternatives are Behavior Machine and Behavior Designer, which offer different pricing tiers (Behavior Machine even offers a free edition) and a wide array of useful features. Many other options can be found for free around the web as both generic C# and Unity-specific implementations. Ultimately, as with any other system, the choice of rolling your own or using an existing solution will depend on your time, budget, and project.

Implementing a basic behavior tree framework

Our example focuses on simple logic to highlight the functionality of the tree, rather than muddy up the example with complex game logic. The goal of our example is to make you feel comfortable with what can seem like an intimidating concept in game AI, and give you the necessary tools to build your own tree and expand upon the provided code if you do so.

Implementing a base Node class

There is a base functionality that needs to go into every node. Our simple framework will have all the nodes derived from a base abstract Node.cs class. This class will provide said base functionality or at least the signature to expand upon that functionality:

using UnityEngine; 
using System.Collections; 
 
[System.Serializable] 
public abstract class Node { 
 
    /* Delegate that returns the state of the node.*/ 
    public delegate NodeStates NodeReturn(); 
 
    /* The current state of the node */ 
    protected NodeStates m_nodeState; 
 
    public NodeStates nodeState { 
        get { return m_nodeState; } 
    } 
 
    /* The constructor for the node */ 
    public Node() {} 
 
    /* Implementing classes use this method to evaluate the desired set of conditions */ 
    public abstract NodeStates Evaluate(); 
 
}

The class is fairly simple. Think of Node.cs as a blueprint for all the other node types to be built upon. We begin with the NodeReturn delegate, which is not implemented in our example, but the next two fields are. However, m_nodeState is the state of a node at any given point. As we learned earlier, it will be either FAILURE, SUCCESS, or RUNNING. The nodeState value is simply a getter for m_nodeState since it is protected and we don't want any other area of the code directly setting m_nodeState inadvertently.

Next, we have an empty constructor, for the sake of being explicit, even though it is not being used. Lastly, we have the meat and potatoes of our Node.cs class—the Evaluate() method. As we'll see in the classes that implement Node.cs, Evaluate() is where the magic happens. It runs the code that determines the state of the node.

Extending nodes to selectors

To create a selector, we simply expand upon the functionality that we described in the Node.cs class:

using UnityEngine; 
using System.Collections; 
using System.Collections.Generic; 
 
public class Selector : Node { 
    /** The child nodes for this selector */ 
    protected List<Node> m_nodes = new List<Node>(); 
 
 
    /** The constructor requires a lsit of child nodes to be  
     * passed in*/ 
    public Selector(List<Node> nodes) { 
        m_nodes = nodes; 
    } 
 
    /* If any of the children reports a success, the selector will 
     * immediately report a success upwards. If all children fail, 
     * it will report a failure instead.*/ 
    public override NodeStates Evaluate() { 
        foreach (Node node in m_nodes) { 
            switch (node.Evaluate()) { 
                case NodeStates.FAILURE: 
                    continue; 
                case NodeStates.SUCCESS: 
                    m_nodeState = NodeStates.SUCCESS; 
                    return m_nodeState; 
                case NodeStates.RUNNING: 
                    m_nodeState = NodeStates.RUNNING; 
                    return m_nodeState; 
                default: 
                    continue; 
            } 
        } 
        m_nodeState = NodeStates.FAILURE; 
        return m_nodeState; 
    } 
}

As we learned earlier, selectors are composite nodes: this means that they have one or more child nodes. These child nodes are stored in the m_nodes List<Node> variable. Although it's conceivable that one could extend the functionality of this class to allow adding more child nodes after the class has been instantiated, we initially provide this list via the constructor.

The next portion of the code is a bit more interesting as it shows us a real implementation of the concepts we learned earlier. The Evaluate() method runs through all of its child nodes and evaluates each one individually. As a failure doesn't necessarily mean a failure for the entire selector, if one of the children returns FAILURE, we simply continue on to the next one. Inversely, if any child returns SUCCESS, then we're all set; we can set this node's state accordingly and return that value. If we make it through the entire list of child nodes and none of them have returned SUCCESS, then we can essentially determine that the entire selector has failed and we assign and return a FAILURE state.

Moving on to sequences

Sequences are very similar in their implementation, but as you might have guessed by now, the Evaluate() method behaves differently:

using UnityEngine; 
using System.Collections; 
using System.Collections.Generic; 
 
public class Sequence : Node { 
    /** Children nodes that belong to this sequence */ 
    private List<Node> m_nodes = new List<Node>(); 
 
    /** Must provide an initial set of children nodes to work */ 
    public Sequence(List<Node> nodes) { 
        m_nodes = nodes; 
    } 
 
    /* If any child node returns a failure, the entire node fails. Whence all  
     * nodes return a success, the node reports a success. */ 
    public override NodeStates Evaluate() { 
        bool anyChildRunning = false; 
         
        foreach(Node node in m_nodes) { 
            switch (node.Evaluate()) { 
                case NodeStates.FAILURE: 
                    m_nodeState = NodeStates.FAILURE; 
                    return m_nodeState;                     
                case NodeStates.SUCCESS: 
                    continue; 
                case NodeStates.RUNNING: 
                    anyChildRunning = true; 
                    continue; 
                default: 
                    m_nodeState = NodeStates.SUCCESS; 
                    return m_nodeState; 
            } 
        } 
        m_nodeState = anyChildRunning ? NodeStates.RUNNING : NodeStates.SUCCESS; 
        return m_nodeState; 
    } 
}

The Evaluate() method in a sequence will need to return true for all the child nodes, and if any one of them fails during the process, the entire sequence fails, which is why we check for FAILURE first and set and report it accordingly. A SUCCESS state simply means we get to live to fight another day, and we continue on to the next child node. If any of the child nodes are determined to be in the RUNNING state, we report that as the state for the node, and then the parent node or the logic driving the entire tree can evaluate it again.

Implementing a decorator as an inverter

The structure of Inverter.cs is a bit different, but it derives from Node, just like the rest of the nodes. Let's take a look at the code and spot the differences:

using UnityEngine; 
using System.Collections; 
 
public class Inverter : Node { 
    /* Child node to evaluate */ 
    private Node m_node; 
 
    public Node node { 
        get { return m_node; } 
    } 
 
    /* The constructor requires the child node that this inverter decorator 
     * wraps*/ 
    public Inverter(Node node) { 
        m_node = node; 
    } 
 
    /* Reports a success if the child fails and 
     * a failure if the child succeeds. Running will report 
     * as running */ 
    public override NodeStates Evaluate() { 
        switch (m_node.Evaluate()) { 
            case NodeStates.FAILURE: 
                m_nodeState = NodeStates.SUCCESS; 
                return m_nodeState; 
            case NodeStates.SUCCESS: 
                m_nodeState = NodeStates.FAILURE; 
                return m_nodeState; 
            case NodeStates.RUNNING: 
                m_nodeState = NodeStates.RUNNING; 
                return m_nodeState; 
        } 
        m_nodeState = NodeStates.SUCCESS; 
        return m_nodeState; 
    } 
}

As you can see, since a decorator only has one child, we don't have List<Node>, but rather a single node variable, m_node. We pass this node in via the constructor (essentially requiring it), but there is no reason you couldn't modify this code to provide an empty constructor and a method to assign the child node after instantiation.

The Evalute() implementation implements the behavior of an inverter.  When the child evaluates as SUCCESS, the inverter reports a FAILURE, and when the child evaluates as FAILURE, the inverter reports a SUCCESS. The RUNNING state is reported normally.

Creating a generic action node

Now we arrive at ActionNode.cs, which is a generic leaf node to pass in some logic via a delegate. You are free to implement leaf nodes in any way that fits your logic, as long as it derives from Node. This particular example is equal parts flexible and restrictive. It's flexible in the sense that it allows you to pass in any method matching the delegate signature, but is restrictive for this very reason—it only provides one delegate signature that doesn't take in any arguments:

using System; 
using UnityEngine; 
using System.Collections; 
 
public class ActionNode : Node { 
    /* Method signature for the action. */ 
    public delegate NodeStates ActionNodeDelegate(); 
 
    /* The delegate that is called to evaluate this node */ 
    private ActionNodeDelegate m_action; 
 
    /* Because this node contains no logic itself, 
     * the logic must be passed in in the form of  
     * a delegate. As the signature states, the action 
     * needs to return a NodeStates enum */ 
    public ActionNode(ActionNodeDelegate action) { 
        m_action = action; 
    } 
 
    /* Evaluates the node using the passed in delegate and  
     * reports the resulting state as appropriate */ 
    public override NodeStates Evaluate() { 
        switch (m_action()) { 
            case NodeStates.SUCCESS: 
                m_nodeState = NodeStates.SUCCESS; 
                return m_nodeState; 
            case NodeStates.FAILURE: 
                m_nodeState = NodeStates.FAILURE; 
                return m_nodeState; 
            case NodeStates.RUNNING: 
                m_nodeState = NodeStates.RUNNING; 
                return m_nodeState; 
            default: 
                m_nodeState = NodeStates.FAILURE; 
                return m_nodeState; 
        } 
    } 
}

The key to making this node work is the m_action delegate. For those familiar with C++, a delegate in C# can be thought of as a function pointer of sorts. You can also think of a delegate as a variable containing (or more accurately, pointing to) a function. This allows you to set the function to be called at runtime. The constructor requires you to pass in a method matching its signature and is expecting that method to return a NodeStates enum. That method can implement any logic you want, as long as these conditions are met. Unlike other nodes we've implemented, this one doesn't fall through to any state outside of the switch itself, so it defaults to a FAILURE state. You may choose to default to a SUCCESS or RUNNING state, if you so wish, by modifying the default return.

You can easily expand on this class by deriving from it or simply making the changes to it that you need. You can also skip this generic action node altogether and implement one-off versions of specific leaf nodes, but it's good practice to reuse as much code as possible. Just remember to derive from Node and implement the required code!

We learned basics of how a behavior tree works, then we created a sample behavior tree using our framework. If you found this post useful and want to learn other concepts in Behavior trees, be sure to check out the book 'Unity 2017 Game AI programming - Third Edition'.

AI for game developers: 7 ways AI can take your game to the next level

Techniques and Practices of Game AI