-----------------------------------

shaon

Sun Apr 13, 2008 9:38 pm


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)


-----------------------------------

Mackie

Sun Apr 13, 2008 10:23 pm


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.

[url=http://www.harveycartel.org/metanet/tutorials/tutorialA.html]Collision Detection


-----------------------------------

OneOffDriveByPoster

Sun Apr 13, 2008 10:55 pm


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.


-----------------------------------

zylum

Sun Apr 13, 2008 11:59 pm


RE:fast search technique for collision detection

-----------------------------------

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

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)