NavigationAgent3D.get_next_location() returns invalid positions around merged NavigationRegion3D

[smix8]

Godot version:
Godot 4.x
commit 4a1f2dc

OS/device including version:
Win 10 64x

Issue description:
NavigationAgent3D.get_next_location() returns many invalid positions around areas that are in close proximity to two merged NavigationRegion3D.

• positions that are not on any designer baked navmesh (collision agents can get stuck easily).
• positions that are floating in air without any (bake) geometry or collision below (physics agents can fall through world).
• positions that confuse NavigationServer on repeated pathfinding requests (agents stuck with pingpong back and forth).

It seems the NavigationServer3D is merging NavigationRegion3D edges to aggressive without any real care for actual source geometry or scene collision from baked navmesh. Lowering the NavigationServer3D.edge_connection_margin to 0.5-1.0 only hides the problem that the merged navmesh behind the scene, while maybe technically correct, is hot garbage for gameplay purposes.

For collision and physics agents this is basically broken gameplay navigation in Godot 4.x as soon as two NavigationRegion3D are merged.

Magenta Capsule = Agent
Cyan Cylinder = NavigationAgent3D.get_next_location()
Yellow Circle = mouse clicked movement target

Left playeragent receives get_next_location() vectors that are in the air around the bridges where the NavigationRegion3D from the topleft block connects. Right patrolagent does not have the same issues as it stays on same NavgiationRegion3D at all time with valid positions.

Top playeragent not only floats in the air but also gets pingpong stuck due to repeated pathfinding requests and a very confused NavigationServer3D.

Lowering NavigationServer3D merge margin to < 1.0 solves most issues (default is 5.0 and way to high for practical use) but what would be the point of a new navigation feature that only "works" while basically disabled?

Steps to reproduce:
Create two NavigationRegion3D islands connected by narrow navmesh paths (e.g. 1 meter) so they are merged by the NavigationServer3D. NavigationAgent3D.get_next_location() returns invalid positions close to the merged NavigationRegion3D areas that shouldn't exist and can get agent lost/stuck.

Minimal reproduction project:

NavigationAgent3DIssue.zip

[AndreaCatania]

Lowering NavigationServer3D merge margin to < 1.0 solves most issues (default is 5.0 and way to high for practical use) but what would be the point of a new navigation feature that only "works" while basically disabled?

I think the issue is that with #47024, 5 units (meters) are too high. Before the edge search was much more strict on the edge shape, and even a relaxed number like 5 was just fine. I think we can lower it now, so to have a much correct scale.

When you lower that parameter, do you see any other issues?
What's the value are you using?

I guess the correct value should be around few centimeters.
Side note: it's better to not overlap the navigation regions.

[smix8]

When you lower that parameter, do you see any other issues?

Yes, if edge_merge_margin is very low it only merges navmeshes that are horizontal and on the same y-axis.
It creates a lot of issues with angled or verticality navmeshes (as if they only use 1/10 of the merge margin).
Maybe the merge margin can be split in a horizontal and vertical value to compensate for this?

What's the value are you using?

I am using the recommended realistic scale in my games so 1 unit = 1 meter. If I remember correctly in the linked demo and animated gifs the edge_connection_margin was set to 1.5.

Now I am testing with edge_connection_margin 0.5 cause it has less issues with pathfinding but getting navmeshes to merge that are not exactly on the same y-axis value is very difficult with such a low value. I am especially frustrated with simple ramps on different navmesh regions as it is pixelhunting to get them merged properly (or get the mentioned pathfinding bugs).

The debug navmesh also does not display the merged navmesh correctly so it requires tedious runtime testing for even small changes.

Side note: it's better to not overlap the navigation regions.

I know that it works better without overlap but I don't think it should be part of a solution to avoid vertical overlap with navmeshes.

The reason for this is that Godot navmesh bake enforces a geometry setup that produces overlap all the time and we currently can't make custom changes to the generated navmesh (e.g. by dragging an edge up/down). Also it works against what most level designers would do in level building. As a level designer you never want to leave geometry gaps for the navmesh and pray to the algorithm goddess where you can't even see the result in the editor.

[AndreaCatania]

The edge merging is not meant to merge really different and faraway edges. Rather the idea was to allow the user setup well defines edges, where the merge will be performed. For all the other cases, the idea is that the user has to use the bake function that allow to rebake the nav-mesh at runtime.

The reason why it's not a good idea allow the overlap merge for such different polygons, is that the edge merge would became equally complex to the baking.

The idea is that you have to cut the map along the same region. So the edges of the two navmesh are basically the same. If you cant do that, a re-bake is needed.

[smix8]

The edge merging is not meant to merge really different and faraway edges.

I didn't expect to merge faraway edges beyond the merge margin but I expected to merge any edges within the merge margin in all axis.

Rather the idea was to allow the user setup well defines edges, where the merge will be performed.

I can't align the baked navmesh edges so perfect on not straight or slightly rotated geometry that it would work with the current limitations.

In another example I created two "bridges" with the excact same mesh placed at the exact same height. Both overlap the same second navmesh at an equal horizontal angle. One bridge gets merged while the other bridge gets ignored. If I move the bridge on the same edge plane a few units into one direction it gets merged. As a level designer I have zero idea/control/feedback when and why the second bridge gets merged or ignored. It is all trial and error that you can do in the editor but good luck at runtime.

the idea is that the user has to use the bake function that allow to rebake the nav-mesh at runtime.

It is unpredictable for merging how the bake function creates a navmesh edge at runtime.

I created a platform like in your demo but slightly rotated. It creates 5 complelty different version when the (re)bake is hit at runtime everytime the geometry mesh has a slightly different global transform position. If the platform is a straight box like in your demo without any rotation it works but it can't be the expectation to limit all gametypes to minecraft boxlevels.

My problem is the lack of control what edges are merged, it is not predictable and we have zero (visual)feedback except for our stuck agents at runtime to work with and around the limitations in an efficient way.

[AndreaCatania]

I agree, right now there is no gizmo that tell you what's going on. A gizmo that show if the connection is enstsablished would improve it a lot. The 2D editor has that gizmo.

However, would be interesting to see a gif / video / image, for these new edges you are trying to merge: so to have a better understanding for the use case.

[smix8]

Here is an overlayed screenshot of a test map with edge_connection_margin 0.5 and realistic 1unit=1m scale.

All "bridges" are the excact same mesh block only the horizontal/y-axis rotation is different. I left vertical rotation out of this example cause it only makes the problem worse and breaks every bridge.

The different colored island meshes are the 3 different NavigationRegion3D.

Notice how the more complex megabridge made out of two bridges on the right gets merged to a proper pathfinding mesh without any issues while the more simple bridges to the left and center are made non-traversable for agents.

What happens if we force an agent on one of the red bridges and click on the bridge end is that as soon as they are on top the other NavigationRegion3D they take a gigantic detour back around the entire map to reach the target. This tells me that around this bridge locations the NavigationRegion3D are not merged at all for unknown reasons.

[AndreaCatania]

Thanks for this screenshot, as shown here #47816 (comment) the idea is that the merged edges must be parallel and the more similar possible.
To achieve that in your scene, the best you can do is to cut the bridges in half, and assign each half bridge to its master platform. In this way the generated nav mesh of each platform also have the bridge, that can now be connected to its half.

[smix8]

I accept that this is intentional and navmeshes need to be aligned more careful so I close this issue.

That said the problems around this could be somehow mitigated with better debug visualization to see merge connections between different navigationregions in both editor as well as at runtime. See proposal: godotengine/godot-proposals#4507