How to efficiently determine all scene objects within range R of some given object X?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By gau_veldt
:warning: Old Version Published before Godot 3 was released.

Are there any gems in the engine API that would make it possible to efficiently ask the scene tree “find all objects X distance away from object Y”. This is not as easy as “scan everything” since that is a big-oh of n-squared solution: “for each object Y in scene tree compare with every object (as X) in scene tree”. BSPs aren’t good since their setup is an offline algorithm (meaning BSPs can’t change easily with runtime object movement). I could implement a range tree for one axis (but the storage blows up to “N to the number of dimensions” for more than one). So I’m not sure what I should use here. Assume LOTS of objects to check (large N).

Why not simply use the collision engine by calling space_state.intersect_shape()?
Or maybe, divide the world into a grid for faster queries? (but Godot already does that)
http://docs.godotengine.org/en/latest/classes/class_physics2ddirectspacestate.html?highlight=intersect_shape#physics2ddirectspacestate

Zylann | 2016-09-28 09:14

You want to check this for many objects or rather single ones like Player? If latter then you can just add area node to player and use area interface.

kubecz3k | 2016-09-28 13:59

basically as was discussed on FB using the collision system with spheres to represent the ranges and bounding cubes to represent objects (layered and masked so cube/sphere emit in/out signals but no cube/cube nor sphere/sphere signals). these could simply be added onto objects as children

gau_veldt | 2016-09-28 20:56

If I understand well, you can do it with an Area, with the signal _on_enter_body.

wf192 | 2016-10-10 17:25