Tuesday, December 14, 2010

Behavior Trees by Example. AI in an Android game.

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:

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.

ClassDiagramBT

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
  1. /**
  2. * Base abstract class for all the tasks in
  3. * the behavior tree.
  4. *
  5. * @author Ying
  6. *
  7. */
  8. public abstract class Task
  9. {
  10. /**
  11. * Reference to the Blackboard data
  12. */
  13. protected Blackboard bb;
  14. /**
  15. * Creates a new instance of the Task class
  16. * @param blackboard Reference to the
  17. * AI Blackboard data
  18. */
  19. public Task(Blackboard blackboard)
  20. {
  21. this.bb = blackboard;
  22. }
  23. /**
  24. * Override to do a pre-conditions check to
  25. * see if the task can be updated.
  26. * @return True if it can, false if it can't
  27. */
  28. public abstract boolean CheckConditions();
  29. /**
  30. * Override to add startup logic to the task
  31. */
  32. public abstract void Start();
  33. /**
  34. * Override to add ending logic to the task
  35. */
  36. public abstract void End();
  37. /**
  38. * Override to specify the logic the task
  39. * must update each cycle
  40. */
  41. public abstract void DoAction();
  42. /**
  43. * Override to specify the controller the
  44. * task has
  45. * @return The specific task controller.
  46. */
  47. public abstract TaskController GetControl();
  48. }

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
  1. /**
  2. * Leaf task (or node) in the behavior tree.
  3. *
  4. * Specifies a TaskControler, by composition,
  5. * to take care of all the control logic,
  6. * without burdening the Task class with
  7. * complications.
  8. *
  9. * @author Ying
  10. *
  11. */
  12. public abstract class LeafTask extends Task
  13. {
  14. /**
  15. * Task controler to keep track of the
  16. * Task state.
  17. */
  18. protected TaskController control;
  19. /**
  20. * Creates a new instance of the
  21. * LeafTask class
  22. * @param blackboard Reference to the
  23. * AI Blackboard data
  24. */
  25. public LeafTask(Blackboard blackboard)
  26. {
  27. super(blackboard);
  28. CreateController();
  29. }
  30. /**
  31. * Creates the controller for the class
  32. */
  33. private void CreateController()
  34. {
  35. this.control = new TaskController(this);
  36. }
  37. /**
  38. * Gets the controller reference.
  39. */
  40. @Override
  41. public TaskController GetControl()
  42. {
  43. return this.control;
  44. }
  45. }

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

  1. GetClosestEnemy
  2. SetClosestEnemyPositionAsDestination
  3. MoveToDestination
  4. WaitUntilPositionNearDestination

Flee

  1. CalculateFleeDestination
  2. MoveToDestination
  3. 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
  1. /**
  2. * Finds the closest enemy and stores
  3. * it in the Blackboard.
  4. * @author Ying
  5. *
  6. */
  7. public class GetClosestEnemyTask extends LeafTask
  8. {
  9. /**
  10. * Creates a new instance of the
  11. * GetClosestEnemyTask task
  12. * @param blackboard Reference to the
  13. * AI Blackboard data
  14. */
  15. public GetClosestEnemyTask(Blackboard bb)
  16. {
  17. super(bb);
  18. }
  19. /**
  20. * Checks for preconditions
  21. */
  22. @Override
  23. public boolean CheckConditions()
  24. {
  25. return Blackboard.players.size() > 1 &&
  26. bb.player.GetCursor().GetPosition() != null;
  27. }
  28. /**
  29. * Finds the closest enemy and stores
  30. * it in the Blackboard
  31. */
  32. @Override
  33. public void DoAction()
  34. {
  35. Enemy closestEnemy = null;
  36. // Finds the closest enemy
  37. // Omited for clarity
  38. // Store it in the blackboard
  39. bb.closestEnemy = closestEnemy;
  40. GetControll().FinishWithSuccess();
  41. }
  42. /**
  43. * Ends the task
  44. */
  45. @Override
  46. public void End()
  47. {
  48. LogTask("Ending");
  49. }
  50. /**
  51. * Starts the task
  52. */
  53. @Override
  54. public void Start()
  55. {
  56. LogTask("Starting");
  57. }
  58. }
