Support Navigation Server

[TokisanGames]

Likely needs to just support collision. Perhaps temporarily baking a very large collision, long enough to bake navigation, then it can revert to a smaller size. Devmar had a video about it for his clipmap terrain.

https://www.youtube.com/watch?v=YiBrZMkCkLs

---

Update: @slashscreen has been working on experimenting with the nav server. They've setup a repo with a makeshift nav baker https://github.com/SlashScreen/terrain3d_nav_bake

Read discord conversation starting here https://discord.com/channels/691957978680786944/1130291534802202735/1136232663989100554

The current primary navigation server core developer was asked about using it on large terrains and this was the conversation:

Slashscreen currrently has a nav baker that can bake a large mesh in about 30 seconds and reports this information:

The general low-level process is as follows:

1. Geometry is parsed from the scene and put into a NavigationMeshSourceGeometryData3D object. This is done on the main thread, since the scene tree is not thread safe.
2. The geometry data and a Navmesh is fed into the NavigationMeshGenerator singleton to bake. This can be done multi-threaded, like I did, and/or a separate thread in the background.
3. The resulting Navmesh can then be put into the scene, usually by creating a NavigationRegion3D, but it looks like you may be able to add a mesh directly to the server without creating a new node.

• Theoretically, as you generate chunks for the collision, you could upload them to the Geometry Data directly, as it has an add_mesh function, and bake that in a separate thread. (A navmesh can be limited to a certain AABB, so you don't have to re-bake the entire thing.)

• I have also found that the slowest part of the process is parsing the scene tree, rather than baking. I like to lazy-load things, so how I would go about parsing the scene tree is to cast a big box on the chunk you wish to bake, grab all of the colliders hit, and add those to the Geometry Data too before baking, to allow for, say, buildings or whatever. To me it seems like doing that every so often won't be super intensive.

[SlashScreen]

should i polish the baker tool and put it in a PR?

[TokisanGames]

Sure, thanks. That will give us rudimentary support for now. Also please give me a writeup on how it works and how to use with the Nav Server that that I can put in the wiki. You can write it all as a comment on the PR with markdown and pictures and I can copy it over.

Place it in the addon tools directory next to the importer. Don't make it a plugin, just a standalone scene with a terrain3d node and your other nodes so they can load in the storage, bake, and save it out for use in other scenes like how the importer is set up.

Is it usable by a new user? Does it support disconnected regions / islands? How big of a space have you tested? Can it do 16 regions (4k)? Include any metrics on time/region or memory/region you've found.

I'm going to release 0.8.2 this weekend, maybe tomorrow. I'm still waiting on two pending PRs. Maybe you can get it in by then as an experimental feature.

[SlashScreen]

[tcoxon]

I've prototyped threaded runtime navmesh baking on my hacks branch here.

@SlashScreen's comments and research helped me an unbelievable amount.

The general design is:

1. Parse source geometry upon entering the scene. The length of time this takes depends on the complexity of the scene. This has to happen on the main thread, but (hopefully?) this can be hidden with a loading screen. Crucially, it does not include terrain geometry, otherwise the engine would pause a long time and probably crash.
2. Center an AABB on the player as they move around the scene. Generate geometry for the terrain within this AABB and add it to the source geometry. This happens on a thread, which is safe if we assume terrain is not modified at runtime.
3. Bake the source geometry (which includes the initial parsed geometry + the new terrain geometry) to a navmesh on the worker thread.
4. Back on the main thread, load the new navmesh into the nav server.

The demo plays without hitching, so it seems to work OK, but I'm unsure how well it would work in more production-realistic scenarios. I don't have any suitable scenes for testing it on. Is the initial pause caused by geometry parsing acceptable in realistic scenarios?

Not sure how well it performs on low-end / console devices. Can the threaded baking actually keep up with moving players in complex scenes?

https://github.com/TokisanGames/Terrain3D/assets/165720/28f0eee8-c4df-47e7-9b41-14cb02995819

[TokisanGames]

@tcoxon This is great and something we can start with. Ultimately, I'd like to move things towards more dynamic generation like this. e.g. Collision should have another mode where it only generates around the player in-game.

For a navigation mesh, I really like this approach where it is paintable. I'm allocating space in the control map for it. We can move towards this direction over time. I haven't played with navigation at all yet, so I don't know how complicated it is, or how it performs. Though we will need it for Out of the Ashes.

https://www.youtube.com/watch?v=_QzzaajTHnw

Code

https://github.com/mohsenph69/Godot-MTerrain-plugin/tree/master/gdextension/src/navmesh

What FPS do you normally get in the demo without any navigation mesh generation?

Center an AABB on the player as they move around the scene.

Of course it needs to be large enough to encompass any enemies that can see the player so they can navigate to them.

The demo plays without hitching, so it seems to work OK, but I'm unsure how well it would work in more production-realistic scenarios.

We'll find out as it gets tested.

Is the initial pause caused by geometry parsing acceptable in realistic scenarios?

Is this on startup of the scene? How long is it?

[SlashScreen]

@tcoxon super glad to hear my research helped. This demo looks good here; does it already support scene geometry? Realtime threaded baking is something a lot of games do, so I don't think it will be a problem in most cases (in my own game, the player moves rather slowly). Just in case, for times when the player would be whipping around the map like, for example, flying in a spaceship or a broomstick or something, you could add a way to temporarily turn off generation.

@TokisanGames I know you've been using heightmaps for collision, but perhaps this could be used instead?

[tcoxon]

@TokisanGames

For a navigation mesh, I really like this approach where it is paintable. I'm allocating space in the control map for it. We can move towards this direction over time.

Oh this is cool! I considered using this approach--glad to see others are already doing it. The two approaches could be combined quite well, and it would be simple to add the control map check to the prototype code.

What FPS do you normally get in the demo without any navigation mesh generation?

I did some non-scientific testing right now. While not recording my screen, I get 350-370 FPS without navigation, about 340-360 with threaded navigation baking.

Is this on startup of the scene? How long is it?

Basically, 'source geometry parsing' takes place at runtime, in the scene's _ready. It's literally microseconds in the demo project, but it's very dependent on what other geometry (besides the terrain) is in the scene. I have one other small scene I can test with where it takes 9ms. It really needs testing with a more realistic & complex project.

@SlashScreen

This demo looks good here; does it already support scene geometry?

You mean like other objects in the scene besides the terrain itself? Yes, that's what the 'parse source geometry' on scene startup is for.

Realtime threaded baking is something a lot of games do, so I don't think it will be a problem in most cases (in my own game, the player moves rather slowly).

I've seen that, but I've been burned in the past when I've thought things that work well in other engines can apply as easily to Godot. 😆

There's a bunch of copying and vertex duplication Godot has to do to get its data into the format Recast wants for baking. Whereas Unreal for example might have everything in the correct form from the start.

[SlashScreen]

@tcoxon Oh, my bad, I got some stuff in my head mixed up. What does it consider "source geometry"? Is it dependent on heirarchy? In my case, I have a ProtonScatter node that creates a load of trees on _ready(), and I would need the baker to parse the geometry after it's done placing the trees.

[tcoxon]

@SlashScreen No worries, I'm probably just not explaining myself very well. Source geometry is stuff in the scene tree. What exactly counts depends on the current settings of the navmesh resource. The prototype parses all that source geometry in the scene tree once, in _ready.

In my case, I have a ProtonScatter node that creates a load of trees on _ready(), and I would need the baker to parse the geometry after it's done placing the trees.

Good point! The baker script should probably wait one frame before parsing scene geometry.

@TokisanGames I thought a bit more about realtime navmesh baking over the weekend. Not sure how you feel about this, but I am starting to think fully-featured realtime navmesh baking might go beyond the scope of a terrain plugin. The exact feature, latency, and performance requirements are going to vary a lot from project to project. I think it does sense to provide some navmesh features for users:

1. Paintable navigability and static in-editor navmesh baking (as slow as that may be)
2. A function on Terrain3D exposed to GDScript that can be used to generate source geometry for threaded baking (like in the prototype)
3. An example script showing how to use this function to bake navmeshes at runtime

But going beyond that will probably mean you'll get inundated with endless contradictory issue reports about the latency and memory usage of realtime navmesh baking, as well as requests to add support for any number of other engine plugins, etc. It might be better to leave that up to users. What do you think?

[TokisanGames]

I am starting to think fully-featured realtime navmesh baking might go beyond the scope of a terrain plugin.

I don't think we need continuous, real-time baking at runtime, unless we're going to only bake a small area around the player.

For a level like the demo, I don't want enemies to go everywhere in the 1k x 3k terrain. If I did, I wouldn't need navigation. I would only want them to stay on the path. The navigable area is quite small and should be bakeable and storable while working in the editor. I don't think a computer is going to automatically figure out this small area either. But if it's paintable, it should be pretty easy to be efficient. And even for larger areas it should be fine as the walkable areas will still be surrounded by cliffs, rivers, and mountains that devs won't want their units traversing.

I think it does sense to provide some navmesh features for users:

• Paintable navigability and static in-editor navmesh baking (as slow as that may be)

Yes. In editor baking of the area painted by the gamedev should be sufficient for +80% of projects including OOTA.

• A function on Terrain3D exposed to GDScript that can be used to generate source geometry for threaded baking (like in the prototype)

So they can regenerate it on the fly during game time if they want? Yes that's good. We should always support code based game-time generation of terrain. Though no guarantees on generation performance. They can use Voxel Tools for a dynamic terrain.

• An example script showing how to use this function to bake navmeshes at runtime

Yes, that can go in the CodeGenerated.tscn demo.

But going beyond that will probably mean you'll get inundated with endless contradictory issue reports

I appreciate your thoughts. I think we're on the same page.

[TokisanGames]

@tcoxon Paintable area with indication is now done in 0.9 as of 4c2a1771ada3717615e0ab502c20807930d7f7ad. You can now generate wherever there is navigation and not a hole: eg (control >>1u & 0x1u) && ! (control >>2u & 0x1u).

[TokisanGames]

Completed in #253 thanks to @tcoxon and @SlashScreen