Navigation recomputes incorrect longer path to unreachable target

[razcore-rad]

Godot version

v4.1.rc2.official.46424488e

System information

Ubuntu 23.04, Vulkan, NVIDIA GeForce RTX™ 2060 / NVIDIA GeForce RTX™ 2060, NVIDIA Driver Version: 525.105.17, NVML Version: 12.525.105.17

Issue description

Navigation server should compute (and recompute) the shortest path to the target. In this example I have two unlinked nav meshes and we want to showcase the edge connection feature in v4.1 with this moving platform. When the connection gets broken and the agent needs to recompute the path it goes to the side instead of remaining stationary.

Expected result is like in the first part of the demo where the agent moves to the edge of the nav mesh then waits for the platform.

2023-07-02_13-26-16.mp4

Steps to reproduce

Run the demo and notice that when the agent has to recompute the path because the link is broken due to the moving platform it computes a path to the side which is not what's expected. The expected behavior is to find the point closest to the target position (on the other island) which in this case should be the middle of the platform where the moving platform connects.

This looks like a bug to me.

Minimal reproduction project

godot-4-dbg.zip

[smix8]

When the bug happens the pathfinding only really has two navigation polygons available for the path search but it does not know that in advance. The one starting polygon that the agent is already standing on and the neighbor polygon that is "behind" it (not really).

The path search starts at the position of the agent and goes to the closest edge position of the neighbor polygon building this as the first "searched" path segment. You can switch the path postprocessing from corridorfunnel to edgecentered to better see what is going on. The path search now realizes that it is stuck as there is no virtual connection (navigation link) that allows the pathfinding to know it could go to the "waiting" position to reach the other side. It has run out of new polygons to search.

The fallback in those situations is to return a path to the closest position possible by distance but only inside the fully searched path polygon corridor. The first, starting polygon is not a fully searched polygon because two edges are not connected with anything, it only is the segment from start position to the only available connected edge. Therefor the start position is further away than the corner of the second polygon. As a result the pathfinding thinks the corner position is closer and snaps to it.

This not searching the start polygon fully considering all the unconnected edges in cases there is no path possible is the actual "bug" ... well ... more unhandled situation because normally you wouldn't search any unconnected edges. That could may be solved by doing additional polygon face searches in the starting polygon in those cases.

While not directly the cause of the issue you need a virtual connection for such a "platform" setup. Due to the lack of virtual connections (navigation links) and the constant severed navigation mesh edge connections and updates (AnimationPlayer moving a NavigationMesh) the agent is searching new paths every single frame. This will give you problems with anything more complex and should not be teached to users like this (I assume you are building a demo for gdquest).

Also regarding the other linked issue in the documentation, when I say navigation links do not work without a script handling it I mean it. Without a navigation link you get sometimes those path corridors depending on polygon layout that are not really usable or cause weird agent behavior from all the navigation map resets. With a navigation link alone without script the agent will just travel through thin air to the other side because it does not understand there is a platform. If a path update is triggered right while an agent is standing on such an unhandled (edge) connection it has a chance to dangle randomly or get stuck between conflicting directions changing every few frames because there is no real navigation mesh below it. In the demo project the RemoteTransforms and physics Area node freeze the agents so they hide / prevent most problems.

[smix8]

If you can please test the linked pr to see if it fixes that issue.

[razcore-rad]

I had time to check the PR (mono artifact) with the platforms demo project and it seems that the issue is fixed. Thanks for the detailed explanation here & on Rocket.Chat as well, I understand the system somewhat now.

So like I mentioned, the moving platform demo is fixed by this PR, but I think the system still has some bugs in the way it handles going to the closest point to the target position that is outside the navigation map.

I merged together the moving platform demo with the islands demo from the docs repo (godotengine/godot-docs#7598) and updated it a bit. Please check res://islands/islands.tscn and see that when the navigation links are disabled and the agent is inside the navigation region to the left, giving it an unreachable target to the right of the screen doesn't compute a closest-to-unreachable-target path. I'm using the white rectangle as an indicator for the given target position.

As you can see in the images above, most of the target positions to the right of NavigationRegion2D1 do not produce any paths.

Giving it a target position other than the right side does produce correct paths:

I'm not sure if this is the same issue so let me know if I should open a separate issue for this case.

Here's the project tried with your PR (Godot Engine v4.1.rc.mono.custom_build.c105e1c2f):

godot-4-dbg.zip

[smix8]

Well in that case the issue is that the left polygon is a single convex polygon disconnected from everything with also not a single internal polygon connection.

Since the pathfinding loops through the established connections it faces a situation with an empty loop because the polygon has no connections at all. The fallback for this situation is returning an empty path.

You can try this by changing the left polygon to a concave layout so that it is forced to rebuild with 2+ convex polygons like the right polygon is. This alone is enough to not show the issue because it now has at least a single self-connection between the two polygon edges so the full loop can run.

[smix8]

@razcore-rad I updated the linked pr with another fix for this new issue. If you find time please test again.

[razcore-rad]

I tested a few scenarios that I could think of with Godot Engine v4.2.dev.mono.custom_build.28e251c5c and it seems like everything works as expected. For now I don't have anything else to report, thanks @smix8!