godot_voxel: Navmesh for Non-Blocky Voxel (Lod) Terrain

Is your feature request related to a problem? Please describe. It’s rather difficult to consider having any kind of in-game AI when you’re unable to pathfind with it, a basic, even if rudimentary, Navmesh system for non-blocky Voxel Terrain probably has probably been long overdue and from what I’ve been able to research, there hasn’t been particular progress as to making one.

Describe the solution you’d like I’ve done a fair amount of research and considered one way of doing things that maybe would be acceptable in performance. (Though I’m still unexperienced with both C++ and Godot Module development, so pardon if parts of this solution are not possible)

We begin when the Voxel Engine has just created the physics mesh (Or at the same time, using the same source) for a block in the terrain, we take that mesh and hand it to Godot, either to NavigationServer3D’s bake_from_source_geometry_data, its async variant or with NavigationMeshGenerator’s. (This is assuming that calling these Godot methods are viable/performant)

Doing this we would get a NavigationMesh for this block of terrain but it wouldn’t quite work just yet because of how agent_radius works. There’s going to be a small margin to the borders of the physics mesh (where it would connect to other voxel blocks) so we will have to fix it.

nav0

We probably would save this result somewhere, so when the terrain is updated only a single block is parsed at a time instead of the whole terrain.

Finally, the navmesh is stitched to the other navmeshes, making a single one. We’re assuming that there would only be one NavigationRegion3D or equivalent, thus, the feature it has for “automatically merging navmeshes with other regions” will not apply as this is all going to be inside a single region, additionally, overlapping navmeshes are very unpredictable in behavior, so merging is required.

In an ideal world, perhaps this merging step can be done in a similar fashion it is done when making the visual or physics mesh but maybe it will be necessary to make its own implementation for navmeshes. And this is still mostly a “barebones” kind of implementation, as all the Navmesh would be:

  • In one layer
  • Only using one agent type
  • Unable to consider things such as spherical planets (Though you could maybe change the “up” direction when baking a block)
  • …or any kind of wall climbing in the style of DRG’s Glyphids (For this it could theoretically be possible to just pass the entire mesh as a raw navmesh, haven’t done any research about this specifically)

But we’ve gotta start somewhere.

Describe alternatives you’ve considered Firstly, I tried the obvious, try to use NavigationRegion3D on a VoxelLodTerrain… but it literally gave me nothing, then I’ve read other issues that talked about Navigation on non-blocky terrain here, but most of the “solutions” I’ve seen were either based on mostly static terrain, baked the entire terrain each time it was called (In addition of using 2 plugins) or finally requires the user to just “figure it out”, while barely having the tools to properly have access to all of the critical voxel data to make a navigation mesh of some sort (And most of these issues are at least 2-3 years old).

Additional context While I’m still learning C++, any indication of where I could search within the source code of the module to make a prototype of some sort would be appreciated. In addition of any observations/critiques/etc.

This is a great module for Godot, and I truly want to make some projects with it, but without any kind of Navigation for AI, it’s losing out a lot.

About this issue

  • Original URL
  • State: open
  • Created 3 years ago
  • Reactions: 6
  • Comments: 16 (12 by maintainers)

Most upvoted comments

Quick update:

Godot just merged a PR that allows plugins to register custom navmesh geometry sources: https://github.com/godotengine/godot/pull/90876 This is good news, and will likely solve half of the reason I opened the proposal (my older heightmap plugin; the other half being Godot hardcoding its own modules into the navigation module).

However this is unfortunately not well-suited with the kind of terrain the voxel module generates, unless maybe you want to bake a fixed navmesh in the editor and never update it at runtime. So it’s not really “missing” it.

I suppose it would work if used at runtime, however the general-purpose logic Godot does to gather geometry for the baker is IMO not scalable enough to be done frequently at runtime in a large 3D procedural streaming environment. What I’ve done already in the navigation branch does it more efficiently than what the exposed API allows, and it still suffers from performance issues (mostly coming from stuff after baking).

