Behavior Trees

1        Introduction

A lot of games have used some form of finite state machine (FSM) for artificial behavior and state change systems.  Despite the popularity of FSM’s for artificial intelligence, behavior trees normally allow users to create more complex artificial behaviors with a lot more ease.

Finite state machines are simple to understand and can be quickly created as creating a new state only requires one to create a state’s logic and then modify any transition functions to and from the new state.  A FSM with 10 or few states is very manageable.  As the number of states grows though, begin to become more error prone and harder to debug as transitions become more convoluted.

To make it easier to picture how the more states in a FSM can cause a lot of headaches, consider the following situation. Some programmer is implementing an enemy AI that can wander and attack for a designer.  This produces the following FSM:

wander_attack

When the AI is close to the player it attacks, else the AI just walks in a random direction.  Later, the designer tests the game and realizes that the enemy has a very generic intelligence and would like to make the enemy more complex.  The designer decides that the enemy should shoot the player from far away causing the programmers FSM to then look like:

wander_attack_shoot

The designer then decides the enemy also has to have a death state.  Leading to the FSM to then look like:

wander_attack_shoot_death

Each time the programmer added a new state, they had to go back and refactor the transitions between each state and or add new transitions.  This can be cumbersome and lead to states not being able to be reused as their transitions depend on certain states.  By now one must realize how adding states to a FSM is like rolling a snow-ball.  The more states that are added, the more one needs to refactor their states.  This is where behavior trees come into play.

A behavior tree is a data structure made up of a hierarchy of behaviors that control how an object makes different decisions.  They are efficient, less error prone, not too difficult to implement, and adding/removing functionality can be done with ease.  Also, with just simple switches between behaviors, the current state of behaviors can be altered safely with little to no overhead.

The best way to describe a Behavior Tree is to think of it as any other node tree architecture in programming, being composed of a root node, branches and leaf nodes. Behavior Trees also have two very special kinds of nodes, composite and decorator nodes.  Composite nodes contain multiple children, and will process its children differently depending on the type of composite node the programmer uses.  Decorator nodes are only have one child, and are being responsible for modifying the result of their child or keep their child on a repeat loop until it reaches a desired output.  We will go into more specific details about these nodes a little later.  First one must understand what a behavior is.

 

2        Behaviors

The major back bone of behavior trees and what makes them so powerful are nodes, called behaviors.  These behaviors are very similar to states of FSM’s in the way they are constructed since they have an initialize, update, and terminate method.  With this being said, they act completely different from one and another.  A behavior that resides within the tree contains logic on how to traverse further through the tree while a leaf behavior will normally contain some kind of game logic to perform.

Behaviors normally consist of three different areas of operation which were mentioned above to be initialize, update, and terminate.  When first entering a behavior, the initialize member is called which will grab / setup any values that may be necessary for the behavior to function.  Directly after the initialize method has finished, the behavior’s main functionality is performed by calling the update method.

The update method is slightly special as it can return several different status flags.  These statuses are normally only comprised of SUCCESS, FAIL, and RUNNING, but one may find the need to add other values like ERROR or INVALID for example.  The method would return SUCCESS if the behavior’s desired purpose was met, RUNNING if the functionality of the behavior had yet to finish, and FAIL if the behavior’s desired purpose was unable to be met.  Now say the whole point of a behavior being visited was to calculate a path to some object.  If during the update method a path to the object was found, the terminate method would be called and then the behavior would return SUCCESS.  RUNNING would be returned if the time to calculate the path was taking too long.  This allows the game to proceed with updating the current frame and continue updating the behavior on the next frame of the game.  Lastly, if for some reason a path could not be found to the object, the terminate method would be called and then FAIL would be returned from the behavior.  The terminate method is where one can free any memory allocated for the behavior, reset any values, and etc.

 

2.1        Construction of Behaviors

When constructing actual behaviors, one should create an abstract class for all behaviors to inherit from.  Doing this allows for an API to be enforced and provides a way to store all behaviors as a single type.  This class should declare update and instantiate both initialize and terminate.  An example of this class may be:

class Behavior {
protected:
  virtual void initialize( ) { }
  virtual void terminate( )  { }
  virtual State update( ) = 0;

  State mStatus;
}

A major thing to notice is that all the methods are protected.  Having these methods protected does not do a tree any good if it cannot call any of them, but it does give the implementer control over how the behaviors are used.   One has to add a public method called tick to fix this problem.  This method will be what manages the behavior every time it is visited, but to do this one will also have to add a protected member to manage the state of the behavior.  The tick method will reference the behavior’s state to know whether the behavior has been running or is just starting up and needs to be initialized.  The behavior’s update method is always called by tick, but if the behavior needs to be initialized then the initialize method is called with the update method being called directly after.  The state of the behavior is updated every time the update method returns the current state of the behavior.  After the update method has finished, if the state of the behavior is FAIL or SUCCESS then the tick method will directly call terminate after calling update since the behavior has served its purpose.  Lastly, tick returns the state of the behavior to its parent behavior.  Setting up this abstract class will allow one to enforce the structure of their behaviors and allow them to construct new behaviors with ease.  The tick function will look something like:

