Pixel-Perfect Collision Detection in ActionScript3
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!
-
package
-
{
-
import flash.display.BitmapData;
-
import flash.display.BitmapDataChannel;
-
import flash.display.BlendMode;
-
import flash.display.DisplayObject;
-
import flash.display.DisplayObjectContainer;
-
import flash.geom.Matrix;
-
import flash.geom.Point;
-
import flash.geom.Rectangle;
-
-
public class PixelPerfectCollisionDetection
-
{
-
/** Get the collision rectangle between two display objects. **/
-
public static function getCollisionRect(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Rectangle
-
{
-
// get bounding boxes in common parent's coordinate space
-
var rect1:Rectangle = target1.getBounds(commonParent);
-
var rect2:Rectangle = target2.getBounds(commonParent);
-
-
// find the intersection of the two bounding boxes
-
var intersectionRect:Rectangle = rect1.intersection(rect2);
-
-
if (intersectionRect.size.length> 0)
-
{
-
if (pixelPrecise)
-
{
-
// size of rect needs to integer size for bitmap data
-
intersectionRect.width = Math.ceil(intersectionRect.width);
-
intersectionRect.height = Math.ceil(intersectionRect.height);
-
-
// get the alpha maps for the display objects
-
var alpha1:BitmapData = getAlphaMap(target1, intersectionRect, BitmapDataChannel.RED, commonParent);
-
var alpha2:BitmapData = getAlphaMap(target2, intersectionRect, BitmapDataChannel.GREEN, commonParent);
-
-
// combine the alpha maps
-
alpha1.draw(alpha2, null, null, BlendMode.LIGHTEN);
-
-
// calculate the search color
-
var searchColor:uint;
-
if (tolerance <= 0)
-
{
-
searchColor = 0x010100;
-
}
-
else
-
{
-
if (tolerance> 1) tolerance = 1;
-
var byte:int = Math.round(tolerance * 255);
-
searchColor = (byte <<16) | (byte <<8) | 0;
-
}
-
-
// find color
-
var collisionRect:Rectangle = alpha1.getColorBoundsRect(searchColor, searchColor);
-
collisionRect.x += intersectionRect.x;
-
collisionRect.y += intersectionRect.y;
-
-
return collisionRect;
-
}
-
else
-
{
-
return intersectionRect;
-
}
-
}
-
else
-
{
-
// no intersection
-
return null;
-
}
-
}
-
-
/** Gets the alpha map of the display object and places it in the specified channel. **/
-
private static function getAlphaMap(target:DisplayObject, rect:Rectangle, channel:uint, commonParent:DisplayObjectContainer):BitmapData
-
{
-
// calculate the transform for the display object relative to the common parent
-
var parentXformInvert:Matrix = commonParent.transform.concatenatedMatrix.clone();
-
parentXformInvert.invert();
-
var targetXform:Matrix = target.transform.concatenatedMatrix.clone();
-
targetXform.concat(parentXformInvert);
-
-
// translate the target into the rect's space
-
targetXform.translate(-rect.x, -rect.y);
-
-
// draw the target and extract its alpha channel into a color channel
-
var bitmapData:BitmapData = new BitmapData(rect.width, rect.height, true, 0);
-
bitmapData.draw(target, targetXform);
-
var alphaChannel:BitmapData = new BitmapData(rect.width, rect.height, false, 0);
-
alphaChannel.copyChannel(bitmapData, bitmapData.rect, new Point(0, 0), BitmapDataChannel.ALPHA, channel);
-
-
return alphaChannel;
-
}
-
-
/** Get the center of the collision's bounding box. **/
-
public static function getCollisionPoint(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Point
-
{
-
var collisionRect:Rectangle = getCollisionRect(target1, target2, commonParent, pixelPrecise, tolerance);
-
-
if (collisionRect != null && collisionRect.size.length> 0)
-
{
-
var x:Number = (collisionRect.left + collisionRect.right) / 2;
-
var y:Number = (collisionRect.top + collisionRect.bottom) / 2;
-
-
return new Point(x, y);
-
}
-
-
return null;
-
}
-
-
/** Are the two display objects colliding (overlapping)? **/
-
public static function isColliding(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):Boolean
-
{
-
var collisionRect:Rectangle = getCollisionRect(target1, target2, commonParent, pixelPrecise, tolerance);
-
-
if (collisionRect != null && collisionRect.size.length> 0) return true;
-
else return false;
-
}
-
}
-
}
If the rendering is using h/w, have you tried folding the intersection rect epeatedly on itself so you can do a smaller getColorBoundsRect() test? Assuming this is the gating function wrt speed.
Rendering is not using hardware, but it is native to the Flash Player, which is the equivalent of hardware-accelerated in the Flash world…
What do you mean by folding the intersection rect in on itself?
I mean that if you want to reduce the number of pixels tested by getColorBoundsRect(), you do additive copy of the right half of the intersection rect to the left, the bottom to the top half and repeat thus halving the dminesions each time, you’ll end up with approx 1×1 rect to test - it probably won’t get down to 1×1 by you get the idea.
That fine RenderWare product used this technique to render lightmaps on a PS2 but on xfer back a small amount of data.
Interesting… I’ll have to do some timing tests to see if the cost of the additive copies outweighs the cost of the getColorBoundsRect() on the smaller bitmap…
Hi,
I tried using the method isColliding. It didn’t work at all. I have two display objects and every time the x and y position of the first object is changed I’m checking if it collides.
Can you give an example of how to use it properly?
Thanks!
Are you providing a DisplayObject that’s common to both of the DisplayObjects? I’ve not used this source in a while (we had to go back to bounding-box collision tests because of the number of the objects) but it was copied nearly verbatim from our project, and it was definitely working.
You’d use isColliding like this:
isColliding(myObject1, myObject2, stage, true, 127);That will test if myObject1 and myObject2 are colliding, checking at the pixel-level (as opposed to just checking bounding boxes) and considering a collision only if the pixels have greater than 50% alpha.
The reason I have you specify the parent instead of assuming the stage is to handle off-stage display lists.
hi Troy,
first of all i must compliment you for your work. nice one!
but, I do face a problem:
i have a movieclip(A) hiding within movieclip(B) :
B.A.visible = false;
if I have movieclip(C) that is same level with B, It will still detected when C hit A even A.visible is set to false. whereas, in Grant Skinner version, it works fine.
any idea?
Hi Troy,
thanks for you reply. I forgot to tell you something .. both Objects are extending from DisplayObjects (they are images actually) however they are rotated using the mx:Rotate flex thing.
Would it still suppose to work?
Thanks!
Hiya,
I needed a pixel perfect collision detection routine for a game i’m making, and i found grant skinners and your version, and wrote a test app - and managed to make a tweaked version which combines a bit from each and gained a speed up. It’s my first ever released bit of Actionscript, let me know if it’s ok to share the modified code on my blog :).
Did you ever try the additive copy folding method someone mentioned above?
@TheActionscriptMan: Looks good. I haven’t spent too much time studying the code, but I guess the big difference from mine is that instead of extracting alpha maps from each image and combining those, you use a ColorTransform to get a similar result (different bit ops). So, instead of 3 draws and 2 copy channels (mine) you’ve got just 2 draws, which should account for most of the speedup you’re seeing.
As far as I can tell, they’re equivalent. I want to take a few minutes and do the math on the combining ops to ensure they’d get the same results in all situations…
The code is totally okay to share. I didn’t stick a license on it, but you can consider it equivalent to MIT or LPGL… free to do with it what you want, commercial or personal, just don’t claim a verboten version as your own. Attribution is always appreciated but not required (what you’ve got on your blog is more than enough).
And if you don’t mind, I’ll probably include your changes into my code!
I haven’t tried the additive copy folding Adam mentioned. Now that I’ve got Flex 3 with its profiler I may be able to get some detailed profiling info to work off of. It depends on whether the extra cost of additional draw calls is more than the savings of a smaller getColorBoundsRect call. My gut tells me it’d break even at best, but I don’t have any numbers to back that up.
Thanks for this. It’s just what I needed.
Does anyone know why flash doesn’t have a proper pixel perfect hit test? It strikes me as odd.
Okay, everything seems to be working fine, except no matter if pixelperfect is turned on or off when I call isColliding, it uses the bounding boxes to determine the collision.
So I went hunting and found out that it’s because the width and height of the collisionRect always comes back as 0. I have no idea why this is - some help? Just so you know, I have a maze type thing (walls) and just a simple little 3 pixel ball. I tried it out with a more solid movieclip as well (a large circle) and it does the same. Here’s my code:
//
ball.addEventListener(Event.ENTER_FRAME, hitTest);
function hitTest(e:Event):void{
if(PixelPerfectCollisionDetection.isColliding(walls, ball, stage, true, 255)){
hitCounter
trace(hitCounter);
}
}
//
If collisionRect comes back with zero size, then no overlap was found between the two display objects. I’d need to step through the code while executing on your actual data set to figure out exactly why there’s no overlap. Some questions:
- Is a valid intersectionRect being calculated? What are its dimensions?
- Are valid alphaMap’s being generated? What are their dimensions?
- What path through the branches does the code take, i.e. where does the code return from each of the main functions?
It should be pretty quick to answer these questions if you’re using an interactive debugger like Flex Builder.
Troy -
Is the above class the newer version (handling rotation, etc.) that you mentioned on 2.25.08 on the Boulevart blog? I am putting together an open-source piece that uses your class, and would like to make sure I have the latest version. Thanks.
No, it’s not the latest version, I haven’t had time to finish/test it and put together the post (but I do have a draft I’m working on). The next few weeks are going to be pretty crazy for me, so it’ll probably be late April before I’m able to get it posted.
The above source *does* handle rotation and all transforms. What it doesn’t account for is the visible flags or alpha values of of DisplayObjects higher up the display list… it’s not intended to, but some users have requested it.
Troy -
I just wanted to follow up and let you know I have officially released the open-source piece I alluded to in my last post. A link to the site can be found below. Thanks again for all your hard work.
https://netfiles.umn.edu/users/frah0005/www/dynamicSpace/dynamicSpace.html
I’d really appreciate reading your thoughts on the blog (a link to the blog can be found on the page).
HI ,
Cool project! I’ve added to my favorites for future projects.
Please, I’ve been testing perfectCollision with two movie clips, and I haven’t got the collision (similar case as Martin)
If I use only BoundingBox(pixelPrecise as false)no problem.
But using pixelPrecise as True then no collision appear. What I’m doing wrong? Is necessary to convert movie clips to Bitmaps? I’m lose.
line of code:
(PixelPerfectCollisionDetection.isColliding(siluetaMC, objMC, stage, true, 120))
Best Regards
I am having trouble properly importing the package into my actionscript file.
I am using “import com.mysite.game.PixelPerfectCollisionDetection;” which is where I have placed the file in the directory structure. When I reference the isColliding function, I get a compiler error saying
1180: call to a possibly undefined method isColliding.
Any help you can offer is greatly appreciated.
Thanks,
Ben
Thanks for the share!!!!!!!!!!!!
[...] Pixel-Perfect Collision Detection in ActionScript3 Currently working on a site that requires collision detection. (tags: as3 collision) [...]
we wrote a version here too http://www.tink.ws/blog/as-30-hittest/
Looks very promising — but I can’t get the pixelPrecise detection to work.
Everythings seems fine in the debugger. intersectionRect, alpha1 and alpha2 have a dimension of e.g. 69×63, but collisionRect is 0×0.
I tried with MovieClip and Bitmap objects.
Any idea how to debug further?
Would it make sense to have a look at the alpha bitmaps? Is there an easy way to do it?
Solved! *g*
I used the main stage object as parent. Using obj.parent instead it works!
But I can’t figure out, which object is being used now. The debugger says: exception thrown by getter! A little confusing…
Anyway, it works…
The tolerance needs to be a number between 0 and 1. See lines 41 - 47.
How could I modify this code or Skinners code to subtract the intersecting pixels from one of the movie clips? I want to create some kind of deformable terrain.
This may be a simple question, but I’m fairly new to Flash. So here’s the situation, I have imported the package declared on this page, but when I try and use the isColliding() function, I get the error: Access of undefined property PixelPerfectCollisionDetection.
I have imported the package using:
import classes.Collision;
What am I doing wrong? Thanks for the help.
Hi,
I’ve tried different pixelperfect sollutions and I also encoutered the display list problem. Your function works fine for me. Thanks.
Though, it would be easier for people if you posted an example in the blog post instead of a reply
(I needed that example cos it didn’t work first time)
@Eric
I think you should give the actinoscript file the same name as the classname.
So that would be PixelPerfectCollisionDetection.as, or rename the class.
Hi there!
Your collision class is not working really well. My simple random vector drawing gets detected inappropriately. I think it has something to do with the bounding rectangles, not very sure though.
I used
if (PixelPerfectCollisionDetection.getCollisionRect(blue, red, stage, true, 255) != null)
trace(”Hit!”);
Pure red and pure blue.
So I can’t be wrong unless there’s something wrong with your functions. =)
Best Regards,
Someone