Jump to content
  • Advertisement
Sign in to follow this  
Deadlybones

Handling object collisions

This topic is 2310 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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. Edited by B O N E S

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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... Edited by serumas

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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... Edited by serumas

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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... smile.png but I will try to calc how mutch collision check iteration will took your suggested method... Edited by serumas

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!