Is there a way to query the engine for nearest neighbor search in all nodes?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By er453r

Is there a build-in nearest neighbor search for all nodes (or all nodes contained in AABB)? Most 3d engines use an underlying oct-tree or a similar space partitioning structure that allow for such queries. Currently I’m holding references to all nodes in script and iterating over them, but that is super non-optimal.

:bust_in_silhouette: Reply From: Zylann

There is no “completely generic” system to do it, this is usually a job for the physics engine. Area, RigidBody or StaticBody can be queried pretty fast using shapes or raycasts.
Otherwise, you’d have to build a data structure yourself.

Area, RigidBody, StaticBody can be queried for collisions given 2 nodes. I would like to query for nearest neighbors, so effectively I would like an answer to “return all nodes in distance from X less than Y”. Alternatively I could create a temporary “neighborhood zone” node, and query for collisions with it, BUT I still need the other nodes explicitly to check for collisions. In this case I would be looking for an answer to “return all nodes that collide with this neighborhood zone”. Is something like this possible?

er453r | 2020-04-07 13:37

Area, RigidBody, StaticBody can be queried for collisions given 2 nodes.

Kind of wrong. A shape query will tell you all nodes intersecting it, not just 2. But in a sense, it is pairing collisions two by two I guess.

I would like an answer to “return all nodes in distance from X less than Y”

How about a shape query using a sphere? This will tell you all nodes which distance is lower than the radius Y of the sphere, centered on X.

return all nodes that collide with this neighborhood zone

That’s what Area and shape queries do. They both tell which nodes are within a given shape.

Zylann | 2020-04-07 17:42

:bust_in_silhouette: Reply From: Calinou

You can use the ProximityGroup node for this purpose. If you need approximate frustum visibility checks, use the VisibilityNotifier or VisibilityEnabler nodes.