[4.5.beta1] Navigation agent looking for longer paths

[Resident05]

Tested versions

• Not reproducible in: 4.1.4.stable.

System information

Godot v4.5.beta1 - Windows 11 (build 26100) - Multi-window, 1 monitor - Vulkan (Forward+) - integrated AMD Radeon(TM) Vega 8 Graphics (Advanced Micro Devices, Inc.; 27.20.1028.1) - AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx (8 threads) - 9.87 GiB memory

Issue description

I'm that guy again from 4.1 that recently moved to 4.5, I'm enjoying it! But found another bug that I gotta report.

For some reason I'm getting paths that look like this:

If I move the target position a bit to the left it looks like this:

In 4.1 it would never take that link to the top as it would always be the longer path, I haven't followed navigation changes between the versions but I'm pretty sure this is a bug.

In the MRP the mouse position is the agent's target position and you can change the parent node's position to test other paths.

Steps to reproduce

• Make a scene with some navigation regions and links of different shapes.
• Add a navigation agent and test what path it takes.

Minimal reproduction project (MRP)

pathfinding-test.zip

[Calinou]

Can you test intermediate versions between 4.1 and 4.5? You can download them here: https://godotengine.org/download/archive/

I suggest trying 4.2, 4.3, 4.4, then trying pre-releases to narrow down which version started the regression exactly.

[smix8]

Not a bug just a limitation how astar explores polygons. That it is different to Godot 4.1 is likely just due to processing order.

In Godot 4.1-4.3 everything runs single-threaded so you often get the same array order of the internal polygons and that is also how the astar pathfinding picks things first to explore.

In Godot 4.5 the region and map updates run by default async on threads so the order in which things update and are placed in the internal arrays is completely different every time due to the async threads.

You can try disabling the async region and map updates in the navigation projectsettings to get back to single-threaded.

In general having navmesh and navlink layouts that break the moment polygon or update order changes is super brittle. Such a layout should be changed by changing polygons or navink positions because it is a big bug surface no matter what Godot version you use.

[Resident05]

I tested the threaded options on my actual project but it doesn't seem change the way my characters interact with pathfinding in 4.5, for some reason they just ignore some navigation links, I think my actual issue is that I don't know what is causing that behavior.
This being how astar works seems to be true and I mistook that with this other issue.
Are there any changes that affect navigation link interactions between 4.1 and 4.5? I have no issues with agents ignoring links in 4.1 compared to 4.5.

[smix8]

Up to Godot 4.3 it should be more or less all the same as in Godot 4.1.

In Godot 4.4 the asnyc map update was added, that already changed the order slightly but that was likely the only big change that could cause a difference.

In Godot 4.5 not only was the async region updated added but also a large amount of the internals got changed including the navlink storage and update.

[Resident05]

I found the issue!

It's the polygon, it doesn't match with the region polygon.

Updating to 4.5 did not update the regions to show they were smaller.
The links in my project are always right on the edges, so they are all out of bounds in my project now, and thus ignored.
Is... there a quick way to update them to match?

This is how they look in 4.1:

[smix8]

Oh that is because Godot 4.1 had no navmesh baking, aka no margin for the agent_radius.

While you can set the agent_radius to zero on the NavigationPolygon I would not do that. You need that margin for physics collision and it also helps you to remove polygon errors on the baking. You might run into broken navmesh bakes with a agent_radius set to zero.

[Resident05]

I see, personally I'd believe it should somehow match the polygon since baking takes a bit to update in the editor, I didn't run into any issues changing the agent_radius in my project at least, though I did run into a different problem:

Is this one actually a bug? I noticed disabled regions affecting enabled region when they overlap, which is also something I never experienced in 4.1

4.1:

[smix8]

In Godot 4.5 all regions are part of the navigation map geometry no matter their disabled state for performance, cache and geometry reasons.

Disabled regions are still ignored in the actual path queries but if you want them to not be part of the navigation map you need to remove the node from the SceneTree like most other nodes.

A region navmesh that overlaps another region navmesh like that is basically a layout bug as navmesh can not overlap, else it is a logical bug. That this even worked somehow in old Godot was basically a dance on the vulcano as it could have easily merged all the edges wrong due to the overlap breaking everything.

[Resident05]

Thank you for all the responses, even if it was mostly me just being unfamiliar with all the updates to Godot, I'm not sure if I should close this report or a contributor should close this, I don't have anything else to add.

[smix8]

When solved we can just close it then.