Handling object collisions

I use this QuadTree implementation as the broad-phase structure to detect collisions in my asteroids game. While developing I didn't sweat about this too much, at first I just had a naive O(n^2) iteration over all object pairs, and only when I got to having so many objects that I could see that in the performance profile, I started to implement something smarter. The current QuadTree code is also there as something that's swappable out if it proves out to be problematic, but I think I'm quite contend with it, since I also use the structure for PVS determination for rendering and other logic.

EDIT2: With some googlin' I have come across the term "broad-phase algorithms" and I think this is what I'm looking for. I've heard the term, just never knew what it was about. Any good sources on this would be really helpful(I'll continue looking).

The goal of the broadphase is to fast-reject every possible pair of objects which is not colliding for sure. What survives the test is passed to narrowphase. If you want details, see the Bullet source code: it gets you incredible value and allows to experiment with different broadphase implementations. Personally I've been pretty impressed by AABBTrees!

Search for "prune and sweep". Arguably the best general graphics book of all has a pretty good description (Real Time Rendering). If you like that approach, I can make a few additional comments to make it simpler, easier and more efficient.

Never forget that "objects that didn't move since last frame cannot cause a collision". You can simply ignore all objects that did not change, and only check those that did. They might have run into objects that didn't move, but you'll find that out by checking the moving objects (where "moving" includes rotation, scaling, skewing, etc).

I think, dont deal with quadtrees, spatial hashing or grid in my experience beats quadtree performance, and qt is harder to implement, its limited in space partition amount (limited of recursiveness), takes longer to add replace object and so on...
I tried sweep and prune algorithm (i think its name so), but in my case even only sorting takes to much time...

I think, dont deal with quadtrees, spatial hashing or grid in my experience beats quadtree performance, and qt is harder to implement, its limited in space partition amount (limited of recursiveness), takes longer to add replace object and so on... I tried sweep and prune algorithm (i think its name so), but in my case even only sorting takes to much time...

The classic "sweep and prune" is indeed a bit overblown, and unnecessarily burdened. In this area (collision detection), it is important to take good approaches like "sweep and prune" and "merge sorts" and "make them your own" (optimize them for your specific situation) to make them efficient enough.

For example, I'll tell you one secret I've never heard elsewhere about "sweep and prune". They always describe sorting and sweeping on 3 axes. Without a doubt, that provides a nice clear coherent image of how to achieve the desired purpose (find objects whose AABBs overlap on all 3 axes). However, consider the following one simple observation: objects that do not overlap on the x-axis do not overlap in 3D --- so why are you going to all the effort to sort all those objects on the other two axes? What I do, and what I determined is much more efficient, is to only perform the sort on one axis (usually x-axis is best, but the y-axis or z-axis might be more efficient in a minority of games/applications). So you sort only in the x-axis, then in those cases you find a moving object overlaps another object, you manually check for overlap on the y-axis and z-axis. This way you only do work on the y-axis and z-axis of those objects you already found overlapping on the x-axis. When you perform the sort on all 3 axes, you effectively are doing 3 times as much work!

Also, you really do need to get inside your sort routine and customize it for this purpose (broad phase collision detection). Remember what I said before... only moving objects can collide. So why sort or otherwise process stationary objects? What a waste!

BTW, I wrote and compared many different sort routines for this purpose, and all things considered, the merge sort was definitely the best if you choose just one sort in all situations. But again, look at your merge sort carefully and optimized for this purpose.If only a few objects move in your game/application, you may find out no formal sort algorithm is best --- what is best in this case often to simply process each object that moved separately, and just move them back and forth in the sorted list until you have it in the correct place (though some kind of speculative binary hopping around can be helpful on objects that move a long way per frame).

but stationary object must be in the list , becouse of dynamic object can hit it, afcous it depends on optimization and "haks"
I didnt tried all sorting algoritms, but quicksort. And results was horrible(i was sorting pointers to objects).
For my 5000 objects only one dimensinal sorting took about ~0.300 mls,when spatial hash with everything collision, movement, constrains and so on takes 0.180 mls
So thats why i am so sceptick about sorting, ofcouse with other sorting algoritms,wat behaves faster with allmost sorted data,results could be better,
but than you must keep list and update it. i have bad experience with updating list , it gets a bit slower in some time, perhaps of cashing or something...

