On the Intelligence of Maggots

An explanation of the path-finding system used in Maggot Blaster, and how it was used for more than finding paths.

Pathfinding is a term used to describe the problem of trying to find the shortest path between two points.  In the case of Maggot Blaster, I needed to find the shortest path between each enemy, and the player.  Both were constantly on the move, the environment was complex and changing, and there were liable to be a lot of enemies.

The heightmap

Focusing on trying to make the game cope with very large numbers of enemies, I decided to use something like a hive mind approach.  Rather than each enemy work out their own path, a central AI will produce a global “heightmap” that all the enemies will use to find their own path using a much more simple (and fast) algorithm.

A screenshot showing the usually invisible pathfinding heightmap superimposed over a map.

A screenshot showing the usually invisible pathfinding heightmap superimposed over a map.

Above you can see their heightmap from a very old build of the game.  Hidden under the brightest area you can just about make out the player.  From the player, the light spreads out as you’d expect in open areas but is blocked by walls and instead must find another route to get to those areas.

If you’re placed anywhere on that heightmap then you can be guaranteed to find the player if you simply always move towards whatever local direction is brighter.  You don’t get the exact shortest route as the heightmap is generated in such a way that implies you can only move in the four cardinal directions, when enemies can actually move in any direction.  However it always turns out “close enough”, with the only artefact being a tendency for enemies to want to approach directly along one of the cardinal directions.

From heightmap to movement

Translating the heightmap data to enemy movement is very simple.  Just look at the values of the heightmap in the grid squares directly above, below, left and right of the grid square that the enemy currently occupies.  Using just those values, an acceleration is applied to the enemy split proportionally between whatever directions have the greatest increase in brightness compared to the current grid square.  To put it in less words, you imagine the heightmap is showing the contours of land with the bright areas are lower; then have the enemy slide down the slopes.

The characteristics of this sliding vary between enemies which give rise to some unique movement styles despite them all using the same pathfinding technique.  The basic slower enemies proceed along the heightmap at a reasonable speed and with well controlled acceleration.  Meanwhile the ‘crazy purple buggers’ (you’ll see when you play the game) have a very high top speed but fairly low acceleration, which means they’ll get up lots of speed when rushing towards the player but often overshoot their target or appear to skid past doorways they’re aiming for.  It really helps give the various enemies their own character.

Suddenly, swarming

A problem with a few hundred enemies all following the same heightmap with the same rules is that they’ll tend to all follow the same path and end up constantly overlapping.  Suddenly your amazing feat of producing masses of enemies looks like you’ve just produced one caterpillar enemy.

Information on how many enemies are in each grid square is already maintained for use in collision detection.  Whilst generating the heightmap I simply darken each grid square based on how many enemies are known to be there.  This has the effect of slightly shifting the paths generated from the heightmap so that they avoid other enemies.  As this alteration to the values take place during the generation of the heightmap they are carried through and keep the overall heightmap consistent: If the player is inside a building with two entrances and one is already filled with enemies then a new enemy approaching from outside will be likely to enter through the other entrance.

Not only did this change keep the enemies from forming boring orderly lines, but it also helped avoid a situation where the player can just stand at one doorway shooting all who come through it; the density of enemies at that entrance will encourage fresh enemies to seek an alternate route to the player even if it is a slightly longer distance.

Unexpected benefits

Now that a heightmap is being maintained for the whole level, I was able to find some other handy uses for it.

Finding ammo crates is an integral part of the game – they force the player to keep moving, and push them into dangerous and tense situations.  However it isn’t fun just having no idea where the ammo is to start with.  So when the player is at a low ammo state the heightmap is used to draw a path of dots from the player to the nearest ammo crate.  How do I find which ammo crate is nearest? Simply look at the value on the heightmap where each crate is and compare them.

Similarly the heightmap value is used to determine if the player is close enough to cause maggots to notice them and start chasing.  Probably faster than working out the ‘true’ distance, and avoids maggots being able to see you through a wall.

Earlier versions of the procedural map generator would occasionally produce areas that were inaccessible.  The heightmap only holds values for areas that are accessible, so I was able to use it to identify these areas and avoid spawning anything in there.

