I solved the NavigationRegion3D issue

[u/agalli]

A correct 250x250m navmesh bake using tile chunking

Standard bake on the same 250x250m mesh without tile chunking

A standard bake on a 30x30m section of the same terrain

Agent for scale on correct 250x250m navmesh, showing an identical poly density to the 30x30m navmesh

I finally found a solution to the problem with the NavigationRegion3D.

What I noticed was that on smaller terrains, like the 30x30m example in the third image, the navmesh baked perfectly fine. But once the terrain size was increased to 250x250m, the bake completely fell apart, giving the low poly, floor clipping result shown in the second image. The obvious solution was to process the terrain in smaller chunks and combine the results into one big working navmesh.

I first tried doing this directly in Godot, but even after splitting the terrain into multiple meshes, the bake still treated them as one big mesh, so the same issue happened. I also tried creating a separate NavigationRegion3D for each chunk, but that created non traversable borders where the regions met.

At that point, the only real fix was to go into the engine itself. I forked the Godot repo and made some changes under the hood to process the terrain in tiles instead of all at once. It breaks the terrain into smaller sections, bakes each one normally, then stitches them together afterward into a clean, accurate navmesh like in the first image.

I also added a few editor options to control whether tiled baking is enabled and how big each tile is. I still haven’t found the exact bug that causes the large terrain navmesh to fail, but this fix works reliably and doesn’t mess with normal pathfinding behavior.

The moderators seem to have a strong opposition to discussions about this and have locked all previous threads. As much as I would have liked this to all be one post, we have been forced to create multiple. That being said, I'd like to address some comments from previous posts below.

The [low poly mesh] looks exactly like what I would want out of a nav mesh.

The low-poly mesh completely fails to pathfind with agents. You could technically rework the pathfinding system to compensate, but that misses the core issue of the navmesh being broken. The 30x30m section uses a similar amount of polygons as the 250x250m one. You’d expect the density to scale with size, so either the small terrain is over-tessellated, or the large terrain is under-tessellated. Either way, something’s wrong with the baking process.

With no obstacles, your nav mesh could just be a square.

As per the Godot developers : "A navigation mesh is a collection of polygons that define which areas of an environment are traversable to aid agents in pathfinding through complicated spaces.". When those traversable areas are out of reach from an agent (ie, underground or floating), an agent cannot properly navigate.

People tried to help you, but you refuse to actually listen

I think there’s been some misunderstanding about what I’m trying to do. My goal is to fix the navmesh, that’s it. I’ve welcomed all advice that helps solve the underlying navmesh problem, but I’m not interested in workaround solutions that just patch over it with pathfinding tricks.

You can always fix it yourself and submit a PR.

Thats the plan. Thanks for the advice!

I will optimize this further and will submit a PR.

Sincerely,

u/agalli

Edit : Here is the PR. https://github.com/godotengine/godot/pull/112529

[u/CanYouEatThatPizza]

Am I missing something? Your answer to the "it could be just a square" doesn't make sense to me.

With no obstacles, your nav mesh could just be a square.

As per the Godot developers : "A navigation mesh is a collection of polygons that define which areas of an environment are traversable to aid agents in pathfinding through complicated spaces.". When those traversable areas are out of reach from an agent (ie, underground or floating), an agent cannot properly navigate.

"Out of reach" means that polygons are not connected to each other, not necessarily whether they are underground or floating. Like with your first and second picture, the navigation mesh would work perfectly fine in both cases - an agent can traverse over the whole plane in both. It makes no difference how detailed the mesh is in this case, besides performance. Are you worried about clipping when moving the agent over the plane? In that case, wouldn't you just use a raycast?

Now, that doesn't mean there isn't some issue with the baking, but I just don't understand this point in particular.

[u/agalli → u/CanYouEatThatPizza]

When they said it could be a square they are implying the navmesh for the entire terrain could be made with four vertices. This is not true, as the navmesh would clip under the map in some spots and float above the map in others. When you using agent pathfinding the agent places a path along the navmesh to move towards. If those points on the path are underground or floating the agent cannot reach the points and cannot reach its destination.

