It’s kind of crazy how many zombie-related games have creeped up in the last year or so.  It’s especially odd that it came at a time when zombie movies have actually been on the low end.  The last real zombie movie I can recall is the remake of Dawn of the Dead or maybe Resident Evil came out after that (if you can call that a zombie movie).  When I started working on Zombpocalypse, the zombie scene was pretty dim.  Left for Dead was just a screenshot and the most zombie games up to that point had stuck with the old rigid zombies.  I thought it would be cool to make them fast and fierce, but I had no idea of the kind of technical issues it would bring.

Zombies Zombies Everywhere

AI was especially hard to master in the game.  This may sound silly for a game centered around mindless drones, but their fast pace and ability to navigate the terrain intelligently put some real hurdles in my way.  Originally the arenas were planned to be screen-sized square rooms with no obstacles, similar to the game that inspired the arcade flare; SmashTV.  I suppose you could say that I got a little zealous.  I wanted to have larger environments to place weapons through out as well as have multiple entrances for zombies to appear on the stage.  I wanted obstacles to help the player be more strategic and use the environment to his advantage.  Though all of these things sound cool on paper it quickly became a programming nightmare.  Zombies could no longer dart toward the player in a straight line (as with most arena shooters), they had to avoid environment obstacles to prevent from looking completely stupid and allowing the player to just stand behind a barrel and pick them off, one at a time.

Method #1: Bounce with Me

I did not want to spend a lot of time on AI, so my first attempt was a simple reflection AI.  You may have recalled this if you’ve ever worked in the Quake2 source code.  The idea was simple:

• aim toward the player and start walking
• if an obstacle if in my way, calculate a reflection vector that will cause me to slide along the obstacle (toward the player) until it’s not blocking me anymore.
• repeat step 1

That’s it!  It actually works quite brilliantly simple and works great… Well most of the time.  If the environment contains only simple obstacles then we can create a small cylinder for each obstacle; creating a perfectly smooth surface to slide around.  Even if the player was on the exact opposite side of the cylinder the AI could pick a random side to take.  The problem gets more complicated when you are dealing with long or irregular shaped obstacles like concrete barricades, or fences.  The player can easily trick the AI into a concave obstacle where the only thing the AI can do is sit there and scream idle threats at you or run in circles, trying to get out.

Method #2: Thanks Hansel

My second attempt was to create a fixed-sized queue of footsteps left by the player.  Like breadcrumbs, the AI could find the nearest footstep that was not blocked and aim for that direction; knowing that the next node in the queue would get the AI one step closer to catching it’s target.  This approach only worked in cases where the player had actually traveled to.  The player could exploit the AI by simply not exploring all corners of the map.  In doing so, no footsteps would be available and the AI would have to fall back to Method #1, with all of it’s flaws.

Method #3: The Right(?) Way

Figure 1: The environment geometry was used to auto-generate the Area Mesh. The inner dark ring was used as padding to prevent the AI from getting too close to walls.

As they say, third time is a charm.  I gave up on the “quick fix” to intelligent AI and decided to go with a path planning approach.  Each AI update would sample the players position and the AI position to ensure that it was on the right path.  This was actually quite fast because the paths were stored in a shared manager and cached for use across multiple frames.  The nice part of this approach is that a swarm of zombies that are standing near eachother will likely share the same path information.  This allowed me to compute paths once and share it’s results without any special code or broadcasting of the data.  The AI simply queried the cache, regardless of whether it was the originator of the path or not.  The cache only told the AI what direction to walk, so no costly information needed to be stored by the AI entity since it will simply query for a new direction on it’s next update.  If the player moved or the AI moved off of it’s path a new path is computed and stored into the cache.

Area-Based Navigation

Figure 2: Most of the environment was eye-candy, but the auto-builder had no intelligent knowledge of what was playable.

What made the caching system work so well is that the number of nodes in the graph were actually very small.  This meant that it was less likely that the player would move off of the path by simply taking a couple steps in any direction.  Once the AI and the player were on the same Area node, the AI could assume that there were no obstacles remaining.  The advantage of this approach instead of a traditional navigation mesh was that it allowed me to create irregular nodes with an arbitrary number of connections to neighbors.  Figure 1 shows that the Areas computed are large and not uniform in shape; allowing for less nodes and reduced memory for stored paths.  One disadvantage was that it did not always compute the most optimal path.  Run-time calculations were required to reduce the path on the fly and determine if the AI could skip a few nodes along the path to reach the player.  This was required for several reasons that are native to navigation mesh approaches.  One example is that the AI generated a path to the target Area, not the target position.  If the Area was very large, then the player could potentially exist anywhere inside of it.

Auto-Generated Area Meshes are a Pain

Figure 3: Bad Areas generated by curved / rounded walls.

As a programmer, I came up with a programmer solution to the problem of constructing these Area Meshes.  Unfortunately, Zombpocalypse was such a simple game that my auto-magic approach turned out to be one of my biggest time wasters.  It would have been a beautiful thing to exploit for massive environments, but it just proved to be an overbuilt piece of technology for this game.  Most of the arenas were simple and flat playable spaces with eye candy that populated the outer region of the arena.  This resulted in poorly constructed Area Meshes where 60% of the Mesh went unused by the game because the AI could never reach these locations.  In addition to the unused Areas, smooth curved surfaces would create a geometry explosion because of all the bad cuts that it made into the AI Mesh.

Automatic generation also meant that floating-point errors caused some neighboring Areas to not connect to eachother.  A second pass was required to add logical edge connections for falling off of ledges.  In this second pass, I also did additional checks to catch many of those simple “walking” edges that should have been connected, but failed.  The whole process was very touchy and in retrospect would have been easier to simply model the Area Mesh and use the tool to generate the connections from clean source data instead of carving up the world and trying to put the pieces back together in some intelligent manor.