Page 1 of 1

Useful and quick Collision detection between simple shapes

PostPosted: Fri May 24, 2013 9:16 pm
by Game A Gogo
First of all,

Hello everyone :P

Anyways, recently I've been a bit bored when doing my practicum so I started making functions in C++ then decided to make them to C of GE.. though I still have a some work to do..

So put this in your global:

Code: Select all
#define bool int
#define true 1
#define false 0

double M_Clamp(double value, double min_range, double max_range)
{
    return min(max_range, max(value, min_range));
}

double M_Square(double value)
{
    return value * value;
}

double M_1Distance(double a, double b)
{
    double answer = a-b;
    //Iz answer < 0?
    //if so return -answer
    //otherwise return answer
    return answer < 0?-answer:answer;
}
double M_2Distance(double x1, double y1, double x2, double y2)
{
    return sqrt(M_Square(x2-x1) + M_Square(y2-y1));
}
double M_2Distance_Squared(double x1, double y1, double x2, double y2)
{
    return (M_Square(x2-x1) + M_Square(y2-y1));
}
double Col_Value_Range(double Value, double Range_Start, double Range_End, bool Include_End, bool Include_Start)
{
    if (Value < Range_Start || (Value == Range_Start && !Include_Start))
        return -1;//Value is to the "left", or is lesser
    if (Value > Range_End || (Value == Range_End && !Include_End))
        return -2;//Value is to the "right", or is greater
 
    return Value - Range_Start; //Return the offset of the collision in refference to the range
}
double Col_Range_Range(double Start1, double End1, double Start2, double End2, bool Include_End1, bool Include_Start1, bool Include_End2, bool Include_Start2)
{
    if (End1 < Start2 || (End1 == Start2 && (!Include_End1 || !Include_Start2)))
        return -1;//Range is to the "left", or is lesser
    if (Start1 > End2 || (Start1 == End2 && (!Include_Start1 || !Include_End2)))
        return -2;//Range is to the "right", or is lesser
 
    return End1 - Start2; //Return the offset of the collision in refference to the second range
}

bool Col_Point_Box(double x1, double y1, double x2, double y2, double width2, double height2)
{
    //double bx1_ax = x1;
    //double bx1_bx = x1;
    //double bx1_ay = y1;
    //double bx1_by = y1;
 
    double bx2_ax = x2 - width2*0.5;
    double bx2_bx = x2 + width2*0.5;
    double bx2_ay = y2 - height2*0.5;
    double bx2_by = y2 + height2*0.5;
 
    if ( Col_Value_Range( x1, bx2_ax, bx2_bx, true, true) >= 0 && Col_Value_Range( y1, bx2_ay, bx2_by, true, true) >= 0)
        return true;
    return false;
}
bool Col_Box_Box(double x1, double y1, double width1, double height1, double x2, double y2, double width2, double height2)
{
    double bx1_ax = x1 - width1*0.5;
    double bx1_bx = x1 + width1*0.5;
    double bx1_ay = y1 - height1*0.5;
    double bx1_by = y1 + height1*0.5;
 
    double bx2_ax = x2 - width2*0.5;
    double bx2_bx = x2 + width2*0.5;
    double bx2_ay = y2 - height2*0.5;
    double bx2_by = y2 + height2*0.5;
 
    if ( Col_Range_Range( bx1_ax, bx1_bx, bx2_ax, bx2_bx, true, false, true, false) >= 0 && Col_Range_Range( bx1_ay, bx1_by, bx2_ay, bx2_by, true, false, true, false) >= 0)
        return true;
    return false;
}
bool Col_Point_Circle(double x1, double y1, double x2, double y2, double radius2)
{
    if( M_2Distance_Squared( x1, y1, x2, y2) < M_Square(radius2 + 0.5) )
        return true;
    return false;
}
bool Col_Circle_Circle(double x1, double y1, double radius1, double x2, double y2, double radius2)
{
    if( M_2Distance_Squared( x1, y1, x2, y2) < M_Square(radius1 + radius2) )
        return true;
    return false;
}
bool Col_Box_Circle(double x1, double y1, double width1, double height1, double x2, double y2, double radius2)
{
    double bx_ax;
    double bx_bx;
    double bx_ay;
    double bx_by;
 
    double clp_x;
    double clp_y;
 
    //If they're not even close, don't bother doing complicated collision!
    if (!Col_Box_Box( x1, y1, width1, height1, x2, y2, radius2 * 2, radius2 * 2))
        return false;
 
    bx_ax = x1 - width1*0.5;
    bx_bx = x1 + width1*0.5;
    bx_ay = y1 - height1*0.5;
    bx_by = y1 + height1*0.5;
 
    clp_x = M_Clamp(x2, bx_ax, bx_bx);
    clp_y = M_Clamp(y2, bx_ay, bx_by);
 
    if( Col_Point_Circle( clp_x, clp_y, x2,y2, radius2))
        return true;
    return false;
}
bool Col_Point_Triangle(double x1, double y1, double x2, double y2, double width2, double height2, char * facing)
{
    double tr_ax;
    double tr_bx;
    double tr_ay;
    double tr_by;

    if(!Col_Point_Box( x1, y1, x2, y2, width2, height2) )
        return false;
 
    tr_ax = x2 - width2*0.5;
    tr_bx = x2 + width2*0.5;
    tr_ay = y2 - height2*0.5;
    tr_by = y2 + height2*0.5;
 
    if( strcmp(facing,"TL") == 0)
    {
        double d = (x1 - tr_ax) / (tr_bx - tr_ax);
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( y1 > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"TR") == 0)
    {
        double d = 1 - ((x1 - tr_ax) / (tr_bx - tr_ax));
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( y1 > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"BL") == 0)
    {
        double d = (x1 - tr_ax) / (tr_bx - tr_ax);
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( y1 < y)
            return true;
        return false;
    }
 
    if( strcmp(facing, "BR") == 0)
    {
        double d = 1 - ((x1 - tr_ax) / (tr_bx - tr_ax));
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( y1 < y)
            return true;
        return false;
    }
 
    return false;
}

