Behavior Trees - DustinKushnereit/Behavior-Trees GitHub Wiki
Behavior Trees
Behavior Trees (BT) are the most usable, at least in my opinion, artificial intelligence tactic in games. Because of their simplicity in the fact that behavior trees can do anything from changing an NPC’s health to making an NPC wander aimlessly.
The beauty of behavior trees is that you can design the way the tree functions, to make it more suited to the task at hand. Meaning, if you want an NPC to do tasks in a certain order, you can set up the tree to do so, or you want the NPC to do an action if another action failed, you can do that as well. Behavior trees give an NPC the look of a complex AI system without actually being an overly complex system.
But what are Behavior Trees? Behavior Trees are a method to improve upon the complexities of finite state machines. Whereas Behavior Trees are easily modifiable, state machines can grow to ridiculous sizes and make understanding them more and more difficult. This problem with state machines is that once you set them up, they become difficult to adjust and reuse.
Transitions can become problematic with portions of game logic being set to specific areas; and the whole process becomes a jumbled mess. This is where Behavior Trees come in. With the idea being that non-programmers can understand and design BT’s with relative ease; this is something that finite state machines are lacking in, ease of understanding.
BT’s can also allow for expansion transparently by attaching root nodes to sub-nodes forming a tree-like structure. These main nodes are called Selectors. A selector acts as the root of the tree, building child tasks off of it. The child tasks, which can be either a leaf task or composite task, are what give the tree its real form.
Leaf Tasks – Broken down into two groups of either actions of conditions, these are what give the tree shape.
Composite tasks – The trunk of the tree that defines an order in which its child nodes are selected i.e. left to right, right to left, random, etc…
Leaf Tasks
Leaf tasks are those that give AI life. Leaf tasks are the part of the BT that holds the operation part of the code, in which something is done. Whether that’s asking a question in the form of a condition, or causing the AI to perform an action. An example of a small tree holding a root task of “patrol” with two basic leaf tasks, one condition and one action, can be seen below.
Each leaf task, that can be seen above, holds its own status that it returned to the parent node upon completion. These statuses are either a FAIL, SUCCESS, or RUNNING status. After completion of a leaf task, and if the node returns either a fail or success status, the parent will then decide how/what to do with that node. If the node returns a running status, the next time the parent of that particular node tries to run through its leaf nodes again, it will start with that particular node, which has another chance to return one of the three statuses.
An example of this would be: if the “Patrol Perimeter” parent node calls the “Enemy within range” node, and that returns a success, we could branch off that node with another saying “Attack Enemy”, in which this new node “Attack Enemy” would return a status of running. The attack node becomes the new primary node that continues running until the status is changed, and all the other nodes are ignored for the time being.
To sum it up, leaf nodes are the fists of the trees that hold the actions within them, whether that changing the health of an NPC, or sending an NPC to forcefully change the health of the player with an AK-47, leaf tasks contain the part of the code that does the dirty work.
Composite Tasks
Composite tasks are the aspect of the BT that decides in what way the BT will process its nodes. This is where the tree can become pretty complex. The idea is, from the main node, you have children stemming off of it, which then in turn have other composite tasks stemming off of them. This can give the tree more robust shape, giving the AI more of a sentient appearance. To understand this further, we’ll look at two types of composite tasks, sequences and selectors.
Sequence
A sequence is the easiest to understand of the composite tasks, in my opinion at least. You move in a predefined order from one node to another, usually going either left to right or right to left. The sequence task goes from one child to another as long as a child node doesn't return a fail status.
If a fail status is ever returned, then the sequence automatically stops moving through its children nodes and returns a fail. If the sequence successfully goes through all its children, then a success status is returned and it starts the process again. Looking at the example below, we can see that the sequence labeled in blue chooses to move through its leaf tasks in a set order that makes sure to hit each task in the same fashion every time the process is run.
Sequences are one of the more common composite tasks, since they make sure to hit every node that’s attached to them. The reason why this can get complex is that if one of the child nodes to the sequence node is another sequence node, or some other composite task, then the AI at hand will have to perform additional operations with every cycle.
Selector
A selector is a composite task that can define an order to the nodes in any fashion. Now this can mean the nodes are randomly selected, of the nodes are selected in a certain order. Below are three orders that can shed some light on this style of choosing.
But that’s only half of why selectors are a main composite task to look at. Selectors will run through their children nodes until a success status is reached. If a selector’s leaf tasks keep failing, it will keep running until it runs out of children. This is the opposite of sequences that will stop as soon as a fail is reached, but will run as long as a success is met.
Now, when would something like this be useful, well here’s an example: say an enemy AI is losing a fight, and it needs to heal before it can continue, you can run through the selector until a possible solution can be found; solutions such as flee from the area, use a potion of some sort, hide and recover health over time, or some other measure. The selector will continue running until the best possible solution can be found. And once it’s found it will immediately stop and choose said solution.
Decorator Tasks
Decorators are actually composite tasks with one child attached to them. Decorators can be readily modifiable based on the style of decorator that is chosen. There are many different decorators that can be used in a BT. Here are a few of them:
Inverter – reverses the status that is received by the child task, ex. – if it’s fail, makes it a success; if it’s a success, makes it a fail.
Repeat Until Fail – continues looping through the child task until a fail status is received.
Repeat Until Success – continues looping through the child task until a success status is received.
Repeat X Times – will continue looping for X amount of times.
Always Fail – will always return a fail no matter what the child task returns.
Always Succeed – will always return a success no matter what the child task returns.
Now for a few examples of Behavior Trees:
Listed below I have an example of a sequence styled BT that moves through its nodes from left to right. When the conditional tasks are reached, the tree goes down another level, giving the tree more of a robust appearance.
From here I have a small BT with two child nodes. This BT uses a sequence style that goes back and forth between the children until the enemy AI is killed off. For this I use a switch statement to represent the composite task. From the switch I have two cases, and a default case that’s only called if the switch fails for some reason. The two children have the following actions, fallDown, and rollLeft. The action fallDown, makes the enemy fall from the sky until it collides with a wall, the ground, or the enemy, if this happens the fallDown stops running and returns a fail which switches the task to rollLeft, which makes the enemy roll left until it either hits an enemy or can be affected by gravity again, allowing it to fallDown. If one of these options happen, the enemy returns a fail and the node switches back to fallDown.
switch(currentState) //Behavior Tree - Back and Forth
{
case 1:
if (!fallDown())
currentState = 2;
break;
case 2:
if (!rollLeft())
currentState = 1;
break;
default:
currentState = 1;
break;
}
Why Behavior Trees?
We can see now how Behavior Trees work, but you may still be wondering "why would I choose to use behavior trees?"
There are several reasons why you should consider using Behavior Trees over other types of similar AI techniques. First, Behavior Trees are simple to implement. It's just too easy to choose your own way to create a behavior tree, just look at my code example above. I used a switch statement to make a decision tree. Add in if statements and the tree becomes a clear cut reality.
Second reason why you should choose Behavior Trees, they're quick. In today's industry, games are all about speedy code that doesn't eat away at a system's memory. Where as a finite state machine is can be slow due to transitions being so heavily interlocked to specific items within the code base; a BT is quick because of the ambiguity that you can give it.
What I mean by this is, say you want an NPC to run through an area is a certain manner, all the while being on alert for enemies; and if an enemy is found, the NPC starts attacking. Well, if we were using a state machine, the NPC would have to transition from "Searching" to "Wandering" to "Alerted" to "Attacking" (or something of the likeness). Each transition would take time to process, in even a small 2D game. Add a whole engine and 3D world around these transitions, and everything starts slowing down. Who knows how much memory is being consumed in this process as well; the whole scenario can become incredibly inefficient.
Now, switch out the state machine for a BT, and all those large transitions happen within one area of code. This means that the AI switches from "search and wander" to "attack" faster. There's less pointers eating up chunks of memory and the whole situation is just quicker, because there's less time calling up other files that hold that designated "state".
Final Words
Because of the versatility of this AI process, you can use it for virtually any kind of game. Even my minimalistic game where you simply dodge enemies until the timer runs out can use this AI technique. Any game that has AI, and would like to have an easily modifiable but seemingly complex styled AI system should use Behavior Trees in some shape or form. Behavior Trees really are the Swiss knife of the AI industry.
References and Mentions
To better understand Behavior Trees, I used the following articles by user Byte56 on http://gamedev.stackexchange.com/questions/51693/decision-tree-vs-behavior-tree, team libgdx’s article on https://github.com/libgdx/gdx-ai/wiki/Behavior-Trees, and user Chris Simpson’s article on http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php. Each post helped to further more knowledge about Behavior Trees as a whole, with each article containing pieces of information that I collected and put together to form this one idea of just what Behavior Trees are. Website used to make GIFs http://gifmaker.me/