I'm a gameplay programmer
focused on developing
engaging and unique experiences!

My Resume Learn more

Decision Making Algorithms in openFrameworks

The code for this article can be found on GitHub here!

Perhaps one of the most well known problems in AI programming is figuring out how to best organize an agent's behavioral implementation. Solutions range from having a mishmash of if statements to the established technique of Behavior Trees, which are even featured as Unreal Engine's core AI framework!

This article will explore building Decision Trees and Behavior Trees around the concept of Actions, which are data structures that describe what an agent should do! The end result will be a monster that intelligently wanders or patrols the landscape to hunt a player character!

Actions

Before taking on the implementations of Decision and Behavior Trees, one of the first things we can do is encapsulate actionable logic into a data structure. These allow us to treat small snippets of behavior as data that can be reused as we please.

class CAction
{
public:
	CAction(double InExpiryTime, double InPriority, bool InCanInterrupt);
	~CAction();

	double GetQueuedTime ();
	void SetQueuedTime(double InQueuedTime);
	bool IsExpired();

	double GetPriority() const;
	bool GetCanInterrupt() const;

	bool GetIsComplete() const;
	void SetIsComplete(bool InIsComplete);

	virtual bool CanDoBoth(CAction* InAction);
	virtual void Execute() {}

protected:
	double QueuedTime;
	double ExpiryTime;
	double Priority;

	bool CanInterrupt;
	bool IsComplete;
};

The extra data values for QueuedTime, ExpiryTime, Priority, CanInterrupt, and IsComplete allow us to sort and manipulate our Actions in a Priority Queue. This gives designers finer control over how and when Actions are executed. Another notable feature is the function CanDoBoth(). This gives us the ability to state whether or not 2 actions can occur together. One example where this would be useful is if we had a Sleep Action that we didn't want to run at the same time as a Walk Action.

Action Managers

Action Managers are classes that handle the processing and execution of Actions. Their underlying structure is a Priority Queue, which will allow us to take advantage of the Priority data we have in our Actions. Their declaration is relatively straightforward with all the implementation handled in an Update loop.

class CActionManager
{
public:
	CActionManager();
	~CActionManager();

	void ScheduleAction(CAction* InAction);
	void Update(double InDeltaTime);

private:
	CPriorityQueue<CAction*> PendingActions;
	CPriorityQueue<CAction*> ActiveActions;
};

Something to note is that we have a Priority Queue for Pending Actions as well as Active Actions. Pending Actions are Actions that have been queued for processing in this frame that will be considered for promotion to Active Actions in the next Update loop. Active Actions are Actions that are currently being executed in the Update loop. Here's some basic pseudo code for that loop:

void CActionManager::Update(double InDeltaTime)
{
	// Step 1: Update Queued Time of Pending Actions
	// If they have expired, remove them

	// Step 2: Check if any Pending Actions can interrupt Active Actions
	// If so, promote them to Active Actions

	// Step 3: Promote Queued Actions that can run with Active Actions

	// Step 4: Execute Active Actions
}

Decision Trees

After encapsulating behavioral implementation logic into Actions and Action Managers, we can finally start exploring how to decide between which Actions to take. One of the simplest data structures to help us with this is a Decision Tree. Decision Trees are binary trees that are composed of nodes. Each node has a condition which indicates which branch we should follow to reach our desired Action.

For example, in the image below the diamond shape is a Decision Node which asks the condition, "Have we reached our Pathfinding Location?" If so, our desired action is to Wander around the area. If not, our desired action is to continue pathfinding.

To construct a Decision Tree, let's start by defining the data structures it's composed of.

Decision Tree Node

The first thing we can do is create a simple interface that all nodes in our Decision Tree will implement.

class CDecisionTreeNode
{
public:
	virtual CDecisionTreeNode* MakeDecision() = 0;
};

For each node in a Decision Tree we have a choice to make, so each node will have to implement the function MakeDecision().

Decision Nodes

Decision Nodes are the core data structures that make up a Decision Tree. They are the diamonds in the diagram above that indicate which branch we follow.

class CDecisionNode : public CDecisionTreeNode
{
public:
	CDecisionNode(CDecisionTreeNode* InTrueNode, CDecisionTreeNode* InFalseNode);
	~CDecisionNode();

	virtual CDecisionTreeNode* MakeDecision() override;

private:
	CDecisionTreeNode* GetBranch();
	virtual bool IsTrue() = 0;

private:
	CDecisionTreeNode* TrueNode;
	CDecisionTreeNode* FalseNode;
};

Similar to a Binary Tree Node, Decision Nodes hold pointers to two other Decision Tree Nodes. These represent the Yes and No branches in the diagram above. Something to note is the pure virtual function IsTrue(), which represents the conditional, "Reached Pathfinding Location?" in the image above. These are game specific, so a custom Decision Node needs to be implemented for each unique diamond. Something to note is MakeDecision() is implemented with the helper function GetBranch():

CDecisionTreeNode* GetBranch() 
{ 
	return IsTrue() ? TrueNode : FalseNode; 
}

CDecisionTreeNode* CDecisionNode::MakeDecision()
{
	CDecisionTreeNode* Branch = GetBranch();
	if (!Branch)
	{
		return nullptr;
	}

	return Branch->MakeDecision();
}

Action Nodes

With Action Nodes, we can reap the fruits of encapsulating our actionable logic into Actions and Action Managers. They are the leaf nodes of our Decision Tree that we reach after traversing a chain of Decision Nodes.

class CActionNode : public CDecisionTreeNode
{
public:
	CActionNode(CAction* InAction);
	~CActionNode();

	virtual CDecisionTreeNode* MakeDecision() override;
	CAction* GetAction();

private:
	CAction* Action;
};

Most noteworthy about Action Nodes is how simple their implementations are. MakeDecision() simply returns the Action Node itself as there are no branches to traverse!

CDecisionTreeNode* CActionNode::MakeDecision()
{
	return this;
}

Decision Tree

With all the nodes that compose a Decision Tree implemented, we can finally declare the class of a Decision Tree!

class CDecisionTree
{
public:
	CDecisionMakingBehavior(CDecisionTreeNode* InRoot);
	~CDecisionTree();

	virtual CAction* GetAction();

private:
	CDecisionTreeNode* Root;
};

Decision Trees are just like Binary Trees in that their core logic is encapsulated in their nodes. Whenever we're curious about what Action we should be doing, we can simply ask our Decision Tree to get an action for us!

CAction* CDecisionTree::GetAction()
{
	if (!Root)
	{
		return nullptr;
	}

	CDecisionTreeNode* Node = Root->MakeDecision();

	if (!Node)
	{
		return nullptr;
	}

	return static_cast<CActionNode*>(Node)->GetAction();
}

The last line is interesting in that our Decision and Action Node logic should always return us an Action Node or a nullptr. This is because we should keep traversing our Decision Tree until we reach a leaf node, which we defined as being an Action Node!

Using Decision Trees

With Actions and Decision Trees, we can now take an organized approach to implementing intelligent behavior!

CActionNode* PathfindNode = new CActionNode(new PathfindingAction());
CActionNode* WanderNode = new CActionNode(new CWanderAction());

CCharacterDecisionNode* Root = new CCharacterDecisionNode(WanderActionNode, FollowActionNode);

CDecisionTree* DecisionTree = new CDecisionTree(Root);

I used this structure to simply have an agent wander around an environment until I commanded it to pathfind to a specified location. With the core Decision Node seeing if an agent has reached its destination. A behavior like this could be useful for RTS or Simulation games!

Behavior Trees

Finally, we've arrived to the main event! However, our time and effort on Actions and Decision Trees aren't wasted as Behavior Trees build off them. Before diving into the implementation details, let's look at an example of one.

Tasks

While looking a bit more complicated, Behavior Trees come with added flexibility and power! As Decision Trees are composed of nodes, Behavior Trees are composed of Tasks. So every rectangle in the diagram above is a type of Task. Let's look at the implementation details of this class:

class CTask
{
public:
	CTask();
	~CTask();

	EStatus Run(CTick* InTick);

	void Enter(CTick* InTick);
	void Exit(CTick* InTick);
	void Open(CTick* InTick);
	void Close(CTick* InTick);
	EStatus Execute(CTick* InTick);

	const std::vector<CTask*>& GetChildren() const;
	void AddChild(CTask* InTask);

protected:
	virtual void OnEnter(CTick* InTick);
	virtual void OnExit(CTick* InTick);
	virtual void OnOpen(CTick* InTick);
	virtual void OnClose(CTick* InTick);
	virtual EStatus OnExecute(CTick* InTick);

protected:
	int TaskId;
	std::vector<CTask*> Children;
};

The first thing you may notice is the function group consisting of Enter(), Exit(), Open(), Close(), and Execute(). Tasks are more complex than Decision Nodes in that they take several steps to run through. Enter() and Close() are called at the beginning and end of running through a Task respectively.

Re-entrant Behavior

Something to mention about Behavior Trees is that they are Re-entrant. This means you can leave the execution of a Behavior Tree and come back to it at another time at the same execution point. This is where Open() comes in, which is a function that's only called on the first entry of a Task. For comparison, Enter() is called every time we come back to the Task. Open() is only called once until Close() is called. The TaskId property is also used for the Re-entrant behavior of our Behavior Tree.

Another thing to note is the vector of child Tasks. Unlike nodes in Decision Trees, Tasks can have much more than two children.

Status Codes

Another thing to note is the type EStatus. Another feature of Tasks and Behavior Trees is that they return status codes based on their execution. These status codes can look like this:

enum class EStatus
{
	SUCCESS,
	FAILURE,
	RUNNING,
	ERROR
};

Status codes affect the pathways a Behavior Tree may take to a desired action and can also help with debugging.

Tick

One final feature to note is a type called Tick. Let's take a look at it:

class CTick
{
public:
	CTick(CBehaviorTree* InBehaviorTree, CBlackBoard* InBlackBoard);
	~CTick();

	CBlackBoard* GetBlackBoard();
	CBehaviorTree* GetBehaviorTree();

private:
	CBehaviorTree* BehaviorTree;
	CBlackBoard* BlackBoard;
};

A Tick is simply an object created by Behavior Trees to help with Re-entrant behavior. This is most notably done with a class called a BlackBoard.

Blackboard

Perhaps one of the most common features found on Behavior Trees is a Blackboard. These are data structures that keep track of data across the execution of a Behavior Tree. Let's look at it's class declaration:

class CBlackBoard
{
public:
	CBlackBoard();
	~CBlackBoard();

	// Scoped by Task
	void SetValue(std::string InKey, CBlackBoardValue* InValue, int InTreeId, int InTaskId);
	CBlackBoardValue* GetValue(std::string InKey, int InTreeId, int InTaskId);

	// Scoped by Tree
	void SetValue(std::string InKey, CBlackBoardValue* InValue, int InTreeId);
	CBlackBoardValue* GetValue(std::string InKey, int InTreeId);

	// Global Scope
	void SetValue(std::string InKey, CBlackBoardValue* InValue);
	CBlackBoardValueBase* GetValue(std::string InKey);
};

A Blackboard's main functionality is to Get and Set data for Tasks. Additionally, this data can be tracked across 3 different scopes. One is scoped by keeping track of data of a specific Task in a specific Behavior Tree. This is where the TaskId comes in handy! The next scope is by Behavior Tree, where we indicate that each tree may have its own ID. Finally, we also have a global scope.

Blackboard Keys & Values

Blackboards are usually implemented as several Maps. One implementation we usually see are keys implemented as strings and values being generic! This is an interesting implementation problem as C++ is a statically typed programming language. However, one way to solve this is with templates:

template<class T>
class CBlackBoardValue
{
public:
	explicit CBlackBoardValue(const T& InValue) : Value(InValue) {}

	const T& GetValue() const { return Value; }
	void SetValue(const T& InValue) { Value = InValue; }

private:
	T Value;
};

Behavior Tree

With Tasks, Ticks, and Blackboards detailed, we can finally declare the Behavior Tree class!

class CBehaviorTree : public CDecisionTree
{
public:
	CBehaviorTree(int InTreeId, CTask* InRootTask, CBlackBoard* InBlackBoard);
	~CBehaviorTree();

	inline int GetTreeId() const;
	virtual CAction* GetAction() override;

private:
	int TreeId;
	CTask* RootTask;
	CBlackBoard* BlackBoard;
};

Again, much of the logic is embedded into our Tasks with the Blackboard helping out! Our Behavior Tree simply acts as the interface to our logic

Using Behavior Trees

Now, let's take a second look at the example Behavior Tree.

Like Decision Trees, the Tasks that aren't leaves operate the core logic that control which branches we traverse to reach an action. The tasks Selector and Sequencer are very common to find among Behavior Tree implementations. Selectors run through every Child task of there's from left to right until one returns a Success status code. Sequencers run through every Child task from left to right until one returns a Failure status code. In addition to those I created a Randomizer task that randomly chooses a child Task upon entry!

Finally, all the leaf tasks are game specific implementations of actions we'd like our agent to perform. Given all this, we can parse this Behavior Tree from left to right as:

1. If you can smell a character, check if you can eat the character.

2. If you can, reset the simulation.

3. Otherwise, try following the player.

4. If you fail to accomplish all of the above, randomly choose between wandering or patrolling the environment.

Of course, this behavior could have been written out in a chain of if/else statements, but our Behavior Tree allows us to easily change the behavior by simply rearranging Tasks instead of editing core logic! Using the diagram's structure, I got a green monster to chase and eat my character that is using our Decision Tree logic! The green radius indicates the monster's sense of smell and the red radius indicate's the monster's eating range.

By nature of Behavior Trees being trees, they are much easier to author visually than in code. With that in mind, I strongly suggest trying out Unreal's Behavior Tree editor!

Converting Behavior Trees to Decision Trees

An interesting property of Decision Trees is that they can be generated based on observations of actions taken! That means, if we created a data set of actions taken based on a Behavior Tree, we could create a Decision Tree from it! One of the most common techniques to achieve this is using the ID3 algorithm.

Iterative Dichotomizer 3 (ID3)

ID3 is a recursive algorithm that starts with a single node containing observations mapped to actions. It splits the node into two groups based on the entropy of actions in the initial node. Afterwards, it continues this process until all observations match up to the same actions. In those cases, leaf nodes are formed! Here's what it looks like in pseudo code:

void ID3::MakeTree(const std::vector<CExample*>& InExamples, const std::set<CAttributes*>& InAttributes, CDecisionNode* InRootNode)
{
	// 1. Calculate Initial Entropy and return if there is no entropy

	// 2. Split examples by each attribute into sets

	// 3. Calculate overall entropy of sets to calculate the best attribute split

	// 4. Subtract the best split attribute set from the original set of attributes

	// 5. Generate a daughter node based on the best split attribute and recurse on the new set of attributes
}

Entropy

Entropy in is measured by how closely all the actions in a single group match each other. Thus, the ID3 algorithm breaks an initial node into groups with an entropy of 0. Here's pseudo code:

float ID3::CalculateEntropy(const std::vector<CExample*>& InExamples)
{
	// 1. Count how many different actions there are

	// 2. For each action calculate the proportion of unique actions to examples

	// 3. Multiply it against the log of proportion and subtract it from total entropy
}

Something to note is that entropy is calculated from the given data set. Thus, the accuracy of the Decision Tree entirely depends on the accuracy of the data set. If we give the ID3 algorithm some special case scenario, our outputted tree could perform entirely different from our Behavior Tree.

Conclusion

In the end, whatever implementation technique you use to organize your AI logic entirely depends on the problems you need to solve. In a sense, some AI problems probably only need a couple if statements while other problems AAA studios face usually require something more structured, such as Behavior Trees.



No Comments Yet.

Leave a comment