MoveTo
Code Snippet
  1. /**
  2. * This task requests the player to
  3. * move to a given destination.
  4. * It takes the destination from
  5. * the Blackboard.
  6. * @author Ying
  7. *
  8. */
  9. public class MoveToDestinationTask extends LeafTask
  10. {
  11. /**
  12. * Creates a new instance of the
  13. * MoveToDestinationTask class
  14. * @param blackboard Reference of the
  15. * AI Blackboard data
  16. */
  17. public MoveToDestinationTask(Blackboard bb)
  18. {
  19. super(bb);
  20. }
  21. /**
  22. * Sanity check of needed data for the
  23. * operations
  24. */
  25. @Override
  26. public boolean CheckConditions()
  27. {
  28. LogTask("Checking conditions");
  29. return bb.moveDirection != null;
  30. }
  31. /**
  32. * Requests the cursor to move
  33. */
  34. @Override
  35. public void DoAction()
  36. {
  37. LogTask("Doing action");
  38. bb.player.Move(bb.moveDirection);
  39. control.FinishWithSuccess();
  40. }
  41. /**
  42. * Ends the task
  43. */
  44. @Override
  45. public void End()
  46. {
  47. LogTask("Ending");
  48. }
  49. /**
  50. * Starts the task
  51. */
  52. @Override
  53. public void Start()
  54. {
  55. LogTask("Starting");
  56. }
  57. }

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
  1. /**
  2. * Inner node of the behavior tree, a
  3. * flow director node that selects the
  4. * child to be executed next.
  5. * (Sounds macabre, hu?)
  6. *
  7. * Sets a specific kind of TaskController for
  8. * these kinds of tasks.
  9. *
  10. * @author Ying
  11. *
  12. */
  13. public abstract class ParentTask extends Task
  14. {
  15. /**
  16. * TaskControler for the parent task
  17. */
  18. ParentTaskController control;
  19. public ParentTask(Blackboard bb)
  20. {
  21. super(bb);
  22. CreateController();
  23. }
  24. /**
  25. * Creates the TaskController.
  26. */
  27. private void CreateController()
  28. {
  29. this.control =
  30. new ParentTaskController(this);
  31. }
  32. /**
  33. * Gets the control reference
  34. */
  35. @Override
  36. public TaskController GetControl()
  37. {
  38. return control;
  39. }
  40. /**
  41. * Checks for the appropiate pre-state
  42. * of the data
  43. */
  44. @Override
  45. public boolean CheckConditions()
  46. {
  47. LogTask("Checking conditions");
  48. return control.subtasks.size() > 0;
  49. }
  50. /**
  51. * Abstract to be overridden in child
  52. * classes. Called when a child finishes
  53. * with success.
  54. */
  55. public abstract void ChildSucceeded();
  56. /**
  57. * Abstract to be overridden in child
  58. * classes. Called when a child finishes
  59. * with failure.
  60. */
  61. public abstract void ChildFailed();
  62. /**
  63. * Checks whether the child has started,
  64. * finished or needs updating, and takes
  65. * the needed measures in each case
  66. *
  67. * "curTask" is the current selected task,
  68. * a member of our ParentTaskController
  69. */
  70. @Override
  71. public void DoAction()
  72. {
  73. LogTask("Doing action");
  74. if(control.Finished())
  75. {
  76. // If this parent task is finished
  77. // return without doing naught.
  78. return;
  79. }
  80. if(control.curTask == null)
  81. {
  82. // If there is a null child task
  83. // selected we've done something wrong
  84. return;
  85. }
  86. // If we do have a curTask...
  87. if( !control.curTask.
  88. GetControl().Started())
  89. {
  90. // ... and it's not started yet, start it.
  91. control.curTask.
  92. GetControl().SafeStart();
  93. }
  94. else if(control.curTask.
  95. GetControl().Finished())
  96. {
  97. // ... and it's finished, end it properly.
  98. control.curTask.
  99. GetControl().SafeEnd();
  100. if(control.curTask.
  101. GetControl().Succeeded())
  102. {
  103. this.ChildSucceeded();
  104. }
  105. if(control.curTask.
  106. GetControl().Failed())
  107. {
  108. this.ChildFailed();
  109. }
  110. }
  111. else
  112. {
  113. // ... and it's ready, update it.
  114. control.curTask.DoAction();
  115. }
  116. }
  117. /**
  118. * Ends the task
  119. */
  120. @Override
  121. public void End()
  122. {
  123. LogTask("Ending");
  124. }
  125. /**
  126. * Starts the task, and points the
  127. * current task to the first one
  128. * of the available child tasks.
  129. */
  130. @Override
  131. public void Start()
  132. {
  133. LogTask("Starting");
  134. control.curTask =
  135. control.subtasks.firstElement();
  136. if(control.curTask == null)
  137. {
  138. Log.e("Current task has a null action");
  139. }
  140. }
  141. }

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:

  1. Safety checks to see if we have all the data, and it’s not null
  2. If the current child task is not started, start it
  3. 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)
  4. 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:

    1. GetClosestEnemy
    2. SetClosestEnemyPositionAsDestination
    3. MoveToDestination
    4. 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
  1. /**
  2. * This ParentTask executes each of it's children
  3. * in turn until he has finished all of them.
  4. *
  5. * It always starts by the first child,
  6. * updating each one.
  7. * If any child finishes with failure, the
  8. * Sequence fails, and we finish with failure.
  9. * When a child finishes with success, we
  10. * select the next child as the update victim.
  11. * If we have finished updating the last child,
  12. * the Sequence returns with success.
  13. *
  14. * @author Ying
  15. *
  16. */
  17. public class Sequence extends ParentTask
  18. {
  19. /**
  20. * Creates a new instance of the
  21. * Sequence class
  22. * @param blackboard Reference to
  23. * the AI Blackboard data
  24. */
  25. public Sequence(Blackboard bb)
  26. {
  27. super(bb);
  28. }
  29. /**
  30. * A child finished with failure.
  31. * We failed to update the whole sequence.
  32. * Bail with failure.
  33. */
  34. @Override
  35. public void ChildFailed()
  36. {
  37. control.FinishWithFailure();
  38. }
  39. /**
  40. * A child has finished with success
  41. * Select the next one to update. If
  42. * it's the last, we have finished with
  43. * success.
  44. */
  45. @Override
  46. public void ChildSucceeded()
  47. {
  48. int curPos =
  49. control.subtasks.
  50. indexOf(control.curTask);
  51. if( curPos ==
  52. (control.subtasks.size() - 1))
  53. {
  54. control.FinishWithSuccess();
  55. }
  56. else
  57. {
  58. control.curTask =
  59. control.subtasks.
  60. elementAt(curPos+1);
  61. if(!control.curTask.CheckConditions())
  62. {
  63. control.FinishWithFailure();
  64. }
  65. }
  66. }
  67. }

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
  1. /**
  2. * This parent task selects one of it's
  3. * children to update.
  4. *
  5. * To select a child, it starts from the
  6. * beginning of it's children vector
  7. * and goes one by one until it finds one
  8. * that passes the CheckCondition test.
  9. * It then updates that child until its
  10. * finished.
  11. * If the child finishes with failure,
  12. * it continues down the list looking another
  13. * candidate to update, and if it doesn't
  14. * find it, it finishes with failure.
  15. * If the child finishes with success, the
  16. * Selector considers it's task done and
  17. * bails with success.
  18. *
  19. * @author Ying
  20. *
  21. */
  22. public class Selector extends ParentTask
  23. {
  24. /**
  25. * Creates a new instance of
  26. * the Selector class
  27. * @param blackboard Reference to
  28. * the AI Blackboard data
  29. */
  30. public Selector(Blackboard bb)
  31. {
  32. super(bb);
  33. }
  34. /**
  35. * Chooses the new task to update.
  36. * @return The new task, or null
  37. * if none was found
  38. */
  39. public Task ChooseNewTask()
  40. {
  41. Task task = null;
  42. boolean found = false;
  43. int curPos =
  44. control.subtasks.
  45. indexOf(control.curTask);
  46. while(!found)
  47. {
  48. if(curPos ==
  49. (control.subtasks.size() - 1))
  50. {
  51. found = true;
  52. task = null;
  53. break;
  54. }
  55. curPos++;
  56. task = control.subtasks.
  57. elementAt(curPos);
  58. if(task.CheckConditions())
  59. {
  60. found = true;
  61. }
  62. }
  63. return task;
  64. }
  65. /**
  66. * In case of child finishing with
  67. * failure we find a new one to update,
  68. * or fail if none is to be found
  69. */
  70. @Override
  71. public void ChildFailed()
  72. {
  73. control.curTask = ChooseNewTask();
  74. if(control.curTask == null)
  75. {
  76. control.FinishWithFailure();
  77. }
  78. }
  79. /**
  80. * In case of child finishing with
  81. * sucess, our job here is done, finish
  82. * with sucess
  83. * as well
  84. */
  85. @Override
  86. public void ChildSucceeded()
  87. {
  88. control.FinishWithSuccess();
  89. }
  90. }

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
  1. /**
  2. * Class added by composition to any task,
  3. * to keep track of the Task state
  4. * and logic flow.
  5. *
  6. * This state-control class is separated
  7. * from the Task class so the Decorators
  8. * have a chance at compile-time security.
  9. * @author Ying
  10. *
  11. */
  12. public class TaskController
  13. {
  14. /**
  15. * Indicates whether the task is finished
  16. * or not
  17. */
  18. private boolean done;
  19. /**
  20. * If finished, it indicates if it has
  21. * finished with success or not
  22. */
  23. private boolean sucess;
  24. /**
  25. * Indicates if the task has started
  26. * or not
  27. */
  28. private boolean started;
  29. /**
  30. * Reference to the task we monitor
  31. */
  32. private Task task;
  33. /**
  34. * Creates a new instance of the
  35. * TaskController class
  36. * @param task Task to controll.
  37. */
  38. public TaskController(Task task)
  39. {
  40. SetTask(task);
  41. Initialize();
  42. }
  43. /**
  44. * Initializes the class data
  45. */
  46. private void Initialize()
  47. {
  48. this.done = false;
  49. this.sucess = true;
  50. this.started = false;
  51. }
  52. /**
  53. * Sets the task reference
  54. * @param task Task to monitor
  55. */
  56. public void SetTask(Task task)
  57. {
  58. this.task = task;
  59. }
  60. /**
  61. * Starts the monitored class
  62. */
  63. public void SafeStart()
  64. {
  65. this.started = true;
  66. task.Start();
  67. }
  68. /**
  69. * Ends the monitored task
  70. */
  71. public void SafeEnd()
  72. {
  73. this.done = false;
  74. this.started = false;
  75. task.End();
  76. }
  77. /**
  78. * Ends the monitored class, with success
  79. */
  80. protected void FinishWithSuccess()
  81. {
  82. this.sucess = true;
  83. this.done = true;
  84. task.LogTask("Finished with success");
  85. }
  86. /**
  87. * Ends the monitored class, with failure
  88. */
  89. protected void FinishWithFailure()
  90. {
  91. this.sucess = false;
  92. this.done = true;
  93. task.LogTask("Finished with failure");
  94. }
  95. /**
  96. * Indicates whether the task
  97. * finished successfully
  98. * @return True if it did, false if it didn't
  99. */
  100. public boolean Succeeded()
  101. {
  102. return this.sucess;
  103. }
  104. /**
  105. * Indicates whether the task
  106. * finished with failure
  107. * @return True if it did, false if it didn't
  108. */
  109. public boolean Failed()
  110. {
  111. return !this.sucess;
  112. }
  113. /**
  114. * Indicates whether the task finished
  115. * @return True if it did, false if it didn't
  116. */
  117. public boolean Finished()
  118. {
  119. return this.done;
  120. }
  121. /**
  122. * Indicates whether the class
  123. * has started or not
  124. * @return True if it has, false if it hasn't
  125. */
  126. public boolean Started()
  127. {
  128. return this.started;
  129. }
  130. /**
  131. * Marks the class as just started.
  132. */
  133. public void Reset()
  134. {
  135. this.done = false;
  136. }
  137. }

