Archive for June, 2007

Pixel-Perfect Collision Detection in ActionScript3 21

Posted June 25, 2007

The Flash Player provides vector-perfect collision detection with the hitTest() method. The drawback of this method is that if you use Bitmaps it sees just the bounding-box of the Bitmap, i.e. it ignores alpha. This is pretty frustrating when it comes to a sprite-based game.

A bit of digging on the web found a quick and simple solution from Andre Michelle [.zip]. A slightly more robust version was written for AS2 by Grant Skinner, then ported to AS3 by Boulevart. I grabbed their version to start with...

First, I cleaned up the code and commented it. It's pretty straightforward: you render two display objects to separate color channels, combine the color channels, then search the resulting image for any overlapping color (the previous two sites have deeper explanations).

I found two problems with the code. First, it unions the bounding boxes of the two display objects. This is unnecessary, we only care about the pixels in the intersecting rectangle. And since performance hit of this technique grows with the size of the overlap, this is a critical optimization (you're allocating significantly less BitmapData each test).

Second, the code doesn't account for a display list of any complexity: it assumes the two display objects have the same parent (and are thus in the same coordinate space), and it assumes the display objects do not have any scale or rotation (it only considers linear transformation, i.e. the objects' positions). I fixed both of these.

So, the new code will determine if two DisplayObjects are visibly overlapping with pixel precision. Enjoy!

PLAIN TEXT
Actionscript:
  1. package
  2. {
  3.     import flash.display.BitmapData;
  4.     import flash.display.BitmapDataChannel;
  5.     import flash.display.BlendMode;
  6.     import flash.display.DisplayObject;
  7.     import flash.display.DisplayObjectContainer;
  8.     import flash.geom.Matrix;
  9.     import flash.geom.Point;
  10.     import flash.geom.Rectangle;
  11.    
  12.     public class PixelPerfectCollisionDetection
  13.     {
  14.         /** Get the collision rectangle between two display objects. **/
  15.         public static function getCollisionRect(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Rectangle
  16.         {
  17.             // get bounding boxes in common parent's coordinate space
  18.             var rect1:Rectangle = target1.getBounds(commonParent);
  19.             var rect2:Rectangle = target2.getBounds(commonParent);
  20.            
  21.             // find the intersection of the two bounding boxes
  22.             var intersectionRect:Rectangle = rect1.intersection(rect2);
  23.            
  24.             if (intersectionRect.size.length> 0)
  25.             {
  26.                 if (pixelPrecise)
  27.                 {
  28.                     // size of rect needs to integer size for bitmap data
  29.                     intersectionRect.width = Math.ceil(intersectionRect.width);
  30.                     intersectionRect.height = Math.ceil(intersectionRect.height);
  31.                    
  32.                     // get the alpha maps for the display objects
  33.                     var alpha1:BitmapData = getAlphaMap(target1, intersectionRect, BitmapDataChannel.RED, commonParent);
  34.                     var alpha2:BitmapData = getAlphaMap(target2, intersectionRect, BitmapDataChannel.GREEN, commonParent);
  35.                    
  36.                     // combine the alpha maps
  37.                     alpha1.draw(alpha2, null, null, BlendMode.LIGHTEN);
  38.                    
  39.                     // calculate the search color
  40.                     var searchColor:uint;
  41.                     if (tolerance <= 0)
  42.                     {
  43.                         searchColor = 0x010100;
  44.                     }
  45.                     else
  46.                     {
  47.                         if (tolerance> 1) tolerance = 1;
  48.                         var byte:int = Math.round(tolerance * 255);
  49.                         searchColor = (byte <<16) | (byte <<8) | 0;
  50.                     }
  51.  
  52.                     // find color
  53.                     var collisionRect:Rectangle = alpha1.getColorBoundsRect(searchColor, searchColor);
  54.                     collisionRect.x += intersectionRect.x;
  55.                     collisionRect.y += intersectionRect.y;
  56.                    
  57.                     return collisionRect;
  58.                 }
  59.                 else
  60.                 {
  61.                     return intersectionRect;
  62.                 }
  63.             }
  64.             else
  65.             {
  66.                 // no intersection
  67.                 return null;
  68.             }
  69.         }
  70.        
  71.         /** Gets the alpha map of the display object and places it in the specified channel. **/
  72.         private static function getAlphaMap(target:DisplayObject, rect:Rectangle, channel:uint, commonParent:DisplayObjectContainer):BitmapData
  73.         {
  74.             // calculate the transform for the display object relative to the common parent
  75.             var parentXformInvert:Matrix = commonParent.transform.concatenatedMatrix.clone();
  76.             parentXformInvert.invert();
  77.             var targetXform:Matrix = target.transform.concatenatedMatrix.clone();
  78.             targetXform.concat(parentXformInvert);
  79.            
  80.             // translate the target into the rect's space
  81.             targetXform.translate(-rect.x, -rect.y);
  82.            
  83.             // draw the target and extract its alpha channel into a color channel
  84.             var bitmapData:BitmapData = new BitmapData(rect.width, rect.height, true, 0);
  85.             bitmapData.draw(target, targetXform);
  86.             var alphaChannel:BitmapData = new BitmapData(rect.width, rect.height, false, 0);
  87.             alphaChannel.copyChannel(bitmapData, bitmapData.rect, new Point(0, 0), BitmapDataChannel.ALPHA, channel);
  88.            
  89.             return alphaChannel;
  90.         }
  91.  
  92.         /** Get the center of the collision's bounding box. **/
  93.         public static function getCollisionPoint(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Point
  94.         {
  95.             var collisionRect:Rectangle = getCollisionRect(target1, target2, commonParent, pixelPrecise, tolerance);
  96.        
  97.             if (collisionRect != null && collisionRect.size.length> 0)
  98.             {
  99.                 var x:Number = (collisionRect.left + collisionRect.right) / 2;
  100.                 var y:Number = (collisionRect.top + collisionRect.bottom) / 2;
  101.        
  102.                 return new Point(x, y);
  103.             }
  104.        
  105.             return null;
  106.         }
  107.        
  108.         /** Are the two display objects colliding (overlapping)? **/
  109.         public static function isColliding(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Boolean
  110.         {
  111.             var collisionRect:Rectangle = getCollisionRect(target1, target2, commonParent, pixelPrecise, tolerance);
  112.        
  113.             if (collisionRect != null && collisionRect.size.length> 0) return true;
  114.             else return false;
  115.         }
  116.     }
  117. }