I've done some reading on nav-meshes, and I understand how to generate a path of polygons to reach a goal. However, what I don't understand is how you determine the bearing to follow within each polygon. Without a central node to aim for, what do you aim for? I suppose you could cast a ray to the goal and then head to the point where that ray crosses into the next cell - but that would only work if that next cell is actually on your path. If your ray doesn't cross the edge into the next cell, do you instead plot a path to whichever corner of the edge is closest to the goal? I think that would get you the path shown in the 3rd diagram, but would it work in all cases?

Navigation mesh example from UDN



You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal, the next-to last is moved to minimize the distance to the last waypoint, and so on...

Finding the point with the minimal distance is equivalent to projecting a point (the goal/next waypoint) onto a line segment (edge). Stack Overflow has a few answers on this, Shortest distance between a point and a line segment for example.

Note: this assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

| improve this answer | |
  • \$\begingroup\$ "moving the waypoints along their corresponding edges to minimize the distance to the previous waypoint going backwards from the goal" - that sounds like it, I'd love more detail on how you do that. \$\endgroup\$ – Iain May 16 '12 at 9:37
  • \$\begingroup\$ Well, I'll try and explain the math, it's not really that difficult. Also, I just noticed I've been ambigous in the quoted sentence... editing that to. \$\endgroup\$ – Anton May 16 '12 at 9:39
  • \$\begingroup\$ Or, instead of failing to formulate a readable explanation, I just link to existing answers, that works to :) \$\endgroup\$ – Anton May 16 '12 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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