It takes a very long time to bake a map starting with size 64x64
The documentation says:
NavigationServer2D provides a powerful server API to find the shortest path between two positions on a area defined by a navigation mesh.
As far as I understand, the NavigationServer2D class makes a request to the API, and server responds with ready-made calculations. Why is this happening? Does the API have limitations? Is it possible to carry out calculations on your own machine?
I planned to make a 1000x1000 map…
Mesh-based navigation scales well with large game worlds as a large area can often be defined with a single polygon when it would require many, many grid cells. - docs
As you can see from my baked mesh I have quite a lot of small polygons. Why don’t they unite in larger one? In my last problem, I also complained about small polygons, someone wrote that this happens due to the overlay of tilemap navigation and NavigationPolygon, but I don’t use tilemap navigation
Before this I worked with Unity and their Navigation worked very quickly
With a smaller map everything works quite acceptable
TileMap was just an example for using an inefficient source geometry format to parse and bake because it adds a single polygon with 4+ edges for every single cell and that will be slow to process. So it is not the map size directly but the amount of edges and polygons to process that makes things slow.
The parsing of the source geometry from the SceneTree is single-threaded because the SceneTree is not thread-safe so that will also be slow with many objects. You can work around this by adding the geometry yourself to a NavigationMeshSourceGeometryData2D object using threads, not touching nodes or SceneTree.
There might be more to the performance problems than just the baking because after the baking is done the NavigationServer also needs to reprocess the navigation map. This also can take some time when many, many edges are involved. Currently the navigation map is a single geometry soup so every change requires a full rebuild.
What do you mean with “Is it possible to carry out calculation on your own machine?”. You can create your navigation mesh procedural and update the region on the NavigationServer manually if you do not want to do the baking with the NavigationServer, if that is what you are asking.
The Unity navigation baking is not 2D, it is 3D and based on a heavily modified version of ReCast which is a full voxel rasterization. In Godot ReCast (unmodified version) is used for baking but it is only used in 3D for the navmesh baking because ReCast does not work with large (large as in size, not cells) 2D projects by default due to inflated scale that 2D uses (1 pixel maps to 1 world unit). So theoretically you could bake your navigation mesh with the NavigationServer3D and convert to 2D if you want to risk it. I did in the past and it would break quickly which is why the official 2D navmesh baking uses outline paths and not the ReCast rasterization for the baking .
The Unity navmesh baking also uses the tiled navmesh based on Detour which can be seen in the layout. That is why the edges are all cut while Godot by default does not force the edges to be split up. The tiling would need to be added manually. Because everything is force-tiled it can be processed async with threads by tile speeding the otherwise slow process up considerably. This is currently not an option in Godot because there is no forced tiled layout. Theoretically you could do the same by tiling your source geometry and baking each tile on its own with the async baking of the server but it is not an automated process.
In addition to what smix8 said, your collider shapes are very detailed. If you used axis-aligned rects it would simplify that whole region soup significantly. I have done my own region-placing logic for a project and it was fast, so I’d say using a grid of rects as the polygons to make the base of the navmesh instead of just one big rect will also help. You can do this in code or in the editor. If you give more details about how your levels are made we can help further.
I’m not such a cool programmer to implement what you propose.
I conducted several experiments: first I created 3 more NavigationRegion2d and divided the map between them, this significantly speeded up the baking, but I’m not happy with it.
The issue is clearly the number of edges that need to be processed quickly. Then I decided to bake the area around the agent at a distance of 256 (can be more i think) from his position, and overall it works quite well
Need have to clear NavigationPolygon2d every time, because if don’t do this, i get the effect of “exploring the map” and when you bake a new “unexplored” region, the entire map is baked.
Yes, instead of one giant outline, make a grid of outlines and no matter where they happen to fall, it will be much faster because it will only consider triangulating within each outline instead of the entire large area.
This sped up baking by about 50%, average it is 20 seconds. Perhaps I wrote it crookedly or misunderstood something.
In any case, I think I need to change my approach. I will have a dynamically changing world: collecting resources, building buildings and roads, all this will require re-baking the map, so I came up with this system:
I’m interested to hear your opinion guys @smix8@Efi , how effective is this and is it costly in terms of computer resources? It turns out that each agent has his own NavigationRegion2d component and bakes a polygon around himself at a certain distance. The only thing I don’t know yet is how to make the polygons overlap nicely
now:
I’d write it like this. Easier to tweak. I don’t know it chunk_size should be 32, tho? I think it should be * 8. Maybe that’s what SIZE is in your script? You can tweak it as you need. A good chunk size would contain a square of 8x8 tiles, and that by the chunks per side should cover your map. Adjust as necessary.
@onready var nav_mesh: NavigationRegion2D = $NavigationRegion2D
var chunk_size: int = 32
var chunks_per_side: int = 4
func new_setup_polygon():
for i in chunks_per_side * chunks_per_side:
var x = i % chunks_per_side
var y = floor(i / chunks_per_side)
var rectangle = PackedVector2Array(
[
Vector2(x * chunk_size, y * chunk_size), # top left
Vector2(x * chunk_size + chunk_size, y * chunk_size), # top right
Vector2(x * chunk_size + chunk_size, y * chunk_size + chunk_size), # down right
Vector2(x * chunk_size, y * chunk_size + chunk_size), # down left
]
)
nav_mesh.navigation_polygon.add_outline(rectangle)
nav_mesh.bake_navigation_polygon()
That chunk baking might work as long as you do not need the agent radius to offset your navmesh from collision. There is not really a way to remove the offset at the border edges at the moment. There is a PR to add it for 3D navmesh baking. I am drafting something for 2D that makes it easier to bake tiles with perfectly aligned border edges so they can be merged quickly by the navigation map.
