Add Bounds checking to Navigation Regions when creating connections between them.

[Angular-Angel]

Describe the project you are working on

A first person voxel RTS.

Describe the problem or limitation you are having in your project

The game lags when I try and add a NavigationRegion for every chunk, with the lag scaling based on how many NavigationRegions are already present.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Adding bounds checking when adding a new navigation region, so it only compares vertices with regions it actually touches.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Navigation regions will have bounding boxes, and when trying to form connections between themselves, they will check their bounding boxes first to see if they actually touch each other.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Not to my knowledge. This is an optimization for a major part of the engine - the only direct work around would be to roll my own navigation module, or use an altered version of the engine to implement the feature myself.

Is there a reason why this should be core and not an add-on in the asset library?

Again, an optimization for a core part of the engine. Not practical as an add-on.

Tasks

Preview Give feedback

No tasks being tracked yet.

[Angular-Angel]

I'm not super practiced at C++, but I'd be willing to try and code this myself if people want me to? Someone more experienced should probably check my version over after I finish it, if I do end up coding it, but I'd be willing to do the first draft at least.

[AThousandShips]

I'd suggest gauging the interest in this before doing any work, unless you're willing to have worked unnecessary

[Angular-Angel]

Yeah that's why I asked here. Is there a better place to go to gauge interest?

[AThousandShips]

This is the way to gauge interest, what I mean is to give it some time to see what people think, you're free to work if you like but be aware that it might be rejected if it's not a feature that's demanded

[Angular-Angel]

Ah, yeah I figured! XD

[Angular-Angel]

Also, a link to my code that's causing lag: https://gitlab.com/AngularAngel/omnicraft-infinite-war/-/blob/master/Scenes/Game/NavigationGenerator.gd?ref_type=heads

You need to compile Godot engine with Voxel-Tools if you want to actually run it. Also, I'm pretty sure it's the code for finding connections between meshes that lags, because if I generate my meshes and then simply discard them instead of adding them to the tree, it runs perfectly.

[Angular-Angel]

I could go and code a proper demo project, without the voxel-tools dependency? It'd be a bit of work, but I'm willing to do so if people express interest and it'll actually be used to test improvements to the engine. :/

[Angular-Angel]

Also, while we're here, anybody know of any good examples of Godot using bounding boxes for comparison culling or the like? It's got to have come up for rendering or collision detection at some point.

[RedMser]

Also, while we're here, anybody know of any good examples of Godot using bounding boxes for comparison culling or the like? It's got to have come up for rendering or collision detection at some point.

The AABB class is probably what you'll want to work with. See AABB.
I'm not sure of a good example where this is used in the C++ source though.

[Angular-Angel]

Sounds good, I'll see if I can find one!

[Angular-Angel]

Okay, scene/3d/visual_instance_3d.h has a bounding box. wasn't able to find the code where it's actually used, and not entire sure we should just staple an AABB onto nav_mesh or nav_region or whatever. I was able to solve my performance, at least temporarily, by disabling 'use_edge_connections', and I think I can make my game work without it. Will leave this proposal open for further discussion, though.

[Zylann]

Here are my thoughts on this, in the context of navmesh management on dynamic chunked terrain:

• Using an AABB to broad-phase the calculation of connecting navmeshes is actually a sensible optimization that might not even need extra properties. That could just be done in the navigation server eventually, if not done already.
• Solely relying on AABB broadphase to speed up connections might not be enough. For general purpose cases, it might also be possible to reference regions into an accelerator data structure, such as a grid, BVH, octree etc, in case there are lots of regions to handle dynamically. Although that decision would depend on the measured performance.
• In the cases I work with (voxel terrain with cubic chunks), regions may eventually be structured on potentially hundreds of grid-based chunks. Which means having every region check every other to test if they touch is inefficient, even with AABBs. An accelerator data structure would help, but would remain more complicated than the following: one way I could imagine to "help" the navigation system would be the ability to provide a small list of potential neighbors on each region, so they could check only that list instead of every other region. That might still not the most optimal approach though, but rather an attempt at keeping it "general purpose". Ideally I would like to be able to tell myself the navigation system which regions should be checked with which without even relying on lists, because in my terrain system I can just query neighbor chunks, which are implicitely available on the grid. Or there could be some kind of separate "hashgrid" resource regions can be part of, which the navigation server could use when told to.