Allegro.cc Forums » Programming Questions » Help on a Pixel-Perfect Collision Detection Algorithm

 This thread is locked; no one can reply to it.
 Help on a Pixel-Perfect Collision Detection Algorithm
xmltorrent
Member #7,673
August 2006

I'm creating a scrolling shooter and I need a pixel-perfect collision detection algorithm for bullet-to-obstacle collisions. I started creating one and tested it and it didn't work at all. (ouchies) I think I went about it the entirely wrong way. Here's what I came up with.

I figured that first, I'd obtain the bounding boxes for the sprites. The bounding boxes are at a 20% decreased size. Next I'd check to see if there is a bounding box collision. If there is, then I'd start testing the non-transparent pixels in the bullet against the non-transparent pixels in the obstacle. If they were in the same spot, then there was a collision. But I'm starting to think I thought wrong haha.

Here's the code I came up with. Please scrutinize at will if need be.

 1 int bullets_norm_collision(SPRITE *obstacle){ 2 //variable declarations 3 int left1; 4 int left2; 5 int right1; 6 int right2; 7 int top1; 8 int top2; 9 int bottom1; 10 int bottom2; 11 12 //holds the current pixel color in the bullet 13 int current_pixel_color_bullet; 14 //holds the current pixel color in the obstacle 15 int current_pixel_color_obstacle; 16 //counters for the pixel loops 17 int x1, y1, x2, y2; 18 //holders for the pixel colors 19 int br, bg, bb, oor, oog, oob; 20 //flags 21 int bullet_pixel_trans, obstacle_pixel_trans; 22 23 //store neccessary information for bounding box detection 24 left1 = bullets_norm->x + bullets_norm->col_x_offset; 25 left2 = obstacle->x + obstacle->col_x_offset; 26 right1 = left1 + bullets_norm->col_width; 27 right2 = left2 + obstacle->col_width; 28 top1 = bullets_norm->y + bullets_norm->col_y_offset; 29 top2 = obstacle->y + obstacle->col_y_offset; 30 bottom1 = top1 + bullets_norm->col_height; 31 bottom2 = top2 + obstacle->col_height; 32 33 //check for bounding box collision 34 if(bottom1 < top2 || top1 > bottom2 || right1 < left2 || left1 > right2){ 35 //loop through the obstacle 36 for(y2 = 0; y2 < bottom2; y2++){ 37 for(x2 = 0; x2 < right2; x2++){ 38 //get the current pixel's color 39 current_pixel_color_obstacle = getpixel(obstacle->reference, x2, y2); 40 //debug 41 if(current_pixel_color_obstacle == -1) 42 generic_error("Failed to read obstacle's current pixel!"); 43 else{ 44 //extract the individual hues from the pixel 45 oor = getr(current_pixel_color_obstacle); 46 oog = getg(current_pixel_color_obstacle); 47 oob = getb(current_pixel_color_obstacle); 48 } 49 50 //loop through the bullet 51 for(y1 = 0; y1 < bottom1; y1++){ 52 for(x1 = 0; x1 < right1; x1++){ 53 //get the current pixel's color 54 current_pixel_color_bullet = getpixel(bullets_norm->reference, x1, y1); 55 //debug 56 if(current_pixel_color_bullet == -1) 57 generic_error("Failed to read bullet's current pixel!"); 58 else{ 59 //extract the individual hues from the pixel 60 br = getr(current_pixel_color_bullet); 61 bg = getg(current_pixel_color_bullet); 62 bb = getb(current_pixel_color_bullet); 63 } 64 65 //compare the pixels of the bullet against the obstacle 66 if(oor == 255 && oob == 255 && oog == 0) 67 obstacle_pixel_trans = 1; 68 else 69 obstacle_pixel_trans = 0; 70 if(br == 255 && bb == 255 && bg == 0) 71 bullet_pixel_trans = 1; 72 else 73 bullet_pixel_trans = 0; 74 75 if(!bullet_pixel_trans && !obstacle_pixel_trans) 76 //we have a collision folks! 77 return 1; 78 } 79 } 80 } 81 } 82 } 83 84 //no collision 85 return 0; 86 }

 HardTranceFan Member #7,317 June 2006 Your method, although a nice idea, is way too slow. Instead, have a look at the bitmask collision detection library. It works, it's fast, it's free, you just add it to your projects and it will let you get on with coding the rest of your game. --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 HardTranceFan Member #7,317 June 2006 From memory, there is better much documentation in the download file than there is on the web page.Yes, you create a bitmask from the sprite image you have, and you pass the two bitmasks you want to test for a collision, plus the offsets between the two sprites.I'll provide some sample code when I get home later today, along with a small function I wrote for the library which takes an Allegro bitmap and returns the bitmask.I've attached my updated version of the bitmask library, which includes the function to create a bitmask from an Allegro bitmap.Sample code: ```// Just some 'position' variables for the example int x1 = 100, , y1 = 100, x2 = 120, y2 = 101; // to create the bitmasks from a bitmaps BITMAP* bmp1 = load_bitmap("image1.bmp", NULL); BITMAP* bmp2 = load_bitmap("image2.bmp", NULL); bitmaks_t* mask1 = bitmask_new(bmp1); bitmaks_t* mask2 = bitmask_new(bmp2); // and for collision detection bitmask_overlap(mask1, mask2, x1-x2, y1-y2) ``` Oh, and my memory failed me. The documentation within the orignal code wasn't much better than the web site.[/edit] --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 Andrei Ellman Member #3,434 April 2003 xmltorrent said: (all those for loops... ick!!!) Here's a hint. As well as getting the collision-detection to work as fast as possible, try working on ways to reduce the number of collisons that need to take place. One way of doing it is to divide the world into sectors and only test for collisions of objects in the same sector (in two dimensions, if the minimum sector-size is no smaller than the largest object you want to test for collisions, an object can be in a maximum of four sectors).AE. --Don't let the illegitimates turn you into carbon.
 Dustin Dettmer Member #3,935 October 2003 Hes already doing a bounding box test first, which will be more effective then using sector divisions.
 orz Member #565 August 2000 Quote: Hes already doing a bounding box test first, which will be more effective then using sector divisions. Andrei Ellman is referring to higher level collision detection, i.e. the algorithm for figuring out which objects get checked at all. It can be (if the number of objects is large enough) far faster than a simple bounding box implementation that checks all bounding boxes against all other bounding boxes.
 Dustin Dettmer Member #3,935 October 2003 Bounding box is so fast anyway...If you wanted to get faster I would just convert to circles. Its probably faster anyway (pointer lookups and list management can be sloooow). And keeping everything sorted would be a bigger drain.Sectoring is good for stuff like MMORPGs and crap. Or if you just have an unbelievable amount of units or infinite terrain.
 xmltorrent Member #7,673 August 2006 Quote: If you wanted to get faster I would just convert to circles. You know something, that sounds interesting and I've never thought of using those at all. And considering the fact that I'm still in expiremental stages with the game, I don't see the harm in going back and using a bounding circle rather than a bounding rectangle.Plus I'm having some trouble getting used to using BitMask. I'm not sure if I'm supposed to compile the BitMask files and link an object file or what because just including the header file, it doesn't solve the linker errors.
 HardTranceFan Member #7,317 June 2006 xmltorrent, I don't understand the problem you have with the bitmask functions. I've added the two files (the ones I attached in an earlier post) to my projects, and included the header file in every class that uses a bitmask type or function. No problems.What errors are you getting, and are you including the bitmask files in your project (attach your file(s) if it need be)? --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 Andrei Ellman Member #3,434 April 2003 Optimisation isn't just about creating the fastest collision-detection algorithm possible, but also about deciding on whether or not the collision-detections need to take place in the first place.AE. --Don't let the illegitimates turn you into carbon.
 Jonatan Hedborg Member #4,886 July 2004 How very profound
 xmltorrent Member #7,673 August 2006 Quote: What errors are you getting, and are you including the bitmask files in your project (attach your file(s) if it need be)? The linker says there's an undefined reference to bitmask_new, the function you posted in your sample block above.EDIT:Which I know what that means but I can't seem to come up with where that function came from or it's equivalent. It's not listed anywhere in the header or source file for BitMask.Quote: ... but also about deciding on whether or not the collision-detections need to take place in the first place. Hence the reason I'm trying to get as fast as I can with the collision-detections because they kinda HAVE to happen. ^_^
 HardTranceFan Member #7,317 June 2006 Quote: The linker says there's an undefined reference to bitmask_new, the function you posted in your sample block above.EDIT:Which I know what that means but I can't seem to come up with where that function came from or it's equivalent. It's not listed anywhere in the header or source file for BitMask. Are you sure you know what it means? It means you're using the bitmask header and source files from the web-site, and not those attached to my second post . --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 xmltorrent Member #7,673 August 2006 Haha Whoops. I just noticed that attachment icon at the top of the post haha. My bad.ummmm I can't download the attachment. I click on the icon and it's not doing anything at all.EDIT:Nevermind, I got it to work. I think I just need to go back to bed today.
 HardTranceFan Member #7,317 June 2006 n00b:P;D --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 xmltorrent Member #7,673 August 2006 Haha EDIT:I had to make a slight modification to your function. The for loops in bitmask_new function were picked up as being declared outside C99. I just declared the counter variables as local variables in the function and went from there. Just thought you might want to know that. ^_^EDIT 2:Haha Another problem has arisen. I think it might just be my brain not working right today or what but I'll explain.The sprites that I'm using BitMask for are all animated. Now my first plan of attack was to create a BitMask for each frame of animation then when I perform my collision detection, I loop through all the BitMasks for each frame and perform checking on the other sprites BitMasks. However, while the program runs perfectly fine, it always says that there is a collision with an enemy plane when I know that the player plane isn't anywhere near the enemy plane when the program starts. So I'm guessing that another method is needed. Pondering.....
 HardTranceFan Member #7,317 June 2006 Ta. I probably won't change my code, as I'm developing in C++, which doesn't kick up about it.Heh, I just spotted some redundent code in the function ("temp->w = w;" and "temp->h = h"). --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
 xmltorrent Member #7,673 August 2006 argh!!!What values should I use for the xoffset and yoffset for bitmask? I have a xoffset and yoffset value for my sprite struct but they don't seem to work.
 HoHo Member #4,534 April 2004 Quote: Quote: ... but also about deciding on whether or not the collision-detections need to take place in the first place. Hence the reason I'm trying to get as fast as I can with the collision-detections because they kinda HAVE to happen. ^_^ What he meant by that was that when you have thousands of objects for the level then having a fast collision function is not much use. Much more useful would be to find out those few things you have to collide with and only check those. E.g using a quadtree could tell you what other objects are near the object you need to collide with. Using the same way you can also find out the objects you have on screen. Without any kind of space partitioning you will have to ton N^2 tests whereas with finding only objects on screen you will most likely cut that down to a fraction of it. When you also use quadtree to find objects near the one you are colliding with instead of colliding all the objects on screen it can very easily be that you only have to make only a few collision tests per frame. Finding those few collision detections will save a lot more time than making your collision code 10x faster. I bet even your own ugly version would be good enough with decent partitionig scheme. __________In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de SnepscheutMMORPG's...Many Men Online Role Playing Girls - Radagar"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski
 HardTranceFan Member #7,317 June 2006 Quote: What values should I use for the xoffset and yoffset for bitmask? I have a xoffset and yoffset value for my sprite struct but they don't seem to work. The xOffset and yOffset are just the x and y differences between the two sprites of the bitmasks you are passing (as per my sample code).If you still have trouble, post the code. --"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)
xmltorrent
Member #7,673
August 2006

bllawrgle....

Okay. Here's what I have for the player initialization function: (displays the xoffset and yoffset values)

 1 void init_player(void){ 2 //variable declarations 3 int frame_counter; 4 5 //load the master bitmap into memory 6 master_holder = load_bitmap("player_plane_master.bmp", '\0'); 7 //debug 8 if(master_holder == '\0') 9 generic_error("can't find player sprite master sheet"); 10 else{ 11 //extract the frames to the frame array 12 for(frame_counter = 0; frame_counter < 3; frame_counter++){ 13 player_images[frame_counter] = grab_frame(master_holder, 65, 65, 0, 0, 3, frame_counter); 14 player_mask[frame_counter] = bitmask_new(player_images[frame_counter]); 15 //debug 16 if(player_images[frame_counter] == '\0') 17 generic_error("failed to load the frame into player_images frame array"); 18 //debug 19 if(player_mask[frame_counter] == '\0') 20 generic_error("failed to make bitmask of player sprite frame"); 21 } 22 } 23 24 //remove the master bitmap 25 destroy_bitmap(master_holder); 26 27 //allocate memory for the player sprite 28 player = malloc(sizeof(SPRITE)); 29 30 //define the player sprite 31 player->width = player_images[0]->w; 32 player->height = player_images[0]->h; 33 player->x = (WIN_WIDTH / 2) + (player->width / 2); 34 player->y = 50; 35 player->dir = 0; 36 player->alive = 1; 37 player->xspeed = 0; 38 player->yspeed = 0; 39 player->xcount = 0; 40 player->ycount = 0; 41 player->xdelay = 10; 42 player->ydelay = 10; 43 player->framecount = 0; 44 player->framedelay = 0; 45 player->curframe = 0; 46 player->maxframe = 2; 47 player->animdir = 1; 48 player->bbwidth = player->width * 0.80; 49 player->bbheight = player->height * 0.80; 50 player->xoffset = (player->width - player->bbwidth) / 2; 51 player->yoffset = (player->height - player->bbheight) / 2; 52 player->reference = player_images[0]; 53 player->bullet_mode = 1; 54 player->bullet_timeout = 20; 55 player->allowed_to_shoot = 1; 56 }END_OF_FUNCTION(init_player);

This is where I'm totally lost at. Like I used those values for bounding box collisions but now I'm not sure how to accomidate those values to BitMask.

 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads