Introduction

I'm going to cover the implementation of a very useful technique for AI programmers called Behavior Trees (BT for now on). I've been using this technique for the AI in the Android game I'm working on, and found a few quirks in the architecture that made me have to struggle somewhat. Just thought I'd share what I've learnt during the process.

As this is for an Android game, the code is in Java. Even so, it is easily ported to C++, and there are almost no Android specific libraries or function calls to worry about.

What are Behavior Trees?

The internet is crawling with places to find a good theory on what behavior trees are, and how to implement them, for example:

AIGameDev : Overview; Approaches; Video tutorial part 1, part 2.
Wikipedia (Not recommended for videogame development, but interesting)
Etc...

Overview

This article assumes you know what a BT is. If not have a look at the mentioned articles. I’m going to work with a system with the following architecture.

It may look complex at a glance, but once we’ve gone over each part you will see like it’s quite understandable, elegant and flexible. At a glance you can see 3 “groups” of classes. The Tasks (yellow), the TaskControllers (blue) and the Decorators (green). We shall consider each of these in turn, and then how they all fit together.

Architecture

General

The general idea for the system is that you have a set of modular tasks (MoveTo, FindClosestEnemy, FindFleeDirection, WaitTillArrivedAtDestination…) and you use them to form a BT. The base Task class provides a interface for all these tasks, the leaf tasks are the ones just mentioned, and the parent tasks are the interior nodes that decide which task to execute next.

The tasks have only the logic they need to actually do what is required of them, all the decision logic of whether a task has started or not, if it needs to update, if it has finished with success, etc. is grouped in the TaskController class, and added by composition. This is done for two reasons, one is for elegance when creating new tasks, the other for security when creating new decorators.

The decorators are tasks that “decorate” another class by wrapping over it and giving it additional logic. In our case we use them to give a update speed to a certain task, or to reset it once is done, or similar things. You can read about the Decorator pattern here.

Finally, the Blackboard class is a class owned by the parent AI that every task has a reference to. It works as a knowledge database for all the leaf tasks, and it’s where we keep the data that is generated on one task and needs to be used by another.

Tasks

Task

All tasks follow the same interface:

Code Snippet
 /**
 * Base abstract class for all the tasks in 
 * the behavior tree.
 * 
 * @author Ying
 *
 */
 
public abstract class Task 
{    
    /**
     * Reference to the Blackboard data
     */
    protected Blackboard bb;
    
    /**
     * Creates a new instance of the Task class
     * @param blackboard Reference to the 
     *    AI Blackboard data
     */
    public Task(Blackboard blackboard)
    {
        this.bb = blackboard;
    }
    
    /**
     * Override to do a pre-conditions check to 
     * see if the task can be updated.
     * @return True if it can, false if it can't
     */
    public abstract boolean CheckConditions();
    
    /**
     * Override to add startup logic to the task
     */
    public abstract void Start();
    
    /**
     * Override to add ending logic to the task
     */
    public abstract void End();
    
    /**
     * Override to specify the logic the task 
     * must update each cycle
     */
    public abstract void DoAction();
    
    /**
     * Override to specify the controller the 
     * task has
     * @return The specific task controller.
     */
    public abstract TaskController GetControl();
}
 

As in any BT node, a CheckConditions and a DoAction functions, to check if the node can be updated, and to actually update the node, respectively. The Start and End functions are called just before starting to update the node, and just after finishing the logic of the node.

To be a true interface, the Blackboard member should not be in the class, but for simplicity and ease of use, it’s the perfect place for it. So fuck interfaces then.

Leaf Task

Base LeafTask class

Code Snippet
 /**
 * Leaf task (or node) in the behavior tree.
 *  
 * Specifies a TaskControler, by composition, 
 * to take care of all the control logic, 
 * without burdening the Task class with 
 * complications.
 * 
 * @author Ying
 *
 */
public abstract class LeafTask extends Task 
{
    /**
     * Task controler to keep track of the 
     * Task state.
     */
    protected TaskController control;
 
    /**
     * Creates a new instance of the 
     * LeafTask class
     * @param blackboard Reference to the 
     *  AI Blackboard data
     */
    public LeafTask(Blackboard blackboard) 
    {
        super(blackboard);
        CreateController();
    }
    
