NavigationServer rebaking performance can be too low

[BenjaminNavarro]

Godot version

3.5

System information

Linux, AMD Ryzen 9 5900HX, RTX 3080

Issue description

In my 3D game, I have fairly large levels and the player is able to construct objects (walls, barriers, etc) to defend himself from incoming enemies. This means that I can prebake a navigation mesh for the level but I need to update it when the player finishes a construction or when one is destroyed. The problem is that currently it takes around 5s on my system to rebake the navmesh, and the level is not even complete yet. This leads to enemies bumping into the new constructions for a while until the navmesh is rebaked and they find a new path.

Ideally the rebaking should be done in <1s so that's it's not too visible for the player.

Is there a workaround for this problem?

If not, can something be done to improve the performance? In my case, which should be common, I rebake the navmesh just to add or close a hole in it so I have a feeling that this operation could be done very fast. I don't mind having to call specific functions on NavigationServer and pass the new/deleted object manually for this.

Steps to reproduce

I can't really share my level and I don't know any large and free environments I can use for testing. But generating a navmesh for a single large cube (800x20x800) seems to be equally slow as in my level.

Minimal reproduction project

No response

[smix8]

I have fairly large levels

If you have large levels with a single navmesh the baking process will take long(er) as that entire level needs to be voxeled for the baking, there is no way around it.

There are a few things around the current navmesh system that are not perfectly optimized like #66891 but it can be worked around and you can do some optimizations for performance.

Reduce the complexity of baking source geometry

Ideally only use flat meshes / shapes, e.g. planes instead of boxes. If you have a complex 3D model never use the complex model in the baking, replace it with a simple 3D model just for the baking same as you would for e.g. shadow casters. The source geometry parsing from the SceneTree with a large and complex scene can take a significant amount of time in the baking process.

Reduce the complexity and detail of the baking

E.g. increase NavigationMesh parameters like sizes so there are less voxels to build and / or go from SamplePartition mode "Watershed" to "Monotone" or even "Layers". This will reduce quality but can be significantly faster. The amount of edges and polygons are also important to keep low, as the NavigationServer needs to go through all of them to merge regions.

Don't use a baking thread

By default baking on a NavigationRegion3D / NavigationMeshInstance starts a baking thread. Especially on Windows threading can add a performance hickup. The downside of disabling the threaded baking is that you really need to squeeze the baking time down to not freeze your frame rate. This is also a good indicator if your NavigationMesh is even suitable for dynamic runtime updates. If you already optimized the source and parameters and without a thread it takes to long your level is too large and complex, which means you need to ...

Slice the level

You don't need to use a single navmesh. Using a single large navmesh with dynamic updates is not really maintainable in a large level. You don't even need a navmesh when no one is around that area in your level. On very large levels you usually slice the entire level into smaller sections and only add / update navmesh around actors.

[Zireael07]

@smix8:

But generating a navmesh for a single large cube (800x20x800) seems to be equally slow as in my level.

The first paragraph doesn't apply it seems

[smix8]

It still applies cause that single large cube due to its height value alone needs to be mapped to multiple layers and results into roughly ~50.000.000 cells to calculate with default parameters and that will be slow no matter what you do. That is why I mentioned using flat or mostly flat meshes as source geometry when your game allows it cause the more pointless 3D verticality you stack up the more layers and voxels need to be created and calculated.

I personally think everything over 100 x 100 should be sliced cause there is really not much point for both update and pathfinding performance to keep such large and complex navmeshes. I mean even if the baking would be fast such a large navmesh if not perfectly flat and unobstructed has so many polygons and edges and a lot of them need to be traversed in every single pathfinding path query for each NavigationAgent ... that will turn into a performance bottleneck no matter what you do. Sure you could increase the cell size and the edge length to counter this but then you get such rough navmesh bakes they might be not very useable. Hierarchical path finding might help with this at some point but it is only in the draft phase godotengine/godot-proposals#5635 for Godot 4 so does not really help with the current issue in Godot 3.5.

[BenjaminNavarro]

Thanks @smix8 for the detailed answer.

Just for clarification, I'm not really asking for a way to speed to the whole navmesh baking process but more of a way to update it after an initial bake. I don't know the internals of the navigation system but to me it looks like a typical place where you can have a heavy precompute and cheap updates after that.

In my case, the level is a procedurally generated island that roughly fits into a 500x20x500 cube. The terrain is just a plane but with height variations and a lot of objects (trees, rocks, constructions) on it. The cube example was for performance comparison, it's not what I use. Just for testing, I replaced the cube with a plane and at 700x700 with no subdivisions and with default navmesh parameters it also gets around the 5s baking mark.

I already tried increasing the cell size for my level but it quickly turns into bad navmeshes.

I don't think I can really have a simplified model for the navmesh and I'm not even sure the performance will be much better after my tests with just a plane.

For threading, I'm very surprised that the NavigationServer spawns a new thread instead of using one from an internal thread pool. If that's the case that would be a good, and probably simple, perf improvement.

But regarding your last comment, if generating a path through a large navmesh is significantly slower than generating the same path crossing multiple, smaller, navmeshes then I guess I have to choice but the slice the level even if a quick update mechanism would be implemented.

I'll try to make a tool to do this volume slicing automatically, it shouldn't be too difficult using the baking AABB filter. If I get something that works well I'll submit it to the asset library.

I'll keep the issue open for now because I still think that partial updates of a navmesh could be a nice thing to have and be in line with the Godot philosophy of having easy to use tools that work well enough in most cases.

[Calinou]

For threading, I'm very surprised that the NavigationServer spawns a new thread instead of using one from an internal thread pool. If that's the case that would be a good, and probably simple, perf improvement.

There's WorkerThreadPool in 4.0 which was specifically designed to sidestep that Windows limitation, but it won't be backported to 3.x which still uses ThreadWorkPool: #60366

[smix8]

There is currently no way for small navmesh updates on the server. All navigation regions upload their navmeshes to the navigation map and there they are merged into one connected mesh. This also means that any navmesh change triggers a full update for anything inside the same navigation map.

For threading, I'm very surprised that the NavigationServer spawns a new thread instead of using one from an internal thread pool. If that's the case that would be a good, and probably simple, perf improvement.

It is not the NavigationServer, it is the 3.5 NavigationMeshInstance that uses its own thread for baking.

if generating a path through a large navmesh is significantly slower than generating the same path crossing multiple, smaller, navmeshes

It is not the size in world dimensions but the amount of polygons and edges cause if you have many smaller navmeshes their edges need to be checked / merged by the NavigationServer saving nothing in the process. A single large navmesh could be more efficient but only if it has less polygons / edges. As you noticed reducing the detail too much can turn into a bad navmesh quickly so it is not always possible.

You currently only save performance when you remove unused navigation regions from the navigation map. E.g. if you sliced your level into 10 regions and only 2 regions are currently required for actors remove the other 8 regions from the navigation map temporarily will speed up any update to the navigation map (including those triggered by (re)bakes).

[BenjaminNavarro]

@Calinou Ok, I think I had that 4.0 feature in mind without knowing it was 4.0 only so that's why I was surprised. I'll switch to 4.0 once the bugs impacting my game are resolved so that's not a problem for me.

@smix8

There is currently no way for small navmesh updates on the server
I didn't imply there was one, more asking if it was possible somehow. Maybe I should open a proposal to talk about this.

It is not the size in world dimensions but the amount of polygons and edges
Ok so slicing will only be beneficial for baking. Noted, thanks!

You currently only save performance when you remove unused navigation regions from the navigation map
Ok I'll keep that in mind as well

I just put some AABB filter on the navmesh and it's already faster (2s) as I can exclude altitudes below 0 (water) and above the maximum terrain height (trees could go above that but I don't care).

[kabergames]

Hi Is this also true for the tilemap and baked navigation? I have a project with a tile map of 512 cells by 512 cells, and I need to turn on navigation for tiles that previously had no navigation, i.e. when trees are cut down, i need to make the tile navigatable. The set_cell call hangs my game for 3-5 secs. I tried cutting the tilemap into multiple smaller tilemaps of 32 cells by 32 cells but the set_cell still hangs the game for 3-5 secs. I am beginning to suspect that this has something to do with the navigation server rebuilding the whole navmesh instead of per tilemap.

if so, is there any advice or work around I can use to minimize the computation for the nav meshes? Perhaps threading?

[Zireael07]

Do you mean 2D tilemap or 3D gridmap? Are you using NavigationPolygon2D?

As @SmiX already said, the navigation server (which is IIRC the same for both 2D and 3D navigation) rebuilds the entire navmesh every time.

[kabergames]

Do you mean 2D tilemap or 3D gridmap? Are you using NavigationPolygon2D?

As @SmiX already said, the navigation server (which is IIRC the same for both 2D and 3D navigation) rebuilds the entire navmesh every time.

I am using the 2D Tilemap and I am using the built in navigation region when setting up the tiles in the tilemap. Is there a way to let the navigation server rebuild it without blocking the main thread?

[Zireael07]

