2D collision detection

If the drawing complexity is not an issue, you can use occlusion query.

If you don't think that a bounding box would be good for your preliminary collision check, the nyou should try using a circle for your bounding area.. then it really wouldn't matter. Checking to see if 2 circles overlap is much easier to visualize also, atleast that is my opinion.

A two-dimensional box can be thought of as four segments. To test for a static intersection, just test for all the possible segment-segment intersections.

You may also want each object to have a bounding circle as well. This will help speed up collision detection. Just test for the circle-circle intersections first, and then the box-box intersections, and then the pixel-pixel intersections.

If you need any example code for testing any sort of bounding-volume/geometrical-intersection tests, take a look at the code at Magic-Software.

Although I said earlier that a 2-d box can be thought of as four segments, a 2-d box, as a class, is generally represented with two axis vectors (x-axis and y-axis), a center point, and a vector containing the dimensions of the box (half-width, half-height). Corner points on the box can be determined by multiplying the axis vectors by the dimension vector.

Depending on the shape of your ships, however, it may not be wise to use oriented boxes for collision detection. Unless your ships are awkwardly shaped (long and skinny), it would be more beneficial to only use bounding circles.

Good luck!

EDIT: sphere == 3-d, circle == 2-d

It is usually best to program collision using separate data than the visuals, in just about any case. I would recommend to stay away from visual pixel collision routines of any form. Even for 3d, the same is true of triangle/triangle collision. It generally doesn't happen in games because of the high cost and low reward.

The way to go, as suggested above, is to do sphere/circle queries. You can represent most objects with a combination of spheres or circles to get more detail. Using hierarchy speeds things up tremendously (one big sphere/circle around the whole object for 1 level of hierarchy, but you can optimize further for complex collision shapes, EG more than 2 sphere/circles describing the collision of the object).

You can do circle/line collision for colliding with static parts of your world (walls, etc), or sphere triangle in 3d.

This method will force you to hand edit collision after the graphics are done. But this is generally what the big boys do. Make a routine to draw your sphere or circle and turn it on in debug mode and make some way to adjust the parameters of the sphere/circle at run-time until it matches your graphics. Use wireframe to represent your debug sphere/circle so that you can match it up real good.

Hope this helps.

--
- Aaron

Thanks for all your replies. Sounds like bounding circles is the way to go, I will try that and see how it goes.

Umm.. Chech out his code from my great friends over at thechaosrift.com :

/* Tile based collision and jumping by JS Lemming (Travis Stuart) Random shooting and tile destruction by Super Sonic (Falco Jaenisch) Helluva special thanks to Tvspelsfreak on Super Sonic's behalf requires static linkage to: sdl.lib, sdlmain.lib requires dynamic linkage to: sdl.dll */ //include SDL stuff #include "sdl.h" //include ability to exit program #include <stdlib.h> //include math functions #include <cmath> //Classes class Player {     public:         //general movement         float m_x, m_y;         float m_xvel, m_yvel;         //jumping         bool m_jump;         bool m_letgo;       //keeps track if the user is holding down space       bool m_dir;         float m_jumptimer;         //constructor         Player()         {             m_x = 0;             m_y = 0;             m_xvel = 0;             m_yvel = 0;             m_jump = false;             m_letgo = true;             m_jumptimer = 0;         } }; class Bullet { public:     int x;     int y;     bool active;     int direction; }; bool KeyDown(bool KeyFlag); bool KeyHit(bool &KeyFlag); int MoveHorizontal(float& p_xvel, float& p_x, float& p_y, int p_left, int p_right, int p_top, int p_bottom); int MoveVertical(float& p_yvel, float& p_x, float& p_y, int p_left, int p_right, int p_top, int p_bottom); void Shoot(int x, int y, bool dir); void UpdateBullets(); //These are the T/F flags that will be used to determine if a //key is being held down by the user. If true, the key is down... false its not. bool f_Up; bool f_Down; bool f_Left; bool f_Right; bool f_X; bool f_C; bool f_Escape; //Create 3 bullets that may be shot Bullet bullet[3]; //how much an object gets pulled down per frame float Gravity = 0.38; //screen dimensions const int SCREEN_WIDTH = 640; const int SCREEN_HEIGHT = 480; //array holding map data (0 or 1 for now) int map[20][15]; //display surface SDL_Surface* g_pDisplaySurface; //event structure SDL_Event g_Event; //rectangle SDL_Rect g_Rect; //color components Uint8 g_Red, g_Green, g_Blue; //color value Uint32 g_Color; //main function int main(int argc, char* argv[]) {    //initialize SDL    if (SDL_Init(SDL_INIT_VIDEO)==-1)    {       //error initializing SDL       //report the error       fprintf(stderr,"Could not initialize SDL!\n");       //end the program       exit(1);    }    else    {       //SDL initialized       //report success       fprintf(stdout,"SDL initialized properly!\n");       //set up to uninitialize SDL at exit       atexit(SDL_Quit);    }     //hide mouse     SDL_ShowCursor(SDL_DISABLE);    //create windowed environment    g_pDisplaySurface = SDL_SetVideoMode(SCREEN_WIDTH,SCREEN_HEIGHT,16,SDL_ANYFORMAT|SDL_DOUBLEBUF);    //error check    if (g_pDisplaySurface == NULL)    {       //report error       fprintf(stderr,"Could not set up display surface!\n");       //exit the program       exit(1);    }     //Create instance of class player     Player dude;     dude.m_x = (3*32);     dude.m_y = (10*32);    dude.m_dir = 1;     //clear map array     for(int x=0; x<=19; x++)     {         for(int y=0; y<=14; y++)         {             map[x][y] = 0;         }     }     //put some solids into the map array     for(x=0; x<=19; x++)     {         map[x][0] = 1;         map[x][1] = 1;         map[x][12] = 1;         map[x][13] = 1;         map[x][14] = 1;     }     //add some more solids yo     map[0][9] = 1;     map[0][10] = 1;     map[0][11] = 1;     map[12][6] = 1;     map[13][6] = 1;     map[14][6] = 1;     map[15][6] = 1;     map[16][6] = 1;        /*map[5][6] = 1;     map[6][6] = 1;     map[7][6] = 1;     map[8][6] = 1;*/        map[16][6] = 1;     map[17][11] = 1;     map[18][11] = 1;     for(int y=0; y<15; y++)     {         map[19][y] = 1;     }     //take out some tiles yo     map[8][12] = 0;     map[9][12] = 0;     map[10][12] = 0;     map[11][12] = 0;     map[12][12] = 0;    //main game loop     while(1)    {         //look for an event         if(SDL_PollEvent(&g_Event) == true)         {             //if user closes out of window, exit loop             if(g_Event.type == SDL_QUIT)                 break;             //if ESC key             if(g_Event.key.keysym.sym == SDLK_ESCAPE)          {                 // if ESC was pressed, quit the program.                 SDL_Event quit;                 quit.type = SDL_QUIT;                 SDL_PushEvent(&quit);             }             //check key input             switch( g_Event.type )             {                 //if a key is pressed                 case SDL_KEYDOWN:                     switch( g_Event.key.keysym.sym )                     {                         case SDLK_UP:                             f_Up = true;                             break;                         case SDLK_DOWN:                             f_Down = true;                             break;                         case SDLK_LEFT:                             f_Left = true;                             break;                         case SDLK_RIGHT:                             f_Right = true;                             break;                         case SDLK_x:                             f_X = true;                             break;                    case SDLK_c:                             f_C = true;                             break;                         case SDLK_ESCAPE:                             f_Escape = true;                             break;                     }                     break;                 //a key is released                 case SDL_KEYUP:                     switch( g_Event.key.keysym.sym )                     {                         case SDLK_UP:                             f_Up = false;                             break;                         case SDLK_DOWN:                             f_Down = false;                             break;                         case SDLK_LEFT:                             f_Left = false;                             break;                         case SDLK_RIGHT:                             f_Right = false;                             break;                         case SDLK_x:                             f_X = false;                             break;                         case SDLK_c:                             f_C = false;                             break;                         case SDLK_ESCAPE:                             f_Escape = false;                             break;                     }                     break;                 default:                     break;             }         }         //clear the screen with black         SDL_FillRect(g_pDisplaySurface, NULL, SDL_MapRGB( g_pDisplaySurface->format, 0, 0, 0 ));         //draw the map         for(int x=0; x<=19; x++)         {             for(int y=0; y<=14; y++)             {                 if(map[x][y] == 1)                 {                     //create a bright green rectangle                     g_Rect.x = x*32;                     g_Rect.y = y*32;                     g_Rect.w = 32;                     g_Rect.h = 32;                     //set the color                     g_Red = 0;                     g_Green = 255;                     g_Blue = 0;                     g_Color=SDL_MapRGB(g_pDisplaySurface->format,g_Red,g_Green,g_Blue);                     //fill the rectangle                     SDL_FillRect(g_pDisplaySurface,&g_Rect,g_Color);                                //create a darker green rectangle to go on top of the first                     g_Rect.x = (x*32)+1;                     g_Rect.y = (y*32)+1;                     g_Rect.w = 30;                     g_Rect.h = 30;                     //set the color                     g_Red = 0;                     g_Green = 180;                     g_Blue = 0;                     g_Color=SDL_MapRGB(g_pDisplaySurface->format,g_Red,g_Green,g_Blue);                     //fill the rectangle                     SDL_FillRect(g_pDisplaySurface,&g_Rect,g_Color);                 }             }         }         //move dude in persective of velocities         MoveHorizontal(dude.m_xvel,dude.m_x,dude.m_y,0,32,0,64);         if(MoveVertical(dude.m_yvel,dude.m_x,dude.m_y,0,32,0,64) == 1)         { dude.m_jump = false; }         //simulate gravity (probably should be in jump function later)         dude.m_yvel = (dude.m_yvel + Gravity);         //simulate friction         if(dude.m_xvel < 0) { dude.m_xvel = (dude.m_xvel + Gravity); }         if(dude.m_xvel > 0) { dude.m_xvel = (dude.m_xvel - Gravity); }         //sorry, can't jump while falling :D         if(dude.m_yvel > 1) { dude.m_jump = true; }         //attempt to activate jump         if( KeyDown(f_X) )         {             //if we are not currently jumping, and spacebar wasn't held             if((dude.m_jump == false) && (dude.m_letgo == true))             {                 //set some vars                 dude.m_letgo = false;                 dude.m_jump = true;                 //at this point, we could put in an if statement to see if dude                 //is moving fast enough to jump higer.. but not right now.                 dude.m_jumptimer = 8;                 //make dude bounce into action                 dude.m_yvel = -4.5;             }         }         else         {             //if dude isn't going up or down, reset letgo to true             if(abs((int)dude.m_yvel) < 1) { dude.m_letgo = true; }             //reset the jumptimer to 0             dude.m_jumptimer = 0;         }         //if we are currently jumping         if((dude.m_jump == true) && (dude.m_jumptimer > 0))         {             //adjust velocity for life             dude.m_yvel = dude.m_yvel - 1;             //decrease the jump timer             dude.m_jumptimer--;         }         //the below is not standard and should be implemented elsewhere (but this be just a demo yo.)         //keep dude from going left or right to fast         if( abs((int)dude.m_xvel) > 3 )         {             //if velocity less then 0             if(dude.m_xvel < 0)             {                 dude.m_xvel = (-3);             }             else             {                 dude.m_xvel = (3);             }         }         /*         //keep dude from going up or down to fast         if( abs((int)dude.m_yvel) > 6 )         {             //if velocity less then 0             if(dude.m_yvel < 0)             {                 dude.m_yvel = (-6);             }         }         */         //update all onscreen bullets       UpdateBullets();         //update the box via user input         if( KeyDown(f_Left) ) {             dude.m_xvel = (dude.m_xvel - 1);          dude.m_dir = 0;       }         if( KeyDown(f_Right) ) {             dude.m_xvel = (dude.m_xvel + 1);          dude.m_dir = 1;       }       if( KeyDown(f_C) )             Shoot(dude.m_x, dude.m_y, dude.m_dir);         //create a light blue rectangle         g_Rect.x = (int)dude.m_x;         g_Rect.y = (int)dude.m_y;         g_Rect.w = 32;         g_Rect.h = 64;         //set the color         g_Red = 0;         g_Green = 140;         g_Blue = 255;         g_Color=SDL_MapRGB(g_pDisplaySurface->format,g_Red,g_Green,g_Blue);         //fill the rectangle         SDL_FillRect(g_pDisplaySurface,&g_Rect,g_Color);         //create a dark blue rectangle on top the other         g_Rect.x = (int)dude.m_x+1;         g_Rect.y = (int)dude.m_y+1;         g_Rect.w = 30;         g_Rect.h = 62;         //set the color         g_Red = 0;         g_Green = 0;         g_Blue = 255;         g_Color=SDL_MapRGB(g_pDisplaySurface->format,g_Red,g_Green,g_Blue);         //fill the rectangle         SDL_FillRect(g_pDisplaySurface,&g_Rect,g_Color);         //update the screen         SDL_UpdateRect(g_pDisplaySurface,0,0,0,0);         //flip surface into view         SDL_Flip(g_pDisplaySurface);         //I heard someone say we should delay 10 millisecs to let the         //computer catch up and reduce lag. Is this true?         SDL_Delay(10);    }    //normal termination    fprintf(stdout,"Terminating normally.\n");    //return to OS    return(0); } //Function KeyDown(KeyFlag) - checks whether the arg passed to it is true, //thus returning true. Why have this function at all? For consistancy sakes //of the KeyHit function. bool KeyDown(bool KeyFlag) {     return KeyFlag; } //Function KeyHit(KeyFlag) - checks whether the arg passed to it is true. //Then setting the flag to false, and returning true. bool KeyHit(bool &KeyFlag) {     if(KeyFlag == true)     {         KeyFlag = false;         return true;     }     return false; } //---FUNCTIONS--- //MoveHorizontal() - moves thing based on velocity //returns -1 if top left hits a solid // 1 if right boundry hits a solid // 0 if no collision detected in move int MoveHorizontal(float& p_xvel, float& p_x, float& p_y, int p_left, int p_right, int p_top, int p_bottom) {     for(int i=1; i<=abs( (int)p_xvel ); i++ )     {         //temporarily define the object's bounderies         int BoundLeft   = ((int)p_x + p_left);         int BoundRight  = ((int)p_x + p_right-1);         int BoundTop    = ((int)p_y + p_top);         int BoundBottom = ((int)p_y + p_bottom-1);         //set temp Move = true? vars to false         bool MoveLeft = false;         bool MoveRight = false;         //loop from boundtop to boundbottom (replace loop with mar's idea!)         for(int Point=BoundTop; Point<=BoundBottom; Point++)         {             //if object going left             if(p_xvel < 0)             {                 //if object's left bound minus 1 is in a solid tile                 if(map[ (BoundLeft-1)/32 ][ (Point)/32 ] == 1)                 {                     //set the object's xvel to 0 and return with -1                     p_xvel = 0;                     return -1;                 }                 else                 {                     //set the MoveLeft var to true                     MoveLeft = true;                 }             }             //if object going right             if(p_xvel > 0)             {                 //if object's right bound plus 1 is in a solid tile                 if(map[ (BoundRight+1)/32 ][ (Point)/32 ] == 1)                 {                     //set the object's xvel to 0 and return with 1                     p_xvel = 0;                     return 1;                 }                 else                 {                     //set the MoveRight var to true                     MoveRight = true;                 }             }         }         //if the Move vars are now true, adjust the x values         if(MoveLeft == true) { p_x = p_x - 1; }         if(MoveRight == true) { p_x = p_x + 1; }         //if the object has gone out of array bounds, push it back on         if(p_x < 0) { p_x = 0; p_xvel = 0; }         if(p_x > 640) { p_x = 640; p_xvel = 0; }    //replace 20*32 with map height var/function     }     //if no solids were hit at all, return 0     return 0; } //MoveVertical() - moves thing based on velocity //returns -1 if top boundry hits a solid // 1 if bottom boundry hits a solid // 0 if no collision detected in move int MoveVertical(float& p_yvel, float& p_x, float& p_y, int p_left, int p_right, int p_top, int p_bottom) {     for(int i=1; i<=abs( (int)p_yvel ); i++ )     {         //temporarily define the object's bounderies         int BoundLeft   = ((int)p_x + p_left);         int BoundRight  = ((int)p_x + p_right-1);         int BoundTop    = ((int)p_y + p_top);         int BoundBottom = ((int)p_y + p_bottom-1);         //set temp Move = true? vars to false         bool MoveUp = false;         bool MoveDown = false;         //loop from boundleft to boundright (replace loop with mar's idea!)         for(int Point=BoundLeft; Point<=BoundRight; Point++)         {             //if object going up             if(p_yvel < 0)             {                 //if object's top bound minus 1 is in a solid tile                 if(map[ (Point)/32 ][ (BoundTop-1)/32 ] == 1)                 {                     //set the object's yvel to 0 and return with -1                     p_yvel = 0;                     return -1;                 }                 else                 {                     //set the MoveUp var to true                     MoveUp = true;                 }             }             //if object going down             if(p_yvel > 0)             {                 //if object's bottom bound plus 1 is in a solid tile                 if(map[ (Point)/32 ][ (BoundBottom+1)/32 ] == 1)                 {                     //set the object's yvel to 0 and return with 1                     p_yvel = 0;                     return 1;                 }                 else                 {                     //set the MoveDown var to true                     MoveDown = true;                 }             }         }         //if the Move vars are now true, adjust the y values         if(MoveUp == true) { p_y = p_y - 1; }         if(MoveDown == true) { p_y = p_y + 1; }         //if the object has gone out of array bounds, push it back on         if(p_y < 0) { p_y = 0; p_yvel = 0; }         if(p_y > 15*32) { p_y = 15*32; p_yvel = 0; }    //replace 15*32 with map height var/function     }     //if no solids were hit at all, return 0     return 0; } void Shoot(int x, int y, bool dir) {     for(int i=0; i<1; i++) {         if(bullet.active == false) {             bullet.active = true;             bullet.x = x;             bullet.y = y + 20;          bullet.direction = dir;             break;         }     } } void UpdateBullets() {    for(int a=0; a<1; a++) {       if(bullet[a].active) {          if(bullet[a].direction == 0) bullet[a].x -= 14; // Left          if(bullet[a].direction == 1) bullet[a].x += 14; // Right                         //create a red rectangle             g_Rect.x = bullet[a].x;             g_Rect.y = bullet[a].y;             g_Rect.w = 4;             g_Rect.h = 4;             //set the color             g_Red   = 255;             g_Green = 0;             g_Blue  = 0;             g_Color = SDL_MapRGB(g_pDisplaySurface->format,g_Red,g_Green,g_Blue);             //fill the rectangle             SDL_FillRect(g_pDisplaySurface,&g_Rect,g_Color);             if(bullet[a].x < 0 || bullet[a].x > 640 || bullet[a].y < 0 || bullet[a].y > 480) {                 bullet[a].active = false;          }             else{                 for(int Point = bullet[a].y; Point < bullet[a].y+4; Point++){                     if(map[ (bullet[a].x)/32 ][ (Point)/32 ] == 1) {                   map[ (bullet[a].x)/32 ][ (Point)/32 ] = 0;                   bullet[a].active = false;                }             }          }         }     } } 

just wondering if anyone ever read that...

simple way

give each object a collision radius then pass them into this function, thus if the two objects exist ie a bullet and a ship then do something like remove the ship from screen and show an explosion

void Collision( Actor *a, Actor *b )
{
if( a->active && b->active )
{
float r=
(float)sqrt((a->x-b->x)*(a->x-b->x)+(a->y-b->y)* (a->y-b->y));
if( r<(a->colr+b->colr) )
{
if( b->type==SHIP )
{
if( a->type==BULLET )
{
b->active=false;
}

CreateActor( (a->x+b->x)/2.0f, (a->y+b->y)/2.0f, BLAST );
}
}
}
}


Miikka Laakso used this in his thrust game see nehe downloads under thrust, no code there but he gave it to me and it works every time!

Thanks for the replies The Chaos Phantom and CrystalClear.

The Chaos Phantom thanks for the code, I don't have much time to work on my game right now so I can't really go over all that code, but I appreciate the effort.


CrystalClear thanks for the code, I already have the circle collisions working, I will refer back to your code example when I get to adding the explosions. I'll have to check out the thrust game.


Thanks