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?
1 Answer
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).
-
\$\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\$– IainCommented May 16, 2012 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\$– AntonCommented May 16, 2012 at 9:39
-
\$\begingroup\$ Or, instead of failing to formulate a readable explanation, I just link to existing answers, that works to :) \$\endgroup\$– AntonCommented May 16, 2012 at 9:53