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)

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.

  • \$\begingroup\$ Isn't this a waypoint graph except done on a simplifed mesh? I thought navmeshes allow you to do pathing on polygon. \$\endgroup\$ – Fire Jul 23 '10 at 3:12
  • \$\begingroup\$ The simplified graph lets you do long-distance pathing, short range is usually handled another way. It looks like Valve's system uses the mesh data for both, just in different ways (supernode routing vs. local constraints). \$\endgroup\$ – coderanger Jul 23 '10 at 3:58
  • \$\begingroup\$ A simple set of connections isn't a navmesh is it? I thought it was called navmesh because you do pathing on polygons. \$\endgroup\$ – Fire Jul 23 '10 at 4:17
  • \$\begingroup\$ I don't think local versus global navigation is relevant here. \$\endgroup\$ – Fire Jul 23 '10 at 4:32
  • 1
    \$\begingroup\$ A set of neighboring polygons is still a graph just like a set waypoints and you can do A* on it in the same way. The only difference is once you know which polygons you are going to move through you draw the lines differently. \$\endgroup\$ – coderanger Jul 23 '10 at 4:52

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.