bool Col_Box_Triangle(double x1, double y1, double width1, double height1, double x2, double y2, double width2, double height2, char * facing)
{
    double bx_ax;
    double bx_bx;
    double bx_ay;
    double bx_by;
 
    double tr_ax;
    double tr_bx;
    double tr_ay;
    double tr_by;
 
    if(!Col_Box_Box( x1, y1, width1, height1, x2, y2, width2, height2) )
        return false;


    bx_ax = x1 - width*0.5;
    bx_bx = x1 + width*0.5;
    bx_ay = y1 - height*0.5;
    bx_by = y1 + height*0.5;
 
    tr_ax = x2 - width2*0.5;
    tr_bx = x2 + width2*0.5;
    tr_ay = y2 - height2*0.5;
    tr_by = y2 + height2*0.5;
 
    if( strcmp(facing,"TL") == 0)
    {
        double d = (bx_bx - tr_ax) / (tr_bx - tr_ax);
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( bx_by > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"TR") == 0)
    {
        double d = 1 - ((bx_ax - tr_ax) / (tr_bx - tr_ax));
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( bx_by > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"BL") == 0)
    {
        double d = (bx_bx - tr_ax) / (tr_bx - tr_ax);
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( bx_ay < y)
            return true;
        return false;
    }
 
    if( strcmp(facing, "BR") == 0)
    {
        double d = 1 - ((bx_ax - tr_ax) / (tr_bx - tr_ax));
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( bx_ay < y)
            return true;
        return false;
    }
 
    return false;
}

