Navmesh for Non-Blocky Voxel (Lod) Terrain

[ARandomKrilios]

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.

[Zylann]

*TLDR is that I have to start investigating this eventually, just can't tell when. Will mark the issue as "enhancement" to have an explicit one tracking the state of it.

---

What you describe isn't really new to what I was thinking so far, the same problems remain in terms of actually doing these things:

• If possible we have to use methods that run on different threads, ideally the threads of the voxel engine which have tasks sorted by distance (unfortunately Godot is oblivious of that and might want to use its own threads, which in turn could want to use all CPU cores which in turn might cause contention?). Doing this on the main thread would be really bad because it has to be streamed at runtime constantly (colliders have the same problem and already occupy a lot of the main thread time, so this would exacerbate the issue)
• You don't seem to consider anything other than the ground. There could be additional stuff on top, such as trees, rocks, stuff placed by the player, maybe even other terrains (though probably won't deal with that) that the final navmesh would have to account for, pretty much re-implementing Godot's geometry collection at runtime and in chunks. Gathering all this stuff is time consuming as well (if they are nodes that means no threading possible), and would force users to either put colliders or areas or something to allow picking stuff up, unless spawning itself is constrained to chunks (and that has to be scalable, given the large amount of items there could be on a terrain). It also puts constraints on when users can put such obstacles on chunks (which could mean not on the main thread), so that the navmesh is baked at the right moment
• As the title suggests, it only benefits specific games. As you mentionned, any setup with variable world up like planets even make Godot's system unusable in the first place. But other terrain types would also not be able to use this either. Someone on Discord even diverged from the proposed design using multiple regions to match the way they wanted their game to work.
• Because this terrain is widely meant for runtime rather than being pre-made, users can't "author" much things in the editor (off-mesh links, specific places to carve or make regions with etc). I assume that's a given, but writing it down anyways for expliciteness
• Similarly, "navmesh" may be one more thing that asynchronously loads. Unlike most games where everything is assumed to be loaded after the scene is added to the tree, here streaming takes time and a lot of new users bump into discovering it. So the concept of "is area loaded" might not mean that there is a navmesh yet in a certain chunk, though that probably only matters for AIs and not players.
• This might be only applicable to a certain LOD, or certain distance away from an "invoker" (viewers). Connecting up navmeshes at different LODs sounds like it wouldn't work. But generally the navmesh may have a limit to balance performance. Also, multiplayer implications: if navmeshes are invoked near viewers, that means eventually they will merge if players get close together, and un-merge when they part. If an AI somehow wants to travel very far which goes outside a navmesh, alternatives would have to be considered, within the limitations imposed by Godot.
• It puts more pressure on the fact seemingly "everything" a game engine does has to have its "voxel terrain" version of it, which is a lot of work to make and keep maintaining as stuff changes. So it takes long before things happen because Godot features can rarely be used as-is, or even have annoying constraints. As you found, Godot doesn't know what VoxelTerrain is so it bakes nothing by default. And that would be unusable anyways due to streaming and player edits requiring constant rebakes of the whole scene. Nodes are also generally not used, using servers directly. While this is sadly hard to avoid, if there is a way you could use simpler exposed APIs (like ability to get chunk meshes when they load?) to plug the extra logic in rather than the terrain hardcoding one way of doing the thing, that might be an alternative. Generally, it's best if a feature using the terrain is properly separated and does not require extra changes to many random areas of the engine.
• It might be that coercing Godot's navigation system into working with this terrain is not the best thing. Not saying it won't be done or at least attempted, just that Godot is general-purpose and has less manpower, and so isn't particularly specializing in dynamic streamed large-scale terrain. Few games do this, so it could have unseen problems we might discover. Longer term someone might come up with better options.

One thing however, is that it's true I haven't looked in more details for this, as I've been focused on other things. I'm working on this engine on free time, so priorities are partly what people ask, but also partly what I want to do.
While I have experience in navigation from Unity, I haven't used navigation much in Godot, so there are things I can't really judge yet. For example your description shows certain things without saying how it's actually done: after baking a navmesh, how do we "extend" the borders? Is there an API to do that? And is it assuming there is a navmesh per chunk and Godot would somehow connect them up, hoping border vertices exactly match? I also can't tell how costly this actually is.

