Navigation polygon vanishes when obstruction hole shares corner

[sfcgeorge]

Tested versions

• Reproducible in:
  • v4.3.rc2.official [3978628c6]
  • v4.2.2.stable.official [15073afe3]
  • Missing APIs in 4.1 and below

System information

Godot v4.3.rc2 - macOS 15.1.0 - Vulkan (Forward+) - integrated Apple M1 Max - Apple M1 Max (10 Threads)

Issue description

Sometimes adding obstructions to a navigation polygon breaks (it disappears) and navigation doesn't work.

My game is randomised so sometimes it works, sometimes not. I believe it's something to do with obstructions sharing a corner with the traversable outline, or that a triangle diagonal is cutting through the obstruction, or both.

This also happens when there are 2 obstructions fully within the traversible outline (no points shared with the outline) but the 2 obstacles share a diagonal corner. I've just reproduced the simplest case as above though.

I would prefer a runtime error than this silently broken behavior. Or perhaps bake returning false in error states instead of void. Or even a validate_points kind of method. My game is randomly generated so it was really hard to track down why navigation sometimes just didn't work without such feedback.

The navigation documentation mentions for 2D "avoid nesting any outlines inside other outlines of the same type (traversable / obstruction)" but here I've used 1 traversable and 1 obstruction so I don't think that should apply.

Steps to reproduce

• Add a NavigationRegion2D node so you can see debug shapes later.
• Attach script to dynamically generate the navigation polygon.
• Generate outer outline points and inner obstacle points (see repro). In my game I have dynamic tilemap generation and user dynamically places obstacles, but for this repro I've hard coded the points.
  • The bug seems to occur when the inner obstacle shares a corner diagonally with the outline, or perhaps when a diagonal of a triangle in the mesh goes through the obstacle (or both).
• Use those outlines to make a navigation polygon. Using just the outline it'll show up (debug enabled), but with the obstacle added the polygon disappears (and navigation doesn't work).

I tried 2 methods of generating the navigation polygon to try to find a workaround but couldn't. Both are in my repro project, the first is commented out. Repeating here inline for easier discussion.

First is just adding the outlines directly (hole is clockwise):

navigation_polygon.add_outline(outer_points)
navigation_polygon.add_outline(hole_points) # this line causes polygon to vanish
bake_navigation_polygon()

Second is going via a mesh with explicit obstacles:

var mesh := NavigationMeshSourceGeometryData2D.new()
mesh.add_traversable_outline(outer_points)
mesh.add_obstruction_outline(hole_points) # this line causes polygon to vanish
NavigationServer2D.bake_from_source_geometry_data(navigation_polygon, mesh)

Neither work as expected. If you comment the indicated line then you can see the outline as expected, it's the hole that is breaking something.

Minimal reproduction project (MRP)

1 file 1 node repro. 2 possible ways to reproduce, 1 is commented out.

repro-hole-corner.zip

[smix8]

Don't set the agent_radius to zero as that disables a major correction step that removes most invalid outline overlaps and other precision errors.

The third-party convex partition algorithm does not know what do do with this invalid vertex overlap input and errors out. While this is always an issue you create these problematic layouts easier with clinical geometry input that is axis-aligned.

I looked at what the baking is doing and the actual polygon clipping works just fine but due to the resulting vertex overlap around the "hole" outline the convex partition explodes.

[Calinou]

Don't set the agent_radius to zero as that disables a major correction step that removes most invalid outline overlaps and other precision errors.

There doesn't appear to be a warning in the class reference for this (and/or a warning on bake). There should probably be one 🙂

[sfcgeorge]

@smix8 thank you, agent_radius = 0.1 seems to function as a workaround! I've seen your advice on other nav threads and found it helpful too 😄 Perhaps we could always run the correction, or have a separate setting to turn it on/off?

Adding agent_radius I think will require me to also use edge_connection_margin as polys won't line up properly, I worry that'll cause a performance hit.

Anyway, here it is working with the workaround 🎉 The clinical geometry is because I'm using tile map layers and merging nav polygons for better performance at large sizes. Loving Godot 💙

[smix8]

Perhaps we could always run the correction, or have a separate setting to turn it on/off?

It is not an "option" and more that when you offset polygon outline paths by agent_radius you naturally remove minor overlap errors because you shrink the surfaces. It also helps that Clipper2 upscales and rasterizes all of the points and recalculates some of the edges while doing this. If you just run it with 0.0 agent_radius nothing really changes so those kind of fixes do not really happen.

Adding agent_radius I think will require me to also use edge_connection_margin as polys won't line up properly, I worry that'll cause a performance hit.

With the TileMap build-in navigation perhaps. If you use Godot 4.3 and the newer baking bound and border size you can bake navmesh chunks with the NavigationRegion2D. Those have no issue to merge by edge key instead of using the edge connection margin. See updated documentation here https://docs.godotengine.org/en/latest/tutorials/navigation/navigation_using_navigationmeshes.html#baking-navigation-mesh-chunks-for-large-worlds

Also how do you run your game without an agent_radius? As soon as you have any actor that is not just a point but has a physics shape your run into nonstop collision and stuck problems with the TileMap navigation mesh without a baked agent_radius so not sure how that should be even workable.