Dynamically building a NavigationMesh?

Godot Version

v4.2.1.stable.mono.official [b09f793f5]


I was unable to apply a “padding” to the navigation mesh, so agents were sometimes stuck at corners of a ground, laid out on a rectangular grid (by bumping into the walls at the corners).

I then made the agents able to go through the walls (since ideally they would only want to remain inside the navigable region), but when I applied avoidance, they occasionally left the ground.

Since my game generates the walkable world dynamically, I cannot bake a smaller navigation mesh so that the agents would keep some distance from the walls. I’m now trying to build my own navigation mesh instead. I have already developed the algorithm that essentially shrinks the walkable area as necessary, generates a bunch of interconnected rectangles that I’d like to merge into a mesh, which I could convert dynamically into a navigation mesh.

This image illustrates a possible arrangement of interconnected rectangles that define the walkable region (marked with blue and green to indicate the size): Imgur: The magic of the Internet

How would you recommend doing this – merging the rectangles into a mesh --, without me “re-inventing the wheel”?

1 Like

Take a look at the documentation for NavigationPolygon:

You could either add each rectangle using AddPolygon() or use AddOutline() for creating one polygon of your connected rectangles. For the latter you need to select the outline vertices, but it probably results in a cleaner mesh.

The documentation page has code samples for both functions.

1 Like

You did not mention this but this looks like a problem that only exists with the TileMap or GridMap build-in navigation (or when you use custom tiles and just do a 1:1 copy). What all those tiled layouts have in common is that by default they can not add the required margins around navmesh edges.

If you use a NavigationRegion2D/3D instead and bake a navigation mesh for the TileMap/GridMap it adds the required margin and offset automatically with the NavigationMesh/NavigationPolygon agent_radius property.

For the avoidance you need to add static NavigationObstacles to add boundaries to the avoidance simulation. By default the avoidance simulation is neither physics collision or navmesh surface aware. See Using NavigationObstacles — Godot Engine (latest) documentation in English