Artificial Intelligence  
Lecture 08 Behavior Trees  
Edirlei Soares de Lima  
<edirlei.lima@universidadeeuropeia.pt>  
Game AI Model  
Pathfinding  
Steering behaviours  
Finite state machines  
Automated planning  
Behaviour trees  
Randomness  
Sensor systems  
Machine learning  
Decision Making  
In game AI, decision making is the ability  
of a character/agent to decide what to  
do.  
The agent processes a set of information  
that it uses to generate an action that it  
wants to carry out.  
Input: agent’s knowledge about the world;  
Output: an action request;  
Decision Making  
The knowledge can be broken down into external and  
internal knowledge.  
External knowledge: information about the game environment (e.g.  
characters’ positions, level layout, noise direction).  
Internal knowledge: information about the character’s internal state  
(e.g. health, goals, last actions).  
Behavior Tree  
Behavior trees have a lot in common with Hierarchical State  
Machines but, instead of a state, the main building block of a  
behavior tree is a task.  
A task can be something as simple as looking up the value of a variable  
in the game state, or executing an animation.  
Tasks can be decomposed into sub-trees to represent more complex  
actions.  
Behavior Tree Tasks  
Selector  
Behavior trees are composed of three  
types of tasks:  
Conditions: test some property of the game  
(e.g. proximity, line of sight, state of the  
character).  
Actions: alter the state of the game (e.g.  
animation, movement, state change, dialog).  
Actions  
Sequence  
Composites: Selector and Sequence.  
Selector: returns immediately with a success status  
code when one of its children runs successfully.  
Sequence: returns immediately with a failure status  
code when one of its children fails. As long as its  
children are succeeding, it will keep going.  
Condition Actions  
Behavior Tree Example  
Unity Implementation Class Diagram  
Agent  
WorldManager  
-
-
behaviorTree: Task;  
wordManager: WorldManager;  
-doors: DoorInfo[];  
-waypoints: WaypointInfo[];  
-
-
Start();  
Update();  
+OpenDoor(name);  
+CloseDoor(name);  
+
+
DoorIsOpen(name): bool;  
GetWaypoint(name): Vector3;  
Task  
TaskStatus  
#
+
children: Task[];  
status: TaskStatus;  
None  
Success  
Failure  
Running  
+abstract Run(agent, manager): TaskStatus;  
Sequence  
Selector  
Actions & Conditions  
+
Run(agent, manager): TaskStatus;  
+Run(agent, manager): TaskStatus;  
+Run(agent, manager): TaskStatus;  
Base Task Class  
Task Class:  
public abstract class Task  
{
protected List<Task> children;  
public TaskStatus status;  
public abstract TaskStatus Run(Agent agent,  
WorldManager wordManager);  
public Task(){  
children = new List<Task>();  
status = TaskStatus.None;  
}
public void AddChildren(Task task){  
children.Add(task);  
}
}
Composite Classes  
Sequence Class:  
public class Sequence : Task {  
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
int successCount = 0;  
foreach (Task task in children){  
if (task.status != TaskStatus.Success){  
TaskStatus childrenStatus = task.Run(agent, wordManager);  
if (childrenStatus == TaskStatus.Failure){  
status = TaskStatus.Failure;  
return status;  
}
else if (childrenStatus == TaskStatus.Success){  
successCount++;  
}
...  
Composite Classes  
...  
else{  
break;  
}
}
else{  
successCount++;  
}
}
if (successCount == children.Count)  
status = TaskStatus.Success;  
else  
status = TaskStatus.Running;  
return status;  
}
}
Composite Classes  
Selector Class:  
public class Selector : Task {  
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
int failureCount = 0;  
foreach (Task task in children){  
if (task.status != TaskStatus.Failure){  
TaskStatus childrenStatus = task.Run(agent, wordManager);  
if (childrenStatus == TaskStatus.Success){  
status = TaskStatus.Success;  
return status;  
}
else if (childrenStatus == TaskStatus.Failure){  
failureCount++;  
}
...  
Composite Classes  
...  
else{  
break;  
}
}
}
if (failureCount == children.Count)  
status = TaskStatus.Failure;  
else  
status = TaskStatus.Running;  
return status;  
}
}
Condition Classes  
DoorOpenCondition Class:  
public class DoorOpenCondition : Task {  
private string doorName;  
public DoorOpenCondition(string door){  
doorName = door;  
}
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
if (wordManager.DoorIsOpen(doorName)){  
status = TaskStatus.Success;  
}
else{  
status = TaskStatus.Failure;  
}
return status;  
}
}
Action Classes  
MoveAction Class:  
public class MoveAction : Task{  
private string destionation;  
public MoveAction(string dest){  
destionation = dest;  
}
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
NavMeshAgent navMeshAgent = agent.GetComponent<NavMeshAgent>();  
Vector3 dest = wordManager.GetWaypoint(destionation).position;  
if (status == TaskStatus.None){  
navMeshAgent.destination = dest;  
status = TaskStatus.Running;  
}
else if (IsAtDestionation(navMeshAgent)){  
status = TaskStatus.Success;  
}
return status;  
}
Action Classes  
...  
private bool IsAtDestionation(NavMeshAgent navMeshAgent){  
if (!navMeshAgent.pathPending){  
if (navMeshAgent.remainingDistance <=  
navMeshAgent.stoppingDistance){  
if (!navMeshAgent.hasPath ||  
navMeshAgent.velocity.sqrMagnitude == 0f){  
return true;  
}
}
}
return false;  
}
}
Action Classes  
OpenDoorAction Class:  
public class OpenDoorAction : Task{  
private string doorName;  
public OpenDoorAction(string door){  
doorName = door;  
}
public override TaskStatus Run(Agent agent,  
GameWorldManager wordManager){  
if (!wordManager.DoorIsOpen(doorName)){  
wordManager.OpenDoor(doorName);  
}
status = TaskStatus.Success;  
return status;  
}
}
World Manager Class  
public class WorldManager : MonoBehaviour {  
[SerializeField] private DoorInfo[] doors;  
[SerializeField] private WaypointInfo[] waypoints;  
public void OpenDoor(string doorName){  
for (int x = 0; x < doors.Length; x++){  
if (doors[x].name == doorName){  
doors[x].transform.Translate(Vector3.right * 2f);  
doors[x].open = true;  
break;  
}
}
}
public void CloseDoor(string doorName){  
for (int x = 0; x < doors.Length; x++){  
if (doors[x].name == doorName){  
doors[x].transform.Translate(Vector3.left * 2f);  
doors[x].open = false;  
break;  
}
}
}
World Manager Class  
...  
public bool DoorIsOpen(string doorName){  
for (int x = 0; x < doors.Length; x++){  
if (doors[x].name == doorName){  
return doors[x].open;  
}
}
return false;  
}
public Transform GetWaypoint(string name){  
foreach (WpInfo wp in waypoints){  
if (wp.name == name)  
return wp.transform;  
}
return null;  
}
}
Agent Class  
public class Agent : MonoBehaviour  
{
[SerializeField] private WorldManager wordManager;  
private Task behaviorTree;  
private TaskStatus behaviorTreeStatus = TaskStatus.None;  
void Start(){  
Task sequenceMoveToRoom = new Sequence();  
sequenceMoveToRoom.AddChildren(new DoorOpenCondition("Door1"));  
sequenceMoveToRoom.AddChildren(new MoveAction("Room1"));  
Task sequenceOpenDoorMoveToRoom = new Sequence();  
sequenceOpenDoorMoveToRoom.AddChildren(new MoveAction("Door1"));  
sequenceOpenDoorMoveToRoom.AddChildren(new OpenDoorAction("Door1"));  
sequenceOpenDoorMoveToRoom.AddChildren(new MoveAction("Room1"));  
behaviorTree = new Selector();  
behaviorTree.AddChildren(sequenceMoveToRoom);  
behaviorTree.AddChildren(sequenceOpenDoorMoveToRoom);  
}
Agent Class  
...  
void Update(){  
if ((behaviorTreeStatus == TaskStatus.None) ||  
behaviorTreeStatus == TaskStatus.Running)){  
behaviorTreeStatus = behaviorTree.Run(this, wordManager);  
(
}
}
}
Exercise 1  
1
) Implement and test the following behavior tree:  
Non-Deterministic Composite Tasks  
Sometimes the order in which tasks are executed is extremely  
important. But there are some tasks that don’t need to be  
executed in a particular order.  
Executing tasks in same order can lead to predictable AI who always  
try the same things.  
Example (sequence): get matches and gasoline to burn the door.  
Example (selector): invade the room through the door or through the  
window.  
Non-deterministic composites can be implemented by  
shuffling the order of the children nodes before iterating  
through them.  
Non-Deterministic Composite Tasks  
Non-Deterministic Selector  
Non-Deterministic Sequence  
Non-Deterministic Composite Tasks  
NonDeterministicSequence Class:  
public class NonDeterministicSequence : Task {  
private bool shuffledOrder;  
public NonDeterministicSequence()  
{
shuffledOrder = false;  
}
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
if (!shuffledOrder){  
Shuffle(children);  
shuffledOrder = true;  
}
...  
}
}
Non-Deterministic Composite Tasks  
Simple Shuffle method:  
public void Shuffle(List<Task> list)  
{
int n = list.Count;  
while (n > 1)  
{
int k = Random.Range(0, n);  
Task value = list[k];  
list[k] = list[n];  
list[n] = value;  
n--;  
}
}
Decorators  
Decorator is a type of task that has one single child task and  
modifies its behavior in some way.  
Examples:  
Limit the number of times a task can be run;  
Keep a task running until it fails;  
Decorator  
Decorator Classes  
Decorator Class:  
public abstract class Decorator : Task {  
protected Task child;  
new public void AddChildren(Task task)  
{
child = task;  
}
}
UntilFailDecorator Class:  
public class UntilFailDecorator : Decorator{  
public override TaskStatus Run(Agent agent,  
WorldManager wordManager){  
if (status == TaskStatus.None)  
status = TaskStatus.Running;  
if (child.Run(agent, wordManager) == TaskStatus.Failure)  
status = TaskStatus.Success;  
return status;  
}
}
Parallel Tasks  
When parallel actions are necessary, we can add a third type  
of composite tasks to the behavior tree: Parallel.  
Rather than running all children tasks one at a time, it runs  
them all simultaneously.  
Example: a character rolling into cover at the same time as shouting an  
insult and changing primary weapon.  
The Parallel task acts in a similar way to the Sequence task. It  
has a set of child tasks, and it runs them simultaneously until  
one of them fails.  
Parallel Tasks  
At a higher level, we can also use Parallel tasks to control the  
behavior of a group of characters.  
Parallel  
Parallel Class  
public class Parallel : Task {  
public override TaskStatus Run(Agent agent, WorldManager wordManager){  
int successCount = 0;  
foreach (Task task in children){  
if (task.status != TaskStatus.Success){  
TaskStatus childrenStatus = task.Run(agent, wordManager);  
if (childrenStatus == TaskStatus.Failure){  
status = TaskStatus.Failure;  
return status;  
}
else if (childrenStatus == TaskStatus.Success)  
successCount++;  
}
else  
successCount++;  
}
if (successCount == children.Count)  
status = TaskStatus.Success;  
else  
status = TaskStatus.Running;  
return status;  
}
}
Exercise 2  
2
) Implement and test the following behavior tree:  
Repeat  
Enemy is  
Visible?  
Shoot  
Enemy  
?
Always  
Succeed  
Is Low on  
Ammo?  
Reload  
Weapon  
Further Reading  
Millington, I., Funge, J. (2009). Artificial Intelligence for Games (2nd ed.).  
CRC Press. ISBN: 978-0123747310.  
Chapter 5.4: Behavior Trees