BACKGROUND: As discussed here: Fast 2D collision detection in an unbounded space I am working on a collision detection algorithm for a simulation. The catch that makes this case unique is that the objects in the simulation could all be in a very small area (e.g. 1000x1000) or in a very large area (e.g. 9 bil x 10 bil). Moreover, changes like this could occur very rapidly because of high object velocities, so I needed a somewhat sophisticated algorithm to deal with this situation. In the end, I went with quadtrees (http://en.wikipedia.org/wiki/Quadtree). When I finished writing the quadtree class and determined that it was functioning correctly, I uploaded it into my simulation.
THE PROBLEM: At first, the quadtree worked wonderfully. I was just testing it out for the first time, so instead of feeding it updated bounds every time step of the objects with the least x value/greatest x value/least y value/greatest y value, I just fed is a large area that I knew would be good enough for the test case (10 mil x 10 mil).
In a test involving 1600 objects, my simulation ran almost four times faster than the brute force solution of checking every object against itself! (about 28 fps instead of 7 fps) Wonderful! I then proceeded to feed the quadtree the updated "bounds" of the simulation by finding the min/max x/y each frame (this is where the problem begins). After updating each object's position, I simply checked to see if it was the new min/max extreme in each dimension:
double tempradius = (*getMoveableEntityVector()[n]).Retradius();
double tempx = (*getMoveableEntityVector()[n]).Retxpos();
double tempy = (*getMoveableEntityVector()[n]).Retypos();
if (n == 0) { //if it's the first object initialize the variables based off it
minx = tempx - tempradius;
maxx = tempx + tempradius;
miny = tempy - tempradius;
maxy = tempy + tempradius;
}
else { //all other objects
if (minx > tempx - tempradius) { //if this object has the lowest x value
minx = tempx - tempradius;
}
else if (maxx < tempx + tempradius) { //if has the highest x value
maxx = tempx + tempradius;
}
if (miny > tempy - tempradius) { //if has lowest y value
miny = tempy - tempradius;
}
else if (maxy < tempy + tempradius) { //if has highest y value
maxy = tempy + tempradius;
}
}
Running through this simple code a mere 1600 times per time step slowed the simulation back down below the speed of my original brute force implementation! (about 7 fps)
WHY THIS DOESN'T MAKE SENSE TO ME: The original brute force implementation had to run through the relatively computationally intense distance formula (http://math.about.com/library/bldistance.htm) about 1600*1600 times per time step, or more exactly, 1600*1599/2 = 1,279,200 times per time step. I would think running through the above code once would be about as computationally intensive as doing the distance formula once. How is going through the above code only 1,600 times costing me as much processor time as going through the distance formula more than a million times?!?
EDIT: The question is not directly about the quadtree; it is about the code above that finds the objects with the least/greatest x/y coordinates. (This code feeds its calcuations to the quadtree so the quadtree knows where to start, but it is definitely not quadtree code). The quadtree code ran quite fast until I added the above helper code. The only reason I mentioned the quadtree and the background to this issue is because the quadtree/background stuff gives context on why I think that this code should be going much faster (1000 comparable checks vs 1,000,000!)
TLDR (TOO LONG DIDN'T READ): Check out the code above. Is there something making it take up WAY more (about 1000x more!) processor time than I think it should be taking?
Thanks in advance for the time and help!