ParentTaskController

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

Code Snippet
  1. /**
  2. * This class extends the TaskController
  3. * class to add support for
  4. * child tasks and their logic.
  5. *
  6. * Used together with ParentTask.
  7. *
  8. * @author Ying
  9. *
  10. */
  11. public class ParentTaskController extends TaskController
  12. {
  13. /**
  14. * Vector of child Task
  15. */
  16. public Vector<Task> subtasks;
  17. /**
  18. * Current updating task
  19. */
  20. public Task curTask;
  21. /**
  22. * Creates a new instance of the
  23. * ParentTaskController class
  24. * @param task
  25. */
  26. public ParentTaskController(Task task)
  27. {
  28. super(task);
  29. this.subtasks = new Vector<Task>();
  30. this.curTask = null;
  31. }
  32. /**
  33. * Adds a new subtask to the end
  34. * of the subtask list.
  35. * @param task Task to add
  36. */
  37. public void Add(Task task)
  38. {
  39. subtasks.add(task);
  40. }
  41. /**
  42. * Resets the task as if it had
  43. * just started.
  44. */
  45. public void Reset()
  46. {
  47. super.Reset();
  48. this.curTask =
  49. subtasks.firstElement();
  50. }
  51. }

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
  1. /**
  2. * Base class for the specific decorators.
  3. * Decorates all the task methods except
  4. * for the DoAction, for commodity.
  5. *
  6. * (Tough any method can be decorated in
  7. * the base classes with no problem,
  8. * they are decorated by default so the
  9. * programmer does not forget)
  10. *
  11. * @author Ying
  12. *
  13. */
  14. public abstract class TaskDecorator extends Task
  15. {
  16. /**
  17. * Reference to the task to decorate
  18. */
  19. Task task;
  20. /**
  21. * Creates a new instance of the
  22. * Decorator class
  23. * @param blackboard Reference to
  24. * the AI Blackboard data
  25. * @param task Task to decorate
  26. */
  27. public TaskDecorator(Blackboard bb, Task task)
  28. {
  29. super(bb);
  30. InitTask(task);
  31. }
  32. /**
  33. * Initializes the task reference
  34. * @param task Task to decorate
  35. */
  36. private void InitTask(Task task)
  37. {
  38. this.task = task;
  39. this.task.GetControl().SetTask(this);
  40. }
  41. /**
  42. * Decorate the CheckConditions
  43. */
  44. @Override
  45. public boolean CheckConditions()
  46. {
  47. return this.task.CheckConditions();
  48. }
  49. /**
  50. * Decorate the end
  51. */
  52. @Override
  53. public void End()
  54. {
  55. this.task.End();
  56. }
  57. /**
  58. * Decorate the request for the
  59. * Controll reference
  60. */
  61. @Override
  62. public TaskController GetControl()
  63. {
  64. return this.task.GetControl();
  65. }
  66. /**
  67. * Decorate the start
  68. */
  69. @Override
  70. public void Start()
  71. {
  72. this.task.Start();
  73. }
  74. }

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
  1. /**
  2. * Decorator that resets to "Started" the task
  3. * it is applied to, each time said task finishes.
  4. *
  5. * @author Ying
  6. *
  7. */
  8. public class ResetDecorator extends TaskDecorator
  9. {
  10. /**
  11. * Creates a new instance of the
  12. * ResetDecorator class
  13. * @param blackboard Reference to
  14. * the AI Blackboard data
  15. * @param task Task to decorate
  16. */
  17. public ResetDecorator(Blackboard bb,
  18. Task task)
  19. {
  20. super(bb, task);
  21. }
  22. /**
  23. * Does the decorated task's action,
  24. * and if it's done, resets it.
  25. */
  26. @Override
  27. public void DoAction()
  28. {
  29. this.task.DoAction();
  30. if(this.task.GetControl().Finished())
  31. {
  32. this.task.GetControl().Reset();
  33. }
  34. }
  35. }

