As a gameplay scripter we work a lot with AI, and so it’s important to understand the basics of how these systems are put together so we have a better understanding of how to work with them.
A little history
Historically AI navigation was handled with waypoint grids. They use a search algorithm to query the location of an AI and work out what order they need to travel between nodes to get to the desired location, resulting in a path they can follow.
This was fine for a long time, until someone came up with the concept of a navigation mesh. These have an enormous amount of advantages we'll cover briefly.
For pathfinding they actually work the same way as waypoint grids, only each point is associated with a convex polygon. An initial path is still calculated using the central points of each polygon.
The difference is that the paths then go through two phases of optimisation.
The first is a culling phase, in which the grid works out if there are any unnecessary links.
The path then runs a smoothing algorithm using the bounds of the polygons and a radius for the agent to set how extremely or subtly this path is smoothed.
This gets rid of the strange zigzagging we used to see in games - the result of sticking to the links on a waypoint grid.
Further notes
Just on their own this would be enough to use them over grids, but there are some added benefits that come with this implementation.
Path correction
AI can use the knowledge of polygon bounds to correct their paths around obstacles, as long as they can remain within the bound of the mesh.
Smarter actions
The AI can make sure that they have enough space to complete an action, such as a dodge-roll, so that they avoid doing stupid looking things like rolling into a wall, or worse - rolling off an edge.
Extensibility
Navmeshes allow for multiple agents with different navigation requirements, such as larger or smaller AI's, or AI's that have restrictions based on turning circles (things like planes, boats or vehicles), therefore allowing all of them to use one set of navigation data.
