2d collision detection sources

[Jack Norton]

Could any expert programmer share the C source code for decent 2d collisions? I tried to search around teh net but can't find any good working example in C :(
As some of you may know I'm trying to make a shoot'em up but the actual collision system I've made quite sucks... :D
Help!!

[princec]

Sorry, only got Java code... what sort of collisions were you trying to detect, anyway?

Cas :)

[GameStudioD]

One way to do good collision is with bounding boxes plus per pixel checking. For each sprite, a bit array is built based on its pixels. 0 for transparent, 1 for not transparent. This can be optimized by putting 32 pixels in an unsigned int. If 2 boxes collide, then the bit arrays are compared.

This method should be good for a shooter, especially if you use quad trees or some other thing for reducing dedections.

There are also many other ways to do good collision detection.

[Devman]

Hey Jack,

I posted a quad tree tutorial on my website a few days back, and the next article I am writing is how I did my 2D collision detection. The only things I really do collisions for is circle to circle and circle to line segment, so it may not be exactly what will help your program. I hope to work on it in the next week or two. I will post here when I finish it.

Good luck! I had a tough time with the 2D collision detection for lots of reasons. I wish there were a good library for doing it!

[3dben]

As a quick side note to the bounding box, it probably doesnt need to be said, but it doesnt hurt. Be sure to optimize your compare by checking only the pixels within the union of the overlapping boxes.

Also, dont forget circle collission. This can be a nice fast way to weed stuff out, if it collides then you need to go deeper into the pixel check. One thing to note though is that you might be able optimize by building your union box coords during bounding box check in which case this circle collision (or range check as I like to call it) is probably not necessary. With that said, here's my range checking code for whatever use it might be.

BD_BOOL cBDVector2D::InRange(const cBDVector2D& oVec,
BD_FLOAT fRange){
BD_FLOAT xd = this->x-oVec.x;
BD_FLOAT yd = this->y-oVec.y;

return ((xd*xd + yd*yd)<(fRange*fRange));
} // end of InRange


-=ben
www.clevermonkeystudios.com

[Jack Norton]

well ships sprites almost cover a whole rectangle surface and they'll move a lot so I don't exactly need per pixel-check...
hmm well I'll try with 3dben method, my real problem is that I have 40 different spaceships each one with 2-3 different bullet type (some long rays, other small spheres, etc).
let's see what I can do :)

[3dben]

One thing nice about doing spheres is, its fast and easy, you can always refine later if you find you need it to be a bit more accurate. Also keep in mind the sphere can be any size you want it to be, but to keep it simple probably set your radius to width of your sprites. Also, note if your sprites are much longer or wider then a perfect square then sphere collission will start degrading rather quickly.

In the end of the day, do what makes since. If you have a long missle then a sphere collission is probably a bad idea. But if you have round flying saucers then its hard to beat. You can also mix collission types, create an abstract collission class and derive from that different methods. Use a sphere when it makes since, a box for others, etc.. Then you can easily do sphere/box collissions, etc.. and switch them as needed.

(am I rambling??)

-=ben
www.clevermonkeystudios.com

[RedKnight]

Very easy :D

with box and box collision, I'm even using it in my future "Radiant Silvergun" clone game. (Just watch out for this game!)

You take one 2d vector, from box 1, calculate it with the 4(or more) others vectors from box 2. (computing the angles between two vectors)
if the sum of all the angles are 360. then there's a collision.
else: no collision

[Dan MacDonald]

You can also do circle collision, assign a point and a raidus to each sprite or object you want to collide. If the distance between the the center of the two circles is less then the sum of the raidus of the two circles, there is a collision.

[keethrus]

Another good thing about the circle-circle or circle-line collision tests are that, given each center, radius, and velocity vector, you can find the exact time of collision (if any); not just "collision" or "no collision", but the exact moment in the timeslice that they do collide.

- Jeremiah

[RedKnight]

Try Gametutorials Collision tutorials.

They're 3d but it isn't that hard to convert it in to 2d.

[Larry Hastings]

I'd post my source code, but it's all tied in with my object model and things, so I'm not sure it'd be useful.

But here's a tip I picked up long ago: if x = y, then x^2 = y^2. In other words, when you check to see if two spheres are colliding, don't bother taking the square root of the distance between them. Just square the sum of their radii and compare that to the distance squared. Squaring is fast, and sqrt() is slow.

Cheers,

[GrahamGoring]

