AI Decision Trees & Behavior Trees
The final part of this three part project (which started with Movement algorithms, going on to Pathfinding) involves setting up an architecture which will allow the Boids (characters in the simulation) to make decisions. This architecture will allow the authoring of Decision trees and/or Behavior trees which can then be used in the decision making process.
The GitHub project can be found here.
Revising The Top Level Architecture
First and foremost, I needed to re-do how a Boid character was defined in the program. Up until now, I had completely overlooked this part as it was not important, cramming all logic inside a single class. But, for this final project to work, I had to structure the character correctly.
To start off, I moved all the logic that would be shared between all Boid characters to a base class called BoidBase. This class is primarily responsible for handling the draw logic for the Boid which, in this project, does not change. The existing Boid class inherits from this base and is responsible for the movement logic for a Boid character. This extra layer helps separate Draw call logic from Movement logic. Any class that now inherits from the Boid class can work with its functionality to implement Game logic.
Up until now Boid movement worked primarily on user input. To move completely towards autonomous control, I had to define (and subsequently implement) some basic concepts.
An action is any physical way a Boid can interact with the game world. For this project an Action is limited to various kinds of movements a Boid can perform. Each action has various properties which help differentiate it from other actions. An id to identify the action. A priority number which decides its level of importance. A Boolean flag which keeps track of whether or not the action has been completed.
Since at any given time, multiple actions could be vying for execution, I needed an Action Manager to control which actions are to be executed and when. The action manager maintains two priority queues, a pending queue for actions that are waiting to be executed and an active queue for actions that are being executed.
Decision Making Behavior
This is the interface for implementing a Decision Tree or a Behavior Tree. More on this later.
This is the controller which is responsible for running the Boid. Every autonomous Boid will have an AI Brain component attached. This component contains an action manager and a decision/behavior tree. Every loop, the decision making behavior is invoked and may or may not return a valid action. This action is then fed into the action manager which subsequently executes it.
The first type of decision making behavior that I implemented was a decision tree. At its most basic, a decision tree is a series of if/else statements at the end of which you get an action. At every internal node in the tree a decision is made which then calls one of its children and the process is repeated recursively until a leaf node is reached. This leaf node is returned to the calling function and contains an action which is subsequently extracted from this node and fed into the action manager.
An internal node is called a decision node and a leaf node is called an action node. A decision tree is not necessarily a binary tree as a decision node can have multiple children. Moreover, to make a decision based on world data, a decision node must contain game information. The same is not true for an action node as it simply contains an action to be returned.
The decision tree that I implemented was a simple binary tree as shown below.
This tree has two decision nodes and three action nodes. At the first node it checks if the Boid is close to the edge, if it is move to towards the center. The next check sees if the Boid has been stationary for a given amount of time at which point the boid moves towards a random position in its vicinity. And finally while stationary, the Boid looks around randomly.
Implementing the tree itself was straight forward. I was able to parameterize game data in various different ways. For the boundary check, I simply relied on open frameworks’ built in function to get the window bounds. This worked for me because I used a tile map that spans the entire game window. As for movement itself I passed in a copy of my tile map to whichever node needed it. Passing in a copy instead of a pointer or a reference works because my game world is unchanging. This was not the case for the Boid though and I had to pass in a pointer to the owning Boid to my decision tree. This is because the Boids kinematic data might be updating continuously and the decision tree needs accurate data to make valid decisions. For everything else I just created member variables inside the nodes.
I did face some problems because an action could be either discrete or continuous.
The look action uses Dynamic Face to look around. As steering behaviors were designed to be called every frame and since the decision tree is queried every frame, they went together perfectly. The movement actions however use A* pathfinding to calculate a target node for the Boid to move towards. This procedure happens in a single frame and then ends.
Calling A* every frame is a bad sign.
To get around this, I store the target node inside my action and on every subsequent execute call I compare the Boid’s current node and the target node. If they are not the same, the action is considered “Running” even though I do not perform any pathfinding. The action is only considered complete when the current and target node become equal.
The reason this works is because I pass the action to the action manager as a pointer rather than creating a copy. This allowed me to save information in the action itself. Although it makes my actions (somewhat) bloated, I can get around having discrete and continuous actions.
Authoring a behavior tree was a much more daunting task than a decision tree because of its complexity as well as the extra data structures involved. Surprisingly, once I crossed this initial hurdle, adding and/or modifying different nodes of the tree was a much easier task than for the decision tree.
In general terms, a behavior tree is a directed acyclic graph (DAG). One of its biggest features is the secondary data storage it uses called a Blackboard. It allows the behavior tree to store and retrieve local as well as global data. This offers a behavior tree on of its biggest advantages over decision trees as it allows behavior trees to communicate with the game world an even among themselves.
Another important feature of behavior trees is their re-entrant property where in a behavior tree can stop and resume execution as needed. This is supported by a status reporting system which allows different levels of the tree to know which tasks have failed, succeeded, are still running etc.
A behavior tree is made of nodes called tasks. A task can either set an action to be executed or call a set of child tasks (these are called composite tasks). Some of the common and recognizable composite tasks include Selectors (run until success), Sequencers (run until fail) and Decorators (select task) etc.
For this project, I set up a simple Behavior tree for a Boid character. This tree makes the Boid patrol along certain paths and, if the player Boid is detected in the vicinity, chase it. The tree structure is illustrated below.
The root node here represents a Selector. A selector runs all its child tasks till failure. One level below the first task on the left is a Sequencer. A sequencer runs its children till it encounters the first failure or until all child tasks have succeeded. The node on the right is a Random Decorator. While a Decorator selects one of its children based on a certain criteria, a random decorator does so randomly. For my tree, it randomly selects one of two patrol paths for the Boid to follow.
While setting up the behavior tree, the biggest challenge I faced was creating a meaningful Blackboard data structure. Its easy enough to create a specialized Blackboard to solve a particular problem, it is however difficult to create one that is generalized and can be used in a variety of different ways. The main problem here is that there is no limit to what type of data the game world can represent.
While I didn’t make a generalized Blackboard for this project, this is an interesting challenge which I plan to tackle at a later date.