As humans, we like to implement solutions which are familiar to us. We get caught up doing things the way we know how to do them, rather than the "best" way to do them. It's easy to get caught up in thinking like this and as a result we end up using outdated technologies and implement features in ways that our modern contemporaries don't understand, or are simply less effective or efficient. My purpose with this and future papers will be to expose readers to a broad spectrum of solutions that will hopefully help them in their own coding. Today I'll be covering Action Lists! Action Lists are a simple yet powerful type of AI that all game developers should know about. While ultimately not scalable for large AI networks, they allow for relatively complex emergent behavior and are easy to implement. Whether you are just getting into AI programming or are an experienced industry veteran looking to expand your toolkit, this presentation will introduce you to Action Lists and provide concrete examples to help you implement your own solutions. Let's begin the story.
Once Upon A Time...Several years ago I was starting the development of King Randall's Party, a game in which the player builds a castle and tries to defend it against the King who is trying to knock it down. I needed to create a reasonably smart AI that could look at the player's castle and figure out how to circumvent or destroy it in order to reach its objective - the gold pile the player is defending. This was a big challenge, almost too big to consider all at once. So like any good programmer I broke it down into a more manageable problem set. The first challenges: I needed to get the units to have a specific set of behaviors that they would act according to.
How Action Lists WorkFirst you write down all the behaviors you want your AI to have.
A Simple Finite State MachineWell ok. That sounds workable. Frankie had made a good suggestion and Action Lists seem like a great fit for my project. But I'd never heard of them before so I had my doubts - most of what I hear floating around about AI has to do with transition-based finite state machines, similar to what Unity3D uses for animations in Mechanim. You define a bunch of states, and identify when and how they transition between each other. In exchange for some belly scratches, Frankie explained to me when you make a transition based finite state machine, you need to define all the states you want to have, and then also define all of the transitions to and from each of those individual states. This can get complicated really, really fast. If you have a Hurt state, you need to identify every other state that can transition to this state, and when. Walking to hurt; jumping to hurt, crouching to hurt, attacking to hurt. This can be useful, but can also get complicated really fast. If your AI requirements are fairly simple, that's a lot of potentially unnecessary overhead. Another difficulty with transition-based state machines is that it is difficult to debug. If you set a break point and look at what the AI's current state is, it is impossible without additional debug code to know how the AI got into its current state, what the previous states were and what transition was used to get to the current state.
Drawbacks of Action ListsAs I dug into action lists some more, I realized that they were perfect for my implementation, but I also realized they had some drawbacks. The biggest flaw is simply the result of its greatest strength - its simplicity. Because it is a single ordered list, I couldn't have any sort of complex hierarchy of priorities. So if I wanted Attack Player to be a higher priority than Break Door, but lower than Move To Objective, while also having Move To Objective being lower priority than Break Door... that's not a simple problem to solve with action lists, but trivial with finite state machines. In summary, action lists are really useful for reasonably simple AI systems, but the more complex the AI you want to model, the more difficult it will be to implement action lists. That being said, there are a few ways you can extend the concept of Action Lists to make them more powerful.
Ways to Extend This ConceptSo some of my AI units are multitaskers - they can move and attack at the same time. I could create multiple action lists - one to handle movement and one to handle attacking, but that is can be problematic - what if some types of movement preclude attacking, and some attacks require the unit to stand still? This is where Action Lanes come in. Action Lanes are an extension to the concept of Blocking. With Action Lanes, Action Items can now identify specific types of Action Items that it blocks from executing while allowing others to execute without problem. Let's show this in action. An Action Lane is just an additional way to determine what action. Each Action Item belongs to one or more lanes, and when its Blocking property returns true, it will add the lanes it belongs to Each action has a lane or multiple lanes they are identified with, and they will only block other actions which belong to those lanes. As an example, Attack Player belongs in the Action Lane, Move to Goal belongs in the Movement lane, and Build Ladder belongs in both since the unit must stand still and cannot attack while building. Then we order these items, and if they execute they will block subsequent actions appropriately.
Example ImplementationNow that we've gone over the theory, it is useful to step through a practical implementation. First let's setup our Action List and Action Items. For Action Items I like to decouple implementation, so let's make an interface. Here is an example implementation of the IActionItem for the BreakDoor Action Item. For the Action List itself we can use a simple List. Then we load it up with the IActionItems. After that, we setup a method that iterates over the list every frame. Remember we also have to handle blocking. Things get a bit more complicated if you want to use action lanes. In that case we define Action Lanes as a bitfield and then modify the IActionItem interface. Then we modify the iterator to take these lanes into account. Action Items will be skipped over if their lane is blocked, but will otherwise check as normal. If all lanes are blocked then we break out of the loop.
ConclusionSo that's a lot to take in. While coding the other day Frankie asked me to summarize my learnings. Thinking about it, there were a few key takeaways for me.
- Action lists are easier to setup and maintain then small transition-based state systems.
- They model a recognizable priority system.
- There are a few ways they can be extended to handle expanded functionality.