NavmeshRegions seem to not be quite thought through

[0x0ACB]

Godot version

4.1.1

System information

Issue description

So I have been playing around a bit with the new navigation system for the last couple of days. But it seems I either don't understand how it's supposed to work or it has some major flaws. Since nobody on Discord answered any of my questions and there is no dedicated navigation channel I am now making this issue in the hopes of either understanding what I am doing wrong, or demonstrating what is wrong with the current system.

Two areas in the same plane

With that said let's start with a very simple map; Suppose we have a map with 2 areas, where one of the areas is sometimes non-walkable:

Now what I gather from the doc it should be pretty simple to implement a navigation mesh for this. We just create 2 navigation areas and assign them to each of the 2 meshes, bake the navmesh and oops:

The navmeshes can never overlap since they don't consider the edge geometry. The only possible way I can see to fix this is to do this:

and then try to painstakingly adjust the baking aabb; which honestly could use some editor gizmo similar to the box shape to define. and what's the aabb offset for anyways? The only point in the code I could find where this value is used is here:

godot/modules/navigation/navigation_mesh_generator.cpp

Lines 636 to 639 in 237bd0a

	Vector3 baking_aabb_offset = p_navigation_mesh->get_filter_baking_aabb_offset();
	cfg.bmin[0] = baking_aabb.position[0] + baking_aabb_offset.x;
	cfg.bmin[1] = baking_aabb.position[1] + baking_aabb_offset.y;
	cfg.bmin[2] = baking_aabb.position[2] + baking_aabb_offset.z;

where its added to the baking aabb position. So why not set that one correctly? The purpose of this parameter eludes me.

Then the doc also gives conflicting information about how areas are merged. Using NavigationLayers states:

If two regions have not a single compatible layer they will not be merged by the NavigationServer.

Support different actor area access has a screenshot with only the "DoorOpen" layer enabled on the door mesh.

Looking in the Editor "Support different actor area access" seems to be correct because it draws the connection and I also can't find any filtering on layers in the code that is connecting the different NavigationAreas. Given that you couldn't actually query for a path that is either including or excluding doors the doc in "Using NavigationLayers" seems to be wrong.

Also I have yet to find a way to create an actual door with this technique. Everything I have come up with so far would require placing 4 regions around the door and then one at the door, since you can't really carve out the door of the navmesh. And then you still need to manually adjust the baking aabb in just such a way that you somehow manage to create a connected navmesh.

Two areas in different planes

Now in the example above we basically had a 2d mesh that we wanted to connect. Now lets consider a slightly more advanced 3d scenario where we have a water plane and some ground and our agents can go through the water only if they meet certain conditions. I don't know maybe they can't swim and need to pick up some floats first. In any case here is the basic level:

(I made the water plane black so its easier to see the navmesh later)

Now, from our first try, we already know that placing the ground in one NavmeshRegion and the water in a different one is not going to work. In this case, the water mesh would even just clip straight through the two "ramps" since they would not be considered as part of the baking. So again, we have to painstakingly adjust some baking aabb to somehow try and make this work.

So I try to manually set the 2 baking aabbs of the regions (again why is there no editor gizmo?) and build the maps. But its now a bit more complicated because of the angled surfaces. Even offsetting the 2 regions by Agent Max Climb + Cell Height. The water navmesh just clips through the ramps?

(The water plane is at y=0)

Only if I put it at Agent Max Climb + 2xCell Height does the water mesh no longer clip through the ramp. Fine, I guess I could just place the visible mesh a bit higher/have my water collision a bit lower. But I can't seem to get the two meshes to connect at all. Even if I increase the connection margin. Moving the meshes around it seems something has bugged out because they only connect once they are quite far apart?

This by the way also only "works" in the editor. Once I actually start the map the connection disappears:

And forget getting both ramps to connect at the same time. So I also would need to create separate meshes for each piece of geometry that leads into the water. No matter what I tried I couldn't get this map to work at all.

rcMarkXXArea

Now, given the limitations of NavigationRegions (only square regions) and all the issues I have faced so far trying to implement 2 very basic maps. I do wonder why rcMarkXXArea is not exposed in any way. This seems like the obvious solution to all my issues, you can mark door areas and other temporary "unwakable" areas, you can easily mark areas like water which might have a different pathing cost or be unpathable in some circumstances and you can have way more complex shapes than "Cube". Also, given that the namesh is baked considering all the geometry surrounding the areas, everything is correctly connected.

Parsed Geometry Type defaults to MeshInstances

This is another thing that I don't quite understand. Why does this default to visible Geometry? Given that the Collision is actually the only thing that can impede your pathing and that using the visible geometry violates every point related to navmesh baking in this list I do wonder why it's set like that.

Using the PhysicsServer to gather source geometry

Using the SceneTree to define what geometry to consider when baking the navmesh is fine for very simple maps, but if you have more complex maps with a lot of objects and layers, it seems to me having the option to use the PhysicsServer to query for all Colliders in the NavigationRegion bounding box would be a way better option. Sure you can theoretically implement this yourself using some areas and then assigning groups to the included nodes or using NavigationMeshSourceGeometryData3D, but the first one kinda pollutes the node groups and the second one does not allow to directly add CollisionShapes and also kinda seems like an afterthought for compatibility reasons with the older system since it's never mentioned in the Navigation Manual as far as I can tell.

Final thoughts

All in all, it seems to me that I either overlook something crucial, or the current implementation of NavmeshRegions got "lost in translation" between all the changes that have been made over the last couple of revisions.

Steps to reproduce

Actually try to use multiple NavigationRegions

Minimal reproduction project

navtest.zip

[0x0ACB]

I have now modified the navmesh baking a bit based on the tile building demo of reacast

https://github.com/recastnavigation/recastnavigation/blob/d95483a99351f32e32ac3ca3ce27c540cd979205/RecastDemo/Source/Sample_TileMesh.cpp#L826-L828

and

https://github.com/recastnavigation/recastnavigation/blob/d95483a99351f32e32ac3ca3ce27c540cd979205/RecastDemo/Source/Sample_TileMesh.cpp#L855-L858

by adding

	cfg.borderSize = cfg.walkableRadius + 3;
	cfg.bmin[0] -= cfg.borderSize * cfg.cs;
	cfg.bmin[2] -= cfg.borderSize * cfg.cs;
	cfg.bmax[0] += cfg.borderSize * cfg.cs;
	cfg.bmax[2] += cfg.borderSize * cfg.cs;

before the call to rcCalcGridSize

It seems that at least helps with the water mesh, if I increase the connection margin to 0.5 I now get a correctly connected mesh.

Do note however that the walkable areas below the ramp do not disappear no matter how high I set agent height since the ramp is not fully included during the baking.

I also noticed that changing the connection margin does not seem to update in the editor, making finding the correct parameter a bit more difficult than it needs to be.

EDIT: actually this only seems to help in that specific situation. If I slightly change the angle on one of the ramps it no longer connects

[sehoffmann]

We also tried using Navmesh Regions in the past and failed to get them to work properly.

[MJacred]

I do wonder why rcMarkXXArea is not exposed in any way.

That "area" is part of the build process. So if you mark it unwalkable here and you want it to be walkable later, you'd need to re-bake the whole navmesh.

What you probably want are poly area flags and ability poly flags, which require Tile-support, afaik. At the very least this requires recastnavigation's Detour. Which Godot does not include.

For some more info, see here: godotengine/godot-proposals#5116

Either this needs to be implemented with a custom solution on your end. In Godot itself. Or introduce Detour to Godot.
Or you use https://github.com/TheSHEEEP/godotdetour (though you'd need to update it for Godot 4). Which will cost you some features that only Godot's implementation has, such as merging areas to e.g. allow NPCs to move over gaps via moving platforms.

[0x0ACB]

With rcMarkXXArea you do not need to rebuild the navmesh. I am currently using it for exactly this use case with the water. rcMarkXXArea sets area flags on the polys during the build process. Which can then be used when finalizing the navmesh to add poly flags. These poly flags can then be used in the navmesh query to exclude certain areas or increase their cost. rcMarkXXArea will by the way also cause polygons to be cut on the borders of areas. None of this requires tile support by the way.

https://github.com/recastnavigation/recastnavigation/blob/1adf911a0949cd9f4688da2631843781ad4d5942/RecastDemo/Source/Sample_SoloMesh.cpp#L657

With that being said. I do not particularly care whether or not you expose rcMarkXXArea or not. I simply do not understand how I am supposed to do doors and water with the current system. According to the doc at least doors are supposed to work.
So let me ask again. How am I supposed to mark a water area as water and have it connect to other parts of the navmesh with the current solution? I still don't get it. Neither do I get how I am supposed to do a door or any other kind of cutout? In fact, the only solution I see in the current version is to actually rebuild the navmesh.

Even just having areas connect is quite difficult unless you have platforms that overlap each other because the edge regions are not considered during the build process and there is not really any solution to have the navmesh extend to the edge as far as I can see. Just look at my very first example with two "platforms". They simply do not connect unless you manually extend the bounding box, have the navmesh include both "platforms" and have them sitting right next to each other.

[MJacred]

how I am supposed to do doors

This should help you:
https://youtu.be/lOS2SptNiBM?t=169

how I am supposed to do [...] water