My thoughts about why the new Godot API is not suitable for runtime with this module:

  • AFAIK this remains a “global” parsing process, so if chunking needs to be implemented, it won’t work, or won’t be able to take advantage or space partitionning.
  • We apparently can’t have a workflow involving a single allocation of all vertices ending in one call to set_vertices. Every node has to “add” to the passed object, which generates intermediary work. The array returned by get_vertices can’t be modified because of CoW. Other methods like add_mesh_array have to be used, which require the format Godot meshes take in add_surface_from_arrays, which itself is suboptimal because it requires converting from our internal cache to Godot’s, then copied again into NavigationMeshSourceGeometryData3D;
  • In double-precision builds, such API uses double-precision vertices, which is a waste of space considering the navmesh isn’t supposed to cover such large distances, and also a waste due to navmeshes using single-precision floats anyways, so there goes another unnecessary conversion. Also every vertex has to be transformed, which is a very good case of optimization with SIMD, but if it uses doubles it will run at half the speed.
  • Too much work has to happen on the main thread. For example, add_mesh_array transforms every vertex during the parsing process, an operation that could be done in a separate thread, but can’t here, because it’s called from within a flow that assumes we access the scene tree, so it is forced onto the main thread. The approach I considered instead was to gather the bare minimum (if anything) from nodes on the scene tree by having everything cached/grouped/ready to be picked, and do all the remaining work in a separate thread. This is not how Godot works at the moment, despite some options allowing to pre-filter (like taking from a group).

Regarding the navigation branch, it is still in the same state as mentionned in https://github.com/Zylann/godot_voxel/issues/610#issuecomment-2027510950

I also added a doc page: https://voxel-tools.readthedocs.io/en/latest/navigation/

I spent some time making a prototype of automatic navmesh baker for VoxelTerrain: image

This is a new node which for now I called VoxelTerrainNavigation, that must be child of VoxelTerrain. For now this is pretty much gathering the geometry of all chunks, combining them into a single mesh without extra processing (I dont spend time sharing vertices between chunks for example, this should really not be necessary), and passing that to NavigationServer3D::bake_from_source_geometry_data to make a single navmesh.

I intentionally chose 3D noise here because it creates overhangs and kinda stress-tests the navigation system, which we really need to be robust enough to handle all the crazyness that can exist on such procedural/player-editable terrains, without crashing or breaking somehow.

I havent tried using an agent to pathfind on the resulting navmesh for now.

“Sync” problem

Unfortunately, things are in a rough state, mainly because of this incredibly annoying error that keeps getting thrown by Godot:

ERROR: Navigation map synchronization error. Attempted to merge a navigation mesh polygon edge with another already-merged edge. This is usually caused by crossing edges, overlapping polygons, or a mismatch of the NavigationMesh / NavigationPolygon baked 'cell_size' and navigation map 'cell_size'.
   at: NavMap::sync (modules\navigation\nav_map.cpp:862)

It doesn’t always occur, but as terrain generates, it happens really quickly.

I’m already pretty sure meshes are reasonably manifold (“reasonably” because I didnt run a definite test on it, but from having looked at Transvoxel meshes for a while, I can say they are devoid of self-intersections).

  • I made sure cell_size and cell_height matches with the map by enforcing it in the automatic baker: the error still happens.
  • I increased cell_size and cell_height to 0.5 because honestly 0.25 was likely too small for large terrain where each voxel is 1 unit large: the error still happens.
  • Tried larger: the error still happens.
  • I attempted to increase Sample Max Error to 2 instead. The error went away on a test with view distance 32 (which is tiny), but when going back to default view distance 128, the error still eventually happens.
  • I tried 3, but the error still happens.
  • I tried enabling mesh_optimization_enabled on the mesher, which simplifies geometry a little, getting rid of thin triangles at the cost of much slower meshing: the error still happens.
  • I tried the alternative that was provided by Scony in a recent PR: so far the error hasn’t happened. I’m not sure what setting merge_rasterizer_cell_scale to 0.001 really does compared to 1, it’s quite a large change. That setting is only available in Godot 4.3 though.

See https://github.com/godotengine/godot/issues/85548 for more details.

I can’t really be sure if all points mentionned to use merge_rasterizer_cell_scale are satisfied, as there is no tool to verify it AFAIK. The error doesn’t come with a way to find where exactly the problem is so I don’t know what kind of particular case the terrain is producing that causes the problem. It is also logged with ERR_PRINT_ONCE so once it happened you have to constantly restart Godot to test again.

I even wonder if the error is actually a big problem or something that could be tolerated to some degree. Either way, even if it were to happen due to terrain being too harsh in game, it should not be something we have to constrain manually up-front somehow (because the world is not pre-authored!) and then crossing fingers hoping it doesnt happen when players generate and edit new terrain… there has to be another way to deal with it at runtime with minimal cost, but for now I don’t what.

