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?

Jumbo

Answer 1

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

Gerry

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.

Idiosyncrasy

Added the related questions to my answer and removed the question from your answer since it was distracting. – Jumbo

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)

Echoism

Looking at the image above, would you say that constitutes an uneven enough concentration? Often times the window is much larger with the balls settled at the bottom. Would you still suggest grids over BSP? – Jumbo

A BSP is an irregular Grid, and I'm suggesting a regular chess-like grid. The difference is a chess-like grid is easy to implement and debug compared to a BSP, and more than suitable even for professional games. You could up your Grid to a BSP if performance is a problem, or as personal challenge – Echoism

In your case the concentration actually is uneven, below you have lots of balls and up top less balls. So you could use a finer grid size towards the bottom, which is an application of expert knowledge, since you KNOW what to expect, and its not a really generic situation, like a pool table. – Echoism

Once you've got the balls at the bottom, I'd assume their velocities would degrade to zero pretty quickly, so you wouldn't have to check if they collided with anything (although you would have to check if anything collided with them). – Idiosyncrasy

So expand on that - only do the collision detection when you move something, so once everything is at zero in a grid square, you no longer have to check that square at all. – Idiosyncrasy

@Paul Tomblin I agree with your assertion there, however I'm imagining (because I can't guess from the image) that if the balls have weight, they may be pressing down on balls below them, thus occasionally reshuffling the bottom area into an ever more compact state. But as I say its just a guess. – Echoism

Normally objs are divided into static and dynamic. Dynamic objs check collisions against Dynamic and Static, but Static objs don't check for collisions at all, since they don't move. In many simulations Dynamic objs with low momentum will get placed in the static bin, to optimize performance. – Echoism

@Robert Gould, you are right about the force down on them and them reshuffling into tighter configurations. I'm looking into implementing a grid and editing my post with results – Jumbo