Re: [Algorithms] incremental triangulation for 2D collision detection broadphase

[Sebastian S. <seb...@gm...>]

On Tue, Feb 9, 2010 at 9:35 AM, <Pau...@sc...> 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