Jump to content
  • Advertisement
  • 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

  • Advertisement
  • Popular Now

  • Similar Content

    • By Jackrin
      Hi guys, it's been some weeks since i started to think to create an AI for a mobile game that i play, which can be played on PC as well so that i can use softwares
      The problem is that i'm not really into "AI stuff" so i really don't know where to start, or how can my AI do what i want it to do.
      In this first post i just want some tips about something my AI should do.
      I'm not going to tell you all the game, because i prefer not to, and i think is not necessary either.
       
      Ok so, one of the things my AI should do is this:
      Recognise the map, the border of the map (basically the area where i can tap), it should recognise all the defenses in the map (which you can see, because you see the whole area from above),
      Just this for now, i don't really know how the AI can recognise all the different defenses in the area just by seeing them, and it need to be a precise thing, we are talking about millimiters.
      Maybe the AI can recreate the map in its software, but i don't know if im saying something right, so i'm just gonna leave this to you, hopefully someome will clarify thing to me.
      Thanks.
       
      Edit: just thought about the fact that i could even recreate the map by hand, with an ipotetic software with all the defenses and stats
    • By QwePek
      Hello, I want to make a game where i can procedurally generate caves. I found out that the best way to create this caves for me is by algorithm Perlin Worms, but I'm having problems with understanding it. Could someone explain how it works or write some code examples (best in SFML). Thanks
    • By shreya
      Hello everyone!
      I'm an IB student writing my extended essay in CS comparing Monte carlo tree search and minimax.
      For collecting my primary data, I wish to conduct a benchmark test on both these search techniques. For that I need to use a game that implements the monte carlo tree search and also has a version that implements minimax. Can someone please help me out and send the links of where I can find such an engine/game?
      Thank you!!
    • By Boris The Brave
      I recently discovered the source code to Diablo 1 has been reverse engineered to a readable state: https://github.com/diasurgical/devilution
       
      I did a write up of how the levels are procedurally generated: https://www.boristhebrave.com/2019/07/14/dungeon-generation-in-diablo-1/
    • By GameDev.net
      This is a blog about our development of Unexplored 2: The Wayfarer's Legacy. This game features state-of-the-art content generation, generative storytelling, emergent gameplay, adaptive music, and a vibrant art style.
      Part 1
       
      Unexplored 2 is a roguelite action adventure game where the hero is tasked to travel the world in order to destroy a magic staff. It features perma-death, but when your hero dies you get a chance to keep the world, so you can uncover its many secrets over the course of several runs. In a way, the world is one of the most important and persistent characters in the game. In this article, I'd like to share how we generate it.
      There are several ways in which you can approach world generation for fantasy games. For example, you can use simulation techniques to generate a realistic topography and populate the world from there. Instead, we choose a different approach for Unexplored 2: we used a process where we sketch a rough outline first and try to fill in the map with in a way that optimizes the affordances and gameplay opportunities the map has to offer.
       
      Rough Outline
      It all starts with a random Voronoi graph with 80 cells placed on a map with a 3:2 aspect ratio:

      Figure 1 - The initial Voronoi
       
      We use a Voronoi because it has a fairly natural distribution of cells and because the structure can be treated as a graph with each cell being an individual node and each edge a connection between nodes. This is useful as we use graph grammar rules to generate the map.
      In the first step, the cells on the western edge are set to ocean. Then we grow the ocean a little creating a more interesting coastline, and set the remaining cells to be land mass. A starting location is picked along the coast and a goal location is picked somewhere on the eastern side. Each cell in the graph marked with its distance to the start and the distance to the goal. Distance in this case is measured in the number of cells between two locations.
       

      Figure 2 - Land and Sea
       
      Obviously placing the ocean always on the west is just a choice (Tolkien made us do it). It is easy to make the whole map an island or have the ocean cover other edges of the map. What matters for us, is that this creates a consistently large playing area. But we don't rule out adding other templates and variations in the future.
      The next step is to make sure that the journey will not be too easy. After all, 'one does not simply walk into Mordor'. The way we achieve is also lifted directly from The Lord of the Rings: we simply make sure there is a mountain range between the start and the goal:

      Figure 3 - A Tolkienesque mountain range
       
      The mountains are started somewhere close to the goal and then allowed to grow using the following graph grammar rule, which basically changes one open cell into a mountain for an open cell that is next to one (but no more) mountain cell, relatively close to the goal, and relatively far from the starting location:

      Figure 4 - Graph grammar rule to grow the initial mountain range
       
      Unexplored 2 has a journey from the start location to the goal. In order to tempt the player to divert from the most direct route and explore the rest of the map a number of 'adventure sites' are placed at some distance of the start and goal location. Creating a nice spread of potential interesting travel destinations. Each site is placed inside a region of a different type. In this case, the goal is placed in swamp (s), a haven (green h) is placed in a hill area close to the start, and other sites are placed in a desert (d), forest (f), and a barren area (b). Orange edges indicate the borders between the regions.

      Figure 5 - Adventure sites
       
      Adding Topography
      The remaining cells are randomly grouped into additional regions until every cell is assigned a region on the map. The terrain types for these regions are left undetermined for now.

      Figure 6 - Regions and rivers
       
      Next rivers are added to the map. Initially, rivers are allowed to grow along the borders of regions. Unlike a realistic world generation process, we choose to start growing rivers at the ocean, selecting a new edge to grow into at random, favoring to grow alongside mountains as the go along.

      Figure 7 - Graph grammar rule that changes a region border next to an ocean into a river
       
      After rivers have been added, the region types are filled in and reevaluated. In this case, more forests are added and the desert area in the south is changed into a plain because it was next to the ocean and far to the south (our map is located in the southern hemisphere, hence the south is cold). At a later stage, we might take the opportunity to change the desert into something more interesting, such as a frozen waste.

      Figure 8 - Complete topography
       
      Once the regions are set, rivers are allowed to grow a little more, especially through terrains like hills and swaps. Depending on their length rivers be narrow, wide, or very wide. Only narrow rivers are easy to cross, for the wider rivers certain edges are marked to indicate points where the river can be crossed.

      Figure 9 - Graph grammar rule to grow a river through a swamp
       
      Adding Opportunities
      The topography is fairly basics and we still need to fill in a lot of details. From a design perspective regions (not cells) are the best unit to work with in this respect as we want regions to form coherent units in the experience of the game. To make working with regions a little bit easier, the Voronoi graph is reduced to a graph representation where all cells of each region are combined into one single node.
      Based on the relative distance to the start and the goal regions are assigned a difficulty and a number of opportunities and dangers are generated accordingly.

      Figure 10 - Region graph
       
      At this stage, the generator starts to look for interesting gameplay opportunities. Using several graph grammar rules a large forest with high difficulty will be assigned different attributes than a small, low difficulty swamp harboring an adventure site.
      At this stage, special terrains, such as purple 'obscuri' forests or red sand desert are also added to the mix. When generating the game in the world we have the option to request certain special features such as special rare terrain, or special quest content. These are processed first. To the best of the generator's ability, it might be that no good fit is found, at which point either we need to generate a new or continue without the requested feature.
      One interesting effect is that if certain special terrains require slightly rare conditions to emerge then the terrain type automatically becomes rare content. For example, a special quest might require a large swamp area with a river which will not be present in every world. The downside is that sometimes rarity becomes hard to control or design as there literally is no simple slider to push up if we want to make such a terrain type or quest more frequent.
       
      Creating Visuals

      Figure 11 - The map as it appears in the game
       
      Up until this point, the map is all data. The next step is to create the visual representation based on the map. To this end, we generated a new Voronoi diagram with a higher resolution (about 1200 cells) and map each smaller cell to the cells of the original map data. This creates a better resolution of details. Figure 10 shows how to original cells map to the visual map:

      Figure 12 - Original cells projected onto the map
       
      Individual cells can be raised and lowered to create elevation, and colored and decorated to suggest different terrains. Some of these decorations are assets such as trees which can vary in size and density based on the relative temperature and humidity of each cell. For now, we're using a very simple algorithm to approximate individual climate using longitude, latitude (it gets dryer towards the east), elevation and closeness to water.
      Other decorations are build from simple geometry based on the high-resolution Voronoi graph. This can be easily seen in image 13 below. This geometry includes slightly sloped mountain peaks, elevated patchwork to create the impression of a broken, barren landscape, and sunken centers to create pools.

      Figure 13 - Map detail showing how decorations use geometry based on the Voronoi graph
       
      Regions and their associated terrain types play an important role in the generation of these details. As can be observed in the figure above, forest rise towards their center, as do hills and mountains. Rivers are never elevated (to save us the trouble of trying to do so consistently). Terrain is blended a little so that height difference are not too pronounced where not intended, and interesting borders are created. In many cases, these blended terrains offer ample opportunities to liven op de map with rare features.
       
      Setting Up Nodes
      The world is of Unexplored 2 is not a continuous world. Players travel from node to node and can choose (or are forced) to explore gameplay areas each node represents. Connection between nodes determines where the player can travel. To place the nodes on the map we use to original low-resolution Voronoi diagram. A node is placed on each cell and on each border between cells, as can be witnessed in the image below:

      Figure 14 - Network of nodes placed on the Voronoi graph
       
      Certain connections are special. As mentioned above wide rivers can only be crossed at certain points, and mountains also create barriers. For uncrossable rivers the node that would have been placed on the river is split in two and each node is moved away from the river a little. Where a crossing is needed the node is actually split in three so that a bridge node is created that conveniently only has two connections (and exits) on each side of the river. For mountains and passes across mountains something similar is done.

      Figure 15 - Detail of the node network showing rivers and mountains
       
      Some of the nodes are already marked out as special sites in the generated data. The area templates associated with these sites often indicate special features to appear on the map (for example a volcano, a village, a mud pool, or a group of trees). Although, in some cases these features are only added after the player has visited the area and found its secrets. All other nodes are assigned templates based on the region they belong to and their relative position within that region.
      Each region has a number of types of locations. Typically a region has one 'heart' location assigned to a node quite central in the region, or a 'smallHeart' location if the region is relatively small. A number of 'rare' locations are scattered out across the locations not on the region's edge, and finally, all other locations are drawn from a random destination table associated with the region's terrain. Figure 16 shows sample entries from the table we use to populate forest and plain regions (the 'locations' in this table are the random encounter location the game uses when travelling between each node).

      Figure 16 - Random destination table
       
      Wrapping Up
      At the moment of writing the map generation is still a work in progress. We are constantly adding details as the game's content keeps growing. But I don't expect the general approach to change much.
      We are quite happy with the results, as in our humble opinion the maps are quite beautiful. But what's more important, they are readable: players can predict where barriers and dangerous terrains are to be found. A lot of information is there and we don't hide it behind a fog of war. The map facilitates anticipation and foreshadowing which are two key gameplay design features. We hope that when the game is released in full, players will enjoy simply pouring over the map and plan their journey.
       
      If you are interested in learning more about the game please check us out on Fig.co or on Steam.
       
      Note: This article was originally published on the Ludomotion website, and is reproduced here with the kind permission of the author.
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!