Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 01/10/16 03:03 AM
    Sign in to follow this  

    Action Lists: Simple, Flexible, Extendable AI

    Artificial Intelligence
       (1 review)

    JesseCF
    • Posted By JesseCF

    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.
    Wallpaper1.jpg
    A quick internet search caused my mind to implode, of course. Searching for "Game AI" brought up results on planners, finite state machines, steering behaviors, flocking, A*, pathfinding, etc. I had no clue where to start, so I did what any reasonable, rational person would do. I asked my dog. This isn't anything new, of course. Whenever I have a tech problem, I ask my dog. Now I know what you're thinking "Jesse, that's dumb, and you're crazy... What do dogs know about computers?" Well, let's just gloss over that. It may or may not have involved some illegal technology and or college class auditing. Anyway, I said "Ok Frankie - there is so much going on with AI, I really don't have a clue where to start. How should I go about creating an AI framework for my game units?" Frankie gave me this pretty withering look that basically informed me that I was an idiot and pretty dumb, despite what my high school teacher Mr. Francis may have told me about there never being any stupid questions. I'm pretty sure Frankie wouldn't have had nice thoughts about Mr. Francis either. "Jesse", she asked, "how do you typically start your day?" Well, I write everything that I need to do that day down in a list and then prioritize it according to how important the task is and how soon it needs to be done. I explained this to Frankie and she responded "And that, is an Action list." She told me that an Action List is a list of tasks or behaviors that your game units work their way through one at a time. It is a form of finite state system, and could be described as a simple behavior tree with a single branch level. Here is how they work. According to my dog.

    How Action Lists Work

    First you write down all the behaviors you want your AI to have.
    List Behaviors.png
    Then you order them according to priority. Lowest to highest.
    Ordered List.png
    Now we iterate over the list checking each action to see if it can execute and if it can, executing it. We then check the actions Blocking property, and if the item is Blocking further actions we exit the list. We will get into why Blocking is important later. In our example here, our first action Attack Player will only execute if the AI is close to the player. Let's say it is not, so it checks if it can build a ladder at this location (and should it), and so on until it finds an action item it can execute such as Break Door. It then executes the Break Door code.
    Executing.png
    Here is where Blocking comes into play. If Break Door occurs instantly, then it will not block any further actions and the rest of the list can execute. This is typically not the case - actions usually take up more than one frame. So in this case the Break Door Action Item calls unit.Attack(door), which will change the unit's CurrentState from Waiting to BreakDoor and will return true until the door is broken.

    A Simple Finite State Machine

    Well 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 Lists

    As 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 Concept

    So 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.
    Action Lanes.png

    Example Implementation

    Now 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. Action Item Interface.png Here is an example implementation of the IActionItem for the BreakDoor Action Item. Break Door Action Item.png For the Action List itself we can use a simple List. Then we load it up with the IActionItems. Action List Constructor.png After that, we setup a method that iterates over the list every frame. Remember we also have to handle blocking. Iteration Method.png 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. Action Item Interface With Action Lanes.png 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. Action Item Iterator With Lanes.png

    Conclusion

    So 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.
    As with anything in coding, there is often no best solution. It is important to keep a large variety of coding tools in our toolbox so that we can pick the right one for the problem at hand. Action Lists turned out to be perfect for King Randall's Party. Perhaps they will be the right solution for your project? Originally posted on gorillatactics.com



      Report Article
    Sign in to follow this  


    User Feedback


    Maybe i haven't understood something, but the way i see it, at action lane example - attack player should not  belong to movement lane.

    Share this comment


    Link to comment
    Share on other sites

    Sounds like maybe your dog possibly read some of my old [url=https://docs.google.com/presentation/d/1kzxp8jfO3GvQsfWo3JHW2b44l9rC9g0jEDJzmU5I_No/edit?usp=sharing]Action! List[/url] slides... I like your dog. :)

    Share this comment


    Link to comment
    Share on other sites

    Maybe i haven't understood something, but the way i see it, at action lane example - attack player should not  belong to movement lane.

    Kalo, the colored bar isn't indicating what lane the Action Item is in, rather the red bar is showing that because Attack Player is in the "Action" lane, it blocks Build Ladder, which is in the same lane, but does not block Move To Goal (hence the green bar) because only Move To Goal is in the Movement Lane. 

    A couple of people have mentioned that this graphic is a little confusing, so I'm going to think about how I can change it to be more clear in meaning. Thanks for letting me know. :)

    Share this comment


    Link to comment
    Share on other sites

    Sounds like maybe your dog possibly read some of my old Action! List slides... I like your dog. smile.png

    Hey, neat content. I have to make my own set of slides for a presentation on this topic I'm doing on the 16th for Boston Festival of Indie Games talks. Hopefully they turn out as good as yours. :)

    Share this comment


    Link to comment
    Share on other sites

    Great article,

     

    helped a bunch in combing/structuring my AI logic that was growing wildly day by day.

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By multiappple
      Hi,guys.
          I need to project a picture from a projector(maybe a camera) onto some meshes and save those into the mesh texture according to the mesh's unfolded UV.It  just like the light map which encode the lighting-info into the texture instead of the project-info.
          The following picture is an example(But it just project without writting into texture).I noticed blender actually has this function that allow you to draw a texture on to a mesh.But i have no idea on how to save those project pixel into the mesh's texture.
          I think maybe i can finish this function if i have a better understanding about how to produce Light map.Any advises or matertials can help me out?(any idea,any platform,or reference)>?

    • By Seer
      I have programmed an implementation of the Separating Axis Theorem to handle collisions between 2D convex polygons. It is written in Processing and can be viewed on Github here. There are a couple of issues with it that I would like some help in resolving.
      In the construction of Polygon objects, you specify the width and height of the polygon and the initial rotation offset by which the vertices will be placed around the polygon. If the rotation offset is 0, the first vertex is placed directly to the right of the object. If higher or lower, the first vertex is placed clockwise or counter-clockwise, respectively, around the circumference of the object by the rotation amount. The rest of the vertices follow by a consistent offset of TWO_PI / number of vertices. While this places the vertices at the correct angle around the polygon, the problem is that if the rotation is anything other than 0, the width and height of the polygon are no longer the values specified. They are reduced because the vertices are placed around the polygon using the sin and cos functions, which often return values other than 1 or -1. Of course, when the half width and half height are multiplied by a sin or cos value other than 1 or -1, they are reduced. This is my issue. How can I place an arbitrary number of vertices at an arbitrary rotation around the polygon, while maintaining both the intended shape specified by the number of vertices (triangle, hexagon, octagon), and the intended width and height of the polygon as specified by the parameter values in the constructor?
      The Polygon code:
      class Polygon { PVector position; PShape shape; int w, h, halfW, halfH; color c; ArrayList<PVector> vertexOffsets; Polygon(PVector position, int numVertices, int w, int h, float rotation) { this.position = position; this.w = w; this.h = h; this.halfW = w / 2; this.halfH = h / 2; this.c = color(255); vertexOffsets = new ArrayList<PVector>(); if(numVertices < 3) numVertices = 3; shape = createShape(); shape.beginShape(); shape.fill(255); shape.stroke(255); for(int i = 0; i < numVertices; ++i) { PVector vertex = new PVector(position.x + cos(rotation) * halfW, position.y + sin(rotation) * halfH); shape.vertex(vertex.x, vertex.y); rotation += TWO_PI / numVertices; PVector vertexOffset = vertex.sub(position); vertexOffsets.add(vertexOffset); } shape.endShape(CLOSE); } void move(float x, float y) { position.set(x, y); for(int i = 0; i < shape.getVertexCount(); ++i) { PVector vertexOffset = vertexOffsets.get(i); shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y); } } void rotate(float angle) { for(int i = 0; i < shape.getVertexCount(); ++i) { PVector vertexOffset = vertexOffsets.get(i); vertexOffset.rotate(angle); shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y); } } void setColour(color c) { this.c = c; } void render() { shape.setFill(c); shape(shape); } }  
      My other issue is that when two polygons with three vertices each collide, they are not always moved out of collision smoothly by the Minimum Translation Vector returned by the SAT algorithm. The polygon moved out of collision by the MTV does not rest against the other polygon as it should, it instead jumps back a small distance. I find this very strange as I have been unable to replicate this behaviour when resolving collisions between polygons of other vertex quantities and I cannot find the flaw in the implementation, though it must be there. What could be causing this incorrect collision resolution, which from my testing appears to only occur between polygons of three vertices?
      Any help you can provide on these issues would be greatly appreciated. Thank you.
    • By menyo
      I really like to add AI to my game in the form of behavior trees and have been reading about them. The primary thing I am "stuck" with is how to pass data. Some articles mention a blackboard that should be passed down the tree nodes so they can set fields on it, but this means for each leave task that needs some form of data the blackboard gets a field. I imagine a lot of leave leave tasks and some need many fields to set on this blackboard and this deviates from my perception of clean and scalable code. Are there other ways to handle this?
    • By Adeilton Alves
      Hello everyone, I'm new here and sorry if this isn't the right place to ask but i asked in a few forums around the internet and no one yet help with it.. I'm have been trying to mod this game for years, but I still stuck with the raw files from RACJIN games, 
      Raw Files [ Mod edit: Removed ]
      I would like to identify the compression algorithm used to compress these files so that they can be decompressed and analyzed.

      Game : Naruto Uzumaki Chronicles 2... A.K.A Naruto Konoha Spirits in Japan.
    • By Waaayoff
      I'm looking for an algorithm that I can use to remove vertices that are close to each other within a margin of error in a triangular mesh. Pretty much similar to Blender's "Remove Doubles" feature, if anyone is familiar with it.
      I think the issue isn't just removing the doubles, but also how would I handle the face indices once I remove "duplicate" vertices?
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!