# Pixel-Level Collision Detection Based on Pixel Colors

Difficulty:BeginnerLength:ShortLanguages:
This post is part of a series called Collision Detection and Reaction.
Predicting Collision Points With Math in AS3
This post is part of a series called Shoot-'Em-Up.
Build a Stage3D Shoot-'Em-Up: Score, Health, Lives, HUD and Transitions
Build a Stage3D Shoot-'Em-Up: Full-Screen Boss Battles and Polish

In this tutorial, I'll follow the approach suggested by Richard Davey (Thanks, Richard!), and used by him and others, in detecting collisions between bitmaps with a subtle modification. I'll also compare performance between various approaches of bitmap collision detection using Grant Skinner's PerformanceTest harness.

## Step 1: Overview

I describe this alternative approach in short here.

1. Check whether there's any overlap between the two bitmaps.
2. If there is, proceed to #3. Otherwise, drop out.
3. Check whether the overlap area has any opaque pixels overlapping.
4. If so, the bitmaps overlap. Otherwise, drop out.

## Step 2: Bounding Boxes

First, we check whether the two bitmaps' bounding boxes are overlapping using Rectangle. The scripts are as below. First, the variables.

Here we check for any overlapping area between the boxes. Check out `DetectVisible.as` in the source download for the full script

Here's a demo. Drag the smaller spaceship around.

(Don't worry about the red box that gets "left behind" when the ship is dragged out of the other's bounding box.)

## Step 3: Drawing into the Intersection Area

So if there's an intersecting box area, we proceed to check whether there are overlapping pixels in the area. However, let's first try to draw bitmap into this intersection area. The full script's in `DetectVisible2.as`

Note that since we are drawing the area by the use of a matrix, any scaling, skewing and other transformations on both bitmaps are taken into account. Here's a demo; check out the box in the bottom left corner.

## Step 4: Check for Color in the Intersection Area

So how do we check for the right pixel? Well first of all, we give the color of this intersection box a shade of black (Red = 0, Green = 0, Blue = 0). Then, the shade of the smaller spaceship will painted into this dark box as green, with the blend mode of ADD. Similarly, the shade of the bigger stationary alien spaceship will be painted red.

So now, there will be areas of red and green for the spaceships, and black if there are no overlapping area. However, if there are pixels from these two bitmaps that overlap, these will be drawn in yellow (Red = 255, Green = 255, Blue = 0). We use the method `Bitmapdata.getColorBoundsRect` to check for the existance of this area.

Here's the snippet in `Main.as`

Note that we suppress the Red and Blue components in line 113 to max out Green for the small spaceship. On line 112 we do the same with the alien spaceship with the Blue and Green components.

## Comparing Approaches

So after receiving comments on performance issues regarding collision detection, I decided to do some quick and dirty tests on these approaches. I created 20 enemy spaceships and one player spaceship and checked collision detection between that one player ship against the other 20. These sprites are packed into the same vicinity to force collision detection for all approaches to have a complete run.

The first approach is the simplest. `BitmapData` is captured on initiation and for each frame, collision detection is checked using `BitmapData.hitTest()`. For the second approach, `BitmapData` is updated each frame and collision detection is done based upon those `BitmapData` captured. The third one refers to the approach suggested by this tutorial.

So the result for one of the tests I've done is as below.

The `PerformanceTest` gives different results whenever I run test. So I ran it a few times and derived an average time. Conclusion: the fastest method is the first, followed by the third and then the second approach.

So storing away `BitmapData` for bitmaps when they are first introduced into stage and checking for `hitTest` every frame after is actually efficient, provided these sprites don't perform any transformations other than translation (such as rotation, skewing and scaling) across time. Otherwise, you will be forced to adopt either the second or third approach, and the third one is more efficient as indicated by the image above.

You may check out `Collisions.as` and `Results.as` for the full script.

## Searching for Expensive Methods

I embarked thereafter to search for the specific lines of code that took up more computation time. The second and third approach took more time, so I derived several functions from them, each breaking at different points. Check out one of the results below.

The first, second, and third times refer to the second approach at different breakpoints, and the fourth and fifth times refer to the third approach. Looking at the third and the fifth time results, `BitmapData.draw` seems to take a lot of computation time. And the time taken for drawing with the second approach seems to be more expensive in computation time, which leads me to think that the sizes for `BitmapData.draw` to operate on does matter. You may check out `Collisions2.as` and `Results2.as` for the full scripts.

One thing I find a little disturbing is the inconsistency of these tests - I always don't get the same time results, although they almost follow the same ranking at all times. So, its good enough to do some simple comparison between functions.

## Conclusion

Well, thanks for your time looking reading this little tip. Hope it has been useful. Do leave comments if you don't agree with anything in this tutorial. I'd love to respond to feedback!