@kabergames IIRC no :(

[kabergames]

@kabergames IIRC no :(

Ohh man.. i hope it gets resolved but i read it will need a really huge rework.

[smix8]

The set_cell call hangs my game for 3-5 secs.

The use of "set_cell" makes the entire TileMap quadrant dirty for a full update not just the single cell.
This triggers updates to all navregions for each cell in the quadrant on the NavigationServer.
The change to regions trigger a full recalculation of the navigation map, e.g. all edge connections between the tiles.

One work around is to not change the cells with the baked navigation that in turn change the navregions. Instead only change the navigation layers of each navregions as this does not trigger updates of the navigation map but only changes the path query for the NavigationAgents.

There is little that can be done here at the moment with the current TileMap 2D in particular as the TileMap has no interface to receive the navregions for each tile cell.

I think adding a function to only set navigation_layers for each cell would help with this as changing the navigation_layers bitmask does not trigger updates and only affects the next path query for the NavigationAgents.

[groud]

A simple workaround should be to reduce the quadrant size. It might have a small impact on performances but it should help. Otherwise, consider using scene-based tiles.

[grahamboree]

Apologies for thread necromancy. 🧟

Recast maintainer here. We support tile-based navmesh rebaking specifically to provide an efficient way to do live rebaking. e.g. see this demo code for an example implementation. Both Unity and Unreal's integrations support tile based navmeshes as the default.

Is this issue a matter of integrating that functionality into Godot or are there more considerations in play? I admit my knowledge of Godot is very minimal (though I'm learning!) so I may be way off target here.

If this is something that's currently missing and a feature people agree Godot would benefit from I'd be happy to help with the implementation. I'll defer to someone more knowledgeable about the current state and plan for of nav features in Godot though!

[smix8]

@grahamboree Hi and thanks for getting yourself involved.

We have a public Godot developers channel for those that want to involve themself or talk with fellow devs about Godot engine development. You can find the channel dedicated to Godot navigation development here https://chat.godotengine.org/channel/navigation so we can avoid derailing this issue here too much.

In general Godot currently does not have the same level of tight ReCast and / or Detour integration as other engines but it uses ReCast already for parts of the navigation mesh creation. Godot atm uses ReCast only for the raw voxelize and bake step of the 3D navigation mesh as 2D uses a different implementation to generate navmesh. Both 2D and 3D share the same navigation system on the NavigationServer.

There are a at least a few considerations and / or reasons why Godot navigation has not adopted the ReCast tile update feature yet.

The first and major reason is properly that no contributer had the time to spare to even test if there could be a reasonable implementation with the current navigation system and no volunteer showed up either.

Currently after the navigaton mesh is baked by ReCast it is immediatly converted to a Godot native NavigationMesh resource format. The involvement of ReCast in the Godot navigation system ends early at this point, e.g. ReCast has no further involvement in the actual navigation map and updates or any of the data structures which are done as a part of the NavigationServer.

Godot has NavigationRegion nodes as the smallest navigation update unit that users can directly edit and modify. They do not necessary use a tile friendly or triangulated layout and can be entirely user created as long as a few criteria like edge overlap are meet.

We are currently in the process of rethinking how the navigation map are synced at runtime in general see proposal godotengine/godot-proposals#5635 primarly because the current solution (or any tile / grid based) do not work well with very dynamic navmeshes uses like see #66891. In that case we currently think that working with dynamic Godot NavigationRegion units will be more advantageous over involving a tiled update structure that would be more rigid and heavy with constant navmesh position changes every frame.

There are properly a lot more considerations that I can't think of rightnow that could further complicating the issue or any further ReCast integration attempts but happy to hear your opinion or shared expertise.

[spiderbyte87]

Couldn't spatial hashing be used to look up the parts of the mesh that need to be changed and alter them directly? In other words: keep a spatial hash of the current version of the nav map, then when a bake is called at runtime check for changes, only update the areas that need to be updated, then push those updates directly to the navmesh?

Since it's essentially a 2D heightmap it seems like you could probably just do a grid lookup (not that it'd be "simple", just relatively so). What am I missing?

[Calandiel]

There is currently no way for small navmesh updates on the server. All navigation regions upload their navmeshes to the navigation map and there they are merged into one connected mesh. This also means that any navmesh change triggers a full update for anything inside the same navigation map.

Does that mean that for the purpose of optimizing navmesh update times splitting a large world into small regions is effectively useless (provided the rest of the world is large enough)? 🤔

[smix8]

@Calandiel
Not useless because a navigation region does not recalculate its own navigation mesh when not changed.

The thing that gets recalculated on any map change are the map connections.

The currently biggest culprit for bad update performance is the edge connection margin that can be disabled per region or per map. With disabled edge connection margin the only way to merge navigation meshes is with perfect edge overlap but requires nearly no performance in comparison. Most projects can fix their update performance problems by just disabling the edge connection margin.