Pixel Perfect Collision

From Allegro Wiki

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.

Libraries

Sadly the Bitmask library has a bunch of broken links, so there is currently no link or information on the suggested library for this method.

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:

Red represents your bounding box.

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:

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.