Hey there. I'm trying to implement some basic physics/collisions in my game. I have the formulas I need and I actually have working test collisions with objects(just looping through and checking if they collide). Right now I just have a player(circle physics body), a single enemy(circle physics body), and a static axis aligned rectangle(rectangle physics body obviously). However, I want to add a lot more enemies but I'm not quite sure of the "best" way to do it.

Say there are 100 circular enemies and I want them to all check for collisions with each other. So I would go about this by looping for each of these enemies and checking if they collide with every other enemy on the list. I can see that this isn't really all that efficient so I'm wondering how I could make it better. I only want them to check the ones around them. So I guess I should have a simple distance check to see if they are in the radius of each other, and then do the more complicated checks. What can I do on top of this or instead of this?

Thanks.

EDIT: NOTE: I'm using C++

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).

EDIT3: Or quadtrees? This seems like what I'm gonna roll with. I'll try it.

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.

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...

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 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.