This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.
In this post, I will talk about my implementation of the behavior tree structure.
Behavior Tree
Ever since its appearance in Halo 2, behavior tree has been a pretty dominant decision-making algorithm in practice. However, there are things that are hard to do well with behavior tree and it is not the only solution to all AI implementations. But because of how it is structured, it can be really easy for engineers and designers to work together to create sophisticated behavior while having the responsibilities separated well.
Behavior tree’s main building blocks are tasks, which can be further separated into conditions, actions, decorators and composites (and maybe services depending on the structure). With these building blocks, we can use a behavior tree to create sophisticated but still pretty readable AI behavior.
Also, while it is called a tree since it has a parent-children tree structure, the structure is actually a directed acyclic graph. below is a behavior tree that I created inside Unreal Engine 4.
Behavior Tree Tasks
There are many different kinds of tasks as mentioned above. While they possess different functionalities, they all derive from the same base class cBTTask. The base class defines the workflow of the tasks. Basically, a task’s parent will call its Run() function, and inside the function, it will call Enter(), Open() (if not opened already), Execute(), Close() (if needs to be closed), and Exit() in that order. We adopt the template design pattern and defer the actual implementation into the derived class’s OnEnter(), OnOpen(), OnExecute(), OnClose(), and OnExit() functions, where the actual logic of specific kinds of tasks takes place.
I am gonna go through some of the common behavior tree tasks below!
Condition Tasks
As the name says, condition tasks are used to check on some conditions and return the result accordingly to determine whether the logic after it might get run or not.
Let’s look at one simple example, which is a condition task simply checking if a blackboard value is within some threshold. This is probably as simple as it can get for a condition task. However, these are the crucial building pieces for a behavior tree.
Action Tasks
Action tasks are responsible for putting an action onto the blackboard which allows the behavior tree to return it to the AI controller, later on, to be scheduled into the action manager.
Let’s look at one simple example, which is just a wait for seconds action task in my engine. The task will create an action that is waiting for a certain amount of time, and simply put it on the blackboard during execution.
Composites
Composite nodes will have some children nodes, and they will run their children nodes and return the status codes in some predefined manners.
Sequencer
A sequencer will try to run all of its children until it reaches one task that returns failure, and then it will return failure to its parent.
Selector
A selector is almost the opposite of a sequencer. A selector will run its children tasks until it finds one task that doesn’t return failure, and then return that execution code.
Parallel Sequencer
A parallel sequencer is a little different from the previous two composite nodes. A parallel sequencer will try to run all of its children as long as they return running or success.
Non-deterministic
Some other kinds of composite nodes that will run its children in a non-deterministic fashion, such as randomly. And sometimes this could be useful when we don’t want our AI system to react too redictably. For example, if we want some AI agents to pick up a weapon, and then pick up some armor, we can use a random sequencer that will allow them to sometimes pick up the weapons first, but sometimes pick up the armor first.
Random Sequencer
A random sequencer acts just like a normal sequencer. The only difference is that instead of running the children tasks in the exact same order, we shuffle the order every time the task is opened.
Random Selector
Same with a random sequencer, the execution order will get shuffled every time the task is opened. The rest is the same as a normal selector
Decorator
The decorator is a special kind of tasks. A decorator can tweak the returned execution status of its child or how it is being run. Note that I am using the singular child here since the decorator will generally only have one child, which is the one that it needs to tweak. Basically, the decorator will wrap around its child and do something to it, while its parent does not care about what it is doing at all.
Some examples of decorators are the inverter, run until fail, and time out after seconds.
Service
The service node is another special kind of node, and not all implementations will have this. Some implementation will simply use a parallel sequencer to achieve the same goal. However, I think to have a specific service class can also document the intention better so that we know these are different from action nodes.
Services are usually used to update some blackboard information to reduce repetitive calculation or checking of some values. For example, updating the current distance from an agent to his target. There might be plenty of nodes that require this information, so instead of calculating it every time in every node, we can just update it on a service task and allow other tasks to directly retrieve the value from the blackboard.
Usually, service tasks are very game content and blackboard specific.
Behavior Tree Tick
The behavior tick object is pretty similar to what the decision tree tick object is. It serves as an object to pass on information between tasks, ant to keep track of the currently opened tasks so that we don’t waste time evaluating unnecessary tasks. It also handles calling the tasks’ open and close functions at the correct time.
Behavior Tree Structure
We finally reach the part of the actual behavior tree implementation. However, since we already have all the building blocks and our blackboard data structure, the actual behavior tree class is actually really simple.
The main chunk of the logic lies inside the GetAction() function, in which it will run through the tree, and then see if an action is written onto the blackboard by an action node.
Cheng-Hao "Nick" Chu 祝成豪 