For a 500-object world, what is the most efficient way to do broadphase for collision detection?
Do I have to loop thru each of them, and separate them into regions. It will suffer from performance degrade due to a large number of active objects involved. How do you guys deal with this?
Thanks
Jack

For a 500-object world, what is the most efficient way to do broadphase for collision detection?
Do I have to loop thru each of them, and separate them into regions. It will suffer from performance degrade due to a large number of active objects involved. How do you guys deal with this?
Thanks
Jack

Some optimization can be made if there are basic assumptions that are in effect.

Octtrees and BSPs can be costly when most objects constantly move and you have to rebuild the tree data so much.

If you can find that there are limitations, simpler solutions can be made (ie- regular catesian grid type membership arrays to spatially divide your objects).

If your bounding boxes are small and your map large you can have an array 2D grid sized to just over the diameter of your largest bounding box.
(The grid size also should be at least as large as the largest move increment per time quantum.)
Objects have markers put in the array cells (linked list) they currently are centered in and move the markers if their location causes them to be in another cell (simple coordinate threshold test).
This revising of the position data is quite cheap (and with a fairly fine grained grid the link lists are not too long so linear traversals can be done against the sets for removal, inserts are at the linklist head)
Collision checking for any object will be against the list of objects in their current cell and any of its adjacent (8) cells (since the object may overlap into adjacent cells). Because of the cell sizing the test need only be made within the adjacent cells.
Every time an object moves you do a lazy evaluation check if the objects intersects with any objects within the cells (lazy evaluation is a simpler less costly test that is used to cull obvious non-collisions and any likely collision test are made with much more costly exact tests - bounding box or worst individual bounding boxes of sub-objects) A simple culling test would be to test the box (dx dy, dz) distance of centerpoints being less than twice the max bounding box radius (not even a suqare root is needed).

If you have to also test linear segments of fast projectiles, the same grid data can be used (use bresenham to find all the grid points the segment travels thru and expand that set to include the adjacents).


If your world is 3D, a 2D grid is still usable to break the collision test sets into very small groupings.