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 how I incorporate different behavior making algorithms into my engine along with an action managing system.

Decision-Making Algorithm

There are a lot of different decision-making algorithms. Goal-oriented action planning (GOAP) used in F.E.A.R and the behavior tree AI from Halo 2 are probably the most well-known algorithms. A lot of new modern decision making structures built on the two algorithms mentioned before, such as hierarchical task network, goal-oriented behavior, and so on.

In this post, I will implement the decision tree and behavior tree structure, along with an action managing system, and the blackboard data structure that is used with but not limited to, my behavior tree.

I will be following the decision making schematics from the reference book, which separates world knowledge, agents, decision-making, and actions into different parts with clear boundaries between them.

I also added some extra layers in my engine. Mainly speaking, an AI agent will have a cAIController holding reference to the controlled cGameObject, cDecisionMaking (brain component), and a cActionManager. This structure is shown below in my rough drawing.

DecisionMakingStrucutre.PNG

20190414_112617.jpg
A rough overview of my AI system structure

Action and Action Managing

Please refer to this post for a detailed action managing system structure walkthrough.

I built the action managing system with a focus on good public interfacing in mind, and I tried to not make assumptions about the decision making structures that will be used with this action managing system (which is actually not necessarily a good thing, I’ll talk about this later). Basically, I planned to make it general and use it with all of my decision-making systems such as decision tree, behavior tree, and GOAP in the future.

Each action might carry out some effect on the agent’s internal/external knowledge, it may also request some actions from other systems, such as an animation request. One tricky part of constructing different actions is to determine when the action is “finished”. Take an animation request, for example, should the action be deemed finished once it submits a request to the animation system, or should it wait for the animation to finish? If we directly finish up the action right after a request is being made, what would happen if another animation request comes into execution? In this case, should the action priority determine the result, or we should just let the animation system resolves this situation according to its own rules? This might sound lazy, but it definitely depends on the design of the game and the engine. There will never be one solution that can solve all problems and cater to everyone, we must always make decisions and compromise.

How actions and action manager plays into different decision-making system varies and will be shown below.

Decision Tree

The decision tree structure is one of the simplest decision-making structure to implement, please refer to my post on the decision tree for more detailed implementation.

Simple Decision Tree

I started with a pretty simple decision tree structure without using any navigation to see if the decision tree is working correctly. This tree only has two condition checks and three action nodes. Right here, the target actually means the player object, so if the player is not facing the agent, the agent will try to get close enough and then start flashing colors. If the player is facing the agent, the agent will try to run away if it is too close to the player, or simply idle if it is far enough away.

SimpleDecisionTree.JPG
A very simple decision tree

Below demonstrates how to construct a decision tree in my engine. First, we can create the decision nodes, and then connect them together. Second, we construct the actions and pass them into the action nodes since my structure does not expect the action nodes to be extended, but simply change their purposes by swapping the underlying action pointer. Lastly, we connect all the nodes together and pass the root node into the decision tree’s constructor.

MakingAndConnectingDTreeInCode.PNG
Constructing a decision tree.

Now let’s take a look at the decision tree and the agent running in action. In the video below, the red boid is the AI agent, while the white boid is the player. On the right side of the video, you can kind of see the scheduling of different actions into the action manager.

Incorporating Navigation

Now let’s add the graph navigation framework into the agent. This might sound like a complicated thing to add, but it actually isn’t since all we need to do is swapping out that action that is being used to move toward the player. All of the pathfinding logic and steering algorithm delegation will happen in the action’s execution function.

NavToTargetAction.PNG
Changing action to use navigation action
NavigateToTargetAction.PNG
Action to navigate to the player object

By performing the kind of responsibility separation, we (or the designers) can easily construct and prototype a decision-making structure and see it in action. Now let’s take a look at the result of this decision tree.

Simple Blackboard

Please refer to my other post for my detailed blackboard implementation.

The simple behavior tree that I am going to use for the later demonstration behavior trees only has one global entry currently, which is the target player object, that will be shared between multiple different trees.

The C++ code below shows how to initialize a blackboard and add an entry to it. You can see that the blackboard interface allows users to use it easily without having to worry about the underlying implementation.

AddKeyIntoSimpleBlackboard.PNG
Creating and adding a global entry to the blackboard.

Simple Behavior Tree

Please refer to my other post for my detailed behavior tree implementation.

Now that you know how my behavior tree is structured, let’s take a look at how we can actually construct one in code.

MakingAndConnectSimpleBTInCode_1.PNG

MakingAndConnectSimpleBTInCode_2.PNG

Clearly, this is not too complicated, but this is also not the easiest thing to construct. This is only the code for constructing a simplified behavior tree, and you can already tell that it might get a bit tricky if you need to debug one incorrect connection, that is given the fact that you already know the behavior that you observe is resulting from some incorrect connections but not inside the tasks codes or the actions codes.

This is why a well-made graphics interface or even just a scripting interface of the behavior tree can help with development so much. With the ability to connect and disconnect nodes in a data-driven or easily observable fashion can boost the iteration speed so much. Since I don’t plan to create such a thing currently, setting up the node indices correctly in the order that they will be evaluated should be a good place to start. This is actually the same as performing a pre-order tree traversal. I might add an interface for specifying a behavior tree in a Lua file in the future.

The video below shows this behavior tree agent in action in real-time.

BehaviorTreeSetTasksIDsWithNotes.png
Setting up the tasks indices

 

A More Complicated Behavior Tree

Because the behavior tree that I showed above is basically doing the same thing as my decision tree example, you can see that it won’t actually try to reach the player. However, if we want to create a real “search-and-destroy” kind of style agent, it would definitely need to try to chase down the player.

Fortunately, because of the flexible nature of the behavior tree, we can easily tweak the structure of the tree and get a new behavior that we want!

SimpleBehaviorTreeAddingHunt.PNG
The new behavior tree
BTmodify.PNG
Connecting some extra nodes in code