Oh I see now
The thing is your method has worst case time of n^2 and best case nC2 where as the method I outlined is nC2 worst case.
Computer Science Canada fast search technique for collision detection |
| Author: | shaon [ Sun Apr 13, 2008 9:38 pm ] |
| Post subject: | fast search technique for collision detection |
the simple method of collision checking between two objects at a time, for every combination of objects possible is easy to use but is terrible when there are lots of objects. if you have 30 circles and you want to see whether they are colliding it would take 30^2 for loop cycles to check all possibilities. I was able to cut it down to 30C2 (read as 30 choose 2) where the number of loop cycles was cut down 492 (compared to 900 before). However this method is still not good enough if you have say 500 objects or 1000 objects. When you have a space shooter with a machine gun, it isnt hard to reach such a higher number. So my question is based on the knowledge of the coordinates of the objects is it possible to make a more efficient search algorithm that gives a better time result than O(nC2) |
|
| Author: | Mackie [ Sun Apr 13, 2008 10:23 pm ] |
| Post subject: | RE:fast search technique for collision detection |
Complex collision detection scares me. So, here is a great link I stumbled onto a while ago... I hope it helps. Collision Detection |
|
| Author: | OneOffDriveByPoster [ Sun Apr 13, 2008 10:55 pm ] |
| Post subject: | Re: fast search technique for collision detection |
I don't think it can be better than O(n C 2) with just the positions. Anyhow, not sure if this makes it better or worse... Using spheres, if you do a sort by the distance of the sphere centres to a reference point (e.g., your fighter position), you only have to consider collisions between spheres with centres that are within 2 * maxradius of each other. Start with the object closest to the reference point (like your fighter) and check for collisions with objects farther away (within the limit). You will only need to look "away" from the reference point, so no object-pair will be considered twice. This is worst-case O(n C 2) collision checks with a O(n log n) preprocessing. |
|
| Author: | zylum [ Sun Apr 13, 2008 11:59 pm ] | ||
| Post subject: | RE:fast search technique for collision detection | ||
If you want to check between pairs of objects, then you would do something like this:
as you see, this results in 435 iterations. To further increase the speed of your calculations, avoid the use of square roots. These are horribly slow and you don't need them when doing circle vs circle collision detection. For instance, when checking if circles are colliding rather than if sqrt((b.x - a.x)^2 + (b.y - a.y)^2) <= a.radius + b.radius you can square both sides and have if (b.x - a.x)^2 + (b.y - a.y)^2 <= (a.radius + b.radius)^2 |
|||
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 12:27 am ] |
| Post subject: | Re: RE:fast search technique for collision detection |
zylum @ Sun Apr 13, 2008 11:59 pm wrote: as you see, this results in 435 iterations. You know, (30 C 2) = 435. The OP already has that (i.e., n C 2). |
|
| Author: | zylum [ Mon Apr 14, 2008 2:54 pm ] |
| Post subject: | RE:fast search technique for collision detection |
Indeed, though this method requires no preprocessing. Also, im not sure how your method works. I mean the thing about sorting based on distance to a reference point. Mind elaborating? I'm working on a project where I need a super fast search and maybe I can apply your method. shaon, if the circles have velocities, you can improve speeds by checking if the circles are moving towards each other. For more info on the topic you might want to check out my tutorial about circle collision detection. The example code is in turing but most of the tutorial covers concepts rather than code. |
|
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 3:06 pm ] |
| Post subject: | Re: fast search technique for collision detection |
The preprocessing is not meant to allow for faster worst-case time. In fact, if all your objects are at about the same distance from the reference point, you get hit by the penalty of having the preprocessing. The idea is simply to avoid checking pairs of objects that cannot possibly collide. Think of it as early termination of the inner loop that you had. |
|
| Author: | zylum [ Mon Apr 14, 2008 3:17 pm ] |
| Post subject: | RE:fast search technique for collision detection |
But having two objects the same distance from a reference point does not mean they are colliding. |
|
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 3:39 pm ] |
| Post subject: | Re: RE:fast search technique for collision detection |
zylum @ Mon Apr 14, 2008 3:17 pm wrote: But having two objects the same distance from a reference point does not mean they are colliding. Which is why you still need to do the check for objects that are about the same distance away from the reference point. I did say that. |
|
| Author: | zylum [ Mon Apr 14, 2008 6:07 pm ] |
| Post subject: | RE:fast search technique for collision detection |
I don't see the purpose of the reference point or how it helps with the collision detection. Here's a more concrete example: You have 2 circles or radius 10, one at position (0, 100) and the other at (100, 0). Assuming that the reference point is the origin, then they have the same distance from the reference point. Obviously they are not even close to colliding. So unless I am missing something, I don't see any point of sorting with respect to distance to some reference point. |
|
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 6:22 pm ] |
| Post subject: | Re: RE:fast search technique for collision detection |
zylum @ Mon Apr 14, 2008 6:07 pm wrote: I don't see the purpose of the reference point or how it helps with the collision detection. Here's a more concrete example:
Yes, they aren't colliding. Now if your circles are at position (0, 100) and (0, 120) they are also obviously not colliding and the sorting is supposed to help you make use of that.You have 2 circles or radius 10, one at position (0, 100) and the other at (100, 0). Assuming that the reference point is the origin, then they have the same distance from the reference point. Obviously they are not even close to colliding. So unless I am missing something, I don't see any point of sorting with respect to distance to some reference point. |
|
| Author: | zylum [ Mon Apr 14, 2008 6:47 pm ] |
| Post subject: | RE:fast search technique for collision detection |
Oh I see now
The thing is your method has worst case time of n^2 and best case nC2 where as the method I outlined is nC2 worst case. |
|
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 6:56 pm ] |
| Post subject: | Re: RE:fast search technique for collision detection |
zylum @ Mon Apr 14, 2008 6:47 pm wrote: The thing is your method has worst case time of n^2 and best case nC2 where as the method I outlined is nC2 worst case. I think it still has worst case O(n C 2). O(n C 2) is very close to O(n ^ 2), so the O(n log n) sort should not be significant. Using the same logic that you had for your loops (but with an extra check to break the inner loop earlier) will work just fine after the sort.
Edit: I am pretty sure it has best case O(n log n). |
|
| Author: | zylum [ Mon Apr 14, 2008 7:11 pm ] |
| Post subject: | RE:fast search technique for collision detection |
Worst case is O(n^2) when all circles have identical distance from reference point but this is rather unlikely. If the distances increment by more than 2*radius then I believe the best case would be O(n) because the inner loop would only do one comparison but this is also unlikely if you have many objects on the screen. Plus there's the cost of sorting which is O(nlogn). Doing amortized analysis on this problem wouldn't be too fun :S I wonder which method would be faster in practice.. |
|
| Author: | OneOffDriveByPoster [ Mon Apr 14, 2008 7:16 pm ] |
| Post subject: | Re: RE:fast search technique for collision detection |
zylum @ Mon Apr 14, 2008 7:11 pm wrote: I wonder which method would be faster in practice.. Me too. I understand where you are getting the n^2 from. I should have said "higher post-sort index" instead of whatever I said. I really do mean the exact same loop you have except with a break (as in C/C++ break) at the beginning of the inner loop. |
|
| Author: | r691175002 [ Mon Apr 14, 2008 8:06 pm ] |
| Post subject: | Re: fast search technique for collision detection |
You could always use a quadtree to filter the number of full collision tests you need to perform. |
|
| Author: | shaon [ Mon Apr 14, 2008 9:19 pm ] |
| Post subject: | Re: fast search technique for collision detection |
quadtree? what is that? I have read somewhere on google about octatrees and the likes but never really saw any article expand on it. Care to be the first one? For this part I'm assumming people understand what the "sort by reference position" is. It seems the idea of pre-processing and then only checking with the neighbours which have at max 2*radius might or might not be better than O(nC2). The initial sort algorithm would take O(n log n), assuming the standard sort is the merge sort, plus going through the list and checking the possible collision based on the 2*radius idea. If the distance between the first and the last item is less then 2*radius of the first object then the 2nd part of our algorithm would take us n C 2. Thus the worst case time for this algorithm is O(n log n + n C 2). However if the coordinates were such that the each coordinate neighbor in the sorted list was at max 2*radius distance (example given below): sorted_coordinates = [ (0,0,2) , (0,0,4), (0,0,6), (0,0,8) ] <== the radius of the object is 1.0000 or even this: sorted_coordinates = [ (0,0,20000000) , (0,0,400000000), (0,0,6000), (0,0,800000000000000) ] <== the radius of the object is 1.0000 In such a situation the amount of time that would take would be O(n) for the 2nd part of the algorithm since we only have to look one index down from each one. Thus the best case scenario is O( n log n + n) or O( n[ log + 1] ). The best possible case has a good chance of occuring or atleast the worst case has an extremely high chance of not happening. I'm sure in most games you don't have 1500 objects all in other's radius so this method in practical use, according to the calculations, actually has a good chance of being faster then the standard O(n^2) and O(n C 2). 2nd thing that I found was very awkard about Python: I did a series of test using a time measuring function from pygame, to see how long it takes to calculate square roots and squares of 1,000,000 numbers. The results were very suprising. math.sqrt(i) took about 532 ms to go complete 1,000,000 square roots. Using (i)^(.5) took about 350 ms, significantly less. I then tried to see how long it takes to do (i)^2 which takes about 1500 ms!! (i)^2.0 takes 350 ms!!! It seems (i)^(.5) and (i)^(2.0) takes the same time but (i)^(2) and math.sqrt(i) are terribly slow. As to why i to the power of an integer is so slow is weird... you'd think it would actually be faster. |
|
| Author: | r691175002 [ Mon Apr 14, 2008 10:51 pm ] |
| Post subject: | Re: fast search technique for collision detection |
Wikipedia has a pretty good picture of a quadtree (http://en.wikipedia.org/wiki/Quadtree). I haven't ever implemented a quadtree before but I would use it to eliminate half the possible collisions in each step, reducing your preprocessing to log N (best case) time. It is basically a binary tree in two spatial dimensions. I have done a significant amount of coding in flash (both slow and very graphics centric) and generally collision detection isn't a massive problem. If you take reasonable steps to filter out sprites that aren't on the screen etc there shouldn't be too many problems. Big O notation isn't extremely telling either, it is rare to get more than a few thousand objects at the same time, and the time spent on a pixel perfect detection vs a simple bounding box comparison will make a much bigger difference. |
|