Forums - Collision detection algorithms

Forums (http://www.abandonia.com/vbullet/index.php)

- Programming (http://www.abandonia.com/vbullet/forumdisplay.php?f=25)

- - Collision detection algorithms (http://www.abandonia.com/vbullet/showthread.php?t=25545)

Collision detection algorithms

Assuming the collision detection runs for all objects on the map (because it does; neither programmer has much of an idea how to optimize that).
Which of these solutions is more effective? Is there a better way to do it?

Code:

bool check_collision(int x1, int y1, int x2, int y2, int r1, int r2) {

float d_x=x1-x2, d_y=y1-y2;

if (sqrt(d_x*d_x+d_y*d_y)<r1+r2) return true;

else return false; }

Code:

bool check_collision(int x1, int y1, int x2, int y2, int r1, int r2){

          int d_x=abs(x1-x2), r_t=r1+r2;

          if (d_x<r_t) { int d_y=abs(y1-y2);

                         if (d_y<r_t) { if (d_x*d_x+d_y*d_y<r_t*r_t) return true;

                                        else return false; }

                         else return false; }

Well, eliminating the square root is a good idea, but you're doing it rather inefficiently. This would be a lot easier. Note that there's no need for floating point math (if your coordinates remain under 32768).

Code:

bool check_collision (int x1, int y1, int x2, int y2, int r1, int r2)

{

    int dx = x2 - x1;

    int dy = y2 - y1;

    int sr = r1 + r2;

    return (dx * dx + dy * dy) < (sr * sr);

}

BUT! You're optimising the wrong thing here...

Sure, there are some small gains to be made this way, but the more important thing is to reduce the amount of checks done in the first place. You said to assume that the collision check always runs, but that's a bad premise, especially if that means you're checking every single object against every other object. That has a big-O of n², which is bad. For 1000 objects, the amount of checks would be over half a million, which is ridiculous :no:

Here's some a tip for an method to get that number down, assuming a 2D map (though extendable to 3D):

create a collision grid the same size of your map, just coarser, so that each cell in the collision grid is larger than the largest object
keep a reference to each object in the cell on the collision grid
keep track of which objects have moved
do a collision check only on other objects in the same cell on the collision grid and in directly neighbouring cells