fast search technique for collision detection

[shaon]

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)

[Mackie]

Complex collision detection scares me. So, here is a great link I stumbled onto a while ago... I hope it helps.

Collision Detection

[OneOffDriveByPoster]

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.

[zylum]

If you want to check between pairs of objects, then you would do something like this:

code:

var n := 0 for i : 1 .. 30     for j : i + 1 .. 30         n += 1     end for end for put n

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

[OneOffDriveByPoster]

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

[zylum]

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.

[OneOffDriveByPoster]

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.

[zylum]

But having two objects the same distance from a reference point does not mean they are colliding.

[OneOffDriveByPoster]

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.

[zylum]

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.

[OneOffDriveByPoster]

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:

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.

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.

[zylum]

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.

[OneOffDriveByPoster]

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

[zylum]

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

[OneOffDriveByPoster]

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.