What you're looking for is a spatial tree. Quadtrees and Octtrees are popular, as they're quite simple to implement and use.

Being a pessimistic sort, I'd personally recommend just brute-forcing things to start with. You can always retro-fit a spatial tree in later if you find that collision starts being a bottleneck. Just using simple bounding volumes for complex objects is often good enough.

Yes, a brute force method would simply check every object against other object. If you're using simple bounding objects (like axis-aligned boxes or spheres) then the tests will be ridiculously fast. You'll be surprised at just how many objects you can handle without doing anything particularly clever.

At the very least I'd do the brute force method first. Then when you've got your collision detection working and objects reacting to each other you can optimise it at a later point (where 'later' might be straight after, or in a couple of months time when you actually know you'll need it).

Spatial trees are essentially optimisation techniques, and you always create a working version before trying to optimise it.

If the OP doesn't mind I'd like to push in a related question. What if when using either of two methods (grid or brute force) object A's movement intersects both B's and C's ? How do you know which one to calculate first? If we just iterate through an array and do the A-B Collision first, but in reality C was closer to A, then that collision will be completely missed? And if we start brute forcing to first calculate time required for collision, then act on collisions again wouldn't that require n^2 time for time checks and even more to calculate the next collisions after the first collision is done?

Brute force benefits from full-on optimisations. Since it's an extremely repetitive and simple task, if you align your data according to what's best from the hardware perspective, organise your instructions and cache usage, use registers carefully, it can be EXTREMLY fast.

Of course, it's a different exercise than higher level optimisations.

brute force, unoptimised...

Quote:Original post by Verminox
If the OP doesn't mind I'd like to push in a related question. What if when using either of two methods (grid or brute force) object A's movement intersects both B's and C's ? How do you know which one to calculate first? If we just iterate through an array and do the A-B Collision first, but in reality C was closer to A, then that collision will be completely missed? And if we start brute forcing to first calculate time required for collision, then act on collisions again wouldn't that require n^2 time for time checks and even more to calculate the next collisions after the first collision is done?

Yeah, but usually, it;s a trade-off. Your objects have to move ridiculously fast or have very shallow collisions to have a case like that. Personnaly, I would not worry about it, in a game context. IF you do want to make sure you have the absolute earliest collisoin first, you can reduce collision checks by time, and process the earliest.

say, you do A-B, then A-C, but C should take precendence over B, you do check the two cases, A-B and A-C, but do not act on them right away, just record the earliest. Then you apply the collision response, and then you have to retest all objects against A again... Until no other collisions are detected.

Quake3 works a bit like that. One by one, It traces one object against all others, take the earliest trace result, move the object to that position, apply response to that object, trace again.