    /**
     * Creates the controller for the class
     */
    private void CreateController()
    {
        this.control = new TaskController(this);
    }
    
    /**
     * Gets the controller reference.
     */
    @Override
    public TaskController GetControl()
    {
        return this.control;
    }
}
 

The leaf task has a TaskController for the support logic of the class, and implements the GetControl method. It has no more extra logic or methods.

The child classes of the LeafTask class are the ones with the real logic of the system, and each time we want a new behavior we are going to have to create a few. They are building blocks, modular, and they can be combined in different ways to generate different effects. Take for example simplistic Chase and a Flee strategies, they could work like this:

Chase

GetClosestEnemy
SetClosestEnemyPositionAsDestination
MoveToDestination
WaitUntilPositionNearDestination

Flee

CalculateFleeDestination
MoveToDestination
WaitUntilPositionNearDestination

The italics mark the reused leaf nodes in two different sequences of behaviors. That shows how modular leaf nodes can be recycled and used to conform many different behaviors.

Leaf tasks often calculate data needed by other leaf tasks. Instead of making a complex linking of the whole tree of tasks, we just use a common “data dump” for all of them, a Blackboard object shared by all the tasks, that simply has member data used by the different tasks.

Some examples of Leaf Nodes follow.

LeafTask Examples

GetClosestEnemyTask

Code Snippet
 /**
 * Finds the closest enemy and stores 
 * it in the Blackboard.
 * @author Ying
 *
 */
public class GetClosestEnemyTask extends LeafTask 
{
    /**
     * Creates a new instance of the 
     * GetClosestEnemyTask task
     * @param blackboard Reference to the 
     *  AI Blackboard data
     */
    public GetClosestEnemyTask(Blackboard bb)
    {
        super(bb);
    }
 
    /**
     * Checks for preconditions
     */
    @Override
    public boolean CheckConditions() 
    {        
        return Blackboard.players.size() > 1 && 
        bb.player.GetCursor().GetPosition() != null;
    }
 
    /**
     * Finds the closest enemy and stores 
     * it in the Blackboard
     */
    @Override
    public void DoAction() 
    {
        Enemy closestEnemy = null;
        // Finds the closest enemy
        // Omited for clarity
 
        // Store it in the blackboard
        bb.closestEnemy = closestEnemy;
        GetControll().FinishWithSuccess();
    }
 
    /**
     * Ends the task
     */
    @Override
    public void End() 
    {
        LogTask("Ending");
    }
 
    /**
     * Starts the task
     */
    @Override
    public void Start() 
    {
        LogTask("Starting");
    }
}
 

MoveTo

Code Snippet
 /**
 * This task requests the player to 
 * move to a given destination.
 * It takes the destination from 
 * the Blackboard.
 * @author Ying
 *
 */
public class MoveToDestinationTask extends LeafTask 
{
    /**
     * Creates a new instance of the 
     * MoveToDestinationTask class
     * @param blackboard Reference of the 
     *  AI Blackboard data
     */
    public MoveToDestinationTask(Blackboard bb)
    {
        super(bb);
    }
 
    /**
     * Sanity check of needed data for the 
     * operations
     */
    @Override
    public boolean CheckConditions() 
    {
        LogTask("Checking conditions");
        return bb.moveDirection != null;
    }
 
    /**
     * Requests the cursor to move
     */
    @Override
    public void DoAction() 
    {
        LogTask("Doing action");
        bb.player.Move(bb.moveDirection);
        control.FinishWithSuccess();
    }
 
    /**
     * Ends the task
     */
    @Override
    public void End() 
    {
        LogTask("Ending");
    }
 
    /**
     * Starts the task
     */
    @Override
    public void Start() 
    {
        LogTask("Starting");
    }
}
 

Parent Task

Parent task require a bit more explanation than leaf tasks, but don’t worry, we’ll work through it step by step. The base class is similar to the LeafTask class:

Code Snippet
 /**
 * Inner node of the behavior tree, a 
 * flow director node that selects the
 * child to be executed next.
 * (Sounds macabre, hu?)
 * 
 * Sets a specific kind of TaskController for 
 * these kinds of tasks.
 * 
 * @author Ying
 *
 */
public abstract class ParentTask extends Task 
{
/**
    * TaskControler for the parent task
    */
ParentTaskController control;
    
public ParentTask(Blackboard bb)
{
    super(bb);
    CreateController();
}
    
/**
    * Creates the TaskController.
    */
private void CreateController()
{
    this.control = 
        new ParentTaskController(this);
}
    
/**
    * Gets the control reference
    */
@Override
public TaskController GetControl() 
{
    return control;
}
 
/**
    * Checks for the appropiate pre-state 
    * of the data
    */
@Override
public boolean CheckConditions() 
{
    LogTask("Checking conditions");
    return control.subtasks.size() > 0;
}
    
/**
    * Abstract to be overridden in child 
    * classes. Called when a child finishes 
    * with success.
    */
public abstract void ChildSucceeded();
    
/**
    * Abstract to be overridden in child 
    * classes. Called when a child finishes 
    * with failure.
    */
public abstract void ChildFailed();
 
/**
    * Checks whether the child has started, 
    * finished or needs updating, and takes 
    * the needed measures in each case
    * 
    * "curTask" is the current selected task,
    * a member of our ParentTaskController
    */
@Override
public void DoAction() 
{
    LogTask("Doing action");
    if(control.Finished())
    {
        // If this parent task is finished
        // return without doing naught.
        return;
    }
    if(control.curTask == null)
    {
        // If there is a null child task 
        // selected we've done something wrong
        return;
    }
        
    // If we do have a curTask...
    if( !control.curTask.
        GetControl().Started())
    {
        // ... and it's not started yet, start it.
        control.curTask.
            GetControl().SafeStart();
    }        
    else if(control.curTask.
        GetControl().Finished())
    {
        // ... and it's finished, end it properly.
        control.curTask.
            GetControl().SafeEnd();
            
        if(control.curTask.
            GetControl().Succeeded())
        {
            this.ChildSucceeded();
        }
        if(control.curTask.
            GetControl().Failed())
        {
            this.ChildFailed();
        }
    }
    else
    {        
        // ... and it's ready, update it.        
        control.curTask.DoAction();
    }    
}
 
/**
    * Ends the task
    */
@Override
public void End() 
{
    LogTask("Ending");
}
 
/**
    * Starts the task, and points the 
    * current task to the first one 
    * of the available child tasks.
    */
@Override
public void Start() 
{
    LogTask("Starting");
    control.curTask = 
        control.subtasks.firstElement();
    if(control.curTask == null)
    {
        Log.e("Current task has a null action");
    }
}
}
 

The ParentTask class has a ParentTaskController, identical to the TaskController for the LeafNode (handles state logic, if it’s ready, finished, ect…) but adds responsibility for the child tasks (a subtasks vector) and the current selected task (curTask).

It also implements the Start and End functions, very similar to the LeafTask. But the big change comes in the DoAction function. Here it updates the child of the parent task acordingly. All Parent tasks have the same process, that can be explained conceptually more or less like this:

Safety checks to see if we have all the data, and it’s not null
If the current child task is not started, start it
Else, if the current child task is finished, finalize it propperly and check if it finished with success or failure. Here is where the different ParentTask differ, on what happens if the child fails or succeeds. (ChildSuceeded and ChildFailed virtual functions)
Else, the child must be updated, so we call it’s DoAction.

The abstract ChildSuceeded and ChildFailed functions are for the classes derived from ParentTask to specify how they behave when a child ends their execution. We have two distinct cases for this, Sequence and Selector classes.

Sequence

In a sequence of tasks, if a child ends it’s execution with a failure, we bail and the Sequence ParentTask ends with failure. This makes sense, as sequences are used for example for the Chase explained earlier:

GetClosestEnemy
SetClosestEnemyPositionAsDestination
MoveToDestination
WaitUntilPositionNearDestination

If task 2 fails, we don’t want the ParentTask to continue on to MoveToDestination, as the Destination Vec2 is possibly corrupted, and will result in undefined behavior.

On the other hand if a child finishes with success, we continue onto the next task.

