How AI in Games Works

All Terrain

So you now have characters that look as if they can think for themselves, but how do they know where they are, and how do they know what their environment looks like so that they can reach you in the most efficient way?

NPCs can’t see the same game world you’re viewing – that would take a ridiculous amount of processing power. Instead, they need a guide to the areas to which they can go. This often takes the form of a navigation grid that shows obstacles and the shape of the terrain, but developers often also use a navigation mesh (usually called a navmesh) that’s local to the current 3D scene.

A navmesh is basically a low-resolution 3D mesh that sits on top of a 3D scene and shows an AI character the areas to which it can move, as well as featuring tags and hints to the AI that have been placed by the designer. On the AI development blog for F.E.A.R. 2: Project Origin, Monolith’s senior software engineer, Matt Rice, explains that "the designer will place this invisible mesh any place he wants the AI character to potentially move to".


Rice provides the example of an NPC in the game deftly manoeuvring between objects that provide cover, and then diving through an open window to flank a buddy who’s taking fire. Rice explains that "this is accomplished by our fancy animators creating a palette of animations for the designers to use in any given space. The designer will then tag a portion of the navmesh to indicate to the AI that it must play a particular animation (a dive for instance) in order to traverse that area".

This might sound a lot like scripting, but the NPC will decide for itself whether diving through the window is the best course of action by using the game’s planning system. If it needs to dive through a window, the navmesh will tell it which animation it needs to use when doing it. Amusingly, Rice adds that "if the resulting path ends up by looking cinematic and awesome, then sweet; I’ll take credit for it. If not, it’s back to the drawing board for myself and the designer or animator, or both".

A navmesh provides more flexibility than a standard navigation grid, and not just because of the animation hints. Bethesda’s Jean-Sylvere Simonet points out that the navmesh used in Fallout 3 (see image, right) for local path finding "turned out to be the perfect support for storing cover information that the NPCs needed, and it also allowed us to have a unified pipeline for making small and large creature paths around the environment. Whereas our previous system (a navigation grid) assumed a standard character size, the navmesh let both Bloatflies and Behemoths use the same data to find their way around corridors and alleyways".

Simonet also points out that a navmesh can help the AI with much more than pathfinding. "Because of the inherent spatial information it stores," says Simonet, "we were able to write algorithms that 'thought' about the space. Searching behaviour, for instance, was able to use the navmesh data to map out areas that an NPC had investigated quickly and efficiently, and it could then come to a conclusion about where the target was."