koobas.hobune.stream
Efficient spatial searching (finding game objects within a certain range)
I'd like to try and gather gameobjects in a spatially efficient manner such as
- Gather all gameobjects within r radius of a point p
I was wondering what options were available for doing this, obviously spatial trees could be written in scripts but i'm presuming the performance could suffer a little versus some integrated built in solution.
Mike has suggested Physics.OverlapSphere() if the gameobjects have colliders.. I may consider going down this route though i had planned to NOT have colliders on these gameobjects. I wonder about maybe turning colliders on and off as required, only on for a short period whilst gathering entities. Though i'm sure PhysX won't appreciate having to recalculate its spatial trees, surely it'll still be quicker than trying to write your own?
Thanks
I've done it both with octrees and using triggers. Actually doing it with triggers can put quite a burden, as triggers will fire not only for your spatial-interest objects but for any other collider in the scene. Depending on your implementaiton, you're also likely to end up keeping one proximity list per object, which ends up being updated every time an OnTriggerEnter and OnTriggerExit fires - hardly optimal.
I suggest you implement a simple octree and compare the performance against the physics-based version.
Doing the verification yourself, instead of leaving it to physics engine events, also has the advantage of control. It will allow you to:
- Perform smoothing. If you update the proximity lists every time a relevant object enters or exits the proximity radius, you're likely to end up with a jittery behavior where the objects update their course/awareness too often.
- Control when to update. If you have many objects on the scene, you likely won't want to update many of them several times per frame. Keeping a proximity database yourself will allow you to, for instance, perform round-robin proximity updates where you upgrade a single object's proximity list per frame, thus saving you processing time for other tasks.
i think the best approach is to use triggers in your gameobjects that you want to search for them and then use the physics.OverlapSphere function. triggers are not heavy and you don't need to implement OnTriggerEnter () or other functions for your solution to work. also you can create a big sphere collider(trigger) and then implement it's OnTriggerEnter and OnTriggerExit functions to see what objects are comming in and what objects are going out