bool Col_Circle_Triangle(double x1, double y1, double radius1, double x2, double y2, double width2, double height2, char * facing)
{
    //Constant to get the position at 45 degree on the circle's radius
    double Circle_Corner = 0.70710678118654752440084436210485 * radius1;
 
    double tr_ax;
    double tr_bx;
    double tr_ay;
    double tr_by;
 
    if(!Col_Box_Circle( x2, y2, width2, height2, x1, y1, radius1) )
              return false;
 
    tr_ax = x2 - width2*0.5;
    tr_bx = x2 + width2*0.5;
    tr_ay = y2 - height2*0.5;
    tr_by = y2 + height2*0.5;
 
    if( strcmp(facing,"TL") == 0)
    {
        double d = ((x1 + Circle_Corner) - tr_ax) / (tr_bx - tr_ax);
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( (y1 + Circle_Corner) > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"TR") == 0)
    {
        double d = 1 - (((x1 - Circle_Corner) - tr_ax) / (tr_bx - tr_ax));
        double y = tr_by - (d * (tr_by - tr_ay));
 
        if( (y1 + Circle_Corner) > y)
            return true;
        return false;
    }
 
    if( strcmp(facing,"BL") == 0)
    {
        double d = ((x1 + Circle_Corner) - tr_ax) / (tr_bx - tr_ax);
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( (y1 - Circle_Corner) < y)
            return true;
        return false;
    }
 
    if( strcmp(facing, "BR") == 0)
    {
        double d = 1 - (((x1 - Circle_Corner) - tr_ax) / (tr_bx - tr_ax));
        double y = tr_ay + (d * (tr_by - tr_ay));
 
        if( (y1 - Circle_Corner) < y)
            return true;
        return false;
    }
 
    return false;
}

bool Col_Triangle_Triangle(double x1, double y1, double width1, double height1, char * facing1, double x2, double y2, double width2, double height2, char * facing2)
{
    double tr1_ax;
    double tr1_bx;
    double tr1_ay;
    double tr1_by;
 
    double tr2_ax;
    double tr2_bx;
    double tr2_ay;
    double tr2_by;
 
    if(!Col_Box_Box( x1, y1, width1, height1, x2, y2, width2, height2))
        return false;
 
    tr1_ax = x1 - width2*0.5;
    tr1_bx = x1 + width2*0.5;
    tr1_ay = y1 - height2*0.5;
    tr1_by = y1 + height2*0.5;
 
    tr2_ax = x2 - width2*0.5;
    tr2_bx = x2 + width2*0.5;
    tr2_ay = y2 - height2*0.5;
    tr2_by = y2 + height2*0.5;
 
    if( strcmp(facing1, "BR") == 0)
    {
        if( strcmp(facing2, "TL") == 0)
        {
            double d = (tr1_ax - tr2_ax) / (tr2_bx - tr2_ax);
            double y = tr2_by - (d * (tr2_by - tr2_ay));
           
            if( tr1_by > y)
                return true;
            return false;
        }
    }
 
    if( strcmp(facing1, "BL") == 0)
    {
        if( strcmp(facing2, "TR") == 0)
        {
            double d = 1 - ((tr1_bx - tr2_ax) / (tr2_bx - tr2_ax));
            double y = tr2_by - (d * (tr2_by - tr2_ay));
           
            if( tr1_by > y)
                return true;
            return false;
        }
    }
 
    if( strcmp(facing1, "TR") == 0)
    {
        if( strcmp(facing2, "BL") == 0)
        {
            double d = (tr1_ax - tr2_ax) / (tr2_bx - tr2_ax);
            double y = tr2_ay + (d * (tr2_by - tr2_ay));
     
            if( tr1_ay < y)
                return true;
            return false;
        }
    }
 
    if( strcmp(facing1, "TL") == 0)
    {
        if( strcmp(facing2, "BR") == 0)
        {
            double d = 1 - ((tr1_bx - tr2_ax) / (tr2_bx - tr2_ax));
            double y = tr2_ay + (d * (tr2_by - tr2_ay));
     
            if( tr1_ay < y)
                return true;
            return false;
        }
    }
   
    if( Col_Box_Triangle( x1, y1, width1, height1, x2, y2, width2, height2, facing2) &&
        Col_Box_Triangle( x2, y2, width2, height2, x1, y1, width1, height1, facing1))
        return true;
    return false;
}


In the next few post I will provide a GED example and how to use this... I guess for now look at poorly written code?

Re: Useful and quick Collision detection between simple shap

PostPosted: Fri May 24, 2013 10:00 pm
by Jagmaster
Hello! Good to see you agian! Nice Beard too. :P

Thanks for the functions, they'll sure come in handy.

