Advertisement

Pixel-Level Collision Detection Based on Pixel Colors

by
Student iconAre you a student? Get a yearly Tuts+ subscription for $45 →
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
This post is part of a series called Collision Detection and Reaction.
Predicting Collision Points With Math in AS3

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.

Note: As well as being part of the Shoot-'Em-Up Session, this article is also part of Collision Detection and Reaction.


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.

private var enemy1:Bitmap, myShip:Bitmap;
private var myShipSp:Sprite;
private var rec_e:Rectangle, rec_m:Rectangle;
private var intersec:Rectangle;
enemy1 = new E1 as Bitmap;	addChild(enemy1);
myShip = new My as Bitmap;	
myShipSp = new Sprite; addChild(myShipSp);
myShipSp.addChild(myShip);

enemy1.x = stage.stageWidth >> 1;	myShipSp.x = stage.stageWidth >> 1;
enemy1.y = stage.stageHeight * 0.2;	myShipSp.y = stage.stageHeight * 0.8;

//drawing boxes around the sprite
draw(enemy1.getBounds(stage), this, 0);
draw(myShipSp.getBounds(stage), this, 0);

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

private function refresh(e:Event):void 
{
    //determining the bounding box of intersection area
    rec_e = enemy1.getBounds(stage);
    rec_m = myShipSp.getBounds(stage);
    intersec = rec_e.intersection(rec_m);
    
    //redraw the bounding box of both sprites
    this.graphics.clear();
    draw(enemy1.getBounds(stage), this, 0);
    draw(myShipSp.getBounds(stage), this, 0);
    
    //only draw bounding box of intersection area if there's one
    if (!intersec.isEmpty()){
        lines.graphics.clear();
        draw(intersec, lines);
        
        t.text ="Intersection area by red rectangle."
    }
    else {
        t.text ="No intersection area."
    }
}

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

private function refresh(e:Event):void 
{
    //determining the bounding box of intersection area
    rec_e = enemy1.getBounds(stage);
    rec_m = myShipSp.getBounds(stage);
    intersec = rec_e.intersection(rec_m);
    
    //redraw the bounding box of both sprites
    this.graphics.clear();
    draw(enemy1.getBounds(stage), this, 0);
    draw(myShipSp.getBounds(stage), this, 0);
    
    //only draw bounding box of intersection area if there's one
    if (!intersec.isEmpty()){
        lines.graphics.clear();
        draw(intersec, lines);
        
        //to draw the intersection area and checking for overlapping of colored area
        var eM:Matrix = enemy1.transform.matrix;
        var myM:Matrix = myShipSp.transform.matrix;
        
        bdt_intersec = new BitmapData(intersec.width, intersec.height, false, 0)
        eM.tx -= intersec.x;	eM.ty -= intersec.y
        myM.tx -= intersec.x;	myM.ty -= intersec.y
        
        bdt_intersec.draw(enemy1, eM);
        bdt_intersec.draw(myShip, myM);
        
        bm_intersec.bitmapData = bdt_intersec;
        bm_intersec.x = 10
        bm_intersec.y = stage.stageHeight * 0.8 - bm_intersec.height;
        
        t.text = "Intersection area by red rectangle.\n"
    }
    else {
        t.text ="No intersection area."
    }
}

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

//to draw the intersection area and checking for overlapping of colored area
var eM:Matrix = enemy1.transform.matrix;
var myM:Matrix = myShipSp.transform.matrix;

bdt_intersec = new BitmapData(intersec.width, intersec.height, false, 0)
eM.tx -= intersec.x;	eM.ty -= intersec.y
myM.tx -= intersec.x;	myM.ty -= intersec.y

//tweak color
bdt_intersec.draw(enemy1, eM, new ColorTransform(1,1,1,1,255,-255,-255), BlendMode.ADD);
bdt_intersec.draw(myShip, myM, new ColorTransform(1,1,1,1,-255,255,-255), BlendMode.ADD);

bm_intersec.bitmapData = bdt_intersec;
bm_intersec.x = 10
bm_intersec.y = stage.stageHeight * 0.8 - bm_intersec.height;

t.text = "Intersection area by red rectangle.\n"

//check for the existance of the right color
intersec_color = bdt_intersec.getColorBoundsRect(0xffffff, 0xffff00);
if (!intersec_color.isEmpty())	t.appendText("And there are interesecting pixels in the area.");

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.

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
bitmapdata fixed (1000 iterations)                                      
Player version: WIN 11,1,102,55 (debug)
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
bitmapdata fixed                                            168     0.17
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
bitmapdata updates (1000 iterations)                                    
Player version: WIN 11,1,102,55 (debug)
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
bitmapdata updates                                         5003     5.00
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
custom method (1000 iterations)                                         
Player version: WIN 11,1,102,55 (debug)
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
custom method                                              4408     4.41
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

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.

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
default hitTest (1000 iterations)                                       
Player version: WIN 11,1,102,55 (debug)
include bounds                                                          
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
default hitTest                                             189     0.19
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
default hitTest (1000 iterations)                                       
Player version: WIN 11,1,102,55 (debug)
include transform                                                       
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
default hitTest                                             357     0.36
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
default hitTest (1000 iterations)                                       
Player version: WIN 11,1,102,55 (debug)
include hittest                                                         
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
default hitTest                                            4427     4.43
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
custom method (1000 iterations)                                         
Player version: WIN 11,1,102,55 (debug)
inlcude bounds and transform                                            
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
custom method                                               411     0.41
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
custom method (1000 iterations)                                         
Player version: WIN 11,1,102,55 (debug)
include draw and bounds                                                 
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
custom method                                              3320     3.32
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

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!

Advertisement