How Navigation Meshes Work in 3D Games

click to begin

Youtube

Hi I'm Tommy Thompson and this is AI and Games, a series on research and applications of artificial
intelligence in video games. This video is the beginning of a new series of AI 101, where
I'm going to be looking at many of the fundamental AI tools and techniques used in game development.
This is aimed at helping aspiring game developers understand the basic theory of these methods,
where they become useful in making your own games and how they're applied in some of the
biggest titles in the industry.
In this first video, I want to talk about navigation. One of the most critical and often
unspoken challenges found in modern games is ensuring that non-player characters can
move around an environment. This means walking, running, climbing, hiding behind cover, swimming
and the like. Navigation seldom receives the attention it deserves when talking about how
AI works in a specific game - a point even this series is guilty of. Despite this, faulty
navigation and character movement is arguably one of the easiest ways to break the immersion
of a game.
So let's take a look at how navigation works in 3D games using a tool referred to as a
navigation mesh: what it is, how it works and how some games address very specific issues
that their core design creates for them.
A navigation mesh or navmesh is a data structure used to represent the accessibility of a three
dimensional surface or space by encoding it as a series of polygons. If you watch an AI
character move across a surface in a given game, odds are it's using a navigation mesh
to do so. A navigation mesh stores important data about that region of space for an AI
character to move across it, this includes:
- What parts of the surface is accessible given there might be obstacles or the structure
of the space fractures it into even more polygons. - How individual surfaces link to one another.
This is useful for environment artists given they will build up a game world with smaller
pieces rather than one big chunk of land. - Dictating a type or region for that surface.
Regions can be used to identify how expensive it is to traverse a surface by providing a
cost value and AI agents can be told which types they can navigate across.
Modelling accessibility of the space is critical to achieve any sort of intelligent movement,
given we want to ensure our characters know if they can move around the game space in
a manner that is cheap and easy to calculate. Meanwhile the type of an area is important
in crafting an AI that looks like it's making intelligent decisions about how it uses or
ignores part of the virtual space. This is important in open world games such as Assassin's
Creed and Far Cry, where NPCs will actively avoid moving in water and instead attack from
the shore or move around if possible. Meanwhile, using costs to make regions more expensive
than others can be useful for having characters prioritise surfaces such that their behaviour
is in keeping with expectations. A great example of this is civilians in Grand Theft Auto,
who we expect to walk along sidewalks and use signal crossings rather than just wander
about on patches of grass and cross the road wherever they like. Although if Rockstar ever
decide to make a GTA in Glasgow they can probably throw out those restrictions.
Lastly links helps us manage where and how characters can cross gaps in the nav meshes.
Sure, sometimes you might want to ensure an AI can't follow you to a specific location,
such as the inmates in Outlast who can't follow you after you run through tight gaps. However,
you typically want AI to move between navmesh areas at specific points, such as soldiers
climbing up and down ladders in F.E.A.R. or demons leaping to higher ground in DOOM. Links
dictate where and how this can happen and is often heavily tied to an animation that
should be played whilst the link is traversed: a point that I'll return to in a future video.
As mentioned earlier, navigation is often the first point of failure in a games AI and
its readily apparent when it's not working. Sources close to the development of DOOM 2016
revealed to me that the SnapMap system - a pretty cool map and mode creation tool - was
consistently broken during development, largely due to navmesh integration issues. Plus bugs
in behaviour in a lot open world games such as Watchdogs and Assassin's Creed, have often
stemmed from navigation issues or failing to address how to compensate for limited movement
capabilities.
However, before I get into the fun ways navigation is utilised in game design, lets side step
into how navmeshes are typically adopted in gaming and where they come from.
The history of navigation meshes stems back around 20 years as in-house 3D engines arose
in the late 1990's. The actual tech and theory behind it stems from robotics research from
the 1980's, where back then researchers were faced with how to get a robot to move across
a real world space after being given accurate map data. Some of the early days tech, such
as meadow mapping or voronoi tesselation - which take a space and break it up into polygons
like so - is the cornerstone of how nav meshes are built today. Once a space like this is
broken up, an AI can then use a search algorithm to plot a path through the space and optimise
it to become more natural.
One of the largest moves forward in defining navigation tools for games can be found in
1999's Quake III Arena, which uses a navigation system called the 'Area Awareness System'.
The AAS scans the game map to create convex hulls that define walkable regions and simulates
movement such that it can identify how and if agents can move between them and allows
for custom areas and nav mesh links to be established.
This principle has largely held consistent, with the likes of Mikko Mononen's open source
projects Recast and Detour approach the problem in a similar manner. This consistency, plus
how critical basic navigation is to even the most basic behaviours in 3D video games, means
it's one of the few AI technologies commonly provided in commercial game engines such as
Unreal Engine and Unity. Each engine has it's own way in which it allow users to define
and customise them, but the core logic is largely consistent (with Recast being the
basis of the navmesh systems in Unreal Engine 4)
Navigation meshes are typically built or baked in advance in-engine during development and
are stored as data as part of the level files. Designers and programmers would build navigation
meshes in their engine of choice during development. However this presents a problem: given that
whether an area is accessible or not might not hold true in an environment once gameplay
is underway. Even something as simple as another non-player character moving through the space
can violate the integrity of the navigation mesh, but this is often handled with tools
that identify them as moving obstacles that you should avoid. But what's worse is when
the topology of the map has been fundamentally altered when parts of the level are changed,
disabled or outright removed. As stated, nav meshes are baked in advance because they're
an expensive thing to do that could impact performance. However, nowadays most game engines
do allow for re-baking of a navigation mesh at runtime, this is a still time consuming
and relatively expensive process.
So let's take a look at how some games use nav meshes in clever ways as part of their
core design as well as some of the problems faced along the way.
While nav meshes are critical to achieving basic behaviour and movement, sometimes we
can clever ways to exploit them for the purposes of the games core design. So let's take a
look at some fun and often pragmatic examples of how games work with and around navmeshes
in AAA games.
First up let's talk combat behaviour, knowing where to go in the world and how best to get
there. A great example can be found in my recent case study on DOOM 2016 where the 'exposed
cover' system aims to have demons deliberately position themselves on the navmesh in an effort
to maintain the players line of sight. Not just so that they can attack you, but also
help the player make a decision on which target they're going to move towards next. DOOM much
like all idTech engine games, uses an updated version of the AAS system from Quake III Arena.
This allows for characters in the likes of both DOOM and Rage to be able to navigate
to exact locations in the game world, conducting minor linear interpolation if they're slightly
off point and animating to satisfy the discrepancy. It's what gives characters in id tech games
such wonderful fluid motion.
Meanwhile, Alien Isolation utilises the navigation mesh not just for basic movement, but for
sensory data as well as in-game behaviours. Air vents act as locations for the alien to
enable front-stage mode - where it wanders around the local area - and uses the nav mesh
for realistic navigation. The air vent is actually playing an animation of the alien
crawling out of it. Then the AI in the alien activates at the end of the animation. Conversely,
when the alien is in backstage mode it isn't crawl through vents, it simply disables its
renderer, colliders and attack behaviours and moves around the navmesh randomly in straight
lines with long stops to make you think it's doing something intelligent. So when you see
it move above or below you in the vents, it's actually just walking through you, only it's
invisible, can walk through walls and can't hurt you, which actually makes the game sound
even scarier.
The actual navigation in Alien Isolation is a modified version of the aforementioned Recast
and Detour, only it's got an extra set of sensory gauges that are tied into the navigation
system. The noise players make is passed through the navigation system to the alien such that
is can properly understand whether it would actually be able to hear the noise and pinpoint
it's location. In fact a source once told me that at one point they experimented with
having the alien be able to smell you, but it was too difficult to quantify in-game for
a player to understand it. Lastly, when the alien goes to kill you, it has to sample the
navigation mesh to ensure that the execution it's about to play fits into the space. This
ensures it doesn't try and conduct a death animation such as this one in a tight room
with no floor space.
Next let's consider some open world games. In Tom Clancy's The Division, the manner in
which non-player characters move through the environment and interact with cover is dependent
on their class and faction. With some sprinting to cover and laying low as best as possible,
while others will stay in the open to provide ample targets for players to prioritise. However,
despite this strategic play, NPCs are limited to specific regions of the map for both story
missions and in the open world. They're not permitted to run too far from their original
spawning location so as to manage the experience. Otherwise players could wind up with a conga
line of thugs chasing them from Times Square all the way down to 22nd street.
This same consideration is extended to the Far Cry franchise, with non-player characters
including wildlife only ever spawn onto a navigable surface within a range of around
250m of the player. This provides ample space within which to create interesting puzzles
for players to solve, but also manages resources such that the game isn't wasting CPU power
on processing AI that are miles away.
Lastly, Left 4 Dead breaks up the navigation mesh into chunks and constantly monitors which
regions players are standing in. This is done to allow the director AI to calculate ideal
spawning locations for mobs and special infected that are both local to the team, but outside
of your field of view. You can actually see some this happening in-game if you enable
the debug tools in an offline match.
However it's not just enemy characters that are heavily reliant on navmeshes for core
design, companions in a variety of forms also heavily utilise these tools to know where
to go and how to operate in proximity of the player. In my recent case study on Far Cry
Primal, I looked at how the companion AI utilises navmeshes to follow the player and stays within
the view frustum when on the move. However the game also needs to compensate for issues
where the player has moved into a space the animal cannot and the player is getting even
farther away. This occasionally results in the companion system looking for a valid location
on the navmesh behind the player to teleport towards.
Meanwhile a similar problem arises in Tom Clancy's Ghost Recon: Wildlands, where the
player has three AI companions that assist in combat when playing offline. To keep your
team following your lead during stealth incursions of outposts, the player drops 'breadcrumbs'
onto the navmesh for the teammates to move towards. Plus in much the same behaviour as
Far Cry Primal, in the event companions need to be close to the player but the current
circumstances do not permit it, the game will search positions off-camera for the characters
to spawn onto. This is particularly important should the player be downed and close to death
and needing that all important revival after going off and fighting an entire encampment
by themselves. Silly humans.
Plus, for companions it's sometimes vital to constrain the space within which they navigate,
BioShock Infinite adopts a principle known as the critical path, whereby companion character
Elizabeth will only move towards and engage with interactable objects that are between
the player and the next objective. Allowing for her to express herself in a variety of
ways, but in a manner that ensures players actually pay attention.
Lastly, let's talk about rebuilding navigation meshes. It's not always an easy process to
integrate into your games core design, with a great example found in Ubisoft's Rainbow
Six: Siege. In the game mode Terrorist Hunt, AI opponents need to navigate an environment
that is constantly changing thanks to Siege's procedural destruction system that allows
for surfaces to be destroyed in a variety of ways. Siege has to be ready to rebuild
the navigation mesh at any point time while maintaining performance as an online multiplayer
running at 60 fps.
As detailed in Julien L'Heuruex's 2017 Game Developer's Conference talk, Siege does not
calculate destruction changes in real-time, it pre-calculates them before they happen.
Pretty much all actions that can damage or destroy surfaces have a warm up process, be
it Sledge winding up to with his hammer, to breach charges being placed upon walls or
Hibana and Ash's projectile-based explosives. As the player starts the animation, their
instance of the game spools off a separate thread of execution that calculates how the
surface will be broken, as well as how that region of the navigation mesh will behave
after that surface is damaged, updating whether it is fully accessible or if navmesh links
have been created or destroyed. This is then synchronied into the main game thread and
pushed to server to replicate for others players at the point of destruction. This means that
as soon as the dust has cleared, there's not just a hole in the wall, but the AI now knows
if it can climb or shoot through it.
==CLOSING== In closing, navigation meshes are a critical
component of contemporary AI game development, but also one that requires diligence and attention
when crafting dynamic and ever changing environments. Figuring out how to handle and potentially
update navmeshes as critical to the design of many contemporary games, given that it
is ultimately one of the first points of failure for non-player characters that can break immersion.
If your AI can't figure out how to compensate for environmental change, then your game is
going to suffer in the long run.

The AI of Doom (2016) | AI and Games Dota 2, MOBA's and the Future of AI Research | AI and Games Tom Clancy's The Division: full Agent Origins movie - Live Action Short Film How to Survive in Gamedev for Eleven Years Without a Hit Survival of the Smartest Graphics Rewriting Your Legacy: Campaign Design in Titanfall 2 | Design Dive 2018's Best Game Engines How many AI Agents can Unity handle? LUDUM DARE 42 - Making of EVOLUTION The Director AI of Left 4 Dead | AI and Games

How Navigation Meshes Work in 3D Games | AI 101

Latest Posts