but stationary object must be in the list , becouse of dynamic object can hit it, afcous it depends on optimization and "haks"
I didnt tried all sorting algoritms, but quicksort. And results was horrible(i was sorting pointers to objects).
For my 5000 objects only one dimensional sorting took about ~0.300 mls,when spatial hash with everything collision, movement, constrains and so on takes 0.180 mls
So thats why i am so sceptick about sorting, of couse with other sorting algoritms,wat behaves faster with allmost sorted data,results could be better,
but than you must keep list and update it. i have bad experience with updating list , it gets a bit slower in some time, perhaps of cashing or something...

Yes, stationary objects are in the list, and they must be --- after all, they might be collided with by a moving object, and they themselves might move some frame in the future. However, you can speed up many aspects of the issue by ignoring stationary objects.

Yes! QuickSort is absolutely ABYSMAL for sorting already sorted lists. No wonder you gave up! Switch to merge sort or insertion sort, depending on your situation. I tried 6 different sort algorithms, and the results were hugely different. And when you try to sort a close to sorted list, which is the norm in 3D graphics collision detection, QuickSort takes forever. I'm not kidding, the difference is humongous.

This brings up a hugely important issue, called "temporal coherence". Simply stated, this means "this frame is probably similar to last frame". You need to look at every process you do in collision detection, and ask yourself how can you take advantage of "temporal coherence". For example, choose a sort algorithm that works best for nearly sorted lists (which is almost always the case in this application). In general, the best sort in this situation is usually insertion sort. However, if a large majority of objects are not moving on each frame, the best approach is often to only process moving objects.

I spent a lot of time thinking through issues related to collision detection, and a lot more time testing possibilities (and sort algorithms). Much of what you're told is rubbish --- in the sense "it works", but "is not practical" once the number of objects grows, or other nasty situations arise (like non-convex objects). If you're not willing to invest a LOT of time into this issue, just accept crappy performance, because that's all straightforward generalized approaches will ever achieve.

this is not my theme, but enyway thanks. My situation is a little bit diferent - my own engine is finished, with I think very good performance for world wraped space combat there all objects are moving... but I will try to calc how mutch collision check iteration will took your suggested method...

I think, dont deal with quadtrees, spatial hashing or grid in my experience beats quadtree performance, and qt is harder to implement, its limited in space partition amount (limited of recursiveness), takes longer to add replace object and so on...
I tried sweep and prune algorithm (i think its name so), but in my case even only sorting takes to much time...

Right, I use spatial hashing for object<->world collisions as well. You can also use it for storing the visibility set. I even went as far as hashing the angle of view. Once that's done you just divide the object's position by the cell size and convert that to integers which gives you indexes into the collision/visibility arrays. I can't think of a quicker way to get at the relevant data.

I have tested both algorithms in situation with >3000 difirent size objects, and 2000x2000 spaces as hown in image


And results was approximately from worst case to best, sweap and prune uses insert sort,and time results without collision and response only finding possible cases
iterations=posible cases

Brute force: ~5600000 iterations ~27.870 mls
Only 1axis sweep and prune: ~99000 iterations ~4.300 mls sorting takes ~2.000 mls
Only grid with cell of 70x70: ~18000 iterations ~0.270 mls
Grid with cell 70x70 and 1axis speap and prune inside each cell: ~7000 iterations ~0.186 mls sorting takes ~0.040 mls

with the same objects but space 20000x20000:
sap: ~9000 iterations ~0.450mls
grid with cell 300x300: ~2500 iterations ~0.045 mls
grid with cell 300x300 with sap in each cell:~250 iterations ~0.035 mls

thats my results , so how about that?

I'm convinced. BTW, have you ever played Pulsoids?

http://www.simtel.net/product/view/id/138992

One of these days I'll upload the new version.

Thank you very much for sharing.
As a side note, there's no such thing as "mls", a millisecond is an "ms", no plural as far as I understand.

oh, sorry, in my native language writes "mls"...