The heightmap is also used when determining where to spawn fresh enemies.  As well as never spawning an enemy in a location visible on the screen I sometimes want to make sure an enemy is at a minimum distance.  For instance that crazy purple one I mentioned earlier has a special scream/roar sound when it spawns, so I want a little delay before it actually reaches the player’s screen.  Simply limit spawning to areas with the correct range of values on the heightmap.

This one didn’t make it into the final game, but it is possible to simply reverse how enemies react to the heightmap and they’ll produce rather convincing fleeing behaviour.  Typically their fleeing would lead them into a dead-end corner of a building where they would sit quivering.

The future!

I’m very interested in using multiple heightmaps, and having entities switch between which they’re following depending on what behaviour they should be producing at the time.  A “take cover” heightmap could be produced with areas that are out of line of sight of the player being the most bright.  Each entity could make up its own mind on if it would be best chasing, fleeing, or taking cover and pick the corresponding heightmap to follow.  Imagine hundreds of tiny infantry units scurrying behind cover as the player’s mechanical war machine stomps by.

This was actually the plan from the start for what became Maggot Blaster, but such is the way of games.

5 thoughts on “On the Intelligence of Maggots

  1. I’ve re-read this a few times, and while it’s really great and interesting.. it seems like you never explain exactly how you generate the heightmap! :)

    Are you using some sort of cellular-automata/diffusion process to spread “heat” out from the player, or are you explicitly marching outward from the player, etc?

    • The subtle art of glossing over the area of implementation that I’m not so proud of!

      Checking back on the source now, it’s a pretty basic march outwards from the player:

      /*This snippet makes use of \'Tile\' class which stores some information about each tile/cell on the map.*/
      /*have a queue of tiles which need examining.*/
      var toExamine:Vector.<Tile> = new Vector.<Tile>();

      /*start off at the tile which holds the target for the AI (in this case, the player)*/
      tileWherePlayerIs.distanceFromTarget = 0;
      toExamine.push(tileWherePlayerIs);

      while (toExamine.length > 0)
      {
      var thisTile:Tile = toExamine.shift();
      var distanceForNeighbours:int = thisTile.distanceFromTarget + 1;
      for each (var neighbour:Tile in thisTile.neighbours)
      {
      /*if this neighbour isn\'t a wall tile and either it doesn\'t have a distance set yet, or we have found a new shorter route to this tile, then..*/
      if (!neighbour.isWall && (neighbour.distanceNotYetSet || neighbour.distanceFromTarget < distanceForNeighbours))
      {
      /*set the tile\'s distance, and add it to the stack of tiles that need their neighbours examined.*/
      neighbour.distanceNotYetSet = false;
      neighbour.distanceFromTarget = distanceForNeighbours;
      toExamine.push(neighbour);
      }
      }
      }

      Rest assured the original code is not nearly this neat. Nice to look at it and see how much I’ve improved though!

      It ended up so slow that I had to dynamically split the execution between frames (not shown in the code above) so that the frame rate would never be impacted by time taken waiting for the heat map to be generated. It simply kept track of how long since the last frame rendered, and paused working through the loop as soon as the next frame was due. That actually worked quite well but also meant the game got easier on older machines; updating the heat map would be split over so many frames that enemies were always chasing after where you were several seconds ago. I should have addressed that by having enemies switch to an alternate pathfinding technique once they were close to the player.

      If I were to do it again now I’d at least experiment with using a cellular automata in a custom shader. The shader would have to be repeated many times, and I’m unsure how much of an overhead that would add – might well end up negating the benefits of moving the processing to a shader. Would be worth a try though, and it would be reasonable to have the shader executing asynchronously.

  2. Awesome, thanks! I was hoping you had figured out some sort of super-fast method since you implied that the heatmap is continually updated/recalculated.. alas :(

  3. I would think it easiest to hunt buy using the standard basic maze solver but amendit to instead of searching the door of the maze have it seek the players coordinants only take a few steps at a time (turns) and re solve after each player movement.
    I think I would also compare distance player to aponant as to make oponant ie. aware of the player and ifnot, then aware of another objective or target. I like to also give my oponant players that second/third,more goal or function.

  4. Pingback: Shootron AI » Wizardstar

Leave a Reply

Your email address will not be published.

* Copy this password:

* Type or paste password here:

16,851 Spam Comments Blocked so far by Spam Free Wordpress