[A.I. For Games] Decision Tree

This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.

In this post, I will talk about my implementation of the decision tree structure and the decision/action nodes that come with it.

Decision Tree

The decision tree is one of the simplest decision-making structure to implement, some people might call it a “glorified if-else”, which is not far from the truth actually. However, it provides a much easier and scalable workflow than simply using if-else, and could be a good option for a really simple AI agent (some meta AI or AI director perhaps).

A decision tree will contain the tree, some decision nodes, and some action nodes to function correctly. In the illustration below, You can see how the tree branches on decision nodes and ends up on the action nodes, which are the leaf nodes. I will go through each of these components below.

An example of a decision tree

Decision Tree Node

Every node in the decision tree structure will derive from the base class cDecisionTreeNode. The base class defines some of the public interfaces such as MakeDecision() and CleanUp(), along with a C string as the node’s name, which will only exist in debug mode since we most likely won’t need it in the release build.

Base class cDecisionTreeNode

The source file of cDecisionTreeNode

Decision Node

Decision nodes are in charge of checking on some conditions and keep on evaluating with correct branching. There are some types of basic decision tree nodes, such as boolean decision, floating point number decision, and enumeration decision.

Take the boolean decision node for example. There will be a test value to be evaluated and two children nodes for different evaluation results. If the test value is true, then we keep evaluating through the true node, vice versa.

The public interface of the boolean decision tree node

The main logic of evaluating a boolean decision tree node

Action Node

Action node is pretty simple, it simply holds a reference to the action that it should return to the decision tree, and return itself when evaluating since there are no more children nodes.

The header of the decision tree action node

Action node’s make decision function simply returns itself

Decision Tree Tick

The decision tree tick object is something that I added onto the original decision tree architecture to provide more flexibility to the decision tree. A decision tree tick object will contain the information of the decision tree which created the tick object, and the agent game object that this tree is controlling, if there is one.

The public interface of decision tree tick object.

Decision Tree

Now let’s move on to the actual decision tree structure. The most important function of any decision making algorithm in my structure is the GetAction() function which returns an action pointer to the AI controller and allows it to schedule that action into the action manager.

First, the tree will update the tick object with the correct game object that the tree is controlling, and then pass it on into the root node’s MakeDecision() function through the tree’s Run(). After recursively run through all nodes’ MakeDecision() function, we should retrieve an action node, and then we can get the action pointer from it and return it to the AI controller.

The public interface of the decision tree

Decision tree’s get action function