On Tue, Feb 9, 2010 at 9:35 AM, <Paul_Firth@scee.net> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I should have mentioned that I'm writing a 2D space shooter, so all
> the objects are moving all the time. And I'll have like 200 objects or
> so.

Ahhh, ok - are you on a platform with reasonably quick memory (good caches
etc)? Have you tried just gridding up your world (screen?) using a quite
large cell size and do a simple bounding volume check in each cell
location?

Or even use a fairly small cell size (the size of the largest objects), and store cells with objects in them in a hashmap from the cell coordinate to a list of objects. That way you can have an infinite grid and you only need storage proportional to the number of non-empty cells for the grid itself.

Of course a simple BV hierarchy (e.g. AABB-tree, BIH, etc.) works too, since you can usually adjust it to remain valid without doing a full re-insert each frame.

I suspect that a simple SaP will outdo all of these though. It's just that much simpler.

--
Sebastian Sylvan