Open Article
L4D_IndoorAppartments.icon

There’s a Hole in Your NavMesh, Dear Zombie

Alex J. Champandard on October 26, 2009

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?

Outdoor navigation mesh chunk in a forest.

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.

Navigation mesh chunk inside an apartment building.

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.

Navigation polygon quads outside in the street.

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:

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

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

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

Quad polygons outside near the farmhouse.

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.

REMINDER: Join resident expert Phil Carlisle and your regular host Alex Champandard in a Halloween Special titled “Zombie AI That's Not Brain Dead.” Discussion will focus on the big challenges of zombie behaviors, and what's next for infected AI. The session is open to attend for anyone signed-up (free) to AiGameDev.com and will take place live online on Sunday, November 1st at 16:00 Eastern / 13:00 Pacific / 22:00 Central Europe / 21:00 U.K. time.

Discussion 8 Comments

Ian Morrison on October 27th, 2009

Excellent overview of the system, thanks for posting it! I'm very much looking forward to the design changes in the sequel that'll discourage sitting still so much... the spitter and charger look like the perfect counter to the cheezier strategies like closet camping that infuriate me during Left 4 Dead. I very much like Valve's design strategy in general... that most of the special infected are there specifically in response to certain player patterns says quite a bit. The smoker was introduced to break up well organized teams, the boomer was introduced to make them think twice about shooting everything that moves, and the hunter was meant to punish people who wandered off on their own. This is better than trying to shoehorn the common infected AI into similar roles, since game mechanics are easier to change than behaviour.

chrispaulson on October 27th, 2009

I'm amazed they used quads. I did my own navmesh generation and used quads but only because I'm poor at maths and quads made the maths easy. I eventually aborted it's use and have moved onto recast.

moomin on October 27th, 2009

[QUOTE]Each polygon is an axis-aligned quad, so the orientation is constrained — though the size seems to be very flexible.[/QUOTE] The polygons in the second image don't look axis aligned ([URL="http://files.aigamedev.com/L4D_OutdoorForest.medium.jpg"]this image.[/URL])

alexjc on October 27th, 2009

Good point, moomin. It seems the yaw of the quads is fixed but the pitch is not...

loic on November 3rd, 2009

I used this axis aligned system network and it works better that many systems I used before/after. It allows a representation that is better for designers, and very easy to manipulate by game programmers, better that a polygon soup for this. If you have some holes in it, you can easily add manually the polygon or increase size detection in code. What I see for example on the navigation mesh management in fallout make me more sceptical than that.

jadnohra on November 3rd, 2009

[QUOTE=loic;33162] What I see for example on the navigation mesh management in fallout make me more sceptical than that.[/QUOTE] what does fallout do? do u know?

loic on November 3rd, 2009

You can see [url]http://www.fallout3-france.fr/forum/viewtopic.php?f=31&t=920[/url]. Sorry it's in french but not the youtube video.

jadnohra on November 3rd, 2009

that's ok, I speak frensh too ... :)

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!