Help on a Pixel-Perfect Collision Detection Algorithm

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.

1int bullets_norm_collision(SPRITE *obstacle){
//variable declarations
int left1;
int left2;
int right1;
int right2;
int top1;
int top2;
int bottom1;
int bottom2;

//holds the current pixel color in the bullet
int current_pixel_color_bullet;
//holds the current pixel color in the obstacle
int current_pixel_color_obstacle;
//counters for the pixel loops
int x1, y1, x2, y2;
//holders for the pixel colors
int br, bg, bb, oor, oog, oob;
//flags
int bullet_pixel_trans, obstacle_pixel_trans;

//store neccessary information for bounding box detection
left1 = bullets_norm->x + bullets_norm->col_x_offset;
left2 = obstacle->x + obstacle->col_x_offset;
right1 = left1 + bullets_norm->col_width;
right2 = left2 + obstacle->col_width;
top1 = bullets_norm->y + bullets_norm->col_y_offset;
top2 = obstacle->y + obstacle->col_y_offset;
bottom1 = top1 + bullets_norm->col_height;
bottom2 = top2 + obstacle->col_height;

//check for bounding box collision
if(bottom1 < top2 || top1 > bottom2 || right1 < left2 || left1 > right2){
  //loop through the obstacle
  for(y2 = 0; y2 < bottom2; y2++){
    for(x2 = 0; x2 < right2; x2++){
      //get the current pixel's color
      current_pixel_color_obstacle = getpixel(obstacle->reference, x2, y2);
      //debug
      if(current_pixel_color_obstacle == -1)
        generic_error("Failed to read obstacle's current pixel!");
                              else{
        //extract the individual hues from the pixel
        oor = getr(current_pixel_color_obstacle);
        oog = getg(current_pixel_color_obstacle);
        oob = getb(current_pixel_color_obstacle);
      }
    
      //loop through the bullet
      for(y1 = 0; y1 < bottom1; y1++){
        for(x1 = 0; x1 < right1; x1++){
          //get the current pixel's color
          current_pixel_color_bullet = getpixel(bullets_norm->reference, x1, y1);
          //debug
          if(current_pixel_color_bullet == -1)
            generic_error("Failed to read bullet's current pixel!");
          else{
            //extract the individual hues from the pixel
            br = getr(current_pixel_color_bullet);
            bg = getg(current_pixel_color_bullet);
            bb = getb(current_pixel_color_bullet);
          }
        
          //compare the pixels of the bullet against the obstacle
          if(oor == 255 && oob == 255 && oog == 0)
            obstacle_pixel_trans = 1;
          else
            obstacle_pixel_trans = 0;
          if(br == 255 && bb == 255 && bg == 0)
            bullet_pixel_trans = 1;
          else
            bullet_pixel_trans = 0;
          
          if(!bullet_pixel_trans && !obstacle_pixel_trans)
            //we have a collision folks!
            return 1;
        }
      }
    }
  }
}

//no collision
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)

xmltorrent

Member #7,673

August 2006

Thanks. I had a feeling it was going to be way to slow. (all those for loops... ick!!!)

Onto experimenting with BitMask. After reading and pondering over the very vague usage instructions, I've come to terms with this:

Basically, with BitMask, I create BitMasks for the sprites. Then for collisions, I use the BitMasks (BitMask functions) rather than the sprites themselves. Is that about right?

Any pointers on how to get started using BitMask would be really helpful because I've got this weird feeling that I'm going to have to rewrite a lot of stuff in my code. (actually the more correct term would be re-adapt the code but that's still a pain)

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.

[edit]
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.

ImLeftFooted

Member #3,935

October 2003

Hes already doing a bounding box test first, which will be more effective then using sector divisions.

How is my posting?

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.

ImLeftFooted

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.

How is my posting?

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:

... 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 Snepscheut
MMORPG'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)

1void init_player(void){
  //variable declarations
  int frame_counter;
  
  //load the master bitmap into memory
  master_holder = load_bitmap("player_plane_master.bmp", '\0');
  //debug
  if(master_holder == '\0')
      generic_error("can't find player sprite master sheet");
  else{
      //extract the frames to the frame array
      for(frame_counter = 0; frame_counter < 3; frame_counter++){
          player_images[frame_counter] = grab_frame(master_holder, 65, 65, 0, 0, 3, frame_counter);
    player_mask[frame_counter] = bitmask_new(player_images[frame_counter]);
    //debug
    if(player_images[frame_counter] == '\0')
        generic_error("failed to load the frame into player_images frame array");
    //debug
    if(player_mask[frame_counter] == '\0')
        generic_error("failed to make bitmask of player sprite frame");
}
  }
23 
  //remove the master bitmap
  destroy_bitmap(master_holder);

  //allocate memory for the player sprite
  player = malloc(sizeof(SPRITE));
29 
  //define the player sprite
  player->width = player_images[0]->w;
  player->height = player_images[0]->h;
  player->x = (WIN_WIDTH / 2) + (player->width / 2);
  player->y = 50;
  player->dir = 0;
  player->alive = 1;
  player->xspeed = 0;
  player->yspeed = 0;
  player->xcount = 0;
  player->ycount = 0;
  player->xdelay = 10;
  player->ydelay = 10;
  player->framecount = 0;
  player->framedelay = 0;
  player->curframe = 0;
  player->maxframe = 2;
  player->animdir = 1;
  player->bbwidth = player->width * 0.80;
  player->bbheight = player->height * 0.80;
  player->xoffset = (player->width - player->bbwidth) / 2;
  player->yoffset = (player->height - player->bbheight) / 2;
  player->reference = player_images[0];
  player->bullet_mode = 1;
  player->bullet_timeout = 20;
  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.