How A Navigation Mesh Works in 3D Games | AI 101

Key Takeaways

[Music] 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 Bic 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 in 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 the tool referred to as a navigation mesh what it is how it works and how some games utilize nav meshes to address specific issues that their Core Design creates for them a navigation mesh or nav mesh 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 a given 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 on that structure and this fractures the nav mesh into even more polygons how individual surfaces link to one another this is useful for environment artists given they will build a game world with smaller pieces rather than one big chunk of land dictating a type or region for a given 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 modeling 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 mean while 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 and readily evident 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 making characters prioritize surfaces such that their behavior is in keeping with expectations a great example of these expectations is the civilians found 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 these restrictions lastly links help us manage where and how characters can cross gaps between nav meshes sure sometimes you might want to ensure an AI can't follow you to a specific location such as the inmates and Outlast who can't follow you after you run through tight gaps however you typically want AI to move between nav mesh areas at specific points such as soldiers climbing up and down ladders in fear 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 I'll return to in a future video as mentioned earlier navigation is often the first point of failure in a game's Ai and it's readily apparent when it's not working sources close to the devel velopment of Doom 2016 revealed to me that the snap map system a pretty cool map in mode creation tool was consistently broken during development right up until launch and this was largely due to nav mesh integration issues plus bugs and behavior in a lot of open World Games such as Watch Dogs and again 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 utilized in game design let's Sid step into how nav meshes 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 1990s the actual Tech and theory behind it stems from robotics research from the 1980s 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 vorono illation 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 optimize it to become more natural one of the largest moves forward in defining navigation tools for games can be found in 1999's Quake 3 Arena which uses a navigation system called the area awareness system the AAS for short scans the game map to create convex hulls that Define walkable regions and it simulates movement such that it can identify how and if agents can move between these regions and allows for custom areas and nav mesh links to be established this principle has largely held consistent with the lakes of mik monin 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 behaviors in 3D video games means it's one of the few AI techn Technologies commonly provided in commercial game engines such as unreal and unity each engine has its own way in which it allows users to Define and customize them but the core logic is largely consistent with recast being the basis of the nav mesh 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 game play is underway even something as simple as another nonpar 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 rebaking of a navigation mesh at runtime but despite this it's still a timec consuming and relatively expensive process so let's take a look at how some games use nav meshes in cever 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 behavior in movement sometimes we can find clever ways to exploit them for the the purposes of the game's Core Design so let's take a look at some fun and often pragmatic examples of how games work with and around nav meshes in AAA Games first up let's talk combat Behavior 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 nav mesh in an effort to maintain the player's line of sight not just so 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 3 Arena this allows for characters in the likes of both doom and rage to be able to navigate to exact locations in the world often conducting minor linear interpolation if they're slightly off point and animating to satisfy those discrepancies it's what gives characters in Ed Tech games such wonderful fluid motion meanwhile alien isol another well-known game on this channel utilizes the navigation mesh not just for basic movement but for sensory data as well as in-game behaviors air vents and alien isolation act as locations for the xenomorph to enable front stage mode where it wanders around the local area trying to find you 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 and the alien activates at the end of the animation however this is all an elaborate fiction cuz when the alien is in backstage mode it isn't crawling through vents above you it simply disables its renderer colliders and attack behaviors and moves around the nav mesh 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 in 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 it can properly understand whether it would actually be able to hear the noise and pinpoint its 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 to sample the navigation mesh to ensure that the execution it's about to play fits into the physical space this ensures it doesn't try and conduct a death animation such as this one in a tight room where ultimately it would be clipping through walls next let's consider some open World Games in Tom clanes 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 prioritize however despite the 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 creating a conga line of thugs chasing them from Time 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 spawning onto a navigable surface within a range of around 250 M 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 for 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 such that they're both local to the team but outside of your field of view you can actually see some of this happening in game if you enable the debug Tools in an offline match however it's not just enemy characters that are heavily relying on nav meshes for Core Design companions in a variety of forms also heavily utilize these tools to know where to go and how to operate in proximity of the player in my most recent case study on Far Cry Primal I looked at how the companion AI utilizes nav meshes to follow the player and stays within the view frust them 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 nav mesh behind the player to teleport toward WS meanwhile a similar problem arises in Tom Clan's Ghost Recon wildlands where the player has three AI companions that assist them in combat when playing offline to keep your team follow your lead during stealth incursions of outposts the player character drops breadcrumbs onto the nav mesh for the teammates to move towards Plus in much the same behavior as Far Cry Primal in the event companions need to be close to the player but the current circumstances don't 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 thems 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 an engage with interactable objects that are between the player and the next objective provided they fit on the critical path this allows 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 game's core design with a great example found in ubisoft's Rainbow 6 Siege in the game mode terrorist hunt AI opponents need to navigate an environment that's constantly changing thanks to Si'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 in time while maintaining performance as an online multiplayer running at 60 frames per second as detailed in Julian laru 2017 GDC talk Siege doesn't calculate destruction changes in real time it actually pre-calculates them before they happen pretty much all actions that do damage or destroy surfaces have a warm-up process be it Sledge winding up his hammer to breach charges being placed upon walls or hiana 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's fully accessible or if nav mesh links have been created or destroyed this is then synchronized into the main game thread and pushed a server to replicate for others at the point of Destruction this means that as soon as the dust is cleared there's not just a hole in the wall but the AI now knows whether it can climb or shoot through it in closing navigation meses are a powerful tool tool that enables designers and developers to breathe life into AI characters but they also require diligence and attention when crafting Dynamic and Ever Changing environments figuring out how to handle and potentially update nav meshes is critical to the design of many contemporary games given that it is ultimately one of the first points of failure for non-player characters and breaks the immersion if your AI can't even figure out how to walk in a straight line your game's probably going to suffer in the long run hey everyone Thanks for watch watching the first in this new series of AI 101 and I hope you've all found it interesting if you're interested in learning more about navigation meshes in general and how to make them yourself I've linked to articles and tutorials of All Sorts down in the video description and you should go and check that out special thanks to all the good folk who support the show on patreon including Michael Russell right there I mean everyone's just amazing but Michael he gets a special shout out for today be sure to log in to patreon as I'm running a set of polls right now for what AI 101 topics my viewers want to see in the future so please get in there give me some feedback let me know what your thoughts are and that'd be awesome cuz that'll really help guide this series in the future all right that's it for now I'll see youall next time