# Pixel-Level Collision Detection

This post is part of a series called Collision Detection and Reaction.
Pixel-Level Collision Detection for Transformed Graphics
Predicting Collision Points With Math in AS3

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 3x3 bitmaps, a maximum of 9x9 repetitions is required. If my bitmap size goes to 100x100, 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:

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.

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.

## 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.

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.