Is there a way of including a code-box in replies? Only I'd glad post my stuff for collisions between any two of:

point
circle
rectangle
rotated rectangle

And any two of:

line
circle

[Jack Norton]

Yes, simply paste your code in the reply window then select it all and click the # button (CODE).



Like in this example

[tentons]

I was just going to ask about rotated rectangles, as I'm hoping to use those myself. :)


I think you can put code here.

Use [ code ] and [ /code ] (minus spaces).

[RedKnight]

The distance between two vectors.



Distance = Sqrt ((X1 - X2) * (Y1 - Y2))


You should figure out how to add the radius stuff into it.

[GrahamGoring]

Feel free to rip apart and diss my coding. :)

Part 1 of 2




#define BEFORE_LINE (-1)
#define ON_LINE (0)
#define AFTER_LINE (1)

#define CO_LINEAR (-1)
#define NO_INTERSECTION (0)
#define INTERSECTION (1)

#define NUM_CO_ORDS (4)
#define NUM_AXIS (2)

#define X_CO_ORD (0)
#define Y_CO_ORD (1)


typedef struct
{
int co_ords[NUM_CO_ORDS][NUM_AXIS]; // Don't really need float for the sort of accuracy I'm after.
float angle;
int pivot_x;
int pivot_y;
float cos_angle;
float sin_angle;
} rectangle;



int MATH_sgn_float (float value)
{
if (value<0)
{
return -1;
}
else if (value>0)
{
return 1;
}
else
{
return 0;
}
}



float MATH_distance_to_line (float x1, float y1, float x2, float y2, float px, float py , int *point_of_line , float *ratio_on_line)
{
float v1x,v1y,v2x,v2y,v3x,v3y,temp,vtx,vty,dx,dy,dot_pro duct,distance_to_line;

v1x = px-x1; // Difference between point and start of line
v1y = py-y1;

v2x = x2-x1; // Difference between start and end of line.
v2y = y2-y1;

temp = float (sqrt ( (v2x * v2x) + (v2y * v2y) )); // Length of line

v2x = v2x/temp; // Unit length of line.
v2y = v2y/temp;

dot_product = (v1x * v2x) + (v1y * v2y); // dot-product of the unit-length line vector and the vector to the point from the beginning of the line

if (dot_product<=0) // it's actually the first point of the line that it's closest to...
{
vtx = x1;
vty = y1;
dx = px-vtx;
dy = py-vty;
distance_to_line = float (sqrt ((dx*dx)+(dy*dy)));
*ratio_on_line = dot_product / temp;
*point_of_line = BEFORE_LINE;
return distance_to_line;
}
else if (dot_product>=temp) // it's the last point of the line it's closest to...
{
vtx = x2;
vty = y2;
dx = px-vtx;
dy = py-vty;
distance_to_line = float (sqrt ((dx*dx)+(dy*dy)));
*ratio_on_line = dot_product / temp;
*point_of_line = AFTER_LINE;
return distance_to_line;
}
else // Nope, wait, it's closest to a point on the line... BUT WHERE?!
{
v3x = v2x * dot_product;
v3y = v2y * dot_product;

vtx = x1 + v3x;
vty = y1 + v3y;

dx = px-vtx;
dy = py-vty;

distance_to_line = float (sqrt ((dx*dx)+(dy*dy)));
*ratio_on_line = dot_product / temp;
*point_of_line = ON_LINE;

return distance_to_line;
}
}



bool MATH_same_signs (float a, float b)
{
if (MATH_sgn_float (a) != MATH_sgn_float (b))
{
return false;
}
else
{
return true;
}
}



int MATH_intersect_lines (float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4,float *ix,float *iy)
{
float x,y,a1,b1,c1,a2,b2,c2,r1,r2,r3,r4,denom,offset,num ;

a1 = y2 - y1;
b1 = x1 - x2; // Vector from start to end of line, except mirrored.
c1 = (x2 * y1) - (x1 * y2);

r3 = (a1 * x3) + (b1 * y3) + c1;
r4 = (a1 * x4) + (b1 * y4) + c1;

if ( ( r3 != 0 ) && (r4 != 0 ) )
{
if (MATH_same_signs ( r3, r4 ) == true)
{
return NO_INTERSECTION; // Don't intersect!
}
}

a2 = y4 - y3;
b2 = x3 - x4;
c2 = (x4 * y3) - (x3 * y4);

r1 = (a2 * x1) + (b2 * y1) + c2;
r2 = (a2 * x2) + (b2 * y2) + c2;

if ( ( r1 != 0 ) && (r2 != 0 ) )
{
if (MATH_same_signs ( r1, r2 ) == true)
{
return NO_INTERSECTION; // Don't intersect!
}
}

denom = (a1 * b2) - (a2 * b1);

if ( denom == 0 )
{
return CO_LINEAR; // That's posh talk for parallel. ;)
}

// line segments intersect, compute intersection point

if (denom < 0)
{
offset = -denom / 2;
}
else
{
offset = denom / 2;
}

num = (b1 * c2) - (b2 * c1);

if (num < 0)
{
x = (num - offset) / denom;
}
else
{
x = (num + offset) / denom;
}

num = (a2 * c1) - (a1 * c2);

if (num < 0)
{
y = (num - offset) / denom;
}
else
{
y = (num + offset) / denom;
}

*ix = x;
*iy = y;

return INTERSECTION;
}



bool MATH_line_to_line_intersect (int line_1_x1 , int line_1_y1 , int line_1_x2 , int line_1_y2 , int line_2_x1 , int line_2_y1 , int line_2_x2 , int line_2_y2 )
{
int a1,b1,c1,a2,b2,c2,r1,r2,r3,r4,denom;

a1 = line_1_y2 - line_1_y1;
b1 = line_1_x1 - line_1_x2; // Vector from start to end of line, except mirrored.
c1 = (line_1_x2 * line_1_y1) - (line_1_x1 * line_1_y2); // cross product

r3 = (a1 * line_2_x1) + (b1 * line_2_y1) + c1;
r4 = (a1 * line_2_x2) + (b1 * line_2_y2) + c1;

if ( ( r3 != 0 ) && (r4 != 0 ) )
{
if (MATH_same_signs ( r3, r4 ) == true)
{
return false; // Don't intersect!
}
}

a2 = line_2_y2 - line_2_y1;
b2 = line_2_x1 - line_2_x2;
c2 = (line_2_x2 * line_2_y1) - (line_2_x1 * line_2_y2); // cross product

r1 = (a2 * line_1_x1) + (b2 * line_1_y1) + c2;
r2 = (a2 * line_1_x2) + (b2 * line_1_y2) + c2;

if ( ( r1 != 0 ) && (r2 != 0 ) )
{
if (MATH_same_signs ( r1, r2 ) == true)
{
return false; // Don't intersect!
}
}

denom = (a1 * b2) - (a2 * b1); // cross product

if ( denom == 0 )
{
return false; // That's parallel. ;)
}

return true;
}



int MATH_wrap (int value , int wrap)
{
// It's just like modulus, only it works for negative numbers properly (it doesn't reflect them).

int times;

if (wrap>0)
{
if (value < 0)
{
times = (abs(value) / wrap) + 1;
value += (times * wrap);
}

value = value % wrap;

return value;
}
else
{
return 0;
}
}



void MATH_make_rectangle ( rectangle *r , int x, int y, int upper_width , int upper_height , int lower_width , int lower_height , float angle )
{

r->angle = angle;

r->pivot_x = x;
r->pivot_y = y;

r->co_ords[0][X_CO_ORD] = -upper_width;
r->co_ords[0][Y_CO_ORD] = -upper_height;

r->co_ords[1][X_CO_ORD] = lower_width;
r->co_ords[1][Y_CO_ORD] = -upper_height;

r->co_ords[2][X_CO_ORD] = lower_width;
r->co_ords[2][Y_CO_ORD] = lower_height;

r->co_ords[3][X_CO_ORD] = -upper_width;
r->co_ords[3][Y_CO_ORD] = lower_height;

}



void MATH_rotate_and_translate_rect ( rectangle *r )
{
// Assumes that co-ordinates are supplied already around the origin.

int i;
r->sin_angle = float (sin(r->angle));
r->cos_angle = float (cos(r->angle));
float temp_x, temp_y;
int old_x,old_y;

for (i=0 ; i<NUM_CO_ORDS ; i++)
{
old_x = r->co_ords[i][X_CO_ORD];
old_y = r->co_ords[i][Y_CO_ORD];
temp_x = ( r->co_ords[i][X_CO_ORD] * r->cos_angle ) + ( r->co_ords[i][Y_CO_ORD] * r->sin_angle );
temp_y = ( -r->co_ords[i][X_CO_ORD] * r->sin_angle ) + ( r->co_ords[i][Y_CO_ORD] * r->cos_angle );
r->co_ords[i][X_CO_ORD] = int (temp_x + r->pivot_x);
r->co_ords[i][Y_CO_ORD] = int (temp_y + r->pivot_y);
}

}



