get_simple_path not returning shortest path 3D

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By gmaps

I created a navmesh with few obstacles. I bake it and see that obstacles are filtered out correctly. I run the game and order units to move to a location far away, but they don’t choose the shortest path (example on picture), but tend to go around static objects. What am I doing wrong?
There is no actual obstacle because if i order 20 short commands along the shortest route, they do it successfully.

screenshot hosted at ImgBB — ImgBB [image example]

[UPDATE] I switched to 3.2 dev branch build, and the issue persists. I found issue on github, so I hope the solution is in the current few commits.

gmaps | 2019-07-28 19:14

I have the same issue here. It happens sometimes, that to avoid a wall path is calculated to go left, but after making a step in that direction, new path says it’s better to go right, then AI moves right and get a new path saying to go left.

Both directions would be fine, but the character stucks on the wall going left and right, because it always getting longer path from get_simple_path()

Also, for me, the function sometimes returns empty array, as if there were no path available, even if it was fine last frame and is fine on the next frame.

For me this pathfinding is pretty broken right now.

Skipperro | 2019-07-31 10:51

Why are you calling the get_simple_path that often? Is the navmesh changing on the fly? If not, why not just let the character travel the path instead of calling it so often? And if there are new objects popping out, you could call it once, and if it hits an unknown object, you call it again? Just throwing some random ideas, I don’t know what your use case is :slight_smile:

I decided to ignore pathfinding issues and try to work on other parts of the game until better pathfinding support is implemented. Let’s hope that pathfinding issues will be fixed in 3.2. There are already some commits on navmesh in 3.2 but I wasn’t able to test it extensively yet.

gmaps | 2019-07-31 11:05

Yes, I’m using workaround you mentioned, like setting minimum time between path updates and fall-backing to going straight (or random) until new path is calculated in case it’s missing completely . It’s working fine most of the times, but it shouldn’t rely on some weird workarounds.

Skipperro | 2019-07-31 11:13

I’m curious, why are you updating the paths so often? For example in my game (RTS), I set the path only once, so the units avoid existing buildings and existing environment (trees, rocks, etc), until I order them to go other way, one calculation is enough (at least in my case). In case of AI I suppose that change of path would be needed only in case when their state changes or the navmesh changes.

gmaps | 2019-07-31 12:44

In my current project I’m having something like a Diablo or Magicka with constantly moving player, other enemies and also changing environment, like bridge collapsing, so AI have to go around. If I update paths less than once per 2 seconds, I start to notice, that the bad guys are not reacting to their surrounding.

Skipperro | 2019-07-31 12:52

Oh, I see. Have you tried maybe with Godot 3.2 master branch version? I believe it already has a few commits that address this issue.

gmaps | 2019-07-31 13:02

No, I’m on 3.1.1. Don’t have much time experimenting with pre-release. Will test it when it will be released.

Skipperro | 2019-07-31 13:16

:bust_in_silhouette: Reply From: gmaps

As the navmesh is not documented well enough and there are no information about how to use it or why majority of the settings don’t produce simple paths, I decided to try (almost) all combinations of parameters.

I am using a map 512*512 size, trying to create RTS and I was having issues with units not finding the shortest path in majority of the cases.

So first I tried all three partitioning algorithms.

  1. Watershed, mesh looks pretty, but units tend to walk around trees, and even with tweaking all the parameters, I was unable to make them find the shortest path. Moving on to next one Watershed

  2. Monotone, mesh has a lot of long, thin polygons. Looks weird, but most of the time the units seem to find the shortest path, but sometimes they randomly followed the long edges in opposite direction, probably trying to reach node behind them, so they could turn around which also obviously does not produce the shortest path, so I quickly moved to next one as I found no way to prevent that.
    enter image description here

  3. Layers, this one looked promising. Units didn’t try to slalom around every tree that wasn’t on their way like in watershed, but they did that ocassionally. I decided to stick with this algortithm. Although there is an issue - the engine freezes if I set cell size to too low or edge max error to too low and other parameters.

So now, I had my favorite algorithm, but I wanted the paths to be perfect. And I failed in doing so, but I got it to work decently by tweaking the parameters. In my case, i got good results with this configuration:


Final result was that units still sometimes didn’t find the shortest path, and went around trees, but they didn’t fail a lot as they did when I used other two algorithms. If someone has idea how the parameters influence pathfinding, or has some suggestions on how to improve the navmesh in this or in general case, please go ahead and post an answer :slight_smile:

I didn’t go exploring science behind it, just tried to evaluate it empirically (kinda).

And also, check this question