Pixel Perfect Collision

From Allegro Wiki

Jump to: navigation, search
This article is incomplete and needs some revision or has some pending TODOs. Please help Allegro by editing and finishing it. When the article becomes complete, you may remove this tag.


Pixel Perfect Collision (PPC) is a precise type of 2D collision detection that uses bit-masks to determine whether two objects collide. There are many ways to go about PPC, but all of them are extremely slow compared to bounding boxes. On top of that, there is no real way to get a 1 bpp bitmap in Allegro.

Contents

Libraries

PMASK

PMASK by orz works as is for allegro 4 and is public domain.

As a dirty hack to get it working for allegro 5, rewrite load_allegro_pmask in pmask.c to set individual "pixels" in the pmask with set_pmask_pixel() using 1 or 0 depending on if that pixel is what you want to collide with or not.

For example for colliding with anything but magic pink (red:255 green:0 blue:255) use:

void load_allegro_pmask(PMASK *mask, ALLEGRO_BITMAP *sprite) {
	int x,y;
	unsigned char r, g, b;
	al_lock_bitmap(sprite,ALLEGRO_LOCK_READONLY,al_get_bitmap_format(sprite));
	for(x=0;x<al_get_bitmap_width(sprite);x++)
	{
		for(y=0;y<al_get_bitmap_height(sprite);y++) {
			al_unmap_rgb(al_get_pixel(sprite,x,y), &r, &g, &b);
			if (r==255&&g==0&&b==255){
				set_pmask_pixel(mask,x,y,0);
			}
			else{
				set_pmask_pixel(mask,x,y,1);
			}
		}
	}
	al_unlock_bitmap(sprite);
}

Download allegro 5 semi-compatible PMASK and example at your own risk here: [[1]]

TODO: Add more appropriate way to get PMASK for Allegro 5 working and add other PPCD links (edit)


Theory

If Pixel Perfect is so much slower, why bother? Take round objects, for instance (Especially large ones). Look what happens when you make the box too big:

Image:smileybbcol.JPG

Red represents your bounding box.

TODO: Replace with something not made in Paint (edit)


Even though you can clearly see the Smileyguys aren't touching, your program thinks they are. The corners are colliding, and thus your smileyguy will get hit. (Its little things like this that ruin a game) People aren't going to be happy if they can't figure out why they keep dying. For large, rounded objects you might want to use the Pixel Perfect Collision method instead of bounding boxes.

Bitmask Lib Theory

In theory, you could create a bitmask for every object in the game. This will give you something with which to perform your collision detection. The bitmask would probably look like this:

Image:Spritesbitmask.gif

Sprite by Pheonix_Pinion of DeviantArt

The white pixels represent the areas with color, and thus where he can get hurt. We compare the bitmasks of him and an enemy or projectile; we go through on a pixel by pixel basis and see if the white parts of them collide.

We accomplish this by calculating how two objects overlap, and then testing each pixel to see if they are actually touching. This iteration method can be rather slow, so I advise not using anything derived from the code below. This snippet should illustrate the idea behind Pixel Perfect Collision.

//Go through all the pixels in the range
for(int x = BEGIN_X; x < END_X; x++) {
    for(int y = BEGIN_Y; y < END_Y; y++) {
        //test the pixel at that location on both bitmaps and see if it is transparent
        if(testPixel(x, y, bitmap1) && testPixel(x, y, bitmap2);
            //if they both aren't transparent, then we have a collision
            return 1;
    }
}
//if no non-transparent parts touch, then there isn't a collision
return 0;

http://www.allegro.cc/manual/api/bitmap-objects/bitmap_mask_color

found here: http://www.allegro.cc/forums/thread/587702

bool collide_detect(int mx, int my, int bx, int by, BITMAP *sprite1, BITMAP *sprite2) {
    int xmax1 = mx + mw, ymax1 = my + mh;
    int xmax2 = bx + bw, ymax2 = by + bh;
 
    int xmin = max(mx, bx);
    int ymin = max(my, by);
 
    int xmax = min(xmax1, xmax2);
    int ymax = min(ymax1, ymax2);
 
    if (xmax <= xmin || ymax <= ymin) {
        return false;
    }
 
    int mask1 = bitmap_mask_color(sprite1);
    int mask2 = bitmap_mask_color(sprite2);
 
    for (int y = ymin; y < ymax; y++) {
        for (int x = xmin; x < xmax; x++) {
            int x1 = x - xmin1, y1 = y - ymin1;
            int x2 = x - xmin2, y2 = y - ymin2;
 
            int color1 = getpixel(sprite1, x1, y1);
            int color2 = getpixel(sprite2, x2, y2);
 
            if (color1 != mask1 && color2 != mask2) {
                return true;
            }
        }
    }
 
    return false;
}

Important: Don't forget that the bitmap himself haven't positions like x, y coordinates. You must create a struct or class to set the x,y coordinates, the bitmap and maybe the speed.

Alternate Theory

You could reconcile the two bitmaps by bitwise and-ing the bitmasks together. Then we can test for a 'White pixel', as ANY white at all would mean that there is a collision. Testing just once will drastically reduce the overhead.

Another way to reduce overhead would be to make sure you only test areas probable for collision. Divide the screen into sectors, and test for objects in the same sector before you use PPC.

Then only test a small area, not the entire sprite for collision. Thinking intelligent collisions will help with reducing the time spent on it.

Personal tools
Adsense