Shortest Path vs Minimum Nodes on RecastGraph

As you can see from the attached image, this is my situation. The green path is actual returned path from A* Pathfinding, and the red path is what I preferred as shortest path. A* Pathfinding system does not return the shortest path, but rather it seems to be returning the minimum nodes path. Is this by design and correct?

If then, how can I obtain the red path from RecastGraph? Do you have any suggestion or solution? Please let me know. :slight_smile:

Hi

Yes, this is an unfortunate issue with navmesh based graphs.
What the pathfinding system calculates is the shortest path as it sees it, which is when it goes through the centers of the triangles (you can view it by enabling ‘Detailed Gizmos’ on the Seeker component). Later that path is post processed and smoothed out using the funnel algorithm, but the pathfinding system does not have access to that during pathfinding.

See also http://www.arongranberg.com/astar/docs/getstarted2.php#navmeshnotes

Normally this happens when there are many thin triangles in the scene or when relatively large triangles are adjacent to small triangles. You can see that on your road, there are a lot of pretty thin triangles.

I would suggest lowering the tile size of the recast graph to split up the thin triangles in the road.
Or if your ‘Max Edge Length’ is what is causing the triangles to be that thin, you can try increasing that a bit too.

Also. To avoid these simple cases when the target is in line of sight from the start position you can use linecasting to check if there is a direct path available.

See http://arongranberg.com/astar/docs/class_pathfinding_1_1_recast_graph.php#a09e43f342abae49a7beec8b0af71fad9

Thank you for the quick answer!
It was very helpful!

1 Like