Some code to illustrate this:

Code Snippet
 /**
 * This ParentTask executes each of it's children 
 * in turn until he has finished all of them.
 * 
 * It always starts by the first child, 
 * updating each one.
 * If any child finishes with failure, the 
 * Sequence fails, and we finish with failure.
 * When a child finishes with success, we 
 * select the next child as the update victim.
 * If we have finished updating the last child, 
 * the Sequence returns with success.
 * 
 * @author Ying
 *
 */
public class Sequence extends ParentTask 
{
    /**
     * Creates a new instance of the 
     * Sequence class
     * @param blackboard Reference to 
     * the AI Blackboard data
     */
    public Sequence(Blackboard bb)
    {
        super(bb);
    }
    
    /**
     * A child finished with failure.
     * We failed to update the whole sequence. 
     * Bail with failure.
     */
    @Override
    public void ChildFailed() 
    {
        control.FinishWithFailure();
    }
 
    /**
     * A child has finished with success
     * Select the next one to update. If 
     * it's the last, we have finished with 
     * success.
     */
    @Override
    public void ChildSucceeded() 
    {
        int curPos = 
            control.subtasks.
            indexOf(control.curTask);
        if( curPos == 
            (control.subtasks.size() - 1))
        {
            control.FinishWithSuccess();
        }
        else
        {
            control.curTask = 
                control.subtasks.
                elementAt(curPos+1);
            if(!control.curTask.CheckConditions())
            {
                control.FinishWithFailure();
            }
        }
    }
}
 

Selector

The selector chooses one it’s children to update, and if that fails it chooses another until there are no more left. This means that if the current chosen child ends with failure, we choose another. If we can’t choose another, we end with failure. On the other hand, if our child returns with success, we can happily finish with success as well, as we only need one of the children to succeed.

In retrospect, the Sequencer is like a AND gate, and the Selector as a OR gate, only applied to tasks instead of circuits…

Some code then.

Code Snippet
 /**
 * This parent task selects one of it's 
 * children to update.
 * 
 * To select a child, it starts from the 
 * beginning of it's children vector
 * and goes one by one until it finds one 
 * that passes the CheckCondition test.
 * It then updates that child until its 
 * finished.
 * If the child finishes with failure, 
 * it continues down the list looking another
 * candidate to update, and if it doesn't 
 * find it, it finishes with failure. 
 * If the child finishes with success, the 
 * Selector considers it's task done and 
 * bails with success. 
 * 
 * @author Ying
 *
 */
public class Selector extends ParentTask 
{
    /**
     * Creates a new instance of 
     * the Selector class
     * @param blackboard Reference to 
     *  the AI Blackboard data
     */
    public Selector(Blackboard bb)
    {
        super(bb);        
    }    
    
    /**
     * Chooses the new task to update.
     * @return The new task, or null 
     *  if none was found
     */
    public Task ChooseNewTask()
    {
        Task task = null;
        boolean found = false;
        int curPos = 
            control.subtasks.
            indexOf(control.curTask);
        
        while(!found)
        {
            if(curPos == 
                (control.subtasks.size() - 1))
            {
                found = true;
                task = null;
                break;
            }
            
            curPos++;
            
            task = control.subtasks.
                elementAt(curPos);
            if(task.CheckConditions())
            {
                found = true;
            }
        }
        
        return task;
    }
 
    /**
     * In case of child finishing with 
     * failure we find a new one to update,
     * or fail if none is to be found
     */
    @Override
    public void ChildFailed() 
    {
        control.curTask = ChooseNewTask();
        if(control.curTask == null)
        {
            control.FinishWithFailure();
        }        
    }
 
    /**
     * In case of child finishing with 
     * sucess, our job here is done, finish 
     * with sucess
     * as well
     */
    @Override
    public void ChildSucceeded() 
    {
        control.FinishWithSuccess();        
    }
}
 

Task Controller

Introduction

The task controller, as mentioned earlier, tracks the state of the Task it is added to. It keeps a reference to the task and acts as a wrapper for said class when dealing with all the “Is it finished? Is it ready to update?” kind of questions.

This code is separated from the actual task for two reasons.

