TileMap.set_cell() with navigation takes too long

[werryxgames]

Godot version

v4.0.3.stable.official [5222a99f5]

System information

Linux Ubuntu - Godot v.4.0.3.stable - Compatibility, Mobile, Forward+; Android Redmi 9C - Godot v.4.0.3.stable - Compatibility

Issue description

TileMap.set_cell() takes 5 seconds on Ubuntu and 15 on Android if it replaces a cell with one without. I want to create game with bots, but they go through two walls with touching corners, even with CollisionShape, so i created this navigation shape: I noticed, that if navigation shape completely covers the cell, TileMap.set_cell() takes about 0.2 seconds. In real project i also tried to create a 4-point rhombus (by editing .tscn file), but it didn't speed anything up. Also TileMap.set_cell() takes a few milliseconds if it doesn't replace any cell

Steps to reproduce

Create a TileMap named TileMap Place about 50x50 cells with $TileMap.set_cell(0, Vector2i(x, y), 0, Vector2i(0, 0)) Replace the first cell with $TileMap.set_cell(0, Vector2i(0, 0), 0, Vector2i(1, 0)) Wait 5 - 15 seconds

Minimal reproduction project

demo.zip

[werryxgames]

Also is it possible to somehow rebake the navigation in another thread without freezing the game?

[smix8]

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.

[werryxgames]

And how to improve performance? With 4 vertices, there are 8844 edges, but 0 merged, 15112 connected and 8844 free. Is it possible to keep square shape and make navigation agents not go through wall corners?

[smix8]

Not sure what you did there but when I add a square navigation polygon in your demo I end up with

5066 edges. 3778 of them merged. 0 edge connection. 1288 edges still free.

With edge connections disabled in the ProjectSettings those 1288 free edges do not consume performance with pointless calculations and your demo starts near instantly.

NavigationAgents will go where there is a connected navigation polygon, that is all that counts. To avoid them getting stuck with collision objects or clip through other visuals you need to shrink the polygon so it has enough margin for your agent size.

Unfortunately the TileMap (tile based layouts in general) is not very supportive when it comes to adding margin for agent sizes as it creates seams everywhere if you shrink the polygons. See pr https://github.com/godotengine/godot/pull/70724 that adds 2D navigation mesh baking including for TileMap.

[werryxgames]

Not sure what you did there

your demo starts near instantly I almost don't care about startup speed, I need to reduce freeze delay on cell replacement with set_cell(). On the left mouse button in the demo, a navigation cell is set, on the right button, a wall. I just need to reduce the delay on click so that the player does not see the difference between a normal frame and a frame with set_cell()

you need to shrink the polygon so it has enough margin for your agent size Thanks, I'll try to generate a navigation polygon from cells in a TileMap, but I have to regenerate it every time a cell appears/destroys, which will affect performance

[smix8]

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.

[werryxgames]

In Godot 3 TileMap.set_cell() with navigation was instant. And, if i remember correctly, bots with CollisionShape didn't go through walls.

If you start your game the navigation map syncs, if you change your TileMap cells the navigation map syncs

Can it sync in background without freezing the game at that moment? Bots will use last synced navigation polygon

[smix8]

In Godot 3 TileMap.set_cell() with navigation was instant.

Godot 3.5+ uses the same navigation system as Godot 4.0. The only thing a little faster in Godot 3.5 is the old TileMap cause it does less.

Even older Godot 3 versions can't compare cause they had no navigation mesh merging or edge connections, it was all a simplistic, half-broken navmesh on a local node.

Can it sync in background without freezing the game at that moment?

No, server sync needs to run on the main thread.

I mentioned the optimizations that you can do with more efficient polygon shapes or disabled edge connections. Apart from that you can only reduce the amount of TileMap cells that are active at the same time on the same navigation map or do what the linked pr does and manually merge many of your tile cells together into larger polygons instead of using the tile cell version.

The TileMap adds a polygon for every single tile cell that uses a navigation / physics / occlusion layer which is not very efficient. You will get similar performance issues with physics as soon as the rigid body action starts or with occlusion should more geometry be added and lights move.

[werryxgames]

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

[smix8]

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.

[werryxgames]

With a simple navigation region and edge connections disabled, it still takes 0.2-0.5 seconds per cell, but there can be, for example 10 cell destroys in one frame.

[smix8]

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.

[anonomity]

I have the same issue and I'm using a simple square for my navigations poly

and for me I'm replacing a cell that has nav col, with a cell that also has nav col

[anonomity]

When you have several nav tiles grouped under one source ID, any other tiles with the same source ID, whether they are navigation tiles or not, will experience slower performance.

By setting a cell with a source ID that does not have any navigation tiles associated with it should be normal speed.

[smix8]

