The code used in this tutorial can be downloaded here: The ctf_bt_demo project.

Learning Goal

This tutorial teaches you how to use the behavior tree plugin that comes with PALAIS to add reactive decision making to your agents.

Description

This project showcases the usage of the behavior tree plugin. We will be using a very simple behavior tree to control two independent agents. The two agents are placed as opponents on the Capture the Flag (CTF) map. Our goal is to implement a behavior tree that controls the agents to capture the opponent's flag and return it to their own base.

Defining the Game

Firstly, we have to set up our scenario by defining the game rules. You will find the following functions in the file ctf_game.js:

 1 function shoot(actor, target)
 2 {
 3     ...
 4 }
 5 
 6 function takeFlag(actor, color)
 7 {
 8     ...
 9 }
10 
11 function dropFlag(actor, color)
12 {
13     ...
14 }
15 
16 function capture(actor)
17 {
18     ...
19 }
20 
21 function score(actor)
22 {
23     ...
24 }

These functions define the actions our agents can perform. Their actual implementation should be fairly straight-forward and is omitted for brevity.

Spawning Agents

Next, we will spawn the agents we want to take control over. To do so we will provide a wrapper function that will allow us to spawn an arbitrary amount of actors on both sides using the same code.

The wrapper function spawnFighter is defined in ctf_game.js:

 1 // Spawns a fighter with a given name and color.
 2 function spawnFighter(teamColor, name) 
 3 {
 4     var startPos = Scene.getActorByName("flag_" + teamColor).position;
 5     var actor = Scene.instantiate(name,
 6                                   "Soldier2" + teamColor,
 7                                   startPos)
 8 
 9     var lookAtPos = Scene.getKnowledge("goal_" + otherColor(teamColor));
10     actor.lookAt(lookAtPos)
11     actor.setScale(0.2)
12     setInitialState(actor)
13     ...

The first part of the wrapper function instantiates a named programmable actor with the mesh corresponding to the given teamColor. The actor is immediately rescaled (to fit better into the scene) and turned towards the opposing flag.

1 // Set initial knowledge
2     actor.setKnowledge("team_color", teamColor)
3     actor.setKnowledge("movement_speed", 1)   // in meters per second.
4     actor.setKnowledge("rotation_speed", 140) // in degrees per second.
5     actor.setKnowledge("self", actor);
6     actor.setKnowledge("has_flag", false);
7     actor.setKnowledge("team_has_flag", false);
8     actor.setKnowledge("enemy_in_range", false);
9     ...

The second part sets the initial knowledge of the actor by writing to its blackboard. Notably, the agent knows its team color, that it doesn't have the flag yet and that theren't any enemies in range.

1 // Connect events
2     actor.monitorTask = new MonitorTask(actor);
3     actor.removedFromScene.connect(function() {
4         clearInterval(actor.monitorTask.hasFlagHandle)
5         clearInterval(actor.monitorTask.rangeHandle)
6     });
7     ...

Next, we associate a monitoring task with each spawned actor outside of its blackboard knowledge. This monitoring task provides the environment sensing of the agent. The monitoring tasks are registered to be stopped once the removedFromScene event is emitted for the spawned actor. You can inspect the monitoring task in behaviors.js:

 1 function MonitorTask(actor)
 2 {
 3 	this.actor = actor;
 4 	this.hasFlagHandle = setInterval(250, function() {
 5 		...
 6 	})
 7 
 8 	this.rangeHandle = setInterval(1000, function() {
 9 		var query = Scene.rangeQuery(actor.position, 3)
10 		...
11 	})
12 }

What does this code do? Conceptually, these monitoring tasks register two functions to be executed repeatedly. One of them is executed every 250 ms (1/4th of a second) and checks whether or not the actor has captured or scored the flag by comparing its position with the opponent flag's position. The other one runs every second and checks whether there are any enemies close to the actor by performing a range query on the whole scene.

The motivation to run these sensing tasks on a different rate than the update rate is performance. Querying the scene 60 times a second for every spawned actor is not necessary and would severely impact the simulation's interactivity. Note that timers are still dependant of the simulation time, thus, if you turn down the simulation speed to 0.1 times the normal speed, these functions would be executed every 2.5 seconds (2500ms) and 10 seconds (10000ms) in real time.

 1 // Always turn towards the current movement target
 2     actor.knowledgeChanged.connect(function(key, value) {
 3         if(key === "movement_target") {
 4             value.y = Plane.position.y
 5             actor.setKnowledge("lookat_target", value)
 6         }
 7     })
 8     actor.knowledgeRemoved.connect(function(key) {
 9         if(key === "movement_target") {
10             actor.removeKnowledge("lookat_target")
11         }
12     })
13 }