Hm... without Detour, you can limit pathfinding using agent.navigation_layers to define which they should ignore (aka "cannot swim on water layer"). Your water NavigationRegion needs to have the appropriate layer. Then it should work.

The navigation mesh beneath your "ramp" cannot be avoided if you don't bake them together. You could duplicate your ramp and form it as a block and include it into the other NavigationRegion's baking (a block has a steep 90° incline so it should be ignored. If it's high enough the agent cannot use it as a "step") to prevent.
An in-house equivalent would be something like the AABB filter baker shown in the video at 4:00 but as a separate Godot node, where you define an AABB space and "exclude" that area from the baking process. This you could request with a godot proposal. Though you'd still need to shape your block.
In the meantime, maybe this could help you (though that depends on your setup): https://www.youtube.com/watch?v=_QzzaajTHnw (https://github.com/mohsenph69/Godot-MTerrain-plugin).

Does that address your problems?

[0x0ACB]

This should help you:
https://youtu.be/lOS2SptNiBM?t=169

Yeah, that is exactly what I think is not thought through. Do you not realize how needlessly complicated that is? So first I make everything a child of my "door", set a correct AABB, which as I have mentioned you have to somehow guess the values so it lines up correctly, bake the mesh, and then move the stuff back out and set up everything correctly. And what do I do if I slightly change the position of the door? Have to do everything again. Also this kind of workaround, and it's just that, a workaround; requires converting all the geometry of the level just to get the door mesh baked. I wouldn't really consider this working in any form.

Hm... without Detour, you can limit pathfinding using agent.navigation_layers to define which they should ignore (aka "cannot swim on water layer"). Your water NavigationRegion needs to have the appropriate layer. Then it should work.

I understand this part, however getting the mesh into a different layer in the first place is what I am struggling with.

The navigation mesh beneath your "ramp" cannot be avoided if you don't bake them together. You could duplicate your ramp and form it as a block and include it into the other NavigationRegion's baking (a block has a steep 90° incline so it should be ignored. If it's high enough the agent cannot use it as a "step") to prevent.
An in-house equivalent would be something like the AABB filter baker shown in the video at 4:00 but as a separate Godot node, where you define an AABB space and "exclude" that area from the baking process. This you could request with a godot proposal. Though you'd still need to shape your block.
In the meantime, maybe this could help you (though that depends on your setup): https://www.youtube.com/watch?v=_QzzaajTHnw (https://github.com/mohsenph69/Godot-MTerrain-plugin).

Well, if I bake them together, the ramp is in both the ground and the water mesh, which means they don't connect (since they overlap). So this does not work.

Painting it is not an option since the map is generated dynamically.

The block solution is somewhat workable, and I was thinking about this for some other parts, mainly for dynamic obstacles. But this would require me to mark all the ramps somehow. In the sample I gave that is simple, however in my game I am using a height map for most of the terrain, so this is really also not workable.

Like I said, I still think the current navigation system is severely limited for anything beyond very basic maps. And without any good reason. The standout feature is being able to dynamically connect navigation regions, however the only way to create navmeshes that make this possible is to either use the workaround from your first video, overlap the platforms so the navmeshes touch, bake the navmesh with a larger platform, or somehow manually extend the navmesh to the edges. And vertical layering does not seem to be possible at all. which means doing any kind of water plane is impossible.

[MJacred]

Do you not realize how needlessly complicated that is?

That is plain obvious.

an advanced proposal would be to define a NavigationSplitter3D for "door"/"passage"/"corridor" (AABB or whatever) and auto-cut a NavigationRegion into 3 (or more, depending on your count of NavigationSplitter3D nodes) and the edges will be automatically aligned perfectly.

What it comes down to is that it simply takes time to implement all of this. It's not that it isn't obvious. The navigation code would need more contributors to get this done more quickly.

[0x0ACB]

I don't think we need to have a splitter node or whatever. I would say a solution similar to rcMarkXXArea would be the best way. Just place a shape around your door/water area whatever. Then have it either create a cutout nav region or mark it inside the navmesh. The cutout approach would mean that bake needs to return more than one mesh though.

I still think not basing included geometry on the SceneTree but rather the collision geometry that is inside your navigation region would work better. Then you could easily just define the nav regions using a collision shape. Gather all collision data inside that shape (probably best to slightly extend it so you correctly build the edges) and then use that. This avoids the whole mess of somehow trying to correctly place your nav regions inside the SceneTree and neatly fixes all edge problems as well.

[MJacred]

If Godot's current implementation is not enough, I think it would be better to draw up a clear godot-proposal and state what your needs are and how they could be achieved instead of an issue

[0x0ACB]

Yeah I will do that. I was hoping I was just missing something