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:

• 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

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

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;
20. /**
21. * Creates a new instance of the
22. * LeafTask class
23. * @param blackboard Reference to the
24. * AI Blackboard data
25. */
26. public LeafTask(Blackboard blackboard)
27. {
28. super(blackboard);
29. CreateController();
30. }
32. /**
33. * Creates the controller for the class
34. */
35. private void CreateController()
36. {
37. this.control = new TaskController(this);
38. }
40. /**
41. * Gets the controller reference.
42. */
43. @Override
44. public TaskController GetControl()
45. {
46. return this.control;
47. }
48. }

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. }
20. /**
21. * Checks for preconditions
22. */
23. @Override
24. public boolean CheckConditions()
25. {
26. return Blackboard.players.size() > 1 &&
27. bb.player.GetCursor().GetPosition() != null;
28. }
30. /**
31. * Finds the closest enemy and stores
32. * it in the Blackboard
33. */
34. @Override
35. public void DoAction()
36. {
37. Enemy closestEnemy = null;
38. // Finds the closest enemy
39. // Omited for clarity
41. // Store it in the blackboard
42. bb.closestEnemy = closestEnemy;
43. GetControll().FinishWithSuccess();
44. }
46. /**
47. * Ends the task
48. */
49. @Override
50. public void End()
51. {
52. LogTask("Ending");
53. }
55. /**
56. * Starts the task
57. */
58. @Override
59. public void Start()
60. {
61. LogTask("Starting");
62. }
63. }

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. }
22. /**
23. * Sanity check of needed data for the
24. * operations
25. */
26. @Override
27. public boolean CheckConditions()
28. {
29. LogTask("Checking conditions");
30. return bb.moveDirection != null;
31. }
33. /**
34. * Requests the cursor to move
35. */
36. @Override
37. public void DoAction()
38. {
39. LogTask("Doing action");
40. bb.player.Move(bb.moveDirection);
41. control.FinishWithSuccess();
42. }
44. /**
45. * Ends the task
46. */
47. @Override
48. public void End()
49. {
50. LogTask("Ending");
51. }
53. /**
54. * Starts the task
55. */
56. @Override
57. public void Start()
58. {
59. LogTask("Starting");
60. }
61. }

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;
20. public ParentTask(Blackboard bb)
21. {
22. super(bb);
23. CreateController();
24. }
26. /**
27. * Creates the TaskController.
28. */
29. private void CreateController()
30. {
31. this.control =
32. new ParentTaskController(this);
33. }
35. /**
36. * Gets the control reference
37. */
38. @Override
39. public TaskController GetControl()
40. {
41. return control;
42. }
44. /**
45. * Checks for the appropiate pre-state
46. * of the data
47. */
48. @Override
49. public boolean CheckConditions()
50. {
51. LogTask("Checking conditions");
52. return control.subtasks.size() > 0;
53. }
55. /**
56. * Abstract to be overridden in child
57. * classes. Called when a child finishes
58. * with success.
59. */
60. public abstract void ChildSucceeded();
62. /**
63. * Abstract to be overridden in child
64. * classes. Called when a child finishes
65. * with failure.
66. */
67. public abstract void ChildFailed();
69. /**
70. * Checks whether the child has started,
71. * finished or needs updating, and takes
72. * the needed measures in each case
73. *
74. * "curTask" is the current selected task,
75. * a member of our ParentTaskController
76. */
77. @Override
78. public void DoAction()
79. {
80. LogTask("Doing action");
81. if(control.Finished())
82. {
83. // If this parent task is finished
84. // return without doing naught.
85. return;
86. }
87. if(control.curTask == null)
88. {
89. // If there is a null child task
90. // selected we've done something wrong
91. return;
92. }
94. // If we do have a curTask...
95. if( !control.curTask.
96. GetControl().Started())
97. {
98. // ... and it's not started yet, start it.
99. control.curTask.
100. GetControl().SafeStart();
101. }
102. else if(control.curTask.
103. GetControl().Finished())
104. {
105. // ... and it's finished, end it properly.
106. control.curTask.
107. GetControl().SafeEnd();
109. if(control.curTask.
110. GetControl().Succeeded())
111. {
112. this.ChildSucceeded();
113. }
114. if(control.curTask.
115. GetControl().Failed())
116. {
117. this.ChildFailed();
118. }
119. }
120. else
121. {
122. // ... and it's ready, update it.
123. control.curTask.DoAction();
124. }
125. }
127. /**
128. * Ends the task
129. */
130. @Override
131. public void End()
132. {
133. LogTask("Ending");
134. }
136. /**
137. * Starts the task, and points the
138. * current task to the first one
139. * of the available child tasks.
140. */
141. @Override
142. public void Start()
143. {
144. LogTask("Starting");
145. control.curTask =
146. control.subtasks.firstElement();
147. if(control.curTask == null)
148. {
149. Log.e("Current task has a null action");
150. }
151. }
152. }

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. }
30. /**
31. * A child finished with failure.
32. * We failed to update the whole sequence.
33. * Bail with failure.
34. */
35. @Override
36. public void ChildFailed()
37. {
38. control.FinishWithFailure();
39. }
41. /**
42. * A child has finished with success
43. * Select the next one to update. If
44. * it's the last, we have finished with
45. * success.
46. */
47. @Override
48. public void ChildSucceeded()
49. {
50. int curPos =
51. control.subtasks.
52. indexOf(control.curTask);
53. if( curPos ==
54. (control.subtasks.size() - 1))
55. {
56. control.FinishWithSuccess();
57. }
58. else
59. {
60. control.curTask =
61. control.subtasks.
62. elementAt(curPos+1);
63. if(!control.curTask.CheckConditions())
64. {
65. control.FinishWithFailure();
66. }
67. }
68. }
69. }

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. }
35. /**
36. * Chooses the new task to update.
37. * @return The new task, or null
38. * if none was found
39. */
40. public Task ChooseNewTask()
41. {
42. Task task = null;
43. boolean found = false;
44. int curPos =
45. control.subtasks.
46. indexOf(control.curTask);
48. while(!found)
49. {
50. if(curPos ==
51. (control.subtasks.size() - 1))
52. {
53. found = true;
54. task = null;
55. break;
56. }
58. curPos++;
60. task = control.subtasks.
61. elementAt(curPos);
62. if(task.CheckConditions())
63. {
64. found = true;
65. }
66. }
68. return task;
69. }
71. /**
72. * In case of child finishing with
73. * failure we find a new one to update,
74. * or fail if none is to be found
75. */
76. @Override
77. public void ChildFailed()
78. {
79. control.curTask = ChooseNewTask();
80. if(control.curTask == null)
81. {
82. control.FinishWithFailure();
83. }
84. }
86. /**
87. * In case of child finishing with
88. * sucess, our job here is done, finish
89. * with sucess
90. * as well
91. */
92. @Override
93. public void ChildSucceeded()
94. {
95. control.FinishWithSuccess();
96. }
97. }

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;
20. /**
21. * If finished, it indicates if it has
22. * finished with success or not
23. */
24. private boolean sucess;
26. /**
27. * Indicates if the task has started
28. * or not
29. */
30. private boolean started;
32. /**
33. * Reference to the task we monitor
34. */
35. private Task task;
37. /**
38. * Creates a new instance of the
39. * TaskController class
40. * @param task Task to controll.
41. */
42. public TaskController(Task task)
43. {
44. SetTask(task);
45. Initialize();
46. }
48. /**
49. * Initializes the class data
50. */
51. private void Initialize()
52. {
53. this.done = false;
54. this.sucess = true;
55. this.started = false;
56. }
58. /**
59. * Sets the task reference
60. * @param task Task to monitor
61. */
62. public void SetTask(Task task)
63. {
64. this.task = task;
65. }
67. /**
68. * Starts the monitored class
69. */
70. public void SafeStart()
71. {
72. this.started = true;
73. task.Start();
74. }
76. /**
77. * Ends the monitored task
78. */
79. public void SafeEnd()
80. {
81. this.done = false;
82. this.started = false;
83. task.End();
84. }
86. /**
87. * Ends the monitored class, with success
88. */
89. protected void FinishWithSuccess()
90. {
91. this.sucess = true;
92. this.done = true;
93. task.LogTask("Finished with success");
94. }
96. /**
97. * Ends the monitored class, with failure
98. */
99. protected void FinishWithFailure()
100. {
101. this.sucess = false;
102. this.done = true;
103. task.LogTask("Finished with failure");
104. }
106. /**
107. * Indicates whether the task
108. * finished successfully
109. * @return True if it did, false if it didn't
110. */
111. public boolean Succeeded()
112. {
113. return this.sucess;
114. }
116. /**
117. * Indicates whether the task
118. * finished with failure
119. * @return True if it did, false if it didn't
120. */
121. public boolean Failed()
122. {
123. return !this.sucess;
124. }
126. /**
127. * Indicates whether the task finished
128. * @return True if it did, false if it didn't
129. */
130. public boolean Finished()
131. {
132. return this.done;
133. }
135. /**
136. * Indicates whether the class
137. * has started or not
138. * @return True if it has, false if it hasn't
139. */
140. public boolean Started()
141. {
142. return this.started;
143. }
145. /**
146. * Marks the class as just started.
147. */
148. public void Reset()
149. {
150. this.done = false;
151. }
152. }

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;
18. /**
19. * Current updating task
20. */
21. public Task curTask;
23. /**
24. * Creates a new instance of the
25. * ParentTaskController class
26. * @param task
27. */
28. public ParentTaskController(Task task)
29. {
30. super(task);
32. this.subtasks = new Vector<Task>();
33. this.curTask = null;
34. }
36. /**
37. * Adds a new subtask to the end
38. * of the subtask list.
39. * @param task Task to add
40. */
41. public void Add(Task task)
42. {
43. subtasks.add(task);
44. }
46. /**
47. * Resets the task as if it had
48. * just started.
49. */
50. public void Reset()
51. {
52. super.Reset();
53. this.curTask =
54. subtasks.firstElement();
55. }
56. }

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;
21. /**
22. * Creates a new instance of the
23. * Decorator class
24. * @param blackboard Reference to
25. * the AI Blackboard data
26. * @param task Task to decorate
27. */
28. public TaskDecorator(Blackboard bb, Task task)
29. {
30. super(bb);
31. InitTask(task);
32. }
34. /**
35. * Initializes the task reference
36. * @param task Task to decorate
37. */
38. private void InitTask(Task task)
39. {
40. this.task = task;
41. this.task.GetControl().SetTask(this);
42. }
44. /**
45. * Decorate the CheckConditions
46. */
47. @Override
48. public boolean CheckConditions()
49. {
50. return this.task.CheckConditions();
51. }
53. /**
54. * Decorate the end
55. */
56. @Override
57. public void End()
58. {
59. this.task.End();
60. }
62. /**
63. * Decorate the request for the
64. * Controll reference
65. */
66. @Override
67. public TaskController GetControl()
68. {
69. return this.task.GetControl();
70. }
72. /**
73. * Decorate the start
74. */
75. @Override
76. public void Start()
77. {
78. this.task.Start();
80. }
81. }

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. }
23. /**
24. * Does the decorated task's action,
25. * and if it's done, resets it.
26. */
27. @Override
28. public void DoAction()
29. {
30. this.task.DoAction();
31. if(this.task.GetControl().Finished())
32. {
33. this.task.GetControl().Reset();
34. }
36. }
37. }

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;
14. /**
15. * Update time in seconds per frame
16. */
17. private float updateTime;
19. /**
20. * Creates a new instance of the
21. * RegulatorDecorator class
22. * @param blackboard Reference to the
23. * AI Blackboard data
24. * @param task Task to decorate
25. * @param updateTime Time between each
26. * frame update
27. */
28. public RegulatorDecorator(Blackboard bb,
29. Task task, float updateTime)
30. {
31. super(bb, task);
32. this.updateTime = updateTime;
33. }
35. /**
36. * Starts the task and the regulator
37. */
38. @Override
39. public void Start()
40. {
41. task.Start();
42. this.regulator =
43. new Regulator(1.0f/updateTime);
44. }
46. /**
47. * Updates the decorated task only if the
48. * required time since the last update has
49. * elapsed.
50. */
51. @Override
52. public void DoAction()
53. {
54. if(this.regulator.IsReady())
55. {
56. task.DoAction();
57. }
58. }
59. }

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);
19. // Create chase sequence
20. Task chase = new Sequence(
21. blackboard,
22. "Chase sequence");
23. ((ParentTaskController)chase.GetControl()).
24. Add(new GetClosestEnemyCursorTask(
25. blackboard,
26. "GetClosestEnemyCursor"));
27. ((ParentTaskController)chase.GetControl()).
28. Add(new SetEnemyCursorAsDestinationTask(
29. blackboard,
30. "SetEnemyCursorAsDestination"));
31. ((ParentTaskController)chase.GetControl()).
32. Add(new MoveToDestinationTask(
33. blackboard,
34. "MoveToDestination"));
35. ((ParentTaskController)chase.GetControl()).
36. Add(new WaitTillNearDestinationTask(
37. blackboard,
38. "WaitTillNearDestination"));
40. // Create the flee sequence
41. // It's a normal selector but with extra logic
42. // to see if we want to flee or not
43. Task flee = new Sequence(blackboard,
44. "Flee sequence");
45. flee = new FleeDecorator(blackboard, flee,
46. "Flee sequence");
47. ((ParentTaskController)flee.GetControl()).
48. Add(new CalculateFleeDestinationTask(
49. blackboard,
50. "CalculateFleeDestination"));
51. ((ParentTaskController)flee.GetControl()).
52. Add(new MoveToDestinationTask(
53. blackboard,
54. "MoveToDestination"));
55. ((ParentTaskController)flee.GetControl()).
56. Add(new WaitTillNearDestinationTask(
57. blackboard,
58. "WaitTillNearDestination"));
60. ((ParentTaskController)this.planner.
61. GetControl()).Add(flee);
62. ((ParentTaskController)this.planner.
63. GetControl()).Add(chase);
64. }

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.