Collision Detection of Multiple Objects

[EarthOtherwise]

This is a very general question and seemingly a basic one at that, perhaps so much so that it's just not discussed that much, but it's been eating at me. The basic question is this: How do you structure your code so that, given multiple objects, static or moving, how do you do the least amount of work looking for collisions?

Currently, for every moving object I must check for collisions against every other collidable object, which eats up a lot of time, since the equation for number of collision checks is Number of objects * Number of objects and if I have 100 objects that's 10,000 collision checks per frame, which seems to be like a waste of resources.

Sorry that there's no code to go with this, but I need to know if there's a solution to this problem, and if I've just been looking in the wrong places for it.

[Jaybob66]

use an octree,

They are straight forward, i wrote one myself last year for exactly the same problem.

EDIT.

actually i did a bit more, checking in this order, only perform check 2 if check 1 is true, etc...

1. used an octree to break the items down into regions of space
2. used a sphere collision detection (simple distance between objects)
3. used a box collision detection. (calculate the box when you load the model)
3. used model vertex/plane collision detection.

I did this because my drawing code was super inefficient and had to optimise elsewhere.