Navigation: agents sometimes take indirect routes

[tcoxon]

Terrain3D version

0.9

Godot version

4.1.3.stable.official

System information

Godot v4.1.3.stable - Arch Linux #1 SMP PREEMPT_DYNAMIC Tue, 10 Oct 2023 21:10:21 +0000 - X11 - Vulkan (Forward+) - dedicated NVIDIA GeForce GTX 970 (nvidia; 535.113.01) - AMD Ryzen 5 2600 Six-Core Processor (12 Threads)

Is the issue reproducable in the demo?

Yes

Issue description

Originally noted by @TokisanGames on #253. See also: godotengine/godot#85548

Agents sometimes take indirect routes to their targets. See the video below, where an agent could walk directly to the player, but instead walks to a point near the edge of the navmesh and then back:

navRecording.2023-12-01.173953.mp4

This bug is not limited to Terrain3D: it can be reproduced without Terrain3D at all. However it may be worth considering what we can do to help users with this, in the form of documentation, or a built-in workaround.

Cause

When certain navmeshes enter the navigation map (which is usually when a new scene is entered that contains a NavigationRegion3D), an error is logged:

E 0:00:01:0091   sync: Navigation map synchronization error. Attempted to merge a navigation mesh polygon edge with another already-merged edge. This is usually caused by crossing edges, overlapping polygons, or a mismatch of the NavigationMesh / NavigationPolygon baked 'cell_size' and navigation map 'cell_size'.
  <C++ Source>   modules/navigation/nav_map.cpp:856 @ sync()

This is logged when the navmesh contains vertices closer than the resolution of the navigation map allows. This can cause pathfinding to take strange routes (see smix8's comment on the godot issue).

These vertices are created by the navmesh baking in-engine, not by Terrain3D. The source geometry created by Terrain3D is much more spaced out:

User Workarounds

In the Godot issue, as well as proposing a change to the engine to mitigate the issue, smix8 lists a potential workaround users can try. Users can adjust the sample_distance and sample_max_error (properties on the NavigationMesh resource) until the error message goes away.

Increasing sample_max_error will cause the navigation mesh to adhere less closely to the actual terrain, which may mean that users have to adjust their navigation agent behavior scripts to compensate for it. The same may be true of sample_distance - I'm not sure yet.

Solutions we can build into Terrain3D

Smix8 also describes simplifying the source geometry before baking to avoid creating jagged edges around the sides of curved source geometry. Note that jagged edges are created by the slope of terrain, not just by the edges of areas painted navigable. IMHO it would be very difficult to engineer a fix this way that rules out the error in all cases.

Also note that the LOD levels we have are not the right tool for this. For one thing, if you decrease the LOD but increase the steepness of the terrain then you're back where you started, with jagged source geometry again. There is no LOD level that will fix the error for all terrains. Another issue with decreasing LOD is that it discards detail. Detail can be what makes the difference between navigable/traversable terrain and not. The simplification we're describing would have to reduce edges of navigable terrain to simpler shapes without making anything that shouldn't be navigable navigable.

Something else we could consider is post-processing the navmesh after is has been baked, to merge vertices that are too close. If I've understood everything correctly, then that would allow us to guarantee error-free navmeshes.

Logs

E 0:00:01:0091   sync: Navigation map synchronization error. Attempted to merge a navigation mesh polygon edge with another already-merged edge. This is usually caused by crossing edges, overlapping polygons, or a mismatch of the NavigationMesh / NavigationPolygon baked 'cell_size' and navigation map 'cell_size'.
  <C++ Source>   modules/navigation/nav_map.cpp:856 @ sync()

[TokisanGames]

I situation where a broken navmesh generates. After painting out the whole demo, I found the enemy wouldn't traverse a certain section. I had previously built out a full nav mesh in the demo that was fine, so length wasn't an issue.

broken-navRecording.2023-12-05.161150.mp4

[tcoxon]

That probably has the same cause. Do you have the terrain storage resource that does this? It would make a useful test for my fix.

[TokisanGames]

Here is the terrain storage and nav mesh. The red dots after the first turn on the path indicate about where the issue is. Link expires in a week.
https://we.tl/t-4Em2TSqE9C

I reshaped the navigation area there and it was fine on regeneration. However I found a second area in the middle that had a similar problem. It was in this area.

Then I also found this on the left approach to the mountain.

[tcoxon]

Checked with my WIP and it fixes the bit near the red dots, and the circled yellow area. The error is still printed however - there's another case where recast and the navigation map are speaking a different language (reported on the Godot issue).

I think the hole in the navmesh there may actually be a shader issue. If I replace the line in the shader where index00UV is defined with this:

ivec3 index00UV = get_region_uv(texel_pos_floor);

it becomes apparent that the navigable bits are disabled in that hole:

[TokisanGames]

Ok, I see on the hole.Yes the navigation shader display just looks at one vertex, whereas the true way to do it is sample 4 and bilinear interpolate among them. So there was one or two vertices not painted.

[TokisanGames]

Fixed by #266.