Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.

share|improve this question
    
This turned up in the course of my morning internet wanderings: aigamedev.com/open/reviews/alienswarm-node-graph Might be worth reading :-) –  coderanger Jul 23 '10 at 17:35
add comment

3 Answers

up vote 12 down vote accepted

You may already have found this website but I have found it to be a great resource for understanding pathfinding. http://digestingduck.blogspot.com/ The author maintains Recast navigation library. Hope that you find it as useful as I have.

share|improve this answer
    
+1 for recast/detour. Don't reinvent the wheel unless you have to. –  tenpn Jul 23 '10 at 8:59
add comment

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.

share|improve this answer
    
Isn't this a waypoint graph except done on a simplifed mesh? I thought navmeshes allow you to do pathing on polygon. –  Fire Jul 23 '10 at 3:12
    
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). –  coderanger Jul 23 '10 at 3:58
    
A simple set of connections isn't a navmesh is it? I thought it was called navmesh because you do pathing on polygons. –  Fire Jul 23 '10 at 4:17
    
I don't think local versus global navigation is relevant here. –  Fire Jul 23 '10 at 4:32
1  
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. –  coderanger Jul 23 '10 at 4:52
add comment

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)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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