Pixel-Perfect Collision Detection in ActionScript3
Comments(45)
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
isplayObject, 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)
oint -
{
-
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
Thank you so much for this!
I just used this class in one of my flash game projects and it works perfectly. This is such an improvement over the hitTest functions that come with AS3. I also didn’t notice any speed performance hits during numerous function calls.
Thanks again, you just made my life a whole lot easier;)
Hello!
I have a major problem.
When I set my document class to this class, I get the following error:
5000: The class ‘PixelPerfectCollisionDetection’ must subclass ‘flash.display.MovieClip’ since it is linked to a library symbol of that type.
Suggestion?
@Andreas: This class won’t work as a document class — because, as you mentioned, it’s not a subclass of MovieClip (or more accurately, Sprite). This class just contains static utility functions for you to call from your other code.
@Everyone: This is by far the most popular post on my blog. And there has been a great deal of good feedback in these comments. I’m going to role all this together and make a new post soon.
@Troy: How could I call functions from this?
importing it?
Hi folks. I’m sorry to be so dense, but I’m new to flash, and I don’t understand this: when I use the class and FLA as they are, they work great, but when I replace the movieclips target1 and target2 with my own movie clip symbols, it gives me errors on each line that includes either “target1_mc” or “target2_mc.” Why is that? Thanks!
Sorry. This is the error: “1120: Access of undefined property target1_mc.” This is a great little class, if only I knew enough to use it. Thanks!!
Nevermind. I forgot to name the instances. This thing is great! Thanks!
[...] the source code to make it relatively easy to extend it. Thanks to Troy Gilbert for publishing his PixelPerfectCollisionDetection class – I used his very useful tool to determine the arrow positions. [...]
One issue I had was that I used TweenLiteFilter to fade out a blur on one of the objects I was checking for collisions on but as I didn’t clear the filter array this caused the colour channel to not show up and thus return no collisions. Setting the filter array to [] sorted this out.
Thank you very much for giving some time to read my problem.
I’m building a shooter game where a bullet is call from a class and the enemy is also called from a class.
I cant make them collide. In order for stuff to start exploding.
I keep getting this error:
1120:Access of undefined property nBullet[ I removed the code from the comment. -Troy ]any kind of help will be greatly appreciated!
@Kilamantok: I can’t tell from the code provided what exactly the problem is. It looks as though nBullet is not declared at the right scope for where you’re trying to access it. If they’re declared in separate classes, you’ll need to pass it from one to the other.
Bottom-line: I’d try posting the question to a general programming forum to get it sorted out, it’s not really relevant to this post.
Grabbed this class to do some testing tonight, and am having a puzzling problem. Let me draw out a scenario for you here:
[Stage]
[PLAYER_MC]
[HIT_AREA_MC]
[OBSTACLE]
So I have a player object that rotates(hit_area_mc rotates with it, inside). When doing a collision check it appears that the transform of the shared parent is the only transform applied to the test objects… so my hit_area_mc is not properly testing for collisions against the obstacle.
Any thoughts?
[...] original code, along with its accompanying notes, is here. I have copied it into the below (collapsed) code box (click the triangle): ?View Code [...]
Troy,
I hope i’m not a complete idiot, but here is what I have
blank stage with 2 movieclips… rect1_mc (instance name myRect1_mc) rect2_mc (instance name myRect2_mc)
main timeline just imports stuff
rect1 and 2 have startDrag and stopDrag functions
the startDrag calls the isColliding function in a hitTest function
the stopDrag removes the hitTest function.
main timeline action as follows;
import flash.display.MovieClip;
import flash.events.MouseEvent;
import collDetect;
/*I renamed your source to collDetect.as in the same directory*/
FIRST FRAME OF rect1_mc;
this.addEventListener(MouseEvent.MOUSE_DOWN, myStartDragger);
this.addEventListener(MouseEvent.MOUSE_UP, myStopDragger);
function myStartDragger(e:Event):void
{
this.addEventListener(Event.ENTER_FRAME, hitTest);
this.startDrag();
trace(”draggin ” this);
}
function myStopDragger(e:Event):void
{
this.removeEventListener(Event.ENTER_FRAME, hitTest);
this.stopDrag();
trace(”Done Draggin ” this);
}
function hitTest(e:Event):void
{
if(collDetect.isColliding(this, (parent as MovieClip).myRect2_mc, stage, true, 255))
{
trace(”COLLIDING!!! Yaaaah!”);
}else{
trace(”Rect 1 is not colliding”);
}
}
FIRST FRAME OF rect2_mc
this.addEventListener(MouseEvent.MOUSE_DOWN, myStartDragger);
this.addEventListener(MouseEvent.MOUSE_UP, myStopDragger);
function myStartDragger(e:Event):void
{
this.addEventListener(Event.ENTER_FRAME, hitTest);
this.startDrag();
trace(”draggin ” this);
}
function myStopDragger(e:Event):void
{
this.removeEventListener(Event.ENTER_FRAME, hitTest);
this.stopDrag();
trace(”Done Draggin ” this);
}
function hitTest(e:Event):void
{
if(collDetect.isColliding(this, (parent as MovieClip).myRect1_mc, stage, true, 255))
{
trace(”COLLIDING!!! Yaaaah!”);
}else{
trace(”Rect 2 is not colliding”);
}
}
I can’t seem to get a isColliding = true.
I will continue to look at it until I can’t see(hehe) any help would be appreciated.
Thanks for the great post, I hope this works for me.
Cifpher
It took the better part of a day to finally get here. This pixel perfect collision detection class really works as advertized. I have been using the class from adventures in actionscript but it didn’t work with scaling. Thank you very much!
… it says i have a 1084: Syntax error: expecting rightparen before oint.
public static function getCollisionPoint(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = (0) oint
Looks like the code was copied incorrectly, that line in your code should read:
public static function getCollisionPoint(target1:DisplayObject, target2:DisplayObject, commonParent:DisplayObjectContainer, pixelPrecise:Boolean = false, tolerance:Number = 0):PointLooks like the blog is converting code to emoticons… sorry!