void MATH_find_rotated_rectangle_extents ( rectangle *r , int *rect_x1 , int *rect_y1 , int *rect_x2 , int *rect_y2 )
{
// Find the axis-aligned bounding box required to fit a rotated rectangle.

if (r->co_ords[0][X_CO_ORD] < r->co_ords[1][X_CO_ORD])
{
if (r->co_ords[0][Y_CO_ORD] < r->co_ords[1][Y_CO_ORD])
{
*rect_x1 = r->co_ords[3][X_CO_ORD];
*rect_y1 = r->co_ords[0][Y_CO_ORD];
*rect_x2 = r->co_ords[1][X_CO_ORD];
*rect_y2 = r->co_ords[2][Y_CO_ORD];
}
else
{
*rect_x1 = r->co_ords[0][X_CO_ORD];
*rect_y1 = r->co_ords[1][Y_CO_ORD];
*rect_x2 = r->co_ords[2][X_CO_ORD];
*rect_y2 = r->co_ords[3][Y_CO_ORD];
}
}
else
{
if (r->co_ords[0][Y_CO_ORD] < r->co_ords[1][Y_CO_ORD])
{
*rect_x1 = r->co_ords[2][X_CO_ORD];
*rect_y1 = r->co_ords[3][Y_CO_ORD];
*rect_x2 = r->co_ords[0][X_CO_ORD];
*rect_y2 = r->co_ords[1][Y_CO_ORD];
}
else
{
*rect_x1 = r->co_ords[1][X_CO_ORD];
*rect_y1 = r->co_ords[2][Y_CO_ORD];
*rect_x2 = r->co_ords[3][X_CO_ORD];
*rect_y2 = r->co_ords[0][Y_CO_ORD];
}
}

}



bool MATH_rotated_rectangle_bounding_box_check ( rectangle *r1 , rectangle *r2 )
{


int rect_1_x1,rect_1_y1,rect_1_x2,rect_1_y2;
int rect_2_x1,rect_2_y1,rect_2_x2,rect_2_y2;

MATH_find_rotated_rectangle_extents ( r1 , &rect_1_x1 , &rect_1_y1 , &rect_1_x2 , &rect_1_y2 );
MATH_find_rotated_rectangle_extents ( r2 , &rect_2_x1 , &rect_2_y1 , &rect_2_x2 , &rect_2_y2 );

return MATH_rectangle_to_rectangle_intersect (rect_1_x1 , rect_1_y1 , rect_1_x2 , rect_1_y2 , rect_2_x1 , rect_2_y1 , rect_2_x2 , rect_2_y2);

}

[GrahamGoring]

Part 2 of 2, NB. the intersecting line and nearest point on line stuff wasn't originally written by me.




bool MATH_rotated_rectangle_to_point_intersect ( rectangle *r , int px, int py )
{
int result = 0;
int t;
int p1;
int diff_line_x,diff_line_y,diff_point_x,diff_point_y;

for (t=0; t<NUM_CO_ORDS ;t++)
{
p1 = (t != NUM_CO_ORDS-1) ? t+1 : 0;

diff_line_x = r->co_ords[p1][X_CO_ORD] - r->co_ords[t][X_CO_ORD];
diff_line_y = r->co_ords[p1][Y_CO_ORD] - r->co_ords[t][Y_CO_ORD];

diff_point_x = px - r->co_ords[t][X_CO_ORD];
diff_point_y = py - r->co_ords[t][Y_CO_ORD];

result += (MATH_sgn_int ( (diff_line_x * diff_point_y) - (diff_point_x * diff_line_y) ) >= 0);

if (result != t+1) // ie, the first time it doesn't match it'll quit out to save doing the other checks.
{
return false;
}
}

return true; // Although it should never get here.
}



