What technique should be used to prune 2d collision checks?

Question

From the outset, collision detection feels like it is an O(n^2) problem.

You have a bunch of objects and you need to check if each object is colliding with any of the other objects. However, I know that it is wildly ineffecient to check each object against all the other objects. Why do a relatively expensive collision check between two balls if they aren't even close to eachother?

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

If you have 1000 balls then if you went with the naive collision detection you would have 1000^2 collection checks (a million)! This collision checking has quickly become the bottleneck in my application. I need to implement some broad phase pruning.

What techniques should be used to prune collision checks when working with 2d - circular objects? I've read about QuadTrees, BSP, spatial hashing, etc but it is difficult to sort out what method is most appropriate to this use case.

Does anyone have any knowledge about what might work best?

Answer 1

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 2

Spatial hashing. See Hugo Elias's page about it.

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)