Of all the game modes in Left 4 Dead, Survival has some of the most interesting dynamics from an AI perspective. From the initial concept, to survive as long as you can with help of your four buddies, the game mode quickly turns into a process of finding optimal locations in the map to defend...
Obviously, when there's a medal or achievement involved, this optimization process becomes particularly creative! What makes this interesting for the Zombie AI, is that the best locations are those that the infected horde has a hard time reaching... Cue unexpected results.
This article starts by explaining how the navigation system in L4D works. Then, you'll find out the kinds of problems that occur when players are challenged with finding loopholes in the zombie's ability to move around the world! Finally, the last part discusses the variety of solutions that would be available to resolve such issues.
With What Shall I Build It?
Screenshot 1: Navigation Mesh chunk in the forest. A single polygon is highlighted in yellow, with its neigbours drawn in red.
Left 4 Dead uses navigation meshes as the basis for the zombie's movement around the world. These are based on the technology from Counter Strike: Source that includes the official bot. (See Mike Booth's GDC 2004 presentation.)
The navigation meshes are built partly automatically, but there are many commands in the game's console for manual editing.
Each polygon is an axis-aligned quad, so the orientation is constrained — though the size seems to be very flexible.
The polygons are connected through a variety of links, which can be traversed by walking, jumping, etc.
This solution, in particular the axis aligned quads, is not very common. Most often, polygons can be placed arbitrarily in space — either manually or using automated analysis.
Screenshot 2: Navigation mesh chunk inside an apartment building, littered with debris. (Click to enlarge.)
How Shall I Exploit It?
Zombies are supposed to reach you, the player, anywhere you can stand to keep the pressure on. The Survival levels are in fact customized with barricades and invisible polygons to keep players within the playing area. However, there are bits of the level without (adequate) navigation meshes, so they become inaccessible by the AI zombies.
The following scenario is a typical illustration of the process of exploiting the game's Survival mechanics:
“If you manage to jump onto a tricky location such as the cargo plane in Dead Air, or the chimney in the Lighthouse, the bulk of the horde will not manage to reach you. In fact, they'll simply rush to the location in a polygon on the level beneath you.
Since nobody is killing the zombies, the game ends up with too many entities on the server, and the networking seems to slow the game to a crawl. As long as you can dispatch the occasional Smoker without falling out of position, you can effectively defeat the game.”
Another particularly creative exploit in the Sewers is to jump through the ventilation tunnel and rush back to the Safe Room to deal with (smaller) waves of infected there.
Screenshot 3: Navigation mesh chunk outside in the street, including jump links and drop-down connections.
How Shall I Fix It?
It seems there are three solutions to resolve this problem:
Manually update the navigation meshes in the Survival maps as loopholes are found. Valve has extensive statistics about the game, and can easily find locations in the level that are easy to exploit.
Develop more robust automatic navigation mesh extraction tools and a more flexible (non axis-aligned) representation that reduces the chances of there being discrepancies between the collision mesh and the AI's navigation representation.
Address the problems using game design changes, encouraging the players to move more rather than remain in a fixed position. This is a problem generally with the design of Left 4 Dead as a whole, though, not just survival mode.
Most likely the reason these issues have not been fixed by Valve is that it's not cost effective to implement either of these solutions. And arguably, experienced players take pride in finding loopholes and exploits anyway, so why punish them? For reference, Left 4 Dead 2 seems to address these issues using a redesign.
Screenshot 4: Quad polygons outside near the farmhouse. (Click to enlarge.)
Summary
Replayable games are a good thing for both the developers and the players. However, highly replayable games put a heavy burden on the underlying technology — and AI is no different. Navigation is one of the first things to break in a game, and with highly replayable experiences this becomes more obvious.
Modern technology can be used to resolve such issues and avoid holes in navigation meshes, for example using BSP-based analysis or voxelization techniques. However, by the time you notice the problem it's most likely too late to do anything about it! In that case, redesigning the core mechanics and shipping a sequel the year after is a sensible option.