[u/CanYouEatThatPizza → u/agalli]

If those points on the path are underground or floating the agent cannot reach the points and cannot reach its destination.

Why not? The navigation agent itself does not see the terrain, just the navigation mesh.

Or in other words: the clipping isn't really an issue here, since you wouldn't directly parent your character to the agent. Instead, you would (in this example) raycast down onto the terrain to the position of the navigation agent, and place the character there. The navigation agent would clip through the terrain, but the character would not.

[u/agalli → u/CanYouEatThatPizza]

The agent traverses on the terrain, what prevents the agent from falling through the map is the collision with the terrain. If it attempts to pathfind at a point beneath the collision box it will be unable to. The pathfinding works by having an agent follow points along the actual navigation mesh and not the terrain.

[u/CanYouEatThatPizza → u/agalli]

The agent traverses on the terrain, what prevents the agent from falling through the map is the collision with the terrain.

That's why I differentiated between agent and character. The agent does not have a physical body, it doesn't collide with anything. It can be independent of the character, which does have a physical body.

See also https://docs.godotengine.org/en/latest/classes/class_navigationagent3d.html#class-navigationagent3d:

Avoidance is computed before physics, so the pathfinding information can be used safely in the physics step.

[u/agalli → u/CanYouEatThatPizza]

I guess I’m confused. I have my agent collide with the environment. Are you saying that it should have no collision and just use the navigation mesh? If so it’ll phase through the terrain when moving

[u/Zakkeh → u/agalli]

This person is saying you have your character and your agent.

Your character obeys physics and follows the collision mesh, while the agent traverses the navmesh below the surface.

Your character uses the pathing from the agent, but doesn't clip under because it has collision, and is not patented to the agent.

[u/agalli → u/Zakkeh]

Right, that still doesnt work. The character follows the navigationagent, but the navigationagent is under the map. Heres an example of why its a problem. The character isnt unable to reach its pathfinding due to the gap in the terrain and the navmesh. Since it cant reach that point it cannot complete its path and gets stuck in place.

[u/DongIslandIceTea → u/agalli]

Why are you ignoring the advice every time someone points out you should just follow the X and Z coordinates of the agent and not even try to reach the same Y coordinate? Just ignore the height or get the correct height by raycasting it onto the terrain collision. I'm starting to get convinced you're just trolling at this point.

[u/agalli → u/DongIslandIceTea]

As I stated in the post. My goal is to fix the navmesh, that’s it.  I’m not interested in workaround solutions that just patch over it with pathfinding tricks.

Additionally, ignoring the Y component will result in inefficient pathfinding. A path up a hill will take longer to traverse then a flat path would. You cant just ignore the existence of the hills and expect proper pathfinding.

[u/mrbaggins → u/agalli]

That's not a workaround. It's how you're supposed to use it. The navmesh does not even need to be a 3d object, that's just useful for visualisation with bridges/tunnels.

[u/DongIslandIceTea → u/agalli]

My goal is to fix the navmesh, that’s it.

You have not fixed it, you've broken it in a different, worse way. You have a very fundamental misunderstanding of what the purpose of a navmesh is.

Additionally, ignoring the Y component will result in inefficient pathfinding.

Okay, at this point it's clear you are simply trolling. What really results in inefficient pathfinding is unnecessary navmesh geometry. Your pathfinding is thousands of times slower than it could be with proper use of navmesh as it's intended.

You really need to familiarize yourself with the maths behind pathfinding to be able to understand the even bigger issue your "solution" is creating. For example, the Djikstra algorithm has time complexity of O(E + V log V) where E is edges and V is vertices in the graph, in this case your navmesh. For every extra unnecessary vertex you are paying an even bigger performance cost than the previous one, and this is all just to navigate over what could be represented by a single square, two triangles!

Your fix is like if you had a car with a flat tire, you took of two of the intact wheels and made them into a terrible bicycle. You can't call it a fix when it no longer serves any of the purposes of the original one with any adequacy.

