Understanding Behavior Trees

Alex J. Champandard on September 6, 2007

One of the primary goals of game AI is finding a simple and scalable solution for editing logic. Finite state machines have the advantage of being quite simple, but for large systems you’ll need a hierarchical FSM to provide reusable transitions between states.

Such HFSMs are certainly a popular way for making scalable logic. However, they do not provide any modularity for states; you can’t reuse states to provide logic for different goals or situations without rewiring them. Behavior trees (BT) on the other hand take a different approach…

States or Behaviors

Behavior trees focus on increasing the modularity of states by encapsulating logic transparently, for example by using nested states. Certain hybrid HFSM implementations provide this feature also.

Figure: A tree made of modular behaviors.

The secret is to remove the transitions to external states, so the states become self-contained. In fact, once you do that, they’re not really “states” anymore because they don’t have transitions; they’re just behaviors, or a collection of actions that execute and terminate.

A Programming Analogy

You may ask, since the transitions are no longer encoded explicitly in each state, how is it possible to sequence behaviors using a behavior tree?

This is done using the same method as most programming languages — which is demonstrably more scalable. In C++, Python or any other modern language, each operation does not contain a pointer to its successor, as it would be difficult to reuse these operations in different contexts (like calling them from another function).

Instead, operations are inserted into a parent scope (e.g. in a function, or for a conditional check), and they are executed according to the semantics of the parent scope. So in essence, the transitions between the operations are automatically defined based on which type of parent scope is chosen.

Why Behavior Trees Work

If you make your BT implementation extensible (so any type of scope, or composite behavior can be added), it becomes as powerful as any programming language. But at the same time, BTs remain very simple and usable when you provide standard composites such as sequences and selectors.

In fact, you can rebuild most state machine using only sequences and selectors. Then adding custom decorators into the mix you get something extremely powerful yet still very intuitive.

Ultimately, it is possible to translate a simple BT of sequences and selectors to a FSM if necessary. The FSM does you more control over the individual transitions, but the BT make the logic modular and easier to reuse.

Discussion 8 Comments

FuriCuri on November 9th, 2007

Hi, Joerg. I think parallel behaviors will do the trick. Just put "Watch for cat" and "Do smth" behaviors in parallel and implement override priority to "Watch for cat" tree branch, so if it triggers it will override all current actions in "Do smth" tree branch.

attila on May 16th, 2009

Hi FuriCuri, I think that's about right. This is also how GOAP works; goals are selected using an attention-value function, planning is done, plan is executed. If the plan fails, the things starts anew. Every so much time, the attention-value is re-evaluated and a new plan can be formed if the goal has shifted. Regards, Attila

deadprophet on May 17th, 2009

Wow, this post seems to have an ever increasing span of reply time

nirvana6 on February 25th, 2011

Hi Joerg, I agree with you that this concise overview does not cover how the agent reacts to the state / event. Since the BT is considered to be "purposeful" by the author, so I believe there should be another component which evaluates the current state / event to be of certain purpose (the cat is going to attack me), such that the most effective strategy (let me bite you first) could be chosen, then drill down the tree to locate the corresponding behaviours then react accordingly. Hope my words would make sense, since I am also new to BT. Fu Yong

niello on March 11th, 2011

I try to design core AI for my game now and my decomposition is looking like: 1. Convert your actor state and its environment state to the actual AI variables used for decision making. This is done by sensory system. Say your dog actor sees a cat by its VisualSensor, marks cat as enemy and writes smth like DistanceToNearestEnemy = 0.5 m. 2. Goal formulator processes all the variables (actor's representation of game world state) and decides what goal should be satisfied. This can be done by scripted, data-driven or even hardcoded algorithm. For player-controlled actors player can immediately assign goals by input. Say dog's top-level behaviour logic consists just of: if (DistanceToNearestEnemy < 1) SetGoal("KillNearestEnemy"); else SetGoal("Rest"); 3. Planner makes plan (action list) HOW TO achieve current goal. It can produce such list for our example: PlayAnim("FromRestToAttack") + SetTarget(NearestEnemy) MoveTo(NearestEnemy.Position) while (NearestEnemy.IsAlive) do hit actions... SetGoalDone(true) 4. Action manager executes action list, requesting game subsystems to do actual work. Behaviour trees do a job of point 3 in this model. They decide HOW to do work but not WHAT we want to do. Hope it helps.

yoquankara on August 25th, 2011

Hi Joerg, Don't know whether you found it out or not. But in my opinion, event handler should be included into logic of strategy. I'm not sure adding Hierarchical event handler is possible or not. But a BT with hierarchical event handler may be too strong a mechanism :)

UbisoftMTL on September 15th, 2011

Hi, I just read the first few lines and I disagree when you say: "Such HFSMs are certainly a popular way for making scalable logic. However, they do not provide any modularity for states; you can’t reuse states to provide logic for different goals or situations without rewiring them" I've used some HFSM frameworks that allowed to use pointers to "concrete" substates, with a concept of "state interface inheritance" to make sure that the "pointed to" states would handle the transition calls from other states correctly. It worked well and wasn't conflicting with the concept of HFSM at all. I would be interested in discussing what made you think that HFSM couldn't handle reusing states in the first place. Anyway, great web site, a precious resource! Keep up the good work :)

jesu37 on February 29th, 2012

hi where I can find good books, links , tutorials .... that explain the behavior trees and the links no longer work .. .I will make an AI engine

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!