- Home /
Avoid iterating through all gameobjects to select units using marquee selection box (selection box is already created, just have to be efficient)
I have an rts marquee selection box system working in my game. Currently i iterate through all gameobjects, and if it can be selected, then i check it's position inside the guiTexture of the selection box using:
selectionBox.Contains( MainCamera.WorldToScreenPoint(currentIteratedObject.transform.position) ))
and this seems to work fine. I may have a ton of gameobjects in my scene later, and want to avoid iterating through all of them. Is there a way to do a version of spherecast, but instead of a sphere, do a rectangle? Or, can I determine the size of a spherecast to do, to inscribe my selection rectangle in it, to cut down on the objects I iterate over?
It is relevant, but doesn't cover any new options. I wanted to avoid iterating over a datastructure of all selectable objects, and ins$$anonymous$$d try and get the objects in the rectangle directly.
Thanks for trying to help however :)
Answer by Hoeloe · Aug 24, 2013 at 06:17 PM
Well, generally optimisation of this sort is a little difficult. Honestly, iterating through all objects really won't be too expensive. It's still only an O(n) operation, which is pretty good. An average computer can run O(n) operations on billions of objects before the lag starts to become noticeable. The problem with a spherecast is that, because the selection is in 2D, it has to take into account the depth to infinity, which is awkward to deal with. You could, rather than set a flag in each object, add and remove objects from a static LinkedList (LinkedLists are more efficient than ArrayLists when the primary operations are adding and removing, and iterating through all elements) which is done whenever the object enters or leaves the camera's viewpoint (OnBecameVisible and OnBecameInvisible may be useful for this). It would only be changed when the object enters or leaves the camera view, and you could simply grab this list when you need to calculate the selection box, which would drastically cut down the number of objects to iterate through.
Well that's good to know that billions of objects is where lag happens. I should be comfortable with an amount of 20,000. I might have to keep a list of selectable objects in a list structure due to the add/remove time complexities. I knew about the data structure times, as I've had time complexity work in my data structures CS class, but was unsure of unity limits on mobile hardware of an ipad3 or better.
Plus the sphere cast is not an infinite depth operation, it generates a sphere cast at a location and scans in 3d space.
Well, of course the limits will be different on different hardware, but 20,000 simple comparison operations should be fine on just about anything, as long as you're not doing it every frame.
I know, SphereCast is not an infinite depth operation, but if you are selecting a rectangle (rather than a cuboid), it would have to be to approximate it, as you have to consider objects that are very far away, but still within the bounds of the rectangle.
Ahh ic what you mean. Hmm. Well my objects are going to be aligned to a plane, so I can raycast to the plane from the rectangle center, and then sphere cast to get an object list.
And the check for seeing if its visible by the camera would be every frame, otherwise it wouldn't be accurate....
Answer by meat5000 · Aug 24, 2013 at 11:07 AM
Set a flag in each gameObject that determines whether or not it is currently being rendered by the camera. All the rendered objects can be iterated in to an array. This will cut your gameObject Find down drastically.
http://answers.unity3d.com/questions/8003/how-can-i-know-if-a-gameobject-is-seen-by-a-partic.html
Wouldn't it be expensive to iterate over all gameobjects in the scene every update, and deter$$anonymous$$e if it is seen by the currently active camera? This seems expensive. I would never use gameobject.find in an unconditional statement in an update. Never.
Basically you can set each object to handle this for itself independantly. When it becomes visible it sticks itself into the visible array, rather having to check whether every object is visible or not. After all, I believe isRendered is an automatic flag.
Basically what Hoeloe said but it seems his way involves less work!
Hmm ok. Sounds awesome if unity does this already. Is this calculated in late update? If you don't know I'll just look at the unity documentation rather than waste your time. Thanks for all your help!
http://docs.unity3d.com/Documentation/ScriptReference/Renderer-isVisible.html
This 'flag' is updated automatically for each object as it becomes visible or not. You can choose to use it wherever you like. LateUpdate() sounds like a good option so as to check it when all the other Updates have fired and everything is concluded for that frame or step.
Your ProcessData.AndDoSomeComplexEffect(); (from the reference link) could be used to process the object into the array or LinkedList, as Hoeloe suggests.
For your marqee box simply use this array to search through as it contains only visible objects. Obviously, if an object falls offscreen you cant select it with the box, logically. It will also be automatically removed from the array by itself.