Expose Octree to the scripting API

[gitcatrat]

Describe the project you are working on:
3D project where instances need to be aware of their surroundings, mainly other close instances and do other advanced actions and calculations on close groups and specific parts of the world.

Describe the problem or limitation you are having in your project:
I'd have to use and populate 3rd-party (or my own) Octree to make these lookups efficiently.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:
Godot already has an Octree implementation, I would trust it (bugs and performance wise) a lot more than 3rd-party or my own implementation. I propose to expose it in Godot API.

Another option would be to expose Octree already instantiated and used by servers but that would probably come with lots of issues and caveats? On the up side it would be populated and accurate.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:
Expose Godot internal Octree in Godot API, e.g Octree octree = new Octree();

If this enhancement will not be used often, can it be worked around with a few lines of script?:
It could be easily solved if you find a reliable 3rd-party library but it's already in Godot, isn't it?

Is there a reason why this should be core and not an add-on in the asset library?:
It's already in core.

[clayjohn]

I think that is what ProximityGroup is for.

Alternatively you can query the one in the VisualServer using the instances_cull_* functions (where "*" is "aabb", "convex", or "ray")

Take a look at the links and let me know if those address your needs!

[gitcatrat]

@clayjohn

These are really not an option because I also need Octree for procedural in-memory systems, for example road network generation. I need to check if segment is close to or intersects other segments after adding each of them with random direction in order to correct the segment end point. These segments are not rendered in any way until the whole road network is built. It would seriously harm the performance if I had to render or attach nodes just to get other close segments.

Few notes about your suggestions:

instances_cull_*

Returns an array of object IDs intersecting with the provided AABB. Only visual 3D nodes are considered, such as MeshInstance or DirectionalLight.

Hmm, this description.. Does it consider server instances? Everything I have is added with servers.

It's a very performance-sensitive game and I try to avoid nodes if I can because whole game is procedural and programmatic and attaching "utility" nodes to tree and keeping them in sync (e.g position) feels weird if everything visual and physical is not there. I wish there was a programmatic API behind (some) nodes in a sense that you don't have to use AddChild in order for it to work.

All in all, I still think that general purpose Octree would be very useful.

[Calinou]

Godot's octree implementation was removed in a favor of BVH, so this is longer possible in Godot 4. (For reference, ProximityGroup was also removed in Godot 4.)

[donn-xx]

Sorry to reawaken the dead, but the spirit of the OP is still valid. If not an octree or whatever, there should be an API to some kind of spatial partitioning algorithm for gdscript etc.

I am in a position where I need to know where transform instances are within a multimesh versus the player. Right now I am having to search through the entire multimesh.instance_count OR start writing my own octree I guess.

[Calinou]

there should be an API to some kind of spatial partitioning algorithm for gdscript etc.

There was the ProximityGroup node in 3.x, but it was removed in 4.0 as it wasn't serving its purpose well.

I am in a position where I need to know where transform instances are within a multimesh versus the player. Right now I am having to search through the entire multimesh.instance_count OR start writing my own octree I guess.

Do you need to have this information be up-to-date every frame, or can you stagger the checks to occur over several frames (either sequentially or randomly)? This could speed up checking a lot.

[donn-xx]

Do you need to have this information be up-to-date every frame, or can you stagger the checks to occur over several frames (either sequentially or randomly)? This could speed up checking a lot.

The transforms in the multimesh don't move around, but the player does — I want to know which transforms are closest (say a radius) to the player.
[Because I am then 'popping' them out and instancing real nodes. I then hide the multimesh transforms (at those indexes) by scaling to zero.]

It need not happen in one frame, but it can't be a sequential loop through the entire array either; which is what I am doing right now.

I am searching for BVH examples online now to try learn the algorithm and remake it in gdscript. It seems incomplete to have algorithms within Godot that are not exposed to the editor, like bvh. It would surely help in many common proximity-type problems.

[donn-xx]

I ended up making a spatial dictionary to solve my problem, but it remains true that Godot should expose some of the clever algorithms like BVH and Quadtree as APIs. Only makes sense!

[Zireael07]

Bump. I find myself needing an octree/quadtree

[Calinou]

@Zireael07 This needs a new proposal, now that the octree has been removed in favor of the BVH.

[donn-xx]

Is the BVH being exposed to scripting?

[donn-xx]

Here's a toy API:
spatialMagic.add(pointA, mynode)
spatialMagic.add(pointA2, someTransform)

if spatialMagic.find_object_at(some_later_point, mynode): print ("yay we found mynode)
if spatialMagic.find_object_at( random_point, someTransform): etc.

The objects should take up space (like a bbox size) and position in the spatialMagic structure.

I need to work with my game nodes etc. and if I want to draw one in a place, but don't want to overlap something, then I can ask the spatialMagic for an answer. Or if I need to ask "who's around me right now?"

Think a spatial hash using a dict, but done in c++ with voodo.

If this BVH thing can do that, then please expose it to gdscript!

[Calinou]

@donn-xx Please open a new proposal to discuss this, as this one is archived.

[donn-xx]

Thanks for the heads-up, I have made a new one at #7811