dtNavMeshQuery::findPath might not always generate the shortest path about recastnavigation HOT 13 OPEN

Since endRef is the reference to the polygon that contains endPos, it is guaranteed that any path to endPos ends with this polygon. However, due to the the A* search operating on points, the actual path might not be the optimal one (since the polygons have to be represented by points); this is a really tough problem to solve. Typically an acceptable tradeoff is raycasting a few refs ahead and skipping polygons whenever possible.
Here is more information on it from Mikko's blog.

from recastnavigation.

I don't think it's difficult to solve in the findPath function. I can share my changes if you're interested.

from recastnavigation.

Yeah sure, I would love to see that.

from recastnavigation.

https://github.com/jswigart/recastnavigation/blob/0e243ea95c16bc779ae197c33efaec20ad75b134/Detour/Source/DetourNavMeshQuery.cpp

Specifically dtNavMeshQuery::findMultiPath

I haven't changed dtNavMeshQuery::findPath yet.

The key is that once you've reached the goal poly, the search needs to expand with 1 more 'goal' node, that once chosen as the cheapest from the open list, is truely the best path. That gives further iterations of the search the opportunity for a potential cheaper path into the target goal area to be considered.

from recastnavigation.

the search needs to expand with 1 more 'goal' node, that once chosen as the cheapest from the open list, is truely the best path.

But how do you find this information? If you have this information, you can simply do the path find to that node instead. A property of an optimal path is that it contains optimal paths to all nodes on that path (i.e. if A -> B -> C -> D is an optimal path to D, then A -> B -> C is an optimal path to C). If you know C is contained in the optimal path to D, you can split the path find. If my understanding is correct, this is what you are doing, but I don't see how you can know that C is contained in the final optimal path. Is this simply done by doing simultaneous path finds to the goal poly and all its neighbors? What about neighbors-of-neighbors?

If that is the case, I think this is similar to the improvement axelrodR made in this PR: #17
Except the any angle method works for all polygons during the search, and not just the neighbors to the end poly.
It basically changed the path find to approximate nav mesh polygons with different points depending on what angle the search is approaching from. However, the improvement is only available for the sliced findPath variant, it looks like.
Have you tried this?

from recastnavigation.

When the popped open node matches the goal polyref, that means you've reached the goal area, but the actual goal position is somewhere inside that area, and there is no guarantee that the first node you popped into that area is the shortest path once the distance to the position is taken into account.

My findMultipath is bloated a bit because it searches to multiple goals. I'll move that functionality to findPath as well and it should be clearer.

Basically that 1 additional goal node is flagged with the new node flag of DT_NODE_GOAL that you can see in the code there. Rather than simply comparing for a matching polyref.

It changes the search completion criteria from

if (bestNode->id == endRef)

to

if ( bestRef == endRef )
{
if ( bestNode->flags&DT_NODE_GOAL )
{
found goal
}
else
{
we've reached the destination area, check to see if this path to the goal(if that goal node is already in the list), is shorter
dtNode* goalNode = m_nodePool->getNode( bestRef, DT_NODE_GOAL );
// may or may not be allocated yet, but the costs are compared like any other to see if this is a better path
}
}

The key functionality that is being added with this additional node of exploration is that the distance from the entry point into that poly area to the actual target goal position becomes part of the overall path cost, so the path quality doesnt suffer from not taking that into account.

from recastnavigation.

That other fix sounds like it addresses an issue across tile boundaries, which is definitely a nice fix, but doesn't appear to be redundant with this one from what I can see so far.

from recastnavigation.

I think I understand what you mean now. Any time the end polygon becomes the best node in the open list, the search terminates immediately, seemingly without looking at where the end point is. So the question is whether there could be a better path that approached from a different bordering polygon?
I don't think there can be; the end poly is already special cased when it is pushed onto the open list, and here the end point is taken into account. So the A* search really has no better paths when that becomes the lowest cost node on the open list. It's still possible that the final string pulled path will not be optimal, because of the reasons I've talked about earlier.
Is this a correct understanding of the problem? Or am I wrong yet again? 😝

Also I will admit I didn't have a good enough understanding of the PR I linked; I thought it was for every polygon, but as you said, it appears that it was only border polygons that had that issue.

from recastnavigation.

Oh I remember, the way this solution re-uses and modifies the same node with the cost is not compatible with the findMultiPath, which is where I initially implemented it. In that function it is a single query that is more of a dikistra search to find multiple goals. You can't jack with the cost of that search node to account for the destination when that node through that area may be part of the path to a different goal, and tinkering with the cost will adversely effect that. In fact I need to physically remove that special case cost modification in my multipath function.

Or put more simply. You're right that the special case handling of the cost is probably just fine for the single search in the normal ::findPath, but it's not the way to implement that functionality from the perspective of a multi goal search. For consistency sake I'm probably going to change even my findPath to use the same method, because it's conceivable that the special case shortcut can even be wrong in some fringe circumstances(like intra area teleportation links)

You're also right about non optimal paths in other situations. One of the issues with navmeshes is that they have an inherent source of error in producing optimal paths that are in part an effect of the cost estimations inherent to whatever they use during the A*, whether that be the centers of edges between areas, etc. Some implementations have mechanisms to reduce this by expanding multiple nodes along long ledges, but that of course comes at a cost.

Here's an example of how this error can crop up. Most often in my experience with small areas next to large areas. Note that the size of the detour to go through the center of the long edge ends up bloating the cost estimate to go that way, so the blue path that makes less sense may be chosen.

This effect is reduced to some extent with using tile based navmesh reasonable tile limits, because it will put a ceiling on the length of edges between areas. In large environments with non tile based navmesh, it is generally much worse.

from recastnavigation.

@jswigart thanks for sharing this! I need to implement something like to your findMultiPath(). Did you make any progress on it? The latest version on your fork seems to be still very much work in progress.

from recastnavigation.

I'll check tonight to see if the latest is pushed up to my branch.

from recastnavigation.

The latest is in my fork is up to date, note that my findMultiPath function doesn't actually return the paths right now. I use it to generate paths to a bunch of different destinations and then use the path cost to weigh the desirability of pursuing different goals. It wouldn't be hard to extend it to return the paths to all destinations. I just haven't needed that yet.

from recastnavigation.

Sorry for late reply. Thanks!

from recastnavigation.