Lastly, every actor registers event handlers that automatically turn them towards the next movement_target. They will turn towards the current target position with a turn rate governed by the rotation_speed property we have set earlier.

DEFINING BEHAVIORS

We can now use the behavior tree plugin to define our agent's decision making logic. We do so by wrapping the actions we defined in behaviors (behaviors.js). The following example shows how to wrap actions in behaviors by subclassing.

 1 function Idle(timeInMS)
 2 {
 3 	this.idleTime = timeInMS;
 4 	Behavior.call(this);
 5 }
 6 
 7 Idle.prototype = {
 8 	run: function() {
 9 		var context = this;
10 		this.handle = setTimeout(this.idleTime, function() {
11 			delete context.handle
12 			context.notifySuccess();
13 		})
14 		this.setStatus(Status.Waiting)
15 	},
16 	terminate: function() {
17 		if(typeof(this.handle) !== "undefined") {
18 			clearTimeout(this.handle)
19 		}
20 	}
21 }
22 extend(Behavior, Idle)

This example shows a behavior that lets our agent idle for a specified amount of time. As a first step, we define a constructor function which enables us instantiate this behavior when needed. In this example, the constructor function takes a single parameter: The time (in ms) the actor will idle, when this behavior is activated. We store this parameter in the idleTime property for later access.

It is important that you also call the parent constructor of the Behavior class within your own constructor. Without this step your behavior will not function. We call the parent constructor via the expression Behavior.call(this).

Next, we override the methods Behavior.run and Behavior.terminate to define what our behavior actually does. The run function is invoked repeatedly whenever the behavior is active. We register a timeout handler on the first time run is called.

The timeout handler will call the method Behavior.notifySuccess() that will indicate to the behavior's parent that our behavior has finished successfully. Correspondingly, to indicate a failure we could call Behavior.notifyFailure(). To stop our behavior from repeatedly getting called we set its status to Status.Waiting. This status tells the scheduling system, that our task is waiting for external results and doesn't need computation time.

The terminate method is called whenever the behavior is forcefully changing status from active to inactive without having notified its parent of its resulting status code. This happens when an event forces a change in the Behavior Tree.

Our implementation of the terminate method removes the timeout handler, if it has already been registered before the termiante method is called. Similarly, we wrapped the other possible actions.

USING BEHAVIOR TREES

All that is left is for us to create a behavior tree and tell the environment to schedule it. This process is shown in ctflogic.js.

1 function constructBehaviorTreeForActor(actor)
2 {
3 	var color = actor.getKnowledge("team_color");
4 	var root = new Selector(new HasFlag(new WalkTo(getOwnFlagPos(color)), actor),
5 							new WalkTo(getOpponentFlagPos(color)))
6 
7 	root.setUserData(actor.knowledge);
8 	return root;
9 }

To construct a behavior tree we instantiate the tree nodes one by one. The following composite nodes are available to define your decision making control flow: Selector, Sequence, Parallel, RandomSelector, RandomSequence and BlackboardDecorator. Composite nodes take their child nodes as parameters to their constructors.

The BlackboardDecorator is a notable exception. It provides a conditional inner node that may have only one child node. For an example of how to use the BlackboardDecorator class to react to changes to boolean values in an actor's blackboard take a look at behaviors.js. For non boolean-values you have to define your own conditions by subclassing Behavior.

Note that, to access an actor's blackboard from within behaviors, you have to use Behavior.setUserData() on the root node of the behavior tree as is shown above.

The depicted behavior tree does exactly what we stated in the problem description for this tutorial. The actor returns to its own base's position, if he currently holds the flag, otherwise he walks to the opponent flag to capture it.

1 function onSetup() {
2 	...
3 	var redBT   = constructBehaviorTreeForActor(redAgent)
4 	Scheduler.enqueue(redBT)
5 	redAgent.removedFromScene.connect(function(){
6 		Scheduler.dequeue(redBT)
7 	})
8 	...
9 }

Lastly, we tell the environment to schedule our behavior tree by passing its root node to the Scheduler.enqueue() method. Correspondingly, we pass it to Scheduler.dequeue() to stop the environment from executing behavior tree. We do so when an actor is removed from the scene to prevent any erroneous access to knowledge that was removed.