Recast path is calculated incorrectly?

[noncom]

NOTE: the question consists of 3 posts (see the details below)

Hello! I’m facing a problem where the AI seems to miscalculate the path on a Recast graph. Here’s an example:

The AI fervently sticks to that roundabout path instead of taking the direct one. The green line is the work of Funnel.

Mislaying the path only seems to occur when the destination point is further than some certain distance. Here’s an example of me experimenting with the return path for the agent:

Paths ending on this triangle and further to the north tend to be mislayed:

— Since “new users can’t post more than 2 images in one post”, I am forced to split the post. Please read the continuation in the following post —

[noncom]

However, shorter paths, up to the “previous” triangle, and closer, tend to not have this problem:

And just in case, “Show Search Tree” shows that the “correct” triangles were considered during pathfinding, but were not taken in:

So, effectively, the chosen path is not shorter than the direct path under any terms: it is longer both in the amount of passed triangles and distance.

What is going on and how do I fix this?

— Since “new users can’t post more than 2 images in one post”, I am forced to split the post. Please read the continuation in the following post —

[noncom]

My best guess here is that that particular graph topology somehow causes Recast to fail. But I’m encountering a lot of such behavior in my application and I’m sure this can’t be right. Either I’m doing something wrong, like maybe my graph setup is incorrect, or there’s some kind of a bug. What do you think?

My A* settings look like this:

part 1

part 2

Now, since my post was broken in several, I’d just repeat the question:

What is going on and how do I fix this?

[aron_granberg]

Hi

This is unfortunately a side effect of how pathfinding is done on graphs made up of triangles.
This page has a section at the end that explains things a bit more: https://arongranberg.com/astar/docs/getstarted2.html#navmeshnotes

The RichAI movement script has an option called ‘funnel simplification’ that tries to mitigate this (and is usually quite successful).

[noncom]

Well, I think I’ve figured out what’s going on here…

The vertical edge on the graph that creates the small triangles of the “wrong” path is created by “Use Tiles” in the Recast graph options. The path layed through these small triangles is considered shorter because the A* pathfinder only considers the sum of the distances between triangle centers. It does not take the optimized path length into account, which is obviously longer in this case. It is longer because the triangles on the “right” path are thin and swap directions frequently, hence by the cold logic their centers are further away from each other than the centers of the triangles on the “wrong” path, making the whole path longer. And that also explains why only laying the path through the most southern triangles works correctly – their centers are close to each other.

The solution that worked for me was to disable the Use Tiles option because it creates the unnatural turbulence in the graph, introducing topology that was not actually there and did not reflect the real space, thus confusing the AI.

[noncom]

Thanks! I’ll take a look at this too, it would probably take care of such cases and optimize the original A* path even without the Modifiers!