Starting with Godot 4.2 beta the NavigationRegion2D and the NavigationServer2D have the option to bake the TileMap navigation into a combined navigation mesh with https://github.com/godotengine/godot/pull/80796.

This baking reduces the navigation mesh edge count and improves both update and pathfinding performance significantly. This also allows to add proper margin offset for agent sizes for a navigation mesh that originated from TileMap data.

The TileMap also has new options with https://github.com/godotengine/godot/pull/83273 to disable the build-in navigation so that a call to set_cell() does not trigger updates for all the navigation mesh edges causing performance problems when too many edges are involved.

I think this is what can be expected for performance regarding TileMap navigation options. There is no magic bullet when the TileMap size and edge count go over a critical count performance problems are to be expected. Now with the new changes and additions options exist to work around those so I think this issue can be closed.

[werryxgames]

I have the same issue and I'm using a simple square for my navigations poly

and for me I'm replacing a cell that has nav col, with a cell that also has nav col

In this situation performance is better, but NavigationAgents goes through corners of walls, what looks ugly for players

Starting with Godot 4.2 beta the NavigationRegion2D and the NavigationServer2D have the option to bake the TileMap navigation into a combined navigation mesh with #80796.

This baking reduces the navigation mesh edge count and improves both update and pathfinding performance significantly. This also allows to add proper margin offset for agent sizes for a navigation mesh that originated from TileMap data.

The TileMap also has new options with #83273 to disable the build-in navigation so that a call to set_cell() does not trigger updates for all the navigation mesh edges causing performance problems when too many edges are involved.

I think this is what can be expected for performance regarding TileMap navigation options. There is no magic bullet when the TileMap size and edge count go over a critical count performance problems are to be expected. Now with the new changes and additions options exist to work around those so I think this issue can be closed.

I don't understand how baking will help in situation, when navigation region could be changed very frequently. Yes, now it's possible to disable navigation in TileMap, but only workaround, that I think can help is custom AStar-based navigation: demo_astar.zip - in this demo press left mouse button to place wall, right mouse button to remove it and space to turn movement on or off, also notice that you don't need to wait 5-10 seconds after you place/remove wall like with default navigation to continue enjoying game (or this demo).

This demo isn't perfect navigation system, but it shows that it's possible to add, for example, Static and Dynamic modes to navigation (agent/tilemap). Static navigation maps will work fast, but freeze game for 5-10 seconds when changed; dynamic will work slower, but won't freeze game.

Old demo for comparision: demo.zip

[smix8]

@werryxgames If you do not need pathfinding to any possible position inside a surface and your project works ok with just simple point-based pathfinding AStar2D is the way to go. AStar2D is a very simple pathfinding helper and performance friendly to map changes because it does not care about any TileMap cell layouts. All it does is define a point and a few manual connections to other points.

The NavigationServer2D and navigation mesh pathfinding are a different beast. The navigation meshes allow you to define entire traversable surfaces instead of just points, but this comes at a higher performance cost for updates to build the edge graph. Every navigation mesh edge adds the same cost to the pathfinding graph in 2D or 3D. While a common 3D navigation map can cover large gameplay scenes with a navigation mesh consisting of just a few hundred edges the TileMap in 2D is very wasteful with edges resulting in its general low pathfinding and update performance.

The new 2D navigation mesh baking can help with this so far as it removes a high number of unnecessary navigation mesh edges in the navigation map by merging the cells. This results in better path corridors and better performance. It also allows to offset the navigation mesh by agent size which removes this "agent walks through or gets stuck on corner" problems of the TileMap.

The navigation mesh baking also can be done with background threads and a single NavigationRegion2D with an optimized navigation mesh costs far less to sync on the navigation map than updating 1.000+ TileMap cells with each having its own region and small navigation polygon.

If you have a very large TileMap it might take a second to bake a new navigation mesh but the baking can be done on a background thread so wouldn't directly impact your frame rate. The parsing of the TileMap data needs to be done on the main thread but this data can be cached in a NavigationMeshSourceGeometryData2D resource and only changes added on top so this can be worked around as well.

But as mentioned before, what really makes your project freeze for 5-10 seconds are the edge connection calculations due to having nearly 14.000 free and never merge-able edges in the project.

The edge connections are a feature designed for smaller projects to help beginners connect navigation meshes when hand placed. They are costly to calculate because every free edge is compared against other free edges by angle, distance and connectable edge segment until a match is found. So if not a single edge can be connected of those free edges, which is the case in your layout, you are running a very costly near 14.000 x 14.000 loop with 196.000.000 costly calculations. Nothing will safe that performance with this map size and layout except disabling the edge connection feature. You can do that in the ProjectSettings 2D navigation submenu or with the NavigationServer2D.map_use_edge_connection() function.

[werryxgames]

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