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 have a lot of materials on navigation meshes, what they are, their advantages over graphs made up of waypoints, etc. However, I haven't seen much information regarding the limitations and the disadvantages of using navigation meshes, other than the obvious time they take to be created manually (which is relatively solved by Recast).

Surely this isn't a completely "magical" technique that presents itself without any drawbacks? Could someone please explain what the limitations and disadvantages of using a navigation mesh over, let's say, a graph made up of waypoints? Or point me in the right direction?

Thanks

~Ray

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Nav meshes are a qualitative improvement over waypoint graphs, in the same way that A* is a natural progression over Dijkstra's algorithm. In each case, the former has evolved due to the shortcomings of the latter, and is an entirely more useful algorithm for most applications. The shortcoming is, of course, complexity (time and/or space). But I would have to say the tradeoff is small for nav meshes vs. waypoint graphs (i.e. computational complexity may increase, but not by an order of magnitude). For the practical benefits of nav meshes over waypoint graphs, with diagrams, see this blog post. It's clear from this that the only practical benefit to using waypoint graphs is where you actually want restriction of movement to infinitesimal-width lines.

You don't mention any other common types of navigation approaches. That's because the fundamental nature of pathfinding is graph search, and for animals, at the conceptual level, are represented as a sort of graph linking the idea of one place to the idea of another through association, and so on. There do exist other approaches to eliciting AI movement, such as gradient based approaches (eg. Collaborative Diffusion). But they are not nearly as practical/meaningful to us as graphs, under most circumstances, because that is how we humans grok pathfinding. If a mole, a bat, or an amoeba became sentient/intelligent, they might find diffusion gradients more pertinent, for obvious reasons.

As time passes, improvements do come seemingly "for free" (from the individual perspective). That's why a computer you buy today for $X is many times faster than a computer you could buy ten years ago for the same price. The point is, it's not really free -- somebody, somewhere, has put R&D effort into that. Same with algorithms. And that's why older tech mostly falls by the wayside.

share|improve this answer
2  
Your answer is mostly good, but I'd really like to see a citation for "even at the animal neuron level, [pathfinding] is represented as a sort of graph linking the idea of one place to the idea of another through association, and so on." It's a very strong claim I've not heard before. –  user744 Oct 1 '11 at 18:49
    
I'd say it's straightforward to see that associative structures in thought are fundamentally representable as graphs. That those structures themselves clearly are graphs, at least in the topological sense. –  Nick Wiggill Oct 1 '11 at 19:08
1  
"Are representable" and "are represented" are not at all the same thing. The relationship between thought and neuron structure is not a direct mapping (obviously - neurons signaling red are not themselves red). Anyway, your edit is a far more straightforward claim. –  user744 Oct 1 '11 at 21:04
    
Thank you for the informative answer. I realise that all practical pathfinding examples make use of graphs and guessed that there may be a time/memory complexity issue. However, I was wondering whether there was an edge-case where you could not make use of a navmesh effectively - in hindsight, I think I may have overthought this. Asking the limitations of navigation meshes is most likely asking the limitations of a graph as a form of world representation. Just one more thing, if you could possibly link to an example of Collaborative Diffusion, I'd really appreciate it! Thanks again. –  Ray Dey Oct 1 '11 at 21:50
    
Link attached for the approach mentioned. It's quite a paradigm shift in approach to AI; probably best implemented in a new / greenfields project, unless you're willing to gut an existing one completely in this regard. –  Nick Wiggill Oct 2 '11 at 0:42

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.