bool MATH_rotated_rectangle_to_rotated_rectangle_inters ect ( rectangle *r1 , rectangle *r2 )
{
if ( MATH_rotated_rectangle_bounding_box_check ( r1 , r2 ) == false )
{
return false;
}

int t;

for (t=0; t<NUM_CO_ORDS ; t++)
{
if (MATH_rotated_rectangle_to_point_intersect ( r2 , r1->co_ords[t][X_CO_ORD], r1->co_ords[t][Y_CO_ORD] ) == true)
{
return true;
}
}

for (t=0; t<NUM_CO_ORDS ; t++)
{
if (MATH_rotated_rectangle_to_point_intersect ( r1 , r2->co_ords[t][X_CO_ORD], r2->co_ords[t][Y_CO_ORD] ) == true)
{
return true;
}
}

if (MATH_line_to_line_intersect ( r1->co_ords[0][X_CO_ORD] , r1->co_ords[0][Y_CO_ORD] , r1->co_ords[2][X_CO_ORD] , r1->co_ords[2][Y_CO_ORD] , r2->co_ords[0][X_CO_ORD] , r2->co_ords[0][Y_CO_ORD] , r2->co_ords[2][X_CO_ORD] , r2->co_ords[2][Y_CO_ORD] ) == true)
{
return true;
}

return false;

}




bool MATH_rotated_rectangle_to_rectangle_intersect ( rectangle *r1 , int rect_x1 , int rect_y1 , int rect_x2 , int rect_y2 )
{
rectangle r2;

r2.angle = 0;
r2.cos_angle = 1;
r2.sin_angle = 0;

r2.co_ords[0][X_CO_ORD] = rect_x1;
r2.co_ords[0][Y_CO_ORD] = rect_y1;

r2.co_ords[1][X_CO_ORD] = rect_x2;
r2.co_ords[1][Y_CO_ORD] = rect_y1;

r2.co_ords[2][X_CO_ORD] = rect_x2;
r2.co_ords[2][Y_CO_ORD] = rect_y2;

r2.co_ords[3][X_CO_ORD] = rect_x1;
r2.co_ords[3][Y_CO_ORD] = rect_y2;

return (MATH_rotated_rectangle_to_rotated_rectangle_inter sect ( r1 , &r2 ) );
}



bool MATH_rotated_rectangle_to_circle_intersect (rectangle *r , int px , int py , int radius )
{
if (MATH_rotated_rectangle_to_point_intersect ( r , px, py ) == true)
{
return true;
}

int t,p;
int total = 0;
int result[NUM_CO_ORDS];
float norm_x,norm_y;

int diff_line_x,diff_line_y,diff_point_x,diff_point_y;

for (t=0; t<NUM_CO_ORDS ;t++)
{
p = (t != NUM_CO_ORDS-1) ? t+1 : 0;

diff_line_x = r->co_ords[p][X_CO_ORD] - r->co_ords[t][X_CO_ORD];
diff_line_y = r->co_ords[p][Y_CO_ORD] - r->co_ords[t][Y_CO_ORD];

diff_point_x = px - r->co_ords[t][X_CO_ORD];
diff_point_y = py - r->co_ords[t][Y_CO_ORD];

result[t] = MATH_sgn_int ( (diff_line_x * diff_point_y) - (diff_point_x * diff_line_y) ); // ie, if the sign of the cross-product is negative or zero it's either on this line or outside it so check distance.
total += (result[t] <= 0);
}

if (total == 1) // Only one result was negative, so it's by a line segmentbody.
{
if (result[0] <= 0) // it's closest to the first line section.
{
// The first line section was originally oriented leading to the right.
norm_x = -r->sin_angle;
norm_y = -r->cos_angle;
diff_line_x = r->co_ords[1][X_CO_ORD] - r->co_ords[0][X_CO_ORD];
diff_line_y = r->co_ords[1][Y_CO_ORD] - r->co_ords[0][Y_CO_ORD];
diff_point_x = px - (r->co_ords[0][X_CO_ORD] + int (norm_x * radius));
diff_point_y = py - (r->co_ords[0][Y_CO_ORD] + int (norm_y * radius));
}
else if (result[1] <= 0) // it's closest to the second line section.
{
norm_x = r->cos_angle;
norm_y = -r->sin_angle;
diff_line_x = r->co_ords[2][X_CO_ORD] - r->co_ords[1][X_CO_ORD];
diff_line_y = r->co_ords[2][Y_CO_ORD] - r->co_ords[1][Y_CO_ORD];
diff_point_x = px - (r->co_ords[1][X_CO_ORD] + int (norm_x * radius));
diff_point_y = py - (r->co_ords[1][Y_CO_ORD] + int (norm_y * radius));
}
else if (result[2] <= 0) // it's closest to the third line section.
{
norm_x = r->sin_angle;
norm_y = r->cos_angle;
diff_line_x = r->co_ords[3][X_CO_ORD] - r->co_ords[2][X_CO_ORD];
diff_line_y = r->co_ords[3][Y_CO_ORD] - r->co_ords[2][Y_CO_ORD];
diff_point_x = px - (r->co_ords[2][X_CO_ORD] + int (norm_x * radius));
diff_point_y = py - (r->co_ords[2][Y_CO_ORD] + int (norm_y * radius));
}
else // it's closest to the fourth line section.
{
norm_x = -r->cos_angle;
norm_y = r->sin_angle;
diff_line_x = r->co_ords[0][X_CO_ORD] - r->co_ords[3][X_CO_ORD];
diff_line_y = r->co_ords[0][Y_CO_ORD] - r->co_ords[3][Y_CO_ORD];
diff_point_x = px - (r->co_ords[3][X_CO_ORD] + int (norm_x * radius));
diff_point_y = py - (r->co_ords[3][Y_CO_ORD] + int (norm_y * radius));
}

if ( MATH_sgn_int ( (diff_line_x * diff_point_y) - (diff_point_x * diff_line_y) ) >= 0 )
{
return true;
}
}
else // It was outside two lines therefor closest to a corner - nice and easy to deal with.
{
if ( (result[0] <= 0) && (result[1] <= 0) )
{
return ( MATH_circle_to_point_intersect ( r->co_ords[1][X_CO_ORD], r->co_ords[1][Y_CO_ORD], radius , px , py ) );
}
else if ( (result[1] <= 0) && (result[2] <= 0) )
{
return ( MATH_circle_to_point_intersect ( r->co_ords[2][X_CO_ORD], r->co_ords[2][Y_CO_ORD], radius , px , py ) );
}
else if ( (result[2] <= 0) && (result[3] <= 0) )
{
return ( MATH_circle_to_point_intersect ( r->co_ords[3][X_CO_ORD], r->co_ords[3][Y_CO_ORD], radius , px , py ) );
}
else
{
return ( MATH_circle_to_point_intersect ( r->co_ords[0][X_CO_ORD], r->co_ords[0][Y_CO_ORD], radius , px , py ) );
}
}

return false;

}