Maybe it's simpler than I realize (putting aside the point I listed earlier). I imagine I could start with doing "a thing" after each chunk mesh loads/updates/unloads. Chunked navigation is a go-to I think. But right now it's mostly speculations, not much actionable yet. For now I guess the first step is, I have to start looking into it, but again can't tell when that will happen yet.

[ARandomKrilios]

Oh wow, thank you for responding so quickly lol
I already assumed that there was some investigation being done on "AI Navigation on Voxels" in general (And to be fair, AI Navigation has always been a complicated part of games), but I found it weird how there was no 'Issue' about it, hence why I threw my 2 cents per se.

I admit that I've put a lot of weight on Godot's Navigation system, as if it were a perfect system (it is not). However having a system that outputs a NavigationMesh of some sort would still be ideal (Maybe just not one explicitly made for Godot's Navigation system). And to give a bit more detail from my own research on how Godot's NavigationAgent attempts to pathfind when Navmeshes overlap:

• If it's a single NavigationMesh in a single NavigationRegion3D the AI will just simply freak out most of the time just trying to go in a straight line, but then getting stuck at the point of the overlap (Even if there's no actual physical obstacle).
• If it's 2 NavigationRegions then it depends on how they intersect: if we talk about 2 squares, if one of their sides are either in the exact same position or within the default_edge_connection_margin then they're either merged or connected. However, if it's for example a ramp (with it's own navmesh) on top of a plane, then they're not connected, what this means is that the AI won't actively consider the Ramp's Navmesh for its path, however if it ends up standing on top of said ramp then it will use it for pathfinding.
  So yeah... I'll admit that perhaps Godot's system ain't the most reliable, I mostly used it as a "Base" to work on more than anything.

The point about the "LOD" you brought up is also very important, however, an AI in Godot will just simply travel to the closest point to its objective within the navigation mesh (So it won't stay still even if the target is very far away from the navigation mesh, unlike Unity), a very "low detail" version for a far away navmesh could still be useful for the AI to evade "A* traps" (As the AI's path also updates slightly with every point it crosses).
It also probably would be best for the user to use a different pathfinding algorithm, which Godot seemingly supports (There's an option to change it per NavigationAgent, though without any plugin it will only give you the option for A*, a HPA* plugin would be ideal for this, but that's another topic).

