A* Pathfinding Project

MultiTargetPath can give different results than ABPath for same points


#1

Hi,
I’ve started using MultiTargetPath to get the shortest path from a number of different targets.
The closest endpoint was generally correct, but the path generated for it seemed odd.

I double checked by only sending a single entry in the endpoints array, and sending the same target position to a regular ABPath:

The upper image is with ABPath and the lower is with MultiTargetPath run with the same single target point.

I can avoid the funnel failure in the lower picture by tweaking the recast settings (splitting the tile edge etc to reduce uneven length connections) but I’m still concerned about why it’s taking a different route in the first place.

Is this a bug, or just something unavoidable in how the multi target works?

It seems a bit silly to use MultiTargetPath to find the nearest target, then discard the rest of the result and use ABPath to generate a more correct/reliable path to get to it.

For reference, the same disparity is seen regardless of pathsForAll state and still happens if I use it as multiple starts by sending a 1-length array for the start point instead.


#2

Found the cause: flag2 for the start/end(s) isn’t set for multitarget paths, so TriangleMeshNode.Open doesn’t know to calculate the cost to the specific point instead of just the node itself.

I didn’t think to check because I still get the same path difference if I set the start/endpoint to node center on my seeker:

Seems because start/endpoint modification happens after the path calculation, it still calculates based on the original even if it’ll snap to the node later.
(Using the position of the nearest node as the input target initially does get the expected result of both paths being identical; both using the lower route)

Using flag2 in MultiTargetPath fixes my single endpoint test case and lets it work like the initial ABPath example, but obviously gets odd results once I reintroduce all my other target points nearby.

I’ll have a play and see if I can make a GetConnectionSpecialCost or such that’ll work a bit better with MultiTargetPath than the inherited ABPath one.


#3

Hi

Yeah, this is a drawback to the MultiTargetPath. Due to the way it works it’s not possible to adjust the costs in this way. It would be possible if one introduced N virtual nodes that were hooked up to the graph for every path call (as the N end points), however currently this is not possible with the current architecture I’m afraid.

Another issue here is that paths on navmesh/recast graphs may be suboptimal in some cases. See https://arongranberg.com/astar/docs/getstarted2.html#navmeshnotes


#4

Since there’s only one startnode, (or one endnode if it’s in multi-start mode), the special cost could be applied to that node safely in all cases I think?

Sofar, a combination of calculating the special cost for the startnode plus matching vertices across tile boundaries (splitting tris so the edges line up) has helped a bunch of my test cases.

I’ve also been experimenting with using the special cost for endnodes by finding the shortest one once a target node is found and then nullifying the rest (since I only need a single short path in my case, I can use searchforall false). This fixes the case where there’s multiple endpoints on one node, but it would otherwise just exit with the first found instead of the shortest.

Another test case, no fixes or just the startpoint adjustment applied:

With both endpoint cost calcs and tri splitting:

The triangle splitting makes my mesh a bunch more complicated, but helps it get the correct next node off the heap based on the cost (Without, it can open to a neighbour node it shouldn’t do yet, so it misses testing special cost calculations for nearer nodes if using PathsForAll false)