Broad phase collision detection - Quadtrees, BSP, etc.

Question

Collision detection is naturally an O(n^2) problem.

You have a bunch of objects and you need to check if that object is colliding with every other object. Right now that is my naive approach and while it isn't a problem for a limited number of objects I'm now approaching the point that it is a bottleneck (after profiling my code).

Here is example of my simple program I'm working on:

There are 400 balls in the image and I have added up to 1000. 1000^2 is a million collision checks, each game update. I need to implement some broad phase pruning. It is too slow and you can tell in the simulations that it is taking a definite toll.

What technique do I need to use for my broad phase collision detection? I'm looking for what the best solution to this 2D use-case is. Is it QuadTrees? Is it BSP? What?

Answer 1

spatial hashing. http://freespace.virgin.net/hugo.elias/models/m_colide.htm

Answer 2

I wouldn't use QuadTrees or anything that complicated because you'll be constantly balancing and rebalancing trees as balls move between them. It would probably be more efficient just to have a grid - every time you move a ball, you can just calculate what grid cell it's in, and throw it in there if it's changed. And every time you need to make a collision check, you can just check balls whose center is either in your grid, or in adjacent ones if you're sufficiently close to the edge.

You can experiment with grid size to find the optimum. You may find it depends on how many balls you have.

I said this in a comment below, but I think it deserves to be part of the answer: Only do collsion detection when something moves, so you only have to check the moving thing against things in its grid square (and ajacent ones as mentioned above). That way if you get a pile of things in the bottom that aren't moving, pretty soon those objects are never checked for collision, because nothing is moving within their grid nor is anything moving into or out of their grid.

Answer 3

I second the Grid method. A 2D simulation of balls won't benefit from QuadTrees (which are generally used when you have complex geometry like characters and buildings), or BSPs (which you should choose if you have a very uneven dispersion/concentration of objects, like with high concentration areas and low concentration areas, in a multiplayer or strategy game)