Newbie physics simulation question (collision detection)

[Jaevko]

I'm writing a physics simulation/game in java applets, I have a quick question about collision detection. DISCLAIMER: I am not a math or a CS major, so this is probably a ridiculously easy question for most people on here:

My question regards speed when there are lots of objects. Right now, the game checks all objects (circles) against all objects to see if there is a collision. I was originally gonna divide space up in to grids (squares) and check each item against all items in its grid and (8) adjacent grids. However, I got to thinking...checking to see if the distance is less than the sum of the radii is not that bad, and dividing into grids WILL consume resources. So to test the theory of "leaving it how it is is okay" I added one hundred objects (so each checking against every other is running through this code something like 100*100/2 times, a lot!). However, it still ran fine.

So the question is: Do I just need to add more objects to experience the slow-down that dividing into grids will save me from? Or will dividing the area into grids not provide a significant advantage/actually be worse than my current method?

Relevant code is below:

Code: Select all

       for (int counter1 = 0; counter1 < PhysicsApplet.mastercounter-1; counter1++) { //run all moveable
            for (int counter2 = counter1+1; counter2 < PhysicsApplet.mastercounter; counter2++) //run through all the ones that have not been check against it yet (anything above it on the list)
            {
                srad = PhysicsApplet.masterlist[counter1].radius + PhysicsApplet.masterlist[counter2].radius; //sum radii
                dis = Math.sqrt((PhysicsApplet.masterlist[counter1].x_pos - PhysicsApplet.masterlist[counter2].x_pos)*(PhysicsApplet.masterlist[counter1].x_pos - PhysicsApplet.masterlist[counter2].x_pos) + (PhysicsApplet.masterlist[counter1].y_pos - PhysicsApplet.masterlist[counter2].y_pos)*(PhysicsApplet.masterlist[counter1].y_pos - PhysicsApplet.masterlist[counter2].y_pos));
                if (srad > dis) { //if true then collision

Thanks for your time!!!
-Computational Physics Newbie


P.S. I am eventually gonna do some sort of trajectory analysis to avoid fast objects going through each other, but my question has nothing to do with that issue, for now I am satisfied with the "if its touching during the frame then collision" algorithm.

[h4tt3n]

Hello there,

There are several issues with your current setup, the most notable beeing the use of sqrtf(). Square root functions always take up a relatively large portion of cpu-power, especially when nested inside a double loop. Instead, you could test the circle radiii squared against the distance squared. This way a small code change will provide a pretty large gain in speed. If you want to deal with much larger number of circles, you'll have to implement a grid based system.

Cheers,
Mike