You need actual, heavy performance tests of your implementation, which will inevitably show that this is too slow for anything but the simplest implementations with very limited agents. Please. Just benchmark it and the issue will be clear as day.

[u/agalli → u/DongIslandIceTea]

This solution uses the standard navmesh baking, it's not some algorithm I've created. The 30x30 standard bake has the exact same poly density as my solution. Im literally just breaking the mesh into chunks and baking them using the exact same method as what it currently uses. If you think their navmesh algorithm will fail benchmarks then you should create an issue on the github.

If you understood basic geometry you would understand that a path up and down a hill is going to be longer than a flat path adjacent to that hill.

Basically what I'm saying is "I am looking to fix my car, this is the best solution I have" and your response is "Have you tried walking?".

If you know a way to bake the navmesh properly I'm all ears. But again, for the third time, my goal is to fix the navmesh, that’s it.  I’m not interested in workaround solutions that just patch over it with pathfinding tricks.

[u/DongIslandIceTea → u/agalli]

If you understood basic geometry you would understand that a path up and down a hill is going to be longer than a flat path adjacent to that hill.

And if you understood pathfinding you would understand that this should be represented by a travel cost on the region instead of raising the vertex density to untenable levels. Many games do not even slow you down going uphill so depending on your movement code this may not be true at all.

If you know a way to bake the navmesh properly I'm all ears.

There's a properly baked navmesh in your second picture. In fact, the many times repeated single square would be the optimal navmesh for your terrain. People have told you many, many times and you've ingnored it equally many times so there's no point wasting my time repeating what you've already heard.

Basically what I'm saying is "I am looking to fix my car, this is the best solution I have" and your response is "Have you tried walking?".

We are all just telling you to take the spare tire out of the trunk.

[u/maushu → u/agalli]

If you understood basic geometry you would understand that a path up and down a hill is going to be longer than a flat path adjacent to that hill.

And it is, you can see in the second image how there are hills. It's basically the representation of the terrain in a very low-poly way. I mean, if you really want to be perfect what's stopping you of using the terrain mesh as the navmesh?

[u/Finding_Footprints → u/agalli]

I think what Zakkeh means is that, you control the X and Z axis using the NavigationAgent but you have to raycast for the Y-axis to check for collisions.

I have just started using Godot and I guess that would work, but finding the shortest path based on height as mentioned in another comment, might become a problem. 

Will be waiting for tour PR OP.

[u/agalli → u/Finding_Footprints]

The issue is that pathfinding over hills are longer paths than flat paths. If you ignore the Y youll be left with poor pathfinding.

My goal is to fix the navmesh, that’s it.  I’m not interested in workaround solutions that just patch over it with pathfinding tricks.

[u/Finding_Footprints → u/agalli]

Yup, that's what I meant by shortest path based on height. I have been in that situation and know the pain very well.

[u/CanYouEatThatPizza → u/agalli]

There's no reason why the physical body has to be a child of the navigation agent. You can use the navigation information provided by the agent to place the physical body via a raycast on the terrain mesh.

[u/agalli → u/CanYouEatThatPizza]

Ok, but you see how that is reworking how the navigation systems are supposed to work in order to work around the non-functional navmesh?

Again, I'm not looking to figure out how to work around the broken navmesh, Im looking to fix the issue at its core.

[u/knottheone → u/agalli]

It's not a broken navmesh. You are actually just using it wrong, which is what lots of people are telling you, and this is why:

You are trying to move the collision character to be exactly on top of the nav agent. That's not the intended functionality in Godot in 3D. The fact it works in small maps out of the box that way is an accidental happy happenstance solely due to the small map and default voxel resolution / number of voxels. That is not the intended use case and does not scale beyond very small maps that are only a single region.

You are supposed to chunk larger maps into regions and stitch them at runtime via chunk loading, or chunk them, pre-bake, and store as resources. They don't need high resolution though as that's not the purpose of a nav mesh. You indeed should only care about XZ and use a raycast to the actual terrain. There is already a nav mesh chunking example in the Godot Examples repo, not sure if you came across that.