bool MATH_rectangle_to_rectangle_intersect (int rect_1_x1 , int rect_1_y1 , int rect_1_x2 , int rect_1_y2 , int rect_2_x1 , int rect_2_y1 , int rect_2_x2 , int rect_2_y2)
{
// Note that x1,y1 is the top-left of the rectangle and x2,y2 is the bottom right!
// If you pass them the wrong way around it won't work.

if ( (rect_1_x2 < rect_2_x1) || (rect_1_y2 < rect_2_y1) || (rect_2_x2 < rect_1_x1) || (rect_2_y2 < rect_1_y1) )
{
return false;
}
else
{
return true;
}
}



bool MATH_rectangle_to_circle_intersect ( int rect_x1 , int rect_y1 , int rect_x2 , int rect_y2 , int circle_x , int circle_y , int radius )
{
// This is a simple enough test although it's split into a few stages. First of all we do a simple point in rect
// check and return true if it succeeds.

if ( MATH_rectangle_to_point_intersect ( rect_x1 , rect_y1 , rect_x2 , rect_y2, circle_x, circle_y) == true )
{
return true;
}
else
{
// If it isn't inside the rectangle then it's either closest to a side or a corner. So first we check whether the
// point is within the scope of one of the sides...

if ( (circle_x >= rect_x1) && (circle_x <= rect_x2) )
{
// It's within the horizontal scope.
if (circle_y < rect_y1)
{
// It's above the rectangle.
if (rect_y1 - circle_y <= radius)
{
return true;
}
else
{
return false;
}
}
else
{
// It's below the rectangle.
if (circle_y - rect_y2 <= radius)
{
return true;
}
else
{
return false;
}
}
}
else if ( (circle_y >= rect_y1) && (circle_y <= rect_y2) )
{
// It's within the vertical scope.
if (circle_x < rect_x1)
{
// It's to the left of the rectangle.
if (rect_x1 - circle_x <= radius)
{
return true;
}
else
{
return false;
}
}
else
{
// It's to the right of the rectangle.
if (circle_x - rect_x2 <= radius)
{
return true;
}
else
{
return false;
}
}
}
else if ( (circle_x < rect_x1) && (circle_y < rect_y1) )
{
// It's up-left of the rectangle.
return ( MATH_circle_to_point_intersect ( rect_x1, rect_y1, radius , circle_x , circle_y ) );
}
else if ( (circle_x > rect_x2) && (circle_y < rect_y1) )
{
// It's up-right of the rectangle.
return ( MATH_circle_to_point_intersect ( rect_x2, rect_y1, radius , circle_x , circle_y ) );
}
else if ( (circle_x < rect_x1) && (circle_y > rect_y2) )
{
// It's down-left of the rectangle.
return ( MATH_circle_to_point_intersect ( rect_x1, rect_y2, radius , circle_x , circle_y ) );
}
else if ( (circle_x > rect_x2) && (circle_y > rect_y2) )
{
// It's down-right of the rectangle.
return ( MATH_circle_to_point_intersect ( rect_x2, rect_y2, radius , circle_x , circle_y ) );
}
else
{
// WHERE THE HELL IS IT THEN?!!
assert (0);
return false; // SHOULD NEVER GET HERE!
}

}

}