RegulatorDecorator

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

Code Snippet
  1. /**
  2. * Decorator that adds a update speed
  3. * limit to the task it is applied to
  4. * @author Ying
  5. *
  6. */
  7. public class RegulatorDecorator extends TaskDecorator
  8. {
  9. /**
  10. * Regulator to keep track of time
  11. */
  12. private Regulator regulator;
  13. /**
  14. * Update time in seconds per frame
  15. */
  16. private float updateTime;
  17. /**
  18. * Creates a new instance of the
  19. * RegulatorDecorator class
  20. * @param blackboard Reference to the
  21. * AI Blackboard data
  22. * @param task Task to decorate
  23. * @param updateTime Time between each
  24. * frame update
  25. */
  26. public RegulatorDecorator(Blackboard bb,
  27. Task task, float updateTime)
  28. {
  29. super(bb, task);
  30. this.updateTime = updateTime;
  31. }
  32. /**
  33. * Starts the task and the regulator
  34. */
  35. @Override
  36. public void Start()
  37. {
  38. task.Start();
  39. this.regulator =
  40. new Regulator(1.0f/updateTime);
  41. }
  42. /**
  43. * Updates the decorated task only if the
  44. * required time since the last update has
  45. * elapsed.
  46. */
  47. @Override
  48. public void DoAction()
  49. {
  50. if(this.regulator.IsReady())
  51. {
  52. task.DoAction();
  53. }
  54. }
  55. }

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
  1. /**
  2. * Creates the behavior tree and populates
  3. * the node hierarchy
  4. */
  5. private void CreateBehaviourTree()
  6. {
  7. // Create a root node for the tree, that
  8. // resets itself and updates at 10 fps
  9. this.planner = new Selector(
  10. blackboard,
  11. "Planner");
  12. this.planner = new ResetDecorator(
  13. blackboard,
  14. this.planner, "Planner");
  15. this.planner = new RegulatorDecorator(
  16. blackboard,
  17. this.planner, "Planner", 0.1f);
  18. // Create chase sequence
  19. Task chase = new Sequence(
  20. blackboard,
  21. "Chase sequence");
  22. ((ParentTaskController)chase.GetControl()).
  23. Add(new GetClosestEnemyCursorTask(
  24. blackboard,
  25. "GetClosestEnemyCursor"));
  26. ((ParentTaskController)chase.GetControl()).
  27. Add(new SetEnemyCursorAsDestinationTask(
  28. blackboard,
  29. "SetEnemyCursorAsDestination"));
  30. ((ParentTaskController)chase.GetControl()).
  31. Add(new MoveToDestinationTask(
  32. blackboard,
  33. "MoveToDestination"));
  34. ((ParentTaskController)chase.GetControl()).
  35. Add(new WaitTillNearDestinationTask(
  36. blackboard,
  37. "WaitTillNearDestination"));
  38. // Create the flee sequence
  39. // It's a normal selector but with extra logic
  40. // to see if we want to flee or not
  41. Task flee = new Sequence(blackboard,
  42. "Flee sequence");
  43. flee = new FleeDecorator(blackboard, flee,
  44. "Flee sequence");
  45. ((ParentTaskController)flee.GetControl()).
  46. Add(new CalculateFleeDestinationTask(
  47. blackboard,
  48. "CalculateFleeDestination"));
  49. ((ParentTaskController)flee.GetControl()).
  50. Add(new MoveToDestinationTask(
  51. blackboard,
  52. "MoveToDestination"));
  53. ((ParentTaskController)flee.GetControl()).
  54. Add(new WaitTillNearDestinationTask(
  55. blackboard,
  56. "WaitTillNearDestination"));
  57. ((ParentTaskController)this.planner.
  58. GetControl()).Add(flee);
  59. ((ParentTaskController)this.planner.
  60. GetControl()).Add(chase);
  61. }

Diagram

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

FlowDiagramBT

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.

14 comments:

  1. wow - thankyou immensely - The code examples given are a great help for me at the planning stage of an AI system.

    Don
    have a great day

    ReplyDelete
  2. Hello,

    first of all, awesome post!

    Can you take a look at this part in your ParentTask:

    # if(control.curTask.
    # GetControl().Succeeded())
    # {
    # this.ChildSucceeded();
    # }
    # if(control.curTask.
    # GetControl().Failed())
    # {
    # this.ChildFailed();
    # }

    If "this" is a Sequence "this.ChildSucceeded" will set a new curTask and the next if-clause automatically fails the sequence since that curTask hasn't actually run yet(Actually, I think this breaks any ParentTask with multiple children). I replaced the 2nd if-clause with a simple "else" and it seems to run fine ...

    ----

    How do you run the whole thing ? I'm currently doing repeated calls to doAction on my root task. Is that the proper way?

    Anyway, many thanks for this, has been a great help.

    ReplyDelete
  3. @RL
    Your version is probably better, I can't think up any arguments against putting an else there, tough note that with my implementation it works, because success is initialized to true, so GetControl().Failed() should return false.

    That said, it looks like an ugly hack now that you mention it, I'll update it when I have some time.

    And yes, just calling DoAction in the root node is the way to go.

    Thanks for commenting, it always makes my day when someone finds this useful. :)

    ReplyDelete
  4. Hola, espero que no te moleste que te escriba en español (ya que veo que eres de valencia), es que mi inglés es un poco peste :)

    Lo primero felicitarte por tu artículo, me ha parecido muy interesante y me ha ayudado a conocer los behavior trees, pero aún tengo algunas dudas y me preguntaba si podrías ayudarme a resolverlas.

    Imagina que tenemos una IA que está en estado relajado, y queremos que cuando vea al jugador empiece a mosquearse (va subiendo un mosqueómetro de 0 a 100 p.e.), cuando llega a 100 va a por ti, pero si deja de verte antes el mosqueómetro va bajando hasta 0 y vuelve a estado relajado.

    Yo aquí identificaría 4 estados: relajado, mosqueándome, mosqueado, desmoqueándome. En los 3 primeros lo único que haría sería poner una animación, y en el último iría a por el player.

    A la hora de modelar esto como BT es cuando comienzan las dudas. Está claro que tendríamos un nodo padre que tendría como hijo los 4 estados, e iría uno por uno comprobando su condición de activación. El estado relajado se activaría si el mosqueómetro vale 0, el estado mosqueándome se activaría si el mosqueómetro es mayor de 1 pero menos de 100, y así el resto. Mi primera duda es donde metería la comprobación del mosqueómetro. Tendría que crear un LeafTask por cada comprobación? un leaftask que lo único que hiciera es mirar si el mosqueómetro es mayor de 0, y en caso afirmativo se ejecutaría la leaftask de su derecha que sería tocar una animación? Quizás no lo entiendo bien, pero esto me parece muy redundante y pesado, andar creando clases solo para hacer este tipo de comprobación.

    Por lo que veo también el leafparent solo comprueba que tengo hijos para ejecutarse, si por ejemplo yo tengo una secuencia de acciones a ejecutar la primera siempre debería ser comprobar que se cumple todo lo necesario para ejecutarse? En el ejemplo anterior, el leafparent Dormido tendría 2 leaftask que la primera comprueba que el mosqueómetro es 0, y la otra toca la animación?

    Espero haber sabido explicarme :) Un saludo y gracias.

    ReplyDelete
  5. Im wrong or there is an error with the implementation of Selector and Sequence?

    They never CheckConditions on firstChild Run it!

    ReplyDelete
  6. God, yes.
    Sorry, curiously enough I have just found that bug myself this week. I haven't gotten around to fixing it yet, but basically, instead of just choosing the first child as the current task, it needs to loop through all of them and select one that meets the CheckConditions()

    ReplyDelete
  7. spend a lot of hours looking why my behavior tree fail and found this error.

    Thanks for the tutorial you saving me weeks of work!

    ReplyDelete
  8. RL it's right without the else the parent task controller didnt work ok.

    if(control.curTask.
    GetControl().Succeeded())
    {
    this.ChildSucceeded();
    } else
    if(control.curTask.
    GetControl().Failed())
    {
    this.ChildFailed();
    }

    I add support for parallel parent task i will test it and post.

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. I am confused about why a Sequence when it is Finished() doesn't set curNode to the beginning again. The Sequence never starts over when the node gets called even though it is Finished. Worse yet, if you use a ResetDecorator, it resets the Sequence okay, but that nver allows the Sequence to finish!! Thus a Sequence of a Sequence doesn't finish!

    I'd love some help if you want to add me on gmail. (DAaaMan64)

    ReplyDelete
  11. I've been using this technique scrolling behavior 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.

    ReplyDelete
  12. Hi, great tutorial! I have to disagree with you assertion that the internet is crawling with information on how to implement behaviour trees, yours is really the only useful one of a very few, so many thanks!

    I realize this post is old but I would like to suggest including a quick overview of the chain of events that happens when the behaviour tree is called, especially for relatively inexperienced programmers (as a lot of game devs are) this is not immediately apparent from looking at the different code snippets.

    Thanks again for such an incredibly useful tutorial!

    ReplyDelete
    Replies
    1. Sorry the blog is a bit out of date by now William. If you're interested on the subject, you can see how BT have improved in the past few years by checking Alex Champanard's excelent video at:

      http://aigamedev.com/insider/tutorial/second-generation-bt/

      (You need to register, but its free, and aigamedev is a good place for game AI anyhow)

      Cheers!

      Delete