8
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
9
\$\begingroup\$

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).

The only practical benefit to using waypoint graphs is where you indeed wish to restrict movement to exact lines rather than areas. Waypoint graphs = infinitesimal points and lines, whereas nav meshes are much the same thing just with (convex) polygonal areas attached which describe a valid space considered to be "this cell's territory ". Either way you are interpolating an AI entity's position from one node to another; the only difference with navmeshes is that you are doing it from one locus of points to another, whereas with waypoint graphs you are doing it from one point to another, and potentially giving due consideration to the edge separating nodes A and B. And of course from a complexity perspective, it's easy to see that waypoint graphs are moderately cheaper to operate.

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.

Improve this answer
\$\endgroup\$
9
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – user744 Oct 1 '11 at 18:49
  • 1
    \$\begingroup\$ "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. \$\endgroup\$ – user744 Oct 1 '11 at 21:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Ray Dey Oct 1 '11 at 21:50
  • \$\begingroup\$ -1, because you didn't really answer the question. You said navmeshes are a qualitative improvement, but the original poster wanted to know what those qualities were. \$\endgroup\$ – Kylotan Oct 2 '11 at 10:48
  • \$\begingroup\$ @Kylotan: No, in fact, the question says "I have a lot of materials on navigation meshes [and] their advantages". \$\endgroup\$ – user744 Oct 2 '11 at 11:14
0
\$\begingroup\$

Navigation meshes are restricted to surfaces, while waypoints can be placed anywhere and can do any number of connections (edges) towards any direction. Thus, waypoints can provide a more generalized and flexible solution to, for example games with abstract or extraordinary units or environments.

Improve this answer
\$\endgroup\$

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