bool MATH_rectangle_to_point_intersect (int rect_x1 , int rect_y1 , int rect_x2 , int rect_y2 , int px, int py)
{
if ( (px<rect_x1) || (py<rect_y1) || (px>rect_x2) || (py>rect_y2) )
{
return false;
}
else
{
return true;
}
}



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

// Obviously this is good ol' pythag but with the sqrt's squared out.

if ( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) < (r1 + r2) * (r1 + r2) )
{
return true;
}
else
{
return false;
}

}



bool MATH_circle_to_point_intersect ( int x1 , int y1 , int r1 , int x2 , int y2 )
{

// Obviously this is good ol' pythag but with the sqrt's squared out.

if ( ( (x1-x2) * (x1-x2) ) + ( (y1-y2) * (y1-y2) ) < (r1 * r1) )
{
return true;
}
else
{
return false;
}

}

[tentons]

Wow, I may try this and see how easily it drops into an existing codebase. :cool:

I swear there needs to be a forum for posting code like this... hmm.

[Jack Norton]

Actually that's a good idea.
When I was using Blitzbasic one of the best resource for me was the "Code Archive" forum, where I could find lot of working code for common stuff like this collisions detection but also pathfinding, etc...
I'd really like to see something like that here :)

[Znarkus]

Huge thanks to you Graham! Very useful code! Only one question:
What does the coordinates define? :confused: Are they the corner's position relative to the pivot point? Or are they absolute?
Again, thanks for a great collision detection code!

[Sharpfish]

Does this correct for overlap (backing up through time?) can't have a good look at the code atm, just skimmed through. I think that is one of the hardest parts to get right for someone setting up collision detection. The system I have in my framework at the moment works (it's 3d and has some collision response as well but nothing super fancy yet) but really needs simplifying. Sphere > Sphere overlap correction (before render) 100% robust is a fairly simple thing but trying to implement it into my object class at the moment it only works at lower speeds (velocities) on objects. Go too fast and it can get stuck in an infinite loop of retesting / backing up.. but it is early days for that at the moment.. still any tips on that specific area welcome.

[Dingo Games]

I don't think this has been mentioned yet.. another very simple collision technique would be using multiple circles for each object. This allows you to have oddly shaped objects.

This is essentially what I do in Laser Dolphin (http://www.dingogames.com/dolphin/) for creature to creature collision detection.

[GrahamGoring]

Blimey, talk about digging up an old thread. Um, the code doesn't manage for time (ie, it isn't swept or anything). I just rely on things either not moving too fast or being big enough to not pass through without coinciding.

All co-ordinates are absolute except in the rectangle structure, which is relative to the pivot point.

Tbh, the more interesting part of the collision code isn't in here, which is the bit which optimises it all by only checking nearby objects for collisions with each other. Though all that is, is a grid of linked lists which is built every frame.

[Znarkus]

Thanks a lot! :)

[LamptonWorm]

Hi,

@RedKnight, I'm interested in your collision method, can you post some more details please? For example, which vector do you take for Box 1, does it matter? If you could post some pseudo that would be cool.

btw, currently I'm using box standard area checks for by rec-to-rec collision, but I'm using vectors for movement, would be good to use vecs for collision as I assume that would be a faster check.

Cheers :)