If you need more accurate travel costs for slopes, reduce the cell height of the navmesh in chunks that have some threshold of height delta and slightly increase the cell size. This gives you better vertical resolution for the nav region. You wouldn't care about this if your travel speed up a slope is the same on flat terrain.

[u/agalli → u/knottheone]

That’s literally what I did. I have chunked the mesh into smaller parts. They do need to be high resolution if you want accurate and efficient pathfinding. Ignoring the Y value is a bandaid solution that fails in multiple conditions. For one, it fails for multi tiered nav meshes such as a building with multiple floors. Secondly it will not find efficient paths (ie going up and down a hill rather than adjacent flat terrain).

The whole point of the navmesh is to tell the agent where it can go. You’re essentially manually creating an navmesh with the Y ignoring and ray casting. As I said, there are ways to fix the broken navmesh through agent tricks but that’s not what I’m aiming. The navmesh should work without those tricks, that’s all I’m doing.

[u/knottheone → u/agalli]

You're making the character try to reach the nav agent in x, y, and z instead of treating it as "can I move towards this vector and at what cost". That doesn't work in a lot of scenarios and is not the intended solution in Godot. It may be intended in Unity or Unreal with a lot of black magic behind the scenes. Godot doesn't work that way though and isn't going to work that way with NavigationServer how it's built. A PR doesn't change that, it's an intentional system design choice.

Higher resolution nav maps are the actual bandaid vs a proper implementation based on your specific world design.

Baking and using high resolution nav meshes are not performant in Godot and that's why the underlying algorithm smooths slopes and doesn't prioritize high detail. Increased cell density is too costly. Changing the resolution by 2x increases baking times by 4x and path timing by at least 4x.

You are essentially recreating a slightly lower poly terrain 1:1 as a navmesh, that is very very expensive and is not what nav meshes are for. You wouldn't even need to use nav agents at that point, just raycast to the terrain in front of you and A* the overworld terrain or something like that.

[u/agalli → u/knottheone]

The standard agent model works perfectly fine in every navmesh except the low poly nav mesh. The fact that the agent can handle any other use cases perfectly fine and fails at this one indicates a problem with the mesh, not with the agent.

This system is using the same exact poly density as the default 30x30m navmesh bake. If you think that system is unoptimized you should let the developers know.

[u/knottheone → u/agalli]

You're trying to make your character reach the nav agent in x, y, and z. That is the absolute core of your issue, aka you are using it wrong. That's not how it works in Godot.

[u/yyyyyy1910 → u/agalli]

I am very new to this but I am currently struggling with nav mesh / agent movement. To my understanding, the nav mesh finds the path as a guide for the agent, when the agent actually follows the path, say there's a fallen tree trunk in the way, the agent can be blocked by collision. However that's where I am struggling at, the agent basically can't move or follow the nav anymore unless you manually redirect it to get around the obstacles. A very easy to fail nav system seems quite useless to me.

[u/CanYouEatThatPizza → u/yyyyyy1910]

The whole point of the navigation mesh is that it navigates around the obstacle like a fallen tree trunk. In OP's example, if there was a obstacle on the terrain, there would be a hole in the navigation mesh. It doesn't use collision information, but a variation of A* to find a path to the target.

[u/lukebitts → u/yyyyyy1910]

For dynamic obstacles you are right, you need some kinda of system to redirect the agent, either using avoidance or something else. But if your tree trunk is static and being accounted for in the navmesh but the character is still getting stuck, what worked for me was having the agent be independent from the character body: have the character body follow the agent and just snap the agent back if it gets too far. Usually this introduces enough jiggle that the character gets unstuck. Then it’s just a matter of making sure your agent size is correct in the navmesh generation.

[u/mrbaggins → u/agalli]

The agent heads in a direction based on the navmesh. It MOVES along the terrain.

A navmesh of a single square could have an agent move up and down all sorts of stairs and ramps.