Artificial Intelligence for Games 101 – Navigation Meshes

Previous Post: Introduction to Artificial Intelligence

For this, I will explain using Unreal Engine as my examples, though this works similarly for other Engines like Unity.

An AI Mesh is a type of Data Structure that shows the AI where it is allowed to move. In UE4 this can be placed in using the NavMesh Volume class, which can then be seen as a green layer by pressing P. This can be used in conjunction with either of two pre-built navigation functions called “Get Random Reachable Point in Radius” or “Get Random Point in Navigable Radius” – with the latter being faster but often causing bugs like the character crashing into walls. Here is an example I used in one of my previous projects:

Navigational Meshes work by breaking down geometry into different regions, breaking down into even smaller surfaces when it is close to a blockage. This can also be done to show different regions that can be used to make a game more realistic and immersive, such as the Civilians in GTA walking along paths as opposed to walking into the middle of the road all the time. It is also what allows the cars to move on the road instead of crashing into civilians on the pavement all the time. Although for a game like that to keep its “realism”, it is fine to have a couple of civilians every now and then deciding to walk along the road. Breaking down the geometry into different sections allows the AI to create a Search algorithm, giving each section a number and the higher the number is, the better route it would be. As this is done within microseconds, AI seems to just walk around normally even though it has to calculate every minor detail. This is why games like GTA can be so expensive / Demanding to run. This is what Nav Meshes look like in Unreal:

In UE4, Nav Meshes appear to be a big box, with anything inside it being a new Navigable Area. If you use this but you can’t see it, you just need to press ‘P’ and it will show as Green for any walkable area.

What to Read Next

AI Algorithms: Dijkstra and A*
AI Algorithms: Flow Fields
Finite State machines