godot: TileMap.set_cell() with navigation takes too long

Did exactly what I wanted in demo with NavigationServer2D.agent_set_radius(...) and NavigationServer2D.map_get_path(..., optimize=false), disabled edge connection and square navigation shape. Thank you for advices, now I’ll finally try to update the project to Godot 4.

demo_ok2.zip

The navigation map syncs once each physics frame should anything change on the navigation map. Does not matter if you change 1 cell or 10.000 cells as the entire navigation map is rebuild regardless.

While the navigation map syncs on any change the navigation regions themself only update when their transform or navigation polygon is changed. So if you change a single cell only this navigation region updates and the navigation map, but not all other navigation regions on the map. The navigation map sync is still costly because it needs to match all those external edges together but at least it should not be affected by how many cells you updated in a single frame.

If you notice a difference in performance depending on how many cells you change in the same frame might be something TileMap internal or Node related but likely not navigation map sync related.

Looking at the TileMap source code when you change a cell the entire TileMap quadrant size of cells will be reset. This means all existing navigation regions for that quadrant are deleted and created new. How many cells those are depend on your quadrant size.

As said, can’t compare. All the old 3.4 TileMap navigation did was set vertices and polygons on an isolated Navigation2D node and even at that simple job it failed multiple times.

You can have this simplicity without all the old TileMap bugs if you use a single navigation region and disable edge connections.

Even older Godot 3 versions can’t compare

This is a demo for Godot v3.4.5.stable.official [f9ac000d5]. TileMap.set_cell() takes a few milliseconds.

demo_ok.zip

You can test it here: https://editor.godotengine.org/releases/3.4.5.stable/ Right mouse button places a wall, left places a navigation cell

That is a diamond, not a square. A very inefficient navigation polygon due to the empty corner space and impossible to merge single vertex per tile side. If you do not overlap tiles with e.g. half-offsets nothing can merge performantly with such a layout. An efficient square navigation polygon would cover the entire tile cell size.

I almost don’t care about startup speed

Your performance bottleneck is the navigation map syncs which has too many polygon and edge calculations to do with your TileMap size and layout. If you start your game the navigation map syncs, if you change your TileMap cells the navigation map syncs. It is all the same process triggered with navigation region or mesh changes on the TileMap.

What is destroying your performance is the amount of edges and your polygon layout cause it takes a long time to synchronize them all for the navigation map.

You have

• 2211 navigation polygons
• 15799 polygon edges
• 1889 of those edges are merged by vertex which is a far too low number
• 9445 edges are connected with a very expensive edge connection calculation
• 13910 edges are just doing nothing except making the edge connection calculation even more expensive

You can look at those stats yourself in the debug monitor in the navigation section.

The heavy performance killer are the edge connections, you can disable them in the ProjectSettings if you do not need them. See pr that made them optional for more infos here https://github.com/godotengine/godot/pull/75601.

There is nothing to rebake in a thread here. The navigation map synchronization is the server sync point for all commands from threads.

The reason why a square navigation polygon is faster is because it has less edges and they are all merged by vertex overlap which is quick and efficient. The layout you currently use has more edges and many of them can never be merged like that so they all go through the expensive and slow edge connection calculation destroying your performance.