If you have 100 objects on screen and want to see about collisions...

Do you just check all 100 objects with the 99 others? (thus doing 9900 collision checks)


Is there a better way?

not only is there no better way, there is no other way - period.

all collision detection schemes and strategies are a form of "divide and conquer" to deal with this fact.

all seek to reduce that 100 objects somehow, by dividing up the scene into smaller sets of objects, by dividing up the object types and skipping the collisions you don't need to check (like my bullets colliding with each other), by culling objects you don't need to check from the list (asleep, etc), by storing history of past checks and positions, and so on.

but in the end, if you need to check a given pair-wise collision, you have to break down and do a collision check (of some sort).

that's where the second way to speed things up comes into play...

you ramp-up the complexity of the checks.

you start with fast inaccurate, and go to slower more accurate checks. the fast checks trivially reject anything that's not close to being a collision. the slower more accurate checks are performed only on those object pairs that pass the first check.

unfortunately in the end, a lot of how fast the actual checks are usually has a lot to do with:

1. how anal-retentive one is about collision check accuracy. most folks go way overkill.

2. how poor an algo choice one makes. less than optimal choices are all too common. most geometry problems can be solved in more than one way. many times folks seem to know of a number of possible (usually complex) methods, but somehow don't know of the the best one (hit or miss learning i suspect, or perhaps the "i have a hammer [oct-tree for example], so everything looks like a nail" mentality).

3. how obtusely one implements the ill-suited overkill algo chosen. overly complicated code on top of poor algo choice is also very common.

avoid these pitfalls, divide and conquer, and ramp up check complexity, and you'll be fine, even with 100,000 dynamic objects.

not only is there no better way, there is no other way - period.

I only slightly agree with this statement. Worst case most solutions to pruning collision detections have a degenerate case which ends up comparing everything against everything else anyways. However, this generally isn't typical or in most systems (with some form of broad-phase implementation) possible, so finding a means to take advantage of such spatial coherence is actually very beneficial and actually does reduce the number of collision checks (simple or complex).

@ms75124 I would recommend reading / getting a copy of Christer Ericson's book "Real-Time Collision Detection". In it he outlines several different methods for reducing the number of collision checks upfront (generally in what he calls "Spatial Partitioning" and most call "broad-phase" collision detection; simple checks to that reduce which objects get checked for collision). To list a few of the *types* of methods he mentions (within each there are a few algorithms): uniform grids, hierarchical grids, trees, and sort and sweep. He also offers some insight on the benefits performance-wise of most.

I only slightly agree with this statement.

ah, you misunderstand!

my only point is that after you've divided and conquered as much at possible, whatever's left you end up pair-wise checking. THEN you can apply progressively more accurate and slower checks, until you reach the level of accuracy desired.

In short explanation: Using a variety of different techniques you basically just bundle together objects so that you -know- they can not possibly be colliding and then use that to narrow down how many collision checks you need to do.

You can't really get rid of the checking but you can try to eliminate as many redundant ones as possible.