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.
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.
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.
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.
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.
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.