# Pixel-Level Collision Detection

##### Tutorial Details
• Difficulty: Beginner
• Platform: Flash (Flash Player 10.1)
• Language: AS3
• Software Used: FlashDevelop
• Estimated Completion Time: 25 minutes
This entry is part 5 of 8 in the Collision Detection and Reaction Session
« PreviousNext »

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.

 Observation Description Top left pixels The top left pixels for both bitmaps are used as the starting pixel for checkings. For example, a1 is the starting pixel checked against all pixels in b, which starts with b1. Both top left pixels. Scan-line progression As mentioned in previous point, checking is done in order of a1, a2, a3 … a9. Note the way these pixels are arranged. Common coordinate space Assume both graphics are added to the stage’s display list. The location of each pixel in both bitmaps, in the stage’s coordinate space, will be compared to see if any overlappings occur. Expensive computation For two 3×3 bitmaps, a maximum of 9×9 repetitions is required. If my bitmap size goes to 100×100, you can see how quickly the total calculation grows. However, if any one check returns a positive result then the remainder of the checks can be aborted, since when one pixel overlaps in both bitmaps, we can say that a collision happens between the bitmaps

## 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();
coconut.x = stage.stageWidth * 0.3; coconut.y = stage.stageHeight * 0.2;
bdat1 = new BitmapData(150, 150, true, 0x00000000);
bdat1.draw(coconut);

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

t1.x = stage.stageWidth * 0.2; t1.y = stage.stageHeight * 0.8;
t1.width = 300; t1. height = 100;

}

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.

• http://www.bubbleknotmediastudios.com Josh Byvelds

Awesome Tutorial, i have been scanning the internet for how to do this type of collision detection for a long time. Thank you!

• Frank

Geat tutorial…also your previous ones. Maybe you could make a polygon collision detection in the future.. :) Thanks

• shiu

Yup Frank, that’s definitely coming up soon.

• http://www.photonstorm.com Richard Davey

This is an extremely expensive method of pixel checking! Used on any number of objects, or those of a significant size, would cause a huge hit on speed. It works but it’s about as brute-force as you can get! Would be much better off using the ColorTransform blend normal/difference method and using a getColorBoundsRect on the resulting bitmap. Example code here: https://github.com/photonstorm/Flixel-Power-Tools/blob/master/Test%20Suite/src/org/flixel/plugin/photonstorm/FlxCollision.as (it’s for Flixel but you can easily modify it to use 2 bitmapDatas instead) and it’s fast enough to use in real-time in games with hundreds of sprites flying around, because we do :)

• http://michaeljameswilliams.com/ Michael James Williams

Nice! Thanks :)

• shiu

Brillian work around!

• Shafeen

I would like to focus on the point Richard has made.

While I see that you put effort into this tutorial, I feel that this technique you talked about needs more examples with practical uses.

Tuts+ needs to take a bit more care about what kind of content is okay to accept.

• Shafeen

TLDR:

Make Bounding Box around objects, if too far —> dont check anything.
If closer than a threshold value ——–> check pixels for overlap

• http://michaeljameswilliams.com/ Michael James Williams

It’s my fault – I should have made it clearer that this is a shorter tutorial than usual, with another piece on bitmap/pixel collision detection coming next week. (And possibly more to follow.)

• Aqif

Great Tutorial, Nicely Explained.

• Mike

Awesome, despite whether or not it will perform well in high stress tests is a mute point. I think it’s important to understand the concept and then let the developer continue the process or making it better. Too many developers want to copy/paste code from online, but that isn’t developing. Development is learning a concept and improving and improvising to solve a business need. People need to stop thinking “I just got to get this done” and start thinking “how do I make this concept work for me”.

Sorry about the soap box. Fantastic job on this tutorial!

• Briandito Priambodo

I want to thank you from the bottom of my code :)
This has helped me a lot in developing my skills. You did not just show me how to do it, but you made me understand the whole thing. Thank you :)