Pixel-Level Collision Detection

Up until now, our collision detection methods have been mathematically based. Although this is helpful, there are cases where the mathematical approach is just not worth it, such as with an irregular, organic shape - the computations required are too complex and expensive to justify. Instead, we can check each individual pixel of the shapes. This is also an expensive approach, but it can at least be optimised.

Collision Detection

This is the final piece we will try to create. Drag the hook over the coconut tree, and note what the text at the bottom says.

Step 1: One by One

Assume we have two bitmaps and we would like to check whether they collide, pixel by pixel: what does it mean? Well, let's suppose both your bitmaps are 3x3px, and all the pixels are filled.

We will be doing literally this:

1. Check if a1 and b1 share the same location.
2. Repeat step (1) but now for a1 and b2.
3. Repeat same between a1 and b3, b4 ... b9.
4. Repeat step (1) to (3) for a2, a3 ... a9.

There are a few observations that I'd like to point out.

Step 2: Extra Considerations

Now, Step 1 can be taken literally if all the pixels are filled. With bitmap graphics, we define an area of rectangular dimension. But not all pixels are filled to form the graphic.

The example below shows the right bitmap occupying only b2, b4, b5, b6 and b8. In this case, we should check each pixel in the left bitmap (a1, a2, a3 ... a9) against only the pixels b2, b4, b5, b6, b8 in the right bitmap.

Now ActionScript provides us with another parameter, alpha, which defines the transparency of the pixel, with 0 being completely transparent and 1 being completely opaque. For b2, b4, b5, b6, b8, we can define a threshold value for alpha, say 0.5.

So, assume that b2 and b8 are both pixels with alpha 0.1; because they are less than the threshold value of 0.5, we will not consider them to be filled pixels, and therefore not check them. So in the end, each pixel in the left bitmap (a1, a2, a3 ... a9) is checked against b4, b5, b6 in right bitmap only.

Step 3: ActionScript Implementation

In ActionScript, we can superimpose vector graphics into BitmapData instances. You can imagine ActionScript taking an X-ray of a vector graphic, and transferring it to a BitmapData, which acts like the photographic film.

(Tip: If you are drawing in Flash IDE and then exporting to FlashDevelop as I'm doing, make sure that the dimensions of the BitmapData are large enough to contain the drawing.)

Here, CTree and Hook are two MovieClip symbols, drawn in Flash; we "X-ray" them to obtain a BitmapData instance for each:

private var coconut:CTree, hk:Hook;
private var bdat1:BitmapData, bdat2:BitmapData;
private var t1:TextField;

public function Matrix_Bitmap() 
{
	coconut = new CTree(); 
	addChild(coconut);
	coconut.x = stage.stageWidth * 0.3; coconut.y = stage.stageHeight * 0.2; 
	bdat1 = new BitmapData(150, 150, true, 0x00000000);
	bdat1.draw(coconut);

	hk = new Hook(); addChild(hk);
	bdat2 = new BitmapData(100, 50, true, 0x00000000);
	bdat2.draw(hk);

	hk.addEventListener(MouseEvent.MOUSE_DOWN, start);
	hk.addEventListener(MouseEvent.MOUSE_UP, end);

	t1 = new TextField(); addChild(t1);
	t1.x = stage.stageWidth * 0.2; t1.y = stage.stageHeight * 0.8; 
	t1.width = 300; t1. height = 100;

	stage.addEventListener(Event.ENTER_FRAME, check);
}

So after that, we'll start the checks by using the hitTest() method of the BitmapData class.

On each passing frame, we will update location of the top left pixel for each bitmap before putting instances of BitmapData through these rigourous hitTest() checks. Note as well that the range for alpha input here is 0 ~ 255 - i.e. there is no threshold. More on transparency in the next step.

private function check(e:Event):void 
{
	var point1:Point = new Point(coconut.x, coconut.y);  //top-left pixel of tree
	var point2:Point = new Point(hk.x, hk.y);  //top-left pixel of hook
	if (bdat1.hitTest(point1, 255, bdat2, point2, 255)) {  //check whether any filled pixels overlap
		t1.text = "At least one pixel has collided"
	}
	else {
		t1.text = "No collision"
	}
}

Here's an example of the output from ActionScript above. Click on the hook and bring it near to the coconut tree and check the response on the text box. Play around with this by bringing the end of the hook near to the edge of the coconut tree's leaves, to see whether this collision is of pixel-level precision.

Step 4: Transparency Level

If you have an image that is, say, gradually disappearing (becoming transparent), you can tell ActionScript at which level of transparency you consider a pixel fit to perform collision checks.

Take the example below: there are several levels of transparency on the sprite and, as you can see, it is gradually lowered to the right. If we set the transparency level to 0.5, then any pixel with an alpha of 0.5 ~ 1 will be considered opaque and fit for collision detection. Those lower than 0.5 will be considered transparent. Even when these pixels collide with that of another object, they will not register a true collision.

Another detail I mentioned just now is that ActionScript BitmapData's hitTest function alpha parameter value actually ranges from 0 ~ 255. So what I do is simply multiply my threshold value by 255 to convert the range.

private function check(e:Event):void 
{
	var point1:Point = new Point(bar1.x, bar1.y);
	var point2:Point = new Point(bar2.x, bar2.y);
	var threshold:Number = 255*0.5
	if (bdat1.hitTest(point1, threshold, bdat2, point2, threshold)) {
		t1.text = "At least one pixel has collided"
	}
	else {
		t1.text = "No collision"
	}
}

Step 5: Optimisation

I've mentioned that pixel-level collision detection is computationally expensive. This means we shoudl only opt for it when it's strictly necessary. If two objects are very far apart, then there's no reason to use this approach, and a normal bounding box collision detection (hitTestObject()) will do.

Here's the idea:

1. Use hitTestObject() to see if two objects's bounding boxes have collided.
2. If the answer is yes, then these two objects are pretty close. Proceed with pixel-level checking.
3. If the answer is no, then these two objects are far apart. End collision checks without pixel-level checking.

private function check(e:Event):void 
{
	var closeEnough:Boolean = coconut.hitTestObject(hk)
	if(closeEnough){
		var point1:Point = new Point(coconut.x, coconut.y);
		var point2:Point = new Point(hk.x, hk.y);
		if (bdat1.hitTest(point1, 255, bdat2, point2, 255)) {
			t1.text = "At least one pixel has collided"
		}
		else {
			t1.text = "No collision"
		}
	}
}

For a full ActionScript reference, check out Matrix_Bitmap3.as from the source download.

Conclusion

Thanks for the read. In the next Quick Tip, we'll be using matrices to transform BitmapData.