Nav Mesh

Navigation is important when developing video games because it creates an immersive and fun experience and Non-playable Characters (NPCs) play a huge roll in this. With navigation, it allows for NPCs to be able to "sense" the location around them, and react according to the situation. This allows for less scripting when trying to create AI and also create a more dynamic AI because instead of following a script on how the NPC should move, it reacts to the world itself.

The most basic use of an NPC command, is to go from point A to point B. The  steps used for this are:

1. NPCs figure out their location relative to the world
2. Get the coordinates of the point the NPC will travel to
3. Find a path to the destination
4. Scan for any objects that will be in the way of the NPC

Other uses for AI/NPC navigation is target scanning, monitor threat perception, determine spawn locations, and the ability to reuse levels.

Insomniac games uses navigation by:

1. Game AI: set up NPC's navigation requirements (e.g. Go-To Command)
2. Navigation: Path-Finding & smoothing
3. Steering: Locate Obstacles in the path and avoid them
4. Game AI: Transform steering output to animation-input
5. Final Position & Orientation of NPC

Nav meshes are used as a layout of the level, that are used for AI navigation. These Nav meshes are divided into sections where the AI navigates through them to go to their end point. These sections also have properties such as elevation or areas where the AI will not go such as certain building roofs where the enemies can climb or jump to, or areas such as lava or water where the enemies will avoid.
To move around these sections in Resistance 2, A* is almost always used because hardly 10% of the nav SPU budget was used for it even with their coop mode with a maximum number of 100 NPCs using navigation on screen.

The AI steering in R2 was light weight or simple and barely satisfied the needs of the programmers/designers. The main issue Insomniac focused on was the issue where when animation around corners did not slow down enough and  a NPC had to not only get to the first bend point but also orientate towards the bend point along the path. What they used to fix this problem was using a bezier curve approach for the bend points. The used of bezier curves ensured that the NPCs will stay on the nav-mesh.

There are many areas of a level where a nav mesh alone will not be enough for navigation. Objects such as ladders, tunnels or actions such as teleporting or jumping will not work with the current nav mesh, because these are considered non mesh links. To fix this problem, Insomniac uses a custom clue boxes which help connect that specific point to the actual mesh itself.

This picture shows that there is a custom link where the AI is suppose to jump, so a custom clue is added at the bottom of the jump, and at the top of the jump. This lets the NPC jump up onto the high level mesh or jump down to the lower level mesh. Although this does have a problem where multiple NPCs will be using this custom link. Instead of creating multiple custom links around the edges, there are other alternatives such as finding a different path. 

This picture shows there is a hybrid climbing through the window, which is the most effective path to get to the 2nd floor, but since its occupied, another path opens up allowing for the 2nd hybrid to use this path (the door way) to get to the 2nd floor. Not only does is this efficient in terms of having multiple enemies able to navigate at once, it creates dynamic gameplay where there are enemies coming form multiple different paths. 

To create a nav mesh there are a few steps:

1. Voxelize the scene geometry
2. Build navigable voxels
3. Clear Voxels NPC height above and below custom-override-polys
4. Render custom-override-polys into the best filtered voxel grid
5. Build watershed partitioning
6. Trace catchment basin's contours with filtering
7. Triangulate/tesselate to generate the nav mesh

Custom-override-polys are meshes created by the designers to fix areas of the original mesh that are disconnected or unwanted areas of the mesh. They basically override what the original mesh was in the unwanted area, and replaces it with the custom mesh to create a final desirable mesh that can be used for the game.

Nav meshes are really helpful when the developers want dynamic AI for their NPCs. It lets the NPCs use the level fully and create a more dynamic gameplay for the players. Nav meshes remove the need to use boring linear pathing since it allows the NPC do what they want, depending on the situation. It is always changing and different so the player cannot predict easily what the enemy's behaviour will be.