Returned Vector Path is not the shortest


#1

The returned paths are clearly not the shortest path. There is no obstacle as the image shows. Why is the path so far off from the straight line?


#2

Hi

This is due to the pathfinding being done on node centers. The funnel modifier (which simplifies the paths) is done as a post-processing step. To plan optimal paths a more advanced algorithm is required which is called Theta*, however that is not currently implemented in this package.

If you use the RichAI movement script it has an option for to try to simplify the funnel even more which fixes a lot of these issues. You can try that out and see if it helps.

The navmesh tutorial also has a few notes about this issue: https://arongranberg.com/astar/docs/getstarted2.html#navmeshnotes


#3

Wait, shouldn’t A* find always the shortest path? As the documentation states “The ABPath findts the shortest path from A to B” and even without funnel the path is absolutely not the shortest, not even on node centers.

While 4 paths in the image look at least “close” the path which goes to the bottom and then to the left is MUCH longer than the shortest path going over the diagonal even if it goes from node center to node center? Simply because the path describes almost walking along the edges of a rect, while the diagonal is would be free?


#4

I took the liberty of drawing the node based path for what it currently returns as well as a hypothetical shorter path (in black):


I haven’t measured, but I think the black path is actually longer. Note that nodes are only connected along triangle edges.

Also. You should try increasing the tile size for your recast graph. Currently it is so small it is almost emulating a grid graph.


#5

@aron_granberg You are the man! While you are obviously right, increasing the tile size reduced our problem by so much, as obviously it was less zig-zack and more straight paths from center to center!

We really got a bit shocked on the first solution and now am much more happy with it again :slight_smile: