Navigating different terrain types, i.e. making sub-NavigationRegions

[Gobra]

Description

Present state of the NavigationServer support covers all the basics and them some, however, there isn't anything about navigating different terrain types. Texturing terrain basically does that, i.e. defines various terrain subtypes within the terrain, however, navigation mesh baking still outputs one big mesh. Documentation mentions the way to define 'baking AABB' to produce multiple navigation meshes, but it won't work properly for some free-shape regions and even if it does - it's extremely cumbersome to build this sub-regions by hand.

Now the solution might be actually quite easy:

• Per each texture of the terrain define something like 'terrain type id', that will allow user to group visual material and 'physical' terrain types
• While baking, produce N regions using not only 'navigable area' map, but also texture map to identify whether specific portion of the terrain belong to the corresponding NavigationRegion
• Hopefully, that will produce auto-linkable meshes right away, although some extra work might be needed to make sure those meshes share edges

The last one is the biggest question that would need proper investigation, but the first seem really straighforward and prototyping the feature should be a quick one.

[TokisanGames]

What is a free-shape region? What is an example of such a region that won't allow AABB filtered navigation regions not able to be baked? What is it about your proposal that fixes that?

@tcoxon Comments?

[Gobra]

You have a terrain with grasslands, marsh and roads, all three suppose different travel speed (NavigationRegion.travel_cost in terms of Godot's data structures). Roads typically don't have rectangular shapes, they branch out very much like rivers and baking them as a set of sub-meshes would require an immense amount of work.

Same goes for any sub-terrain type that won't be rectangular or can't be approximates with reasonable amount of those. Imaging you have a snow/mash/desert part of the terrain in a form of a horseshoe - you'll need to to bake at least 5-6 sub-meshes with AABBs to approximate the shape.

Should you accept my proposal, baking mechanism would separate geometry of the terrain feed to NavMesh builder not only by 'navigable area' map, but by it's type as well, which will result all 'roads' being baked into a single and separate NavMesh of a proper shape. Same would apply to any other 'terrain id', and your output will be a separate NavigationRegion per each terrain type.

Once those regions are generated, one would simply need to assign travel_costs in the editor, and your NavigationAgents will now avoid walking through marshes and prefer walking on roads.

[tcoxon]

In my experience, getting Godot to generate navmeshes that share edges is incredibly difficult. It likes to cut off a border equal to the agent_radius. In my own project I gave up on that and had to manually set up NavigationLinks to join nearby regions. I wouldn't want this to be default for Terrain3D / based on texture ID.

I can see an argument for multiple navigable area bits though, with each bit producing a separate NavigationMesh in baking. Then you can manually set up the links and travel costs afterwards if the meshes don't join.

[Gobra]

OK, but it doesn't have to be the default behaviour.

Baker tool script can have a twin that would accept, let's say, a simple lookup table/dictionary that would link texture id <-> terrain type id, essentially doing the same, but without adjusting the Terrain3DTextureAsset structure.

This lookup structure can be saved as resource or a text file to make it re-usable, and during the baking the same proposal stands: just make N meshes sampling only geometry that belongs to the desired 'terrain id'.

To circumnavigate Godot's problem with altering the mesh - add an option to export just regular MeshInstance3D. It can be later processed to make a NavMesh by other means, like NavigationMesh.create_from_mesh() with some hand-made processing.

[Gobra]

I can think of an extra bonus for this proposal, should there be an option to export raw MeshInstance3D.

This way one would be able to draw a river bed and get it's separate mesh exported, for a purpose to make a waterway. Or to draw snow patches and has those meshes for drawing decals/bump texture to have the tracks on snow. Or export a meadow shape in order to adjust/extrude it later with external tools and have a 3D shape for some 3D fog/particle effects like magic butterflies or something.

There are many applications for having a piece of geometry that follows specific sub-type of the terrain.

[TokisanGames]

...an option to export raw MeshInstance3D.

@Gobra You can already bake the landscape into a mesh and godot can export it as gltf. It's not a good quality mesh unless you remesh it in blender, but it's usable for reference. The last comments on this are a bit off topic of navigation.

@tcoxon What's the conclusion on this? Is there something we should work on for Terrain3D in the future, or something users should do on their own?

32 paintable navigation layers that get baked into different navigation regions that the user can then customize travel cost and join themselves? Not by texture id. Set only by clicking a layer selector and painting.

Could be easier to bake multiple regions than messing with AABBs. If you just want a large bakeable area that is too big to get a good result with Godot's baker, you could paint two layers and set them at the same cost.

We have one navigation bit on the control map, but the GPU doesn't need it. We can free that up, and setup a separate navigable area map per region that is enabled only upon use and remains on the CPU.

[tcoxon]

What's the conclusion on this? Is there something we should work on for Terrain3D in the future, or something users should do on their own?

It's not something users can easily do on their own, as it would require modifying the generate_nav_mesh_source_geoemetry method on the Terrain3D class. So I think it would make sense for Terrain3D to have the suggested 32 paintable navigation layers. However I think we would need to see a prototype before we could commit to having this feature - I think there would be difficulty getting it into a releasable state, due to the brittleness of navigation in Godot.

To circumnavigate Godot's problem with altering the mesh - add an option to export just regular MeshInstance3D. It can be later processed to make a NavMesh by other means, like NavigationMesh.create_from_mesh() with some hand-made processing.

You can't bypass navmesh baking that way. If you create a navmesh directly from a mesh, agents will try walking up cliffs, because the mesh won't exclude impassable terrain. It has to be baked to cut those bits out, and it will be incredibly difficult to provide the guarantee that regions that share a border going into baking, come out of baking still with that shared border. Without such a guarantee, users' agents won't be able to navigate between regions in every case.

There's also geometry other than the terrain. If you put a wall or a tree in the scene, an agent won't walk around them unless the mesh has been baked to cut out the areas occupied by such objects.

Could be easier to bake multiple regions than messing with AABBs. If you just want a large bakeable area that is too big to get a good result with Godot's baker, you could paint two layers and set them at the same cost.

If there's any geometry in the scene other than terrain, you would still need to use AABBs.

Actually, that raises another question - how would we treat other geometry? If there are two painted regions on separate layers, but that have an overlapping AABB, any navigable object in the overlap would be represented in both nav meshes. IIRC overlapping nav meshes are not allowed in Godot so that would produce an error at runtime.

We would have to extend paintable navigation to all meshes/collisions, not just terrain. Which is making this start to sound more like a general engine feature than a Terrain3D feature. Like, if Godot's navmeshes supported arbitrarily shaped polyhedral nav regions, instead of just AABBs, we'd only need the one paintable navigation layer we currently have to support all proposed use cases.