One of the things you mentioned in the second to last point, having a Signal (Especially on VoxelLodTerrain as it doesn't have any), or anything of the sort, could be really useful if niche, cause for one it would allow to make a crude Navmesh using GDScript lol, but it could also maybe have some other use cases that are escaping my mind right now.

To answer one of the final questions, a NavigationMesh is just that, a mesh (Vector3 Vertices and Polygons that reference those vertices, you also have the function create_from_mesh), so it could be modified like any other mesh and thus it is possible to merge 2 meshes into a single mesh (Already did a small prototype of just this in GDScript, though obviously a performant way of doing this is the critical thing here). The original idea i had was to bake the mesh per block, pick the vertices at the border and extend them to the block's border, then stitching everything up.
In an ideal world, having a custom-made Navmesher that doesn't create the small "margin" to the borders of the block so we don't need to innecessarily extend it back is what we would want. But that would just be its own can of worms.

I'll probably just end up taking a look at how Godot actually bakes a NavigationMesh, and maybe see what parts of it could be useful for Voxel navmeshes. Again, I'm still currently getting comfortable with C++, so excuse me for having a "naive" view of things lol.

[Zylann]

I also just thought about yet another annoyance with chunked navmesh:

Let's say you just use individual chunk meshes to make a navmesh. That will work if you consider just one mesh, but then what if that chunk represents only the floor of a very narrow cave? Because it's voxel terrain, it could mean the chunk above it (which might not even be ready yet!) contains a ceiling that's too close for the agent, meaning the navmesh will be incorrect. Same problem with walls on side and below chunks, and same problem if neighbor chunks contain some obstacle spawning on top.
Which brings to an eternal struggle with chunks: you can't bake a chunk's navmesh if you don't also have neighbor chunks AND obstacles on them. Because of this alone, rebaking a single navmesh for loaded chunks even if only a small part changes sounds easier than chunking (but obviously sounds slower). Surely with infinite time a navmesh system adapted to all these constraints is certainly doable, but we have to work with what Godot provides unfortunately^^"

And then if you add neighbor chunks into a bake, it must still only produce a navmesh within that chunk, and not extend further just because the neighbors are provided to the baker. Not sure if there are APIs to limit this.

And this is even more problematic when we consider that meshes themselves need neighbor voxel chunks to even be produced. The end result being, That meshes currently appear only inside an inset-by-1-chunk region of voxels, and then navmesh chunks would end up themselves as an inset-by-1-chunk region of meshes... (on top of that, voxel chunks can have a different size than meshes!).

Checking 26 neighbors volumetrically in all space for various things is one area of the engine that can can be relatively expensive. It's happening so often with voxel chunks that I'm considering to alter the data structure to trade memory usage for speed, but still not the panacea. There are less mesh chunks than voxel chunks tho (if we ignore empty ones).

People often underestimate the sheer amount of shortcuts that just don't work with streaming voxel terrain^^"
Had a peek at another voxel plugin in another engine and the struggle is real there too; though people sometimes find solutions that don't involve a navmesh, like sprinkling a network of waypoints around progressively or using dynamic avoidance, which is probably less precise but sometimes work well enough, especially in very dynamic environments. Because the end goal isn't so much to have a navmesh, but have a way to compute paths for AIs to follow (even though a navmesh allows to use Godot's navigation nodes, which are general-purpose, but again not the one-and-only solution to everything, even if that means having to do more work).

---

Also I guess this is one more place to reference this proposal: godotengine/godot-proposals#5138
There was a pending PR addressing it for a while, but after several re-tries it ended up dropping the 3D part and now it seems nobody is working on that.

[Zylann]

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 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 godotengine/godot#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.

[ARandomKrilios]

Wow you work very fast, I was still doing some research on pathfinding and navmeshing in general and you already pushed a pretty decent rudimentary prototype, I will for sure take a look!
I'll probably make some tests with an agent just to see if it's able to path properly, though, sounds like baking the entire terrain into a navmesh, instead of only updating the chunks that are different, is going to be a sizeable bottleneck in terms of performance.

Already doing some basic tests, the remeshing of the navmesh causes AI paths to be completely recalculated, because even the part of the navmesh the AI was standing on gets re-updated, having a big tendency to get stuck. I'm using an agent that doesn't use gravity nor inertia on purpose, as that's probably the most sensitive agent to changes possible, though even when re-enabling the gravity, it still gets stuck on wilder terrain (Using Noise Terrain).

Particularly with paths such as this:

(This is mostly a Godot issue more than anything though, and again, if the Agent had some sort of inertia it would probably fix itself)

---

I was thinking, now that we got this very rudimentary base, if it would still be possible to make the baking be "Chunked", however with some changes to the original implementation I suggested:

1. We get the cube we want to work with as an AABB variable and also get either all of the voxel terrain or the affected block and neighboring blocks.
2. We clear out all the vertices and polygons in the cube (and probably re-index the polygons that are outside the affected cube)
3. Then we bake (using a different NavigationMesh as we don't want to overwrite our old one), this bake will have its filter_baking_aabb to be the AABB we have.
4. Once the bake is done, we "stitch" this new Navmesh with the old one. How we do it is different to how I originally suggested it: instead of "extending" the vertices so they are at the edges and somehow merge them, we can do something easier, make new polygons that use the vertices on both sides, likely to be much easier to do and performant too. (Problem here would be identifying what vertices we want to use in a very efficient way)

I will start looking around and messing with things, but I'm quite unskilled with C++ so I will be slow, will try to make my code easy to read though, just so it's easier to optimize lol

[Zylann]

sounds like baking the entire terrain into a navmesh, instead of only updating the chunks that are different, is going to be a sizeable bottleneck in terms of performance.

It currently is because I havent optimized anything. The main parts that take time are:

• Gathering geometry from the terrain: I was lazy so I used mesh.surface_get_arrays, which is horribly slow. For terrain that data could be cached from the meshing step so it would just be there to grab for free (at the expense of unavoidable memory usage). It is also nearly possible to do this gathering completely off the main thread.
• Baking is not async. There is a way to run it asynchronously so it doesnt stall the main thread, just didn't use it yet.
• Transforming geometry (many meshes) to fit what the baker wants (a single bigass mesh with transforms applied and different winding). That can easily be moved out of the main thread as well
• [something I dont do yet but may have a hit too]: gathering props. I won't re-use any code from Godot here because I dont think it's thought to be used at runtime on a large scale. If I were to support the same options as on NavigationMesh, in the worst case I would have to parse the entire scene tree to gather stuff and stall the renderer to get mesh data. I personally find this horrible to do at runtime. So I will likely focus on one of the settings, which is to require props to be part of a specific group, and geometry on these nodes may be prepared and simplified such that it should be very fast to gather them on the main thread so that the rest of the work can be done on a separate thread. The least time is spent on the scene tree, the better.

Also, I chose a single-navmesh approach for now because it is A LOT easier to do. Chunking would be ideal in theory, but from what I've seen so far in my experiment, it brings up tons of problems and even makes certain things worse, so I haven't figured it out.

the remeshing of the navmesh causes AI paths to be completely recalculated, because even the part of the navmesh the AI was standing on gets re-updated, having a big tendency to get stuck

This is unfortunate, and I'm afraid this will keep happening even if chunking is implemented. I think that's a Godot issue. Godot should keep the last path it was using and eventually re-path without interrupting agents, otherwise it defeats any attempts at dynamically updating the navmesh. With chunks you could do any edit in a chunk agents are going through and that would bother them as well, which is dumb.
Personally I haven't often used agents. Back in Unity (which uses Recast too) they have a bunch of stuff built-in, but their movement model makes a lot of assumptions, is too restrictive and robotic, not viable for anything that isn't kinematic. Instead I only got the paths and managed the following myself using context steering and other custom logic, which also allows to control how the AI actually moves and plans.

I'm using an agent that doesn't use gravity nor inertia on purpose, as that's probably the most sensitive agent to changes possible, though even when re-enabling the gravity, it still gets stuck on wilder terrain (Using Noise Terrain).

Not much the voxel engine can do about this, you have to tweak navmesh settings and the way your agent follows its path maybe.

I tried some chunking today on a separate project without the voxel engine. I used a very simple heightmap terrain divided in chunks and one region per chunk. I guess I eventually got it to a working-ish state, but it was awful:

• For each chunk, I had to take 3x3 neighbor chunks and combine all their geometry into one NavigationMeshSourceGeometryData3D, which in GDScript is faster than looking manually at every triangle and reject them if not close enough to the chunk. I really don't like the fact Godot requires a single NavigationMeshSourceGeometryData3D to bake navmeshes. If that were possible, I could have separately prepared the geometry of each chunk and not have had to re-combine them for every combination of neighbors. Although maybe that's because Recast wants that?
• The sync error kept happening over and over, until I found out if I trigger a bake during _ready, the NavigationMap itself would NOT return the cell_size and cell_height from ProjectSettings and instead use defaults. Which then caused the error one frame after because then it would get updated and of course mismatch with what was baked a frame earlier.
• filter_baking_aabb actually acts like a wall of geometry, so navmeshes were still "inset" within it and didn't touch each other. So I had to expand AABBs by agent_size to compensate.
• Even though most navmeshes looked connected, I couldn't tell whether they actually were. I haven't tried requesting paths yet.
• Some polygons at chunk borders had a magenta thick line across them. I don't know what that means.
• Some chunks that should have been connecting seamlessly still ended up with polygons that don't match, causing a gap which I guess will not be walkable. I don't know how to fix that. Moving vertices of the navmesh afterwards is not an easy option because there might not even be the same amount of polygons to stitch and could lead to an invalid navmesh.

Sorry I got no screenshot of that project as I'm on another computer.

We get the cube we want to work with as an AABB variable and also get either all of the voxel terrain or the affected block and neighboring blocks.

As you might have figured out from my first experiment, that means instead of gathering everything once, gathering will have to run for every chunk AND its theoretical 26 neighbors, overall resulting in much more work done by the CPU, due to redundancy of data and lookups. Though it's of course true that incremental changes are then cheaper.

We clear out all the vertices and polygons in the cube (and probably re-index the polygons that are outside the affected cube)

As seen in my experiment, I'm not sure of the relevance of manually filtering triangles that are not within the baking AABB. The baker can already do it for us, the downside is there is a lot more data to fetch from the gathering phase because Godot wants a single big list of vertices and indices. So I don't know what will turn out to be faster.
Also raw props (nodes in the tree) are not chunked, but they also have to be in that single list of vertices and indices. Either we'd have to iterate them all and keep only those close enough, or make them part of some data structure to quickly get which ones affect every chunk.

Once the bake is done, we "stitch" this new Navmesh with the old one

In my experiment I did this with multiple regions, so I had multiple navmeshes, I didnt try to make a single one. Though as mentionned, there are weird problems I dont know how to get rid of.

we can do something easier, make new polygons that use the vertices on both sides, likely to be much easier to do and performant too. (Problem here would be identifying what vertices we want to use in a very efficient way)

Not sure if that's a good idea given the API we have access to. Also I don't know if that's doable efficiently. Navmesh polygons in each chunk should line up and therefore be detected by the navigation map connection logic. That said, I don't know how fast that system is (one more thing the single-navmesh approach doesnt need hehe)

[ARandomKrilios]

I feel slow seeing the progress you're doing ^^'

the remeshing of the navmesh causes AI paths to be completely recalculated, because even the part of the navmesh the AI was standing on gets re-updated, having a big tendency to get stuck

Going back to this point, what happens is that the NavigationMesh visibly changes whenever it updates, so with a chunking method it wouldn't happen as often, or at least not cause it to get stuck.

Some polygons at chunk borders had a magenta thick line across them. I don't know what that means.

Thick magenta lines means that the two navmeshes are considered as "Connected" automatically by Godot, which is one benefit of having each "Chunk" have its own region, as basically Godot does the stitching for us, I do wonder if it would actually be better or worse, I imagine it would end up being more memory intensive than just having one Region.

[Zylann]

Thick magenta lines means that the two navmeshes are considered as "Connected" automatically by Godot, which is one benefit of having each "Chunk" have its own region, as basically Godot does the stitching for us, I do wonder if it would actually be better or worse, I imagine it would end up being more memory intensive than just having one Region.

If that's so, then it's spectacularly bad, as very few polygons were connected, despite almost all of them were visually touching each other... (excluding the few ones that unexpectedly deviated)

[ARandomKrilios]

Yes, it is bad, cause it can only connect if:

• The vertices are in the Exact Same Location
• Or if the sides are within an adjustable margin in project settings navigation/3d/default_edge_connection_margin (by default it is really small)

I actually considered suggesting the idea of having one Region per block/chunk, but then figured that might've been a "naive" solution, though at the same time, it would get rid of having to check what polygon should be merged or created.

[Angular-Angel]

I've been working on a navigation solution for my game using one region per chunk, and I think it's workable. There are some difficulties - in particular, you have to turn off 'Use Edge Connections', which means that it can only connect an edge is both vertices that define the edge are in the same spots, and it's still a little slower than I'd like. I added a proposal for Godot to make adding new nav regions more efficient, and I think it'll get added eventually: godotengine/godot-proposals#9381

You can see my current effort here, written entirely in GDScript. It does greedy meshing for the nav mesh atm, which doesn't actually work, but it at least demonstrates the performance is manageable: https://gitlab.com/AngularAngel/omnicraft-infinite-war/-/blob/master/Scenes/Game/NavigationGenerator.gd?ref_type=heads

[Zylann]

I've done some more investigation regarding the sync error: godotengine/godot#85548 (comment)
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.

[Angular-Angel]

I tried out Zylanns current experiment, and it works great! Other than the lag spikes on generating new chunks, anyway.

Oh, no sync errors for me, either. No idea what the deal with those is.

Though actually, now that I think of it, I occasionally got sync errors with my own solution? So, maybe that's just something that happens when working with nav meshes. :/

[Zylann]

Your terrain is blocky, so maybe that plays a role here. What I'm testing with is a relatively intense smooth terrain.

[Zylann]

I noticed that while I can thread most of the baking, Godot's NavigationServer still does something afterwards in NavMap::sync, which is very slow and of course runs on the main thread by default. I don't know what this sync is and why it's so slow, almost as much as the baking itself :( Sync what? I wonder if that can be configured to run on a different thread?

Sadly it seems there is nothing to run that on a thread. It runs directly in the middle of physics process, it's just going to stall all the time for every change we make to a navmesh (chunked or not):
https://github.com/godotengine/godot/blob/29b3d9e9e538f0aa8effc8ad8bf19a2915292a89/main/main.cpp#L3980

(one extreme workaround that starts flying in my head is to implement a whole navigation query system entirely in the voxel module to be better tailored to streaming procedural open-worlds, and completely skip Godot's regions system... but that would be really, really sad)

[Zylann]

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.

[Zylann]

Quick update:

Godot just merged a PR that allows plugins to register custom navmesh geometry sources: godotengine/godot#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 #610 (comment)

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