Re: Useful and quick Collision detection between simple shap

PostPosted: Fri May 24, 2013 10:28 pm
by Game A Gogo
Notes!
Okay, here are some notes! :)
All x and y coordinates are centered! no top left corner stuff

okay here is the functions in their order!

double M_Clamp(double value, double min_range, double max_rannge)
This functions will clip value between min_range and max_range

double M_Square(double value)
pretty simple, it squares the values

double M_1Distance(double a, double b)
Random function that finds the distance between two points on a 1 dimension plane :P
probably should delete

double M_2Distance(double x1, double y1, double x2, double y2)
Finds the distance between two points...
Should be deleted and replaced by GE's function (it's faster)

double M_2Distance_Squared(double x1, doubly y1, double x2, double y2)
This is one is even better!
The slow part of finding the distance between two points is the square root!
so how is this useful?
you can compare two squared distance even faster
for example:
Code: Select all
if( M_2Distance_Squared( x, y, 0, 0) < pow( 200, 2))//pow(#,2) squares the number
//So your check of "is this object 200 pixel from 0,0?"
//is a lot faster than just distance(x,y,0,0)
{
    //Do something :P
}


double Col_Value_Range(double Value, double Range_Start, double Range_End, bool Include_End, bool Include_Start)
This does a collision check on a 1 dimensional plane with a value and a range of values
a bit like a pixel and a box...
here is what the arguments do:

-Value: your point to check against the region
-Range_Start: The start of your region
-Range_End: The end of your region
-Include_End: Should this specific number be included for the region? (>=/<= or >/<)
-Include_Start: Should this specific number be included for the region?

And what it returns is a bit special,
if the number is negative, no collision detected
if the number is 0 or positive, collision!

double Col_Range_Range(double Start1, double End1, double Start2, double End2, bool Include_End1, bool Include_Start1, bool Include_End2, bool Include_Start2)
pretty much the same thing as above, but with two regions instead

bool Col_Point_Box(double x1, double y1, double x2, double y2, double width2, double height2)
This does the collision check between a point (x1,y1) and a box (x2,y2,width2,height2)

bool Col_Box_Box(double x1, double y1, double width1, double height1, double x2, double y2, double width2, double height2)
This does the collision check between two box, (x1,y1,width1,height1) and (x2,y2,width2,height2)

bool Col_Point_Circle(double x1, double y1, double x2, double y2, double radius2)
This does the collision check between a point (x1,y1) and a circle (x2,y2,radius2)

bool Col_Box_Circle(double x1, double y1, double width1, double height1, double x2, double y2, double radius2)
This does the collision check between a box (x1,y1,width1,height1) and a circle (x2,y2,radius2)

bool Col_Circle_Circle(double x1, double y1, double radius1, double x2, double double y2
This does the collision check between two circle (x1,y1,radius1) and (x2,y2,radius2)

bool Col_Point_Triangle(double x1, double y1, double x2, double y2, double width2, double height2, char * facing)
This does the collision check between a point (x1,y1) and a rectangular triangle (x2,y2,width2,height2,facing)
Facing will be either of these string:
"TL", "TR", "BL" and "BR".
which means where the diagonal line faces to...
TL means that the top left part of the triangle is empty, so this:
Code: Select all
   /|
  / |
 /  |
/___|   

is what it looks like.

TR is Top Right,
BL is Bottom Left,
BR is Bottom Right

bool Col_Box_Triangle(double x1, double y1, double width1, double height1, double x2, double y2, double width2, double height2, char * facing)
This does a collision check with a box and a triangle (I think you get the drift with the x1's and the y2's)

bool Col_Circle_Triangle(double x1, double y1, double radius1, double x2, double y2, double width2, double height2, char * facing)
This does a collision check with a circle and a triangle

bool Col_Triangle_Triangle(double x1, double y1, double width1, double height1, char * facing1, double x2, double y2, double width2, double height2, char * facing2)
This does a collision check with two triangles

I will post some example later... Then discuss what I will improve of this!

Re: Useful and quick Collision detection between simple shap

PostPosted: Sat May 25, 2013 2:14 am
by Hblade
Wow very nice!