Transvoxel derives from marching cubes, which naturally produce triangles that can be very thin. I have no idea whether that has an impact or not here. That’s why I though of trying meshoptimizer to “clean” it up, but that didn’t help. Besides, simplifying the mesh has some downsides (lower visual quality, much longer meshing time, and trouble getting perfectly-matching cell triangles when using detail rendering, requiring to keep more memory allocated with the non-simplified meshes).

Regarding the editor

while the node also bakes inside the editor and uses a NavigationRegion3D internally, Godot doesn’t render any debug preview of the navmesh. I don’t know why. The code to render it is also not exposed. So right now I have no idea how to show that, apart from recoding it from scratch. The only way to preview it is launching the game with debug navigation. One option of course would be to inherit from NavigationRegion3D or make it separate, however this is not practical for the following reasons:

  • Multiplayer: I might want to generate multiple regions when multiple viewers move around far from each other in multiplayer, which would also be automatically split or merged based on their position. That means dynamic management of regions, so it makes little sense to place them manually in the editor.
  • Large-coordinates: regions could be translated automatically around viewers so that navmeshes can use local floats without suffering from world-space imprecision (though I have yet to check if Godot really allows to work that way). That also makes manual placement pointless.
  • Also the inheritance option is a bit messy as it will show the “bake” buttons in the editor, despite not being usable in this case.
  • The preview navmesh in editor would end up stored in the scene file, which may not be desired. This is a runtime feature that can change dynamically, so it makes little sense to have a pre-baked saved navmesh. Caching might make more sense, but it’s not really doable without chunking, which isn’t yet the topic of this experiment.

Branch

I pushed my WIP to the navigation branch if you want to look at the code or test it. It’s not final, not optimized, and not threaded, so expect heavy stalls.

Another wonderful thing: While bake_from_source_geometry_data_async exists to bake on a different thread, it won’t actually use threads in the editor. So it will stall constantly, and you’ll have to turn off navigation baking while working on the terrain. For some reason, it has been hardcoded here: https://github.com/godotengine/godot/blob/29b3d9e9e538f0aa8effc8ad8bf19a2915292a89/modules/navigation/3d/nav_mesh_generator_3d.cpp#L88 The reasons invoked are vague and really sound wrong for desktop platforms where 99% of people develop games on.

Update: apparently it’s possible to call the synchronous bake function from a custom thread. So we may have to do that if the editor case is too much of a problem.

Also, NavMap::sync is related to the region connection feature. It was designed for users having small maps, is very slow and not threaded for large terrains, but it can be turned off apparently. Maybe that also removes the need to comply with what the sync errors were raising as well? That’s one point against region-chunking though. Edit: it does NOT get rid of sync errors, so the margin hack is still required to silence them… Also while it makes the NavMap::sync a lot faster, it remains really slow because NavMap still does the work of connecting polygons of the navmesh itself on the main thread, which doesn’t actually happen during baking. Seems the state of NavigationServer in Godot is such that even if everything is threaded and made fast on the gather+bake side, there will always be CPU wasted by NavigationServer’s sync system because it can’t easily be threaded without significant refactorings. I found some optimizations to do in the area I was looking at, but I dont have expertise on the whole system so I can’t contribute that kind of refactoring at the moment.

Update 2, regarding chunking: apparently using the border option is preferable instead of padding the AABB (see docs). Recast will make sure the edges match, without the need to use Godot’s sync margins. Also, that option might also enable us to pass only the relevant chunk to baking, simplifying the gathering process. It could even allow us to bake from the meshing tasks themselves. That would be wonderful, EXCEPT… neighbor chunks are still required in case they contain a wall, ceiling or platform right next to the current chunk, which prevents that whole shortcut… also, props may still have to be figured out, because that involves the scene tree. This will need investigation.


Current state as of 2024/04/11: The navigation branch has something somewhat functional, it bakes a navmesh fully threaded, but performance is still bad due to Godot doing a bunch of work on the main thread (While baking can be threaded with our own tricks, NavigationServer is not multithreaded, and Godot doesn’t seem well optimized to handle dynamic navmeshes on large environments). There is no easy workaround to this. As listed earlier an obvious step would be to find a way to chunk the navmesh, but that isn’t so straightforward and Godot is still going to do a lot of work on the main thread just to connect polygons of the navmesh and connect navmeshes together. For now I left the branch as-is and working on other things.

I’ve done some more investigation regarding the sync error: https://github.com/godotengine/godot/issues/85548#issuecomment-2026344751 I’m still out of ideas to avoid the issue. It’s too unreliable, and the only solution actually silences the error rather than fixing the problem, as well as potentially introducing another problem with connecting regions.