Article
files/QUESTIONS

Popular Approaches to Behavior Tree Design

Alex J. Champandard on December 21, 2007

jjacobsson asks about behavior trees: “What is the root conceptually? How does it deal with events? Is the tree evaluated from the root down to a leaf often / all the time?”

The first thing to note is that behavior trees are rather flexible, so they can be applied in a variety of different ways. However, certain approaches are more common that others and maximize the benefits that behavior trees have to offer. I’ll outline these in the rest of this article.

The Main Behavior

The root of the tree is essentially the top-level task. So, you can consider the root task as representing the overall behavior. This task is decomposed recursively into sub-tasks that accomplish simpler behaviors that make up the whole (as explained here).

In practice, the whole tree is often called BEHAVE, and registered in the lookup table so it is accessible to the game logic in a data-driven way. The first few nodes from the root behavior typically do the following:

  1. Repeat the whole behavior no matter how it terminates.

  2. Handle any kind of failure or error gracefully.

  3. Select from multiple sub-behaviors based on the situation.

For a soldier in first-person shooter, the sub-behaviors would provide appropriate responses for the different states of mind: IDLE, SUSPICIOUS and ALERT.

Reaction Tree for Cosmetic Events

Certain events aren’t very important, but they present an opportunity for providing an extra level of believability. For example, when a soldier is on guard and sees a colleague patrolling in a different direction, the behavior could react to that by looking at the other soldier and making a comment.

This kind of cosmetic detail can be handled in a separate REACT tree that gets executed whenever there’s an event (e.g. actor appear). This tree would contain logic to dispatch the event by selecting the appropriate reaction. That whole sub-tree would run concurrently with the main behavior, and would require a set of resource allocators to make sure there are no conflicts. (They are decorators.)

Incremental Evaluation

Figure 1: Resource allocators (black) to synchronize subtrees.

Dealing with Opportunities and Threats

Only certain events affect the main tree (as discussed in this article on strategies for handling events purposefully). Events are only relevant for the main behavior if they:

  • Open up new opportunities.

  • Present new threats.

The AI logic deals with those by aborting subtrees and enabling other subtrees. In practice, you can achieve this in different of ways:

  1. Using a dynamic selector which keeps rechecking for higher-priority behaviors on a regular basis.

  2. Running conditions in a parallel task for monitoring each tree’s assumptions, to bail out when there’s a problem.

Monitoring Assumptions

Figure 2: Parallel conditions for monitoring subtrees.

Tree Evaluation

Generally speaking, the behavior is NOT evaluated from the root each update. This would make it more of a decision tree (i.e. a classifier) with poor support for executing and monitoring behaviors over time. For instance, if you reset a behavior tree, then typically the sequences would be reset everytime.

However, as I mentioned, the concept of the dynamic selector and having conditions running in parallel with whole subtrees means there’s always some aspect of the logic that’s active high-up in the tree to deal with special case events. This logic is setup as necessary by the designers, and sprinkled around the tree liberally.

Incremental Evaluation

Figure 3: Evaluating a behavior tree incrementally.

In effect, this gives you the benefits of responsiveness and concurrency without having to re-evaluate the tree each frame from the root to adapt to new situations. That would be Memento-style AI which is often used to apply planners in practice, which turns out to be a rather brute force solution in practice.

Discussion 3 Comments

alexjc on December 30th, 2007

Hmm, that's a good question Chris... I think the overall hierarchical approach is similar, but they differ in the amount of responsibility each parent has. In a subsumption architecture, you can only override particular wires, whereas in a behavior tree you can do things like concurrency even... Anyway, I'll think about it and tackle this subject in another issue of the Reader Questions on Friday. Stay tuned!

bknafla on February 18th, 2008

Regarding the difference of subsumption architectures and BTs: as far as I can remember subsumption architectures are layered. The lowest level reacts to direct events and executes direct actions. Higher levels get reports from lower levels (what is going on but no requests to do something as lower levels don't really know about higher levels, just to send data somewhere up the layer chain) and ask the lower level to execute specific actions based on the decision process of the higher level. For example the lower level might be able to do one step while a higher level tries to move to a specific location which needs lots of steps. The lower level also can ignore higher level requests/commands, for example to prevent a collision. The higher level is mainly concerned with high level decision making and not with the nitty gritty details of action execution done by the lower levels. The lowest level is updated most often while higher levels are updated with lower frequencies. A variation of this is an Orwellian State Machine (from Igor Borovikov), which replaces the layers by a tree structure similar to BTs but the data flowing between the tree nodes are messages and not status tokens like in the BT Alex develops (as far as I know). A BT is quite different from a subsumption architecture. First there aren't direct layers but a tree. Information flowing in the tree is: 1) traversal and therefore execution and evaluation of nodes and 2) status reports by the nodes which flow from the nodes up to their parents. A BT is traversed (or might be traversed this way - there can for sure be variations of this idea) until a node returns "running". If the BT is updated the next time it isn't traversed from the root until the last "running" node is found but the last "running" node is called directly. Therefore, the last state of the BT traversal is the next state to start the evaluation again. This idea is complicated by having parallel nodes - so a tree evaluation needs a mechanism to store all "running" or active nodes of the last tree traversal and to work on them in the order the tree traversal dictates to react to conditions that might cancel "running" nodes that might be traversed later on. As far as I understand Alex blog (I haven't looked into the Game::AI++ code but am about to do it) he implements this mechanism (and fights call-stack depth with it, too) by modelling each node as a task that gets inserted into a task scheduler. If you traverse a BT each nodes task is added to a scheduler, the scheduler runs the task. A task might finish as "completed" and then might enqueue its parents node task into the scheduler which then is executed by the scheduler. For example an action below a sequence is "completed" and enqueues the selector task right behind it into the scheduler queue. The scheduler then runs the selector tasks which enqeues the next action in the sequence it controls, and so on. "running" tasks/nodes remain in the scheduler (while completed nodes/tasks are removed) and are executed in the next frame when calling the BT evaluation. These "active" or "running" tasks/nodes therefore represent which nodes to evaluate the next time the BT is called. Well, this is how far I understand Alex's BTs, I hope that Alex or other people that know how BTs work chime in and point out the errors and how BTs really work internally. Cheers, Bjoern

cl2006 on December 10th, 2008

Thanks for the information Bjoern! However, a question would be, assuming you traverse the tree and add tasks into a scheduler - when do you deem it appropriate to leave the BT traversal and return back to the main game updates until the next call to the BT? I'm assuming that at each game update, a call to the BT is made to proceed with its traversal. Thanks!

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!