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.

Friday, October 8, 2010

3D Picking in Android

Introduction

In this short tutorial I’m presenting something that’s made me loose weeks of work. How to implement picking with a perspective camera in the Android platform using OPENGL 1.0.

The process of picking basically involves the user clicking a point in their device screen, we take that point and apply the inverse transforms that opengl applies to it’s 3D scene, and so get a point in the world coordinate system (wcs) that is where the player wanted to click. For the sake of simplicity, we will work on a simple 2D map, instead of having to cast a ray to intersect multiple objects.

Usually, in opengl we would use the function glUnProject to un-project the point and so get the wcs equivalent point, but that function is plagued by errors on the Android platform and it’ very difficult to get the gl transformations for the projection and model matrixes.

Algorithm

So here is my solution. It might not be perfect, but it actually works.

Code Snippet
  1. /**
  2.     * Calculates the transform from screen coordinate
  3.     * system to world coordinate system coordinates
  4.     * for a specific point, given a camera position.
  5.     *
  6.     * @param touch Vec2 point of screen touch, the
  7.       actual position on physical screen (ej: 160, 240)
  8.     * @param cam camera object with x,y,z of the
  9.       camera and screenWidth and screenHeight of
  10.       the device.
  11.     * @return position in WCS.
  12.     */
  13.    public Vec2 GetWorldCoords( Vec2 touch, Camera cam)
  14.    {  
  15.        // Initialize auxiliary variables.
  16.        Vec2 worldPos = new Vec2();
  17.        
  18.        // SCREEN height & width (ej: 320 x 480)
  19.        float screenW = cam.GetScreenWidth();
  20.        float screenH = cam.GetScreenHeight();
  21.               
  22.        // Auxiliary matrix and vectors
  23.        // to deal with ogl.
  24.        float[] invertedMatrix, transformMatrix,
  25.            normalizedInPoint, outPoint;
  26.        invertedMatrix = new float[16];
  27.        transformMatrix = new float[16];
  28.        normalizedInPoint = new float[4];
  29.        outPoint = new float[4];
  30.  
  31.        // Invert y coordinate, as android uses
  32.        // top-left, and ogl bottom-left.
  33.        int oglTouchY = (int) (screenH - touch.Y());
  34.        
  35.        /* Transform the screen point to clip
  36.        space in ogl (-1,1) */       
  37.        normalizedInPoint[0] =
  38.         (float) ((touch.X()) * 2.0f / screenW - 1.0);
  39.        normalizedInPoint[1] =
  40.         (float) ((oglTouchY) * 2.0f / screenH - 1.0);
  41.        normalizedInPoint[2] = - 1.0f;
  42.        normalizedInPoint[3] = 1.0f;
  43.  
  44.        /* Obtain the transform matrix and
  45.        then the inverse. */
  46.        Print("Proj", getCurrentProjection(gl));
  47.        Print("Model", getCurrentModelView(gl));
  48.        Matrix.multiplyMM(
  49.            transformMatrix, 0,
  50.            getCurrentProjection(gl), 0,
  51.            getCurrentModelView(gl), 0);
  52.        Matrix.invertM(invertedMatrix, 0,
  53.            transformMatrix, 0);       
  54.  
  55.        /* Apply the inverse to the point
  56.        in clip space */
  57.        Matrix.multiplyMV(
  58.            outPoint, 0,
  59.            invertedMatrix, 0,
  60.            normalizedInPoint, 0);
  61.        
  62.        if (outPoint[3] == 0.0)
  63.        {
  64.            // Avoid /0 error.
  65.            Log.e("World coords", "ERROR!");
  66.            return worldPos;
  67.        }
  68.        
  69.        // Divide by the 3rd component to find
  70.        // out the real position.
  71.        worldPos.Set(
  72.            outPoint[0] / outPoint[3],
  73.            outPoint[1] / outPoint[3]);
  74.          
  75.        return worldPos;       
  76.    }

In my case, I’ve got a render, a logic and an application thread, this function is a service provided by the render thread, because it needs the gl Projection and ModelView matrixes.

What happens is the logic thread sends a touch (x,y) position, and the current camera (x,y,z, screenH, screenW), to the GetWorldCoords function, and expects the world position of that point taking into accound the camera position (x,y,z), and the view fustrum (represented by the projection and modelview matrixes).

The first lines get the data ready, create auxiliary matrixes and access camera data.

One important point is the line

int oglTouchY = (int) (screenH - touch.Y());

This inversion is needed because android screen coordinates assume a top-left coordinate system, and opengl needs a bottom left. So we change it. And with that we can start doing the picking algorithm.

  1. Transform the point from screen coordinates (ej: 120, 330) to clip space (for a 320 x 480 android, this would be –0.25, 0.375)
  2. Get the transformation matrix (projection * modelView), and invert it.
  3. Multiply the clip-space point times the inverse transformation.
  4. Divide the coordinates x,y,z (positions 0,1,2) times the w (position 3)
  5. You’ve got the world coordinates.

Notes:

The z doesn’t appear because I don’t have need for it, but you can get it easily (outPoint[2] / outPoint[3]).

The situation I’m working on is the following. The red and blue are the frustum limits, the green is the world map, at an arbitrary point in space, and the camera is at the tip of the view frustum.

80880607

There is one very special complication when doing this picking algorithm in the android platform and that is accessing the projection and model view matrixes opengl uses. We manage with the following code.

Code Snippet
  1. /**
  2.     * Record the current modelView matrix
  3.     * state. Has the side effect of
  4.     * setting the current matrix state
  5.     * to GL_MODELVIEW
  6.     * @param gl context
  7.     */
  8.    public float[] getCurrentModelView(GL10 gl)
  9.    {
  10.         float[] mModelView = new float[16];
  11.         getMatrix(gl, GL10.GL_MODELVIEW, mModelView);
  12.         return mModelView;
  13.    }
  14.  
  15.    /**
  16.     * Record the current projection matrix
  17.     * state. Has the side effect of
  18.     * setting the current matrix state
  19.     * to GL_PROJECTION
  20.     * @param gl context
  21.     */
  22.    public float[] getCurrentProjection(GL10 gl)
  23.    {
  24.        float[] mProjection = new float[16];
  25.        getMatrix(gl, GL10.GL_PROJECTION, mProjection);
  26.        return mProjection;
  27.    }
  28.  
  29.    /**
  30.     * Fetches a specific matrix from opengl
  31.     * @param gl context
  32.     * @param mode of the matrix
  33.     * @param mat initialized float[16] array
  34.     * to fill with the matrix
  35.     */
  36.    private void getMatrix(GL10 gl, int mode, float[] mat)
  37.    {
  38.        MatrixTrackingGL gl2 = (MatrixTrackingGL) gl;
  39.        gl2.glMatrixMode(mode);
  40.        gl2.getMatrix(mat, 0);
  41.    }

 

The gl parameter passed to the getCurrent*(GL10 gl) functions is stored as a member variable in the class.

The MatrixTrackingGL class is part of the android samples, and can be found here. Some other classes must be included for it to work (mainly MatrixStack). The MatrixTrackingGL class acts as a wrapper for the gl context, but providing the data we need. For it to work, our custom GLSurfaceView class must have the GLWrapper call, something like this.

Code Snippet
  1. public DagGLSurfaceView(Context context)
  2. {
  3.     super(context);       
  4.         
  5.     setFocusable(true);
  6.         
  7.     // Wrapper set so the renderer can
  8.     //access the gl transformation matrixes.
  9.     setGLWrapper(
  10.     new GLSurfaceView.GLWrapper()
  11.     {
  12.         @Override
  13.         public GL wrap(GL gl)
  14.         {
  15.             return new MatrixTrackingGL(gl);
  16.         }
  17.     });  
  18.         
  19.     mRenderer = new DagRenderer();
  20.     setRenderer(mRenderer);
  21. }

(Where DagRender is my GLSurfaceView.Renderer, and DagGLSurfaceView is my GLSurfaceView)