class Behavior {
public:
    Status Tick( )  {
        // init if no running
        if ( mStatus != Status.RUNNING )
            initialize( );

        // update children
        mStatus = update( );

        // uninit if done running
        if ( mStatus != Status.RUNNING )
            terminate( );

        return mStatus;
    }
}

 

2.2        Types of Behaviors

There are three base types of behaviors that all other behaviors created inherit from in one way or another.  These three types are composite, decorator, and leaf behaviors.  These three types of behaviors act completely different and are the ground work for what make other behaviors so powerful.

 

2.2.1        Composite Node

Composite behaviors contain multiple children behaviors.  By pulling multiple simple behaviors together, composite behaviors can form one complex behavior.  Not only does this add to the intelligence of behavior trees, but it also allow for behaviors to be compartmentalized and split in to small simple tasks.  This also allow one to reuse behaviors for other trees since behaviors don’t have to all be squished into one single behavior and be hard coded for a single object.

To construct a base composite behavior, one will need to inherit from the base Behavior class.  From here, they will need to give the behavior some sort of protected structure for storing children (a list or vector normally work just fine).  Since this structure is private, one will also have to add the functionality to add, remove, and clear children.  One does not necessarily need the ability to remove and clear children, but they do give the ability for extra functionality with in your behaviors.  Lastly, since most composites will update through all of their children, it is smart to add a protected member that points to the current behavior being updated.  Once this has been added, one may want to overload the initialize method to initialize this value, so later behaviors that derive from composite do not have to worry about it.  An example of this class may look something like this:

class Composite : public Behavior {
public:
    void AddChild(Behavior* child);
    bool RemoveChild(Behavior* child);
    void ClearChildren( );

protected:
    std::list< Behavior* > m_children;
    int m_currIndex;

    void initialize( ) { m_currIndex = 0; }
    void terminate( )  { ClearChildren(); }
}

 

2.2.2        Decorator Node

Unlike the Composite node, Decorator nodes can have only one child and exert a supporting role to its leaf node. They can alter the result of a child, execute checks or keep the child in a loop until the desired output is delivered.

A common Decorator node is the one that inverts the result of a child. If we want to check if a player is dead, but we only have a function that checks if the player is alive, we could use a Decorator node that inverts values from true to false. Or if we want a unit to search for a target until it reaches it finds one, we could simply use a Decorator node that keeps the unit on a search state until it finds a target.

There a dozens of Decorator nodes a programmer can come up with, and they make code a lot more reusable, making unnecessary to write check functions for every situations, and making functions smaller without having to redundantly write loops for everything.

Similar to how a programmer breaks large parts of a function into smaller functions; Decorator nodes are a common practice that it is necessary to adopt when writing Behavior Tree systems, keeping the code clean, simple and easier to understand and debug.

 

2.2.3        Leaf Node

If we think of tree architecture as a clock, the frame and pieces that connect the clock as a whole are the tree’s branches; the leaves are like each individual clock gear that makes the tree function in harmony, with each individual leaf having an independent function that gives the tree a purpose and a meaning for its existence.

Going back to FSM’s, which is composed of states; an easy way to understand the leaves of a behavior tree is to think of them as individual states. There are all kinds of leaf nodes the programmer can come up with, each one of them with a unique purpose. With states of FSM’s, one has to specify there transitions to different states.  Whereas in a behavior tree since behaviors are abstracted from one and another, all one has to do is traverse the tree.

Let’s imagine this scenario again, we have to program an enemy that can approach the player and attack the player when it is close to him/her.

So we create a Sequence node that has the following children (leaf nodes) in the following order: approach leaf, attack leaf and hide the body leaf. When traversing the tree system that we developed with a lot care reaches this specific Sequence node, the enemy AI will approach the player, and will keep approaching the player until it reaches the player. When the enemy meets with the player, it will proceed to attack him/her until he/she dies. Once player is dead, the enemy will hide the body of the player.

Ex1

We could keep adding new leaves indefinitely to this system; we could even replace attack with a Selector node that has even more leaves like punch, kick and roundhouse kick. So when the enemy completes the approach sequence it will proceed to choose one of the three possible different attacks.

Ex2.png

 

3        Conclusion

Behavior trees so are a great solution for creating complex AI behaviors.  The programmer can add new states iteratively without the scalability problem that finite state machines may run into.  Not to mention, they are also simple to understand and not that difficult to implement, but they still require the programmer to think ahead and plan before taking any kind of big decision when creating them.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s