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.
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)
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
navigationbranch 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:
set_vertices. Every node has to “add” to the passed object, which generates intermediary work. The array returned byget_verticescan’t be modified because of CoW. Other methods likeadd_mesh_arrayhave to be used, which require the format Godot meshes take inadd_surface_from_arrays, which itself is suboptimal because it requires converting from our internal cache to Godot’s, then copied again intoNavigationMeshSourceGeometryData3D;add_mesh_arraytransforms 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
navigationbranch, it is still in the same state as mentionned in https://github.com/Zylann/godot_voxel/issues/610#issuecomment-2027510950I 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:This is a new node which for now I called
VoxelTerrainNavigation, that must be child ofVoxelTerrain. 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 toNavigationServer3D::bake_from_source_geometry_datato 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:
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).
cell_sizeandcell_heightmatches with the map by enforcing it in the automatic baker: the error still happens.cell_sizeandcell_heightto 0.5 because honestly 0.25 was likely too small for large terrain where each voxel is 1 unit large: the error still happens.Sample Max Errorto 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.merge_rasterizer_cell_scaleto 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_scaleare 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 withERR_PRINT_ONCEso 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
NavigationRegion3Dinternally, 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 withdebug navigation. One option of course would be to inherit fromNavigationRegion3Dor make it separate, however this is not practical for the following reasons:Branch
I pushed my WIP to the
navigationbranch 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_asyncexists 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::syncis 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 theNavMap::synca lot faster, it remains really slow becauseNavMapstill 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
navigationbranch 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,NavigationServeris 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.