Reason One: Elegance of Design.

Once we separate the state control from the task class, we can create new subtasks paying no mind to the whole mechanism going on in the background to keep our task in harmony with it’s parent and children tasks. In the Task classes we just focus on specifying the specific logic for the task at hand.

Reason Two: Safety in the Decorators

If we take the utility/state logic out of the Task class, we can make all the methods abstract, and when we create the Decorator classes, the compiler checks to see if we have overridden all the abstract functions (if we forget to wrap any of the Task functions in the Decorator, we could introduce subtle but dangerous bugs). If we have the utility functions in the Task class we may or may not remember to make a wrapper for them, and if we have to change the interface of the Task class at some point, we could be in for a hell of pain.

Code

All said, some code on how the task controller works:

TaskController

Has the done and success flags, and all the utilities related with them.

Code Snippet
 /**
 * Class added by composition to any task, 
 * to keep track of the Task state
 * and logic flow. 
 * 
 * This state-control class is separated 
 * from the Task class so the Decorators
 * have a chance at compile-time security.
 * @author Ying
 *
 */
public class TaskController 
{
    /**
     * Indicates whether the task is finished 
     * or not
     */
    private boolean done;
    
    /**
     * If finished, it indicates if it has 
     * finished with success or not
     */
    private boolean sucess;
    
    /**
     * Indicates if the task has started 
     * or not
     */
    private boolean started;
    
    /**
     * Reference to the task we monitor
     */
    private Task task;
    
    /**
     * Creates a new instance of the 
     * TaskController class
     * @param task Task to controll.
     */
    public TaskController(Task task)
    {
        SetTask(task);
        Initialize();
    }
    
    /**
     * Initializes the class data
     */
    private void Initialize()
    {
        this.done = false;
        this.sucess = true;
        this.started = false;
    }
    
    /**
     * Sets the task reference
     * @param task Task to monitor
     */
    public void SetTask(Task task)
    {
        this.task = task;
    }
    
    /**
     * Starts the monitored class
     */
    public void SafeStart()
    {
        this.started = true;
        task.Start();
    }
    
    /**
     * Ends the monitored task
     */
    public void SafeEnd()
    {
        this.done = false;
        this.started = false;
        task.End();
    }
    
    /**
     * Ends the monitored class, with success
     */
    protected void FinishWithSuccess()
    {
        this.sucess = true;
        this.done = true;
        task.LogTask("Finished with success");
    }
 
    /**
     * Ends the monitored class, with failure
     */
    protected void FinishWithFailure()
    {
        this.sucess = false;
        this.done = true;
        task.LogTask("Finished with failure");
    }
    
    /**
     * Indicates whether the task 
     * finished successfully
     * @return True if it did, false if it didn't
     */
    public boolean Succeeded() 
    {
        return this.sucess;
    }
    
    /**
     * Indicates whether the task 
     * finished with failure
     * @return True if it did, false if it didn't
     */
    public boolean Failed()
    {
        return !this.sucess;
    }
    
    /**
     * Indicates whether the task finished
     * @return True if it did, false if it didn't
     */
    public boolean Finished() 
    {
        return this.done;
    }
    
    /**
     * Indicates whether the class 
     * has started or not
     * @return True if it has, false if it hasn't
     */
    public boolean Started()
    {
        return this.started;
    }
    
    /**
     * Marks the class as just started.
     */
    public void Reset()
    {
        this.done = false;
    }
}
 

ParentTaskController

We add the subtasks vector, and curTask task to the previous responsibilities of the taskController.

Code Snippet
 /**
 * This class extends the TaskController 
 * class to add support for 
 * child tasks and their logic. 
 * 
 * Used together with ParentTask.
 * 
 * @author Ying
 *
 */
public class ParentTaskController extends TaskController 
{
    /**
     * Vector of child Task
     */
    public Vector<Task> subtasks;
    
    /**
     * Current updating task
     */
    public Task curTask;
 
    /**
     * Creates a new instance of the 
     * ParentTaskController class
     * @param task
     */
    public ParentTaskController(Task task) 
    {
        super(task);
        
        this.subtasks = new Vector<Task>();
        this.curTask = null;
    }
    
    /**
     * Adds a new subtask to the end 
     * of the subtask list.
     * @param task Task to add
     */
    public void Add(Task task)
    {
        subtasks.add(task);
    }
    
    /**
     * Resets the task as if it had 
     * just started.
     */
    public void Reset()
    {
        super.Reset();
        this.curTask = 
            subtasks.firstElement();
    }
}
 

Decorator

The Decorators are used in the BT to add special functionality to any given task. They act as wrappers of the class, calling the class methods and adding the extra functionality where they deem it necessary.

Abstract Decorator Class

A Decorator, as explained in the Decorator Pattern has a reference to the class it “decorates” (in our case private Task task), and also inherits from said class.

Normally, the Decorator adds extra logic in the DoAction method of the task, which is why the base Decorator class presented only overrides the rest of the methods of Task, for simplicity. None the less, if any Decorator subclass needs to override any other method, it can do so with no problem.

Here is the code

Code Snippet
 /**
 * Base class for the specific decorators.
 * Decorates all the task methods except 
 * for the DoAction, for commodity. 
 * 
 * (Tough any method can be decorated in 
 * the base classes with no problem, 
 * they are decorated by default so the 
 * programmer does not forget)
 * 
 * @author Ying
 *
 */
public abstract class TaskDecorator extends Task 
{
    /**
     * Reference to the task to decorate
     */
    Task task;
 
    /**
     * Creates a new instance of the 
     * Decorator class
     * @param blackboard Reference to 
     * the AI Blackboard data
     * @param task Task to decorate
     */
    public TaskDecorator(Blackboard bb, Task task) 
    {
        super(bb);
        InitTask(task);
    }
    
    /**
     * Initializes the task reference
     * @param task Task to decorate
     */
    private void InitTask(Task task)
    {
        this.task = task;
        this.task.GetControl().SetTask(this);
    }
 
    /**
     * Decorate the CheckConditions
     */
    @Override
    public boolean CheckConditions() 
    {
        return this.task.CheckConditions();
    }
 
    /**
     * Decorate the end
     */
    @Override
    public void End() 
    {
        this.task.End();
    }
 
    /**
     * Decorate the request for the 
     * Controll reference
     */
    @Override
    public TaskController GetControl() 
    {
        return this.task.GetControl();
    }
 
    /**
     * Decorate the start
     */
    @Override
    public void Start() 
    {
        this.task.Start();
 
    }
}
 

Examples

Here are some specific examples of Decorators.

ResetDecorator

Simply checks to see if the task it decorates has finished. If it has, it resets the task to “ready to execute again”.

Code Snippet
 /**
 * Decorator that resets to "Started" the task 
 * it is applied to, each time said task finishes.
 * 
 * @author Ying
 *
 */
public class ResetDecorator extends TaskDecorator 
{    
    /**
     * Creates a new instance of the 
     * ResetDecorator class
     * @param blackboard Reference to 
     *  the AI Blackboard data
     * @param task Task to decorate
     */
    public ResetDecorator(Blackboard bb, 
        Task task) 
    {
        super(bb, task);
    }
 
    /**
     * Does the decorated task's action, 
     * and if it's done, resets it.
     */
    @Override
    public void DoAction() 
    {
        this.task.DoAction();
        if(this.task.GetControl().Finished())
        {
            this.task.GetControl().Reset();
        }
 
    }
}
 

RegulatorDecorator

Updates the task it decorates at a specific speed. This case of Decorator also overrides the Start method.

Code Snippet
 /**
 * Decorator that adds a update speed 
 * limit to the task it is applied to
 * @author Ying
 *
 */
public class RegulatorDecorator extends TaskDecorator 
{
    /**
     * Regulator to keep track of time
     */
    private Regulator regulator;
    
    /**
     * Update time in seconds per frame
     */
    private float updateTime;
        
    /**
     * Creates a new instance of the 
     * RegulatorDecorator class
     * @param blackboard Reference to the 
     *  AI Blackboard data
     * @param task Task to decorate
     * @param updateTime Time between each 
     *  frame update
     */
    public RegulatorDecorator(Blackboard bb, 
        Task task, float updateTime) 
    {
        super(bb, task);
        this.updateTime = updateTime;
    }
 
