2D collision detection
I'm trying to do collision detection for a 2D space ship game. I'm using Ortho mode and drawing the ships on quads using png images for transparency around the ships.
I want to do pixel-level detection so I started working with this article: Collision Detection
I started with the simple bounding box collision and got that working by checking if 2 ships quads overlap. During this I realized that the articles method requires the bounding boxes of the 2 ships to be at the same angle. At least I think that is the case, correct me if I am wrong. I want my players ship to be able to rotate to any angle.
Is there another method of doing this type of 2D collision detection? I am interested in what other people would do. Anyone that has made a game similar to what I want that might have advice?
Thanks
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
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
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; } } } } } }
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!
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement