I'm going to cover the implementation of a very useful technique for AI programmers called Behavior Trees (BT for now on). I've been using this technique for the AI in the Android game I'm working on, and found a few quirks in the architecture that made me have to struggle somewhat. Just thought I'd share what I've learnt during the process.
As this is for an Android game, the code is in Java. Even so, it is easily ported to C++, and there are almost no Android specific libraries or function calls to worry about.
What are Behavior Trees?
The internet is crawling with places to find a good theory on what behavior trees are, and how to implement them, for example:
- AIGameDev : Overview; Approaches; Video tutorial part 1, part 2.
- Wikipedia (Not recommended for videogame development, but interesting)
This article assumes you know what a BT is. If not have a look at the mentioned articles. I’m going to work with a system with the following architecture.
It may look complex at a glance, but once we’ve gone over each part you will see like it’s quite understandable, elegant and flexible. At a glance you can see 3 “groups” of classes. The Tasks (yellow), the TaskControllers (blue) and the Decorators (green). We shall consider each of these in turn, and then how they all fit together.
The general idea for the system is that you have a set of modular tasks (MoveTo, FindClosestEnemy, FindFleeDirection, WaitTillArrivedAtDestination…) and you use them to form a BT. The base Task class provides a interface for all these tasks, the leaf tasks are the ones just mentioned, and the parent tasks are the interior nodes that decide which task to execute next.
The tasks have only the logic they need to actually do what is required of them, all the decision logic of whether a task has started or not, if it needs to update, if it has finished with success, etc. is grouped in the TaskController class, and added by composition. This is done for two reasons, one is for elegance when creating new tasks, the other for security when creating new decorators.
The decorators are tasks that “decorate” another class by wrapping over it and giving it additional logic. In our case we use them to give a update speed to a certain task, or to reset it once is done, or similar things. You can read about the Decorator pattern here.
Finally, the Blackboard class is a class owned by the parent AI that every task has a reference to. It works as a knowledge database for all the leaf tasks, and it’s where we keep the data that is generated on one task and needs to be used by another.
All tasks follow the same interface:
As in any BT node, a CheckConditions and a DoAction functions, to check if the node can be updated, and to actually update the node, respectively. The Start and End functions are called just before starting to update the node, and just after finishing the logic of the node.
To be a true interface, the Blackboard member should not be in the class, but for simplicity and ease of use, it’s the perfect place for it. So fuck interfaces then.
Base LeafTask class
The leaf task has a TaskController for the support logic of the class, and implements the GetControl method. It has no more extra logic or methods.
The child classes of the LeafTask class are the ones with the real logic of the system, and each time we want a new behavior we are going to have to create a few. They are building blocks, modular, and they can be combined in different ways to generate different effects. Take for example simplistic Chase and a Flee strategies, they could work like this:
The italics mark the reused leaf nodes in two different sequences of behaviors. That shows how modular leaf nodes can be recycled and used to conform many different behaviors.
Leaf tasks often calculate data needed by other leaf tasks. Instead of making a complex linking of the whole tree of tasks, we just use a common “data dump” for all of them, a Blackboard object shared by all the tasks, that simply has member data used by the different tasks.
Some examples of Leaf Nodes follow.
Parent task require a bit more explanation than leaf tasks, but don’t worry, we’ll work through it step by step. The base class is similar to the LeafTask class:
The ParentTask class has a ParentTaskController, identical to the TaskController for the LeafNode (handles state logic, if it’s ready, finished, ect…) but adds responsibility for the child tasks (a subtasks vector) and the current selected task (curTask).
It also implements the Start and End functions, very similar to the LeafTask. But the big change comes in the DoAction function. Here it updates the child of the parent task acordingly. All Parent tasks have the same process, that can be explained conceptually more or less like this:
- Safety checks to see if we have all the data, and it’s not null
- If the current child task is not started, start it
- Else, if the current child task is finished, finalize it propperly and check if it finished with success or failure. Here is where the different ParentTask differ, on what happens if the child fails or succeeds. (ChildSuceeded and ChildFailed virtual functions)
- Else, the child must be updated, so we call it’s DoAction.
The abstract ChildSuceeded and ChildFailed functions are for the classes derived from ParentTask to specify how they behave when a child ends their execution. We have two distinct cases for this, Sequence and Selector classes.
In a sequence of tasks, if a child ends it’s execution with a failure, we bail and the Sequence ParentTask ends with failure. This makes sense, as sequences are used for example for the Chase explained earlier:
If task 2 fails, we don’t want the ParentTask to continue on to MoveToDestination, as the Destination Vec2 is possibly corrupted, and will result in undefined behavior.
On the other hand if a child finishes with success, we continue onto the next task.
Some code to illustrate this:
The selector chooses one it’s children to update, and if that fails it chooses another until there are no more left. This means that if the current chosen child ends with failure, we choose another. If we can’t choose another, we end with failure. On the other hand, if our child returns with success, we can happily finish with success as well, as we only need one of the children to succeed.
In retrospect, the Sequencer is like a AND gate, and the Selector as a OR gate, only applied to tasks instead of circuits…
Some code then.
The task controller, as mentioned earlier, tracks the state of the Task it is added to. It keeps a reference to the task and acts as a wrapper for said class when dealing with all the “Is it finished? Is it ready to update?” kind of questions.
This code is separated from the actual task for two reasons.
Reason One: Elegance of Design.
Once we separate the state control from the task class, we can create new subtasks paying no mind to the whole mechanism going on in the background to keep our task in harmony with it’s parent and children tasks. In the Task classes we just focus on specifying the specific logic for the task at hand.
Reason Two: Safety in the Decorators
If we take the utility/state logic out of the Task class, we can make all the methods abstract, and when we create the Decorator classes, the compiler checks to see if we have overridden all the abstract functions (if we forget to wrap any of the Task functions in the Decorator, we could introduce subtle but dangerous bugs). If we have the utility functions in the Task class we may or may not remember to make a wrapper for them, and if we have to change the interface of the Task class at some point, we could be in for a hell of pain.
All said, some code on how the task controller works:
Has the done and success flags, and all the utilities related with them.
We add the subtasks vector, and curTask task to the previous responsibilities of the taskController.
The Decorators are used in the BT to add special functionality to any given task. They act as wrappers of the class, calling the class methods and adding the extra functionality where they deem it necessary.
Abstract Decorator Class
A Decorator, as explained in the Decorator Pattern has a reference to the class it “decorates” (in our case private Task task), and also inherits from said class.
Normally, the Decorator adds extra logic in the DoAction method of the task, which is why the base Decorator class presented only overrides the rest of the methods of Task, for simplicity. None the less, if any Decorator subclass needs to override any other method, it can do so with no problem.
Here is the code
Here are some specific examples of Decorators.
Simply checks to see if the task it decorates has finished. If it has, it resets the task to “ready to execute again”.
Updates the task it decorates at a specific speed. This case of Decorator also overrides the Start method.
With all the code mentioned earlier, it’s a little easy to get lost, so here is a reminder of how this is supposed to work. We are going to create a simple BT with just two basic behaviors, Chase and Flee. (This is taken straight from the game code).
The previous code generates the Behavior Tree shown in this diagram.
Behavior trees are a incredibly interesting tool for game AI. They can be applied to many different types of AI and their modularity makes them a blessing when it comes to extending or modifying an existing AI.
I just hope that with this huge post I have provided the necessary tools for someone who is looking for a nice AI technique for his AI to start working and hopefully avoid the pitfalls I had to survive whilst doing this system.
PS: The full code for my game Behavior Tree can be found here.