    /**
     * Starts the task and the regulator
     */
    @Override 
    public void Start()
    {
        task.Start();
        this.regulator = 
            new Regulator(1.0f/updateTime);
    }
    
    /**
     * Updates the decorated task only if the 
     * required time since the last update has 
     * elapsed.
     */
    @Override
    public void DoAction() 
    {
        if(this.regulator.IsReady())
        {
            task.DoAction();
        }
    }
}
 

Example

Usage Example

With all the code mentioned earlier, it’s a little easy to get lost, so here is a reminder of how this is supposed to work. We are going to create a simple BT with just two basic behaviors, Chase and Flee. (This is taken straight from the game code).

Code Snippet
 /**
* Creates the behavior tree and populates 
* the node hierarchy
*/
private void CreateBehaviourTree()
{
    // Create a root node for the tree, that
    // resets itself and updates at 10 fps
    this.planner = new Selector(
        blackboard, 
        "Planner");
    this.planner = new ResetDecorator(
        blackboard, 
        this.planner, "Planner");
    this.planner = new RegulatorDecorator(
        blackboard, 
        this.planner, "Planner", 0.1f);
        
    // Create chase sequence
    Task chase = new Sequence(
        blackboard, 
        "Chase sequence");
    ((ParentTaskController)chase.GetControl()).
        Add(new GetClosestEnemyCursorTask(
        blackboard, 
        "GetClosestEnemyCursor"));
    ((ParentTaskController)chase.GetControl()).
        Add(new SetEnemyCursorAsDestinationTask(
        blackboard, 
        "SetEnemyCursorAsDestination"));
    ((ParentTaskController)chase.GetControl()).
        Add(new MoveToDestinationTask(
        blackboard, 
        "MoveToDestination"));
    ((ParentTaskController)chase.GetControl()).
        Add(new WaitTillNearDestinationTask(
        blackboard, 
        "WaitTillNearDestination"));
        
    // Create the flee sequence
    // It's a normal selector but with extra logic
    // to see if we want to flee or not
    Task flee = new Sequence(blackboard, 
        "Flee sequence");
    flee = new FleeDecorator(blackboard, flee, 
        "Flee sequence");
    ((ParentTaskController)flee.GetControl()).
        Add(new CalculateFleeDestinationTask(
        blackboard, 
        "CalculateFleeDestination"));
    ((ParentTaskController)flee.GetControl()).
        Add(new MoveToDestinationTask(
        blackboard, 
        "MoveToDestination"));
    ((ParentTaskController)flee.GetControl()).
        Add(new WaitTillNearDestinationTask(
        blackboard, 
        "WaitTillNearDestination"));
        
    ((ParentTaskController)this.planner.
        GetControl()).Add(flee);
    ((ParentTaskController)this.planner.
        GetControl()).Add(chase);        
}
 

Diagram

The previous code generates the Behavior Tree shown in this diagram.

Conclusion

Behavior trees are a incredibly interesting tool for game AI. They can be applied to many different types of AI and their modularity makes them a blessing when it comes to extending or modifying an existing AI.

I just hope that with this huge post I have provided the necessary tools for someone who is looking for a nice AI technique for his AI to start working and hopefully avoid the pitfalls I had to survive whilst doing this system.

Happy coding.

PS: The full code for my game Behavior Tree can be found here.

Magic Scrolls of Code

Tuesday, December 14, 2010

Behavior Trees by Example. AI in an Android game.

Introduction

What are Behavior Trees?

Overview

Architecture

General

Tasks

Task

Leaf Task

Base LeafTask class

LeafTask Examples

GetClosestEnemyTask

MoveTo

Parent Task

Sequence

Selector

Task Controller

Introduction

Reason One: Elegance of Design.

Reason Two: Safety in the Decorators

Code

TaskController

ParentTaskController

Decorator

Abstract Decorator Class

Examples

ResetDecorator

RegulatorDecorator

Example

Usage Example

Diagram

Conclusion

Friday, October 8, 2010

3D Picking in Android

Introduction

Algorithm

Notes: