I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
It is same as waypoint pathfinding, only instead of way-points you have way-polygons and You can infer few things about navimesh from it:
- way-polygons are areas where entities can safely walk
- other areas should probably be not considered
- way-points need to do leap of faith into space between them; remember NPCs stucking in walls? It was at places where two waypoints were not directly connected.
- There is potentially less nodes (because polygons are biger)
- Therefore it is most likely faster
- Therefore it has potentially smaller memory requirements
- It is more realistic (because polygon's area contains in theory infinite amount of points)
- At polygons You might do some flocking behaviour to avoid collisions between NPCs
Generally they are used with some kind of enhanced A* algorithm (takes into account jump or fly links for 3D pathfinding). In that way it isn't really a different system than anything else, its more a way of generating a normal pathfinding network directly from high-poly (well, relatively speaking) environment or terrain. For whatever reason we call them beacons here, but the idea is the same, some kind of automated process runs on each map and produces a simple set of connections that can have A* run on them in a reasonable time-frames. If you tried pathfinding against the raw underlying data it would be too slow for a game because of the density of the mesh.
There are many ways you can do it. A* and such is a good option, but lacks in documentation. You could do something like place nodes quasi-randomly around the map and check which nodes can see each other and build a little web of nodes. Not the most optimal but easy to understand.