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 implemented an action manager system for the AI agents in my AI engine.
In my AI engine structure, actions are the actual classes that will change the states of the AI agents. Actions can vary from state change actions, movement actions to animation actions and AI request actions. In my code, all different actions will derive from a base class IAction, where some pure virtual functions and member variables are defined.
Below is the public interface of IAction. Note that there are many design decisions that can change the definitions of the interface. Take CanInterrupt() for example, we can easily extend it to accept other actions as inputs to provide more specific controls. Also, notice that there is a friend function ActionCompFunc which is a custom compare function that compares two actions by their priority in order to make my priority queue to work correctly.
Action Priority Queue
We want to be able to retrieve the top priority action in our queues very quickly in order to compare with current active actions and promote actions from the pending queue. Therefore, it would only make sense to implement a priority queue to support the operations that we need. I use a vector as the underlying container, and support some special operations like removing elements from random positions, and clean up all the actions that are set to pending kill.
One of the design decisions that can be made here is how to handle duplicated actions in the queue? Take my decision tree for example, I am evaluating a action from that tree every frame, which also means that an action will be scheduled into the queue every frame. We could put the responsibility of using the action queue nicely onto the decision tree, or we can add some more operations in the action queue to prevent this from happening by setting a limit to the size or avoid adding duplicates. What I am doing here is simply expire the actions that have reached its expiry time.
Lastly, the entity that holds these pieces together is the action manager class. My action manager has two priority queues, one for active actions and one for pending actions. The public interface is very simple. It supports action scheduling and will promote suitable actions or execute active ones in the update function.
Most of the important operations happen inside the action manager’s update function. First, it will check if there is any action in the pending queue that should be promoted to the active queue, no matter it is because of the active queue is empty or the highest priority action in the pending queue can interrupt the current running actions.
Next, it will check if there is any action in the pending queue that can run simultaneously with the current running actions, and promote them to the active queue if possible.
After that, it will check the active queue and execute the actions that are not expired. Lastly, it updates the queued time of actions in the pending list and checks if any action timed out.