Relative performance for collision detection techniques in ActionScript 3
If you have read my blog any this week, you have probably noticed that I have been doing some basic research on collision detection within the Flash Player. As part of this, I have put together a simple test suite, showing the performance of a couple of different techniques for checking for collision. This is by no means meant to be exhaustive (and currently tilts towards boundary collision). However, I wanted to post the results as the current information is useful (if nothing more than to confirm existing assumptions), and perhaps generate more tests an ideas around collision detection.
First, the test code (uses Flash Pro). clip1 and clip2 reference two overlapping MovieClips on the stage (clip2 is about 1/2 the size of clip1).
package
{
import flash.display.MovieClip;
import flash.geom.Point;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.geom.Rectangle;
import com.gskinner.utils.PerformanceTest;
public class CollisionDetectionTests extends MovieClip
{
public var clip1:MovieClip;
public var clip2:MovieClip;
private var dynamicClip1:MovieClip;
private var dynamicClip2:MovieClip;
var point1:Point = new Point();
var point2:Point = new Point();
private var clip1Rect:Rectangle;
private var clip1ClipBmpData:BitmapData;
private var clip2Rect:Rectangle;
private var clip2ClipBmpData:BitmapData;
public function CollisionDetectionTests()
{
super();
init();
checkCollisions();
runTests();
}
private function init():void
{
clip1Rect = clip1.getBounds(this);
clip1ClipBmpData = new BitmapData(clip1Rect.width, clip1Rect.height, true, 0);
clip1ClipBmpData.draw(clip1);
clip2Rect = clip2.getBounds(this);
clip2ClipBmpData = new BitmapData(clip2Rect.width, clip2Rect.height, true, 0);
clip2ClipBmpData.draw(clip2);
dynamicClip1 = new MovieClip();
dynamicClip1.graphics.beginFill(0xFF0000);
dynamicClip1.graphics.drawEllipse(0,0, 100,100);
dynamicClip1.cacheAsBitmap = true;
dynamicClip1.x = 300;
dynamicClip1.y = 300;
addChild(dynamicClip1);
dynamicClip2 = new MovieClip();
dynamicClip2.graphics.beginFill(0x0000FF);
dynamicClip2.graphics.moveTo(0, 0);
dynamicClip2.graphics.lineTo(100, 0);
dynamicClip2.graphics.lineTo(100, 100);
dynamicClip2.graphics.lineTo(0, 100);
dynamicClip2.graphics.lineTo(0, 0);
dynamicClip2.cacheAsBitmap = true;
dynamicClip2.x = 250;
dynamicClip2.y = 250;
addChild(dynamicClip2);
}
private function checkCollisions():void
{
//make sure everything is working and returns true
trace(checkHitTest());
trace(boundsIntersection());
trace(checkHitTestReverse());
trace(checkBoundsManually());
trace(hitTestCircle());
trace(checkBitmapDataHit());
trace(checkBitmapDataHitReverse());
trace(checkBitmapDataHitInternal());
trace(checkBitmapDataHitDynamic());
}
private function runTests():void
{
var perfTest:PerformanceTest = PerformanceTest.getInstance();
perfTest.out = out;
//this is to work around bug in test lib
perfTest.testSuite({});
perfTest.testFunction(checkHitTest, 10000, "checkHitTest", "Uses DisplayObject.hitTest");
perfTest.testFunction(checkHitTestReverse, 10000, "checkHitTestReverse", "Uses DisplayObject.hitTest with clips reversed");
perfTest.testFunction(boundsIntersection, 10000, "boundsIntersection", "Uses Rectangle.intersects()");
perfTest.testFunction(checkBoundsManually, 10000, "checkBoundsManually", "manually checks if bounds intersect.");
perfTest.testFunction(hitTestCircle, 10000, "hitTestCircle", "Check if bounding circles intersect.");
perfTest.testFunction(checkBitmapDataHit, 10000, "checkBitmapDataHit", "Uses BitmapData.hitTest to check for collision.");
perfTest.testFunction(checkBitmapDataHitReverse, 10000, "checkBitmapDataHitReverse", "Uses BitmapData.hitTest to check for collision. Instances reversed.");
perfTest.testFunction(checkBitmapDataHitInternal, 10000, "checkBitmapDataHitInternal", "Uses BitmapData.hitTest to check for collision. BitmapData not cached.");
perfTest.testFunction(checkBitmapDataHitDynamic, 10000, "checkBitmapDataHitDynamic", "Uses BitmapData.hitTest to check for collision. BitmapData not cached. MovieClips dynamic.");
}
private function checkHitTest():Boolean
{
return clip1.hitTestObject(clip2);
}
private function checkHitTestReverse():Boolean
{
return clip2.hitTestObject(clip1);
}
private function boundsIntersection():Boolean
{
return clip1.getBounds(this).intersects(clip2.getBounds(this));
}
private function hitTestCircle():Boolean
{
var dx:Number = (clip2.x + clip2.width / 2) - (clip1.x + clip1.width / 2);
var dy:Number = (clip2.y + clip2.height / 2) - (clip1.y + clip1.height / 2);
var dist:Number = Math.sqrt(dx * dx + dy * dy);
return (dist < ((clip1.width / 2) + (clip2.width / 2)));
}
private function checkBoundsManually():Boolean
{
if(clip1.x < clip2.x + clip2.width &&
clip2.x < clip1.x + clip1.width &&
clip1.y < clip2.y + clip2.height &&
clip2.y < clip1.y + clip1.height
)
{
return true;
}
return false;
}
private function checkBitmapDataHit():Boolean
{
point1.x = clip1.x;
point1.y = clip1.y;
point2.x = clip2.x;
point2.y = clip2.y;
if(clip1ClipBmpData.hitTest(point1,
255,
clip2ClipBmpData,
point2,
255
))
{
return true;
}
return false;
}
private function checkBitmapDataHitInternal():Boolean
{
var _clip1Rect:Rectangle = clip1.getBounds(this);
var _clip1ClipBmpData:BitmapData = new BitmapData(_clip1Rect.width, _clip1Rect.height, true, 0);
_clip1ClipBmpData.draw(clip1);
var _clip2Rect:Rectangle = clip2.getBounds(this);
var _clip2ClipBmpData:BitmapData = new BitmapData(_clip2Rect.width, _clip2Rect.height, true, 0);
_clip2ClipBmpData.draw(clip2);
point1.x = clip1.x;
point1.y = clip1.y;
point2.x = clip2.x;
point2.y = clip2.y;
var hits:Boolean = false;
if(_clip1ClipBmpData.hitTest(point1,
255,
_clip2ClipBmpData,
point2,
255
))
{
hits = true;
}
_clip1ClipBmpData.dispose();
_clip2ClipBmpData.dispose();
return hits;
}
private function checkBitmapDataHitDynamic():Boolean
{
var dynamicClip1Rect:Rectangle = dynamicClip1.getBounds(this);
var dynamicClip1ClipBmpData:BitmapData = new BitmapData(dynamicClip1Rect.width,
dynamicClip1Rect.height, true, 0);
dynamicClip1ClipBmpData.draw(dynamicClip1);
var dynamicClip2Rect:Rectangle = dynamicClip2.getBounds(this);
var dynamicClip2ClipBmpData:BitmapData = new BitmapData(dynamicClip2Rect.width,
dynamicClip2Rect.height, true, 0);
dynamicClip2ClipBmpData.draw(dynamicClip2);
point1.x = dynamicClip1.x;
point1.y = dynamicClip1.y;
point2.x = dynamicClip2.x;
point2.y = dynamicClip2.y;
var hits:Boolean = false;
if(dynamicClip1ClipBmpData.hitTest(point1,
255,
dynamicClip2ClipBmpData,
point2,
255
))
{
hits = true;
}
dynamicClip1ClipBmpData.dispose();
dynamicClip2ClipBmpData.dispose();
return hits;
}
private function checkBitmapDataHitReverse():Boolean
{
point1.x = clip1.x;
point1.y = clip1.y;
point2.x = clip2.x;
point2.y = clip2.y;
if(clip2ClipBmpData.hitTest(point2,
255,
clip1ClipBmpData,
point1,
255
))
{
return true;
}
return false;
}
private function out(str:*):void
{
trace(str);
}
}
}
You can download the code from here (requires Flash Pro and Grant Skinner’s Performance Testing Harness).
And here are the raw results:
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkHitTest (10000 iterations) Uses DisplayObject.hitTest –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 8 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkHitTestReverse (10000 iterations) Uses DisplayObject.hitTest with clips reversed –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 7 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– boundsIntersection (10000 iterations) Uses Rectangle.intersects() –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 33 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkBoundsManually (10000 iterations) manually checks if bounds intersect. –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 18 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– hitTestCircle (10000 iterations) Check if bounding circles intersect. –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 22 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkBitmapDataHit (10000 iterations) Uses BitmapData.hitTest to check for collision. –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 7 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkBitmapDataHitReverse (10000 iterations) Uses BitmapData.hitTest to check for collision. Instances reversed. –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 7 0.00 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkBitmapDataHitInternal (10000 iterations) Uses BitmapData.hitTest to check for collision. BitmapData not cached. –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 6332 0.63 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– checkBitmapDataHitDynamic (10000 iterations) Uses BitmapData.hitTest to check for collision. BitmapData not cached. Dynamic MovieClips –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– method...................................................ttl ms...avg ms [function] 1892 0.19 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Most of the results are as expected, although there is one surprise.
Doing a BitmapData.hitTest on a MovieClip placed onto the stage at author time (in Flash Pro) is 3 times slower than testing against a MovieClip generated and drawn at runtime. The only thing I can think that is happening is that perhaps for some reason the garbage collector is being triggered in the checkBitmapDataHitInternal and not the checkBitmapDataHitDynamic test. I have asked around internally what might be causing it, but I would be curious if anyone else is seeing the same results.
So, some quick conclusions from this:
- DisplayObject.hitTest is a fast way to do a quick boundaries check.
- Having to dynamically generate BitmapData for BitmapData.hitTest leads to a big performance hit.
- If you can cache the BitmapData being compared, then BitmapData.hitTest performance is on par with the other techniques / APIs tested. However, performance degrades as the dimensions of the clips increase (see here).
- Getting the BitmapData from a MovieClip that has cacheAsBitmap = false is 3 times slower than getting it from a MovieClip with the property set to true (Thanks to Renaun Erickson who figured out the performance discrepancy).
I will update the post and results as I learn more techniques and get more information.
If you find any bugs with the test, or would like to add some more tests (such as a test using BitmapData.getColorBoundsRect), just post them in the comments.
Updated : July 6, 2009 : Added info on cacheAsBitmap property impact on performance. (See this comment).
Updated : November 6, 2009 : Added optimized circle test in comments : Approaches performance of hitTest.
Mike,
This is most likely why all game developers write their own collision detection. 7 ms is horrible.
This is 3D and runs faster than 7ms in some cases with multiple bodies:
http://www.bolt3d.org/examples/ex3/ex3.html
Matt Bolt
26 Jun 09 at 3:38 pm
7ms for 10000 iterations is horrible? In my opinion, that is at the very least tolerable.
TK
26 Jun 09 at 4:06 pm
Very interesting. Will need to return to it later for reference when will be brainstorming pixel precise collisions. Thanks for sharing.
wonderwhy-er
26 Jun 09 at 4:19 pm
@Matt
You do realize that is 7ms for 10,000 iterations?
i.e. each individual check averages .0007 ms.
mike chambers
mesh@adobe.com
mikechambers
26 Jun 09 at 5:01 pm
@Matt: That bolt3d demo is obviously bogging down with the max number of spheres (which is much less than 10k). Maybe it is the rendering.
To give some perspective, if you have a world with 1000 objects and 10 dynamic objects moving around, you will be able to do your collision checking in 7ms. If that was all you did, your game could run at 148 frames/second.
If you cap your game at 60Hz (like I do), then you would have 9ms left of each frame to do gameplay logic, rendering, etc. Hardly the end of the world!
But this really underscores why you want to have higher-level collision routines for more complex scenes. If you had some sort of spatial structure for our 1000/10 example, you might end up doing 9 checks per dynamic object, 90 checks total, taking far less than a millisecond to complete. That would leave you more like 15ms/frame for other work.
@Mike: Great post! (The whole series has been fun to follow.)
I’d love to see how your numbers look when you do random orientations of the two objects; I think that would give a much truer picture of what performance with these different methods looks like. I am guessing that hitTest early-outs when it finds a contact, so you could see a very different performance picture as things move relative to one another, are bigger/smaller, etc.
Ben Garney
26 Jun 09 at 8:11 pm
@Ben – Excellent points. Do you have an example of something that even comes close to what you just described? A PushButton application maybe?
Also, you seemed to ignore the fact that 3D bodies handle collision slightly different than 2D as well as the fact that calculation speed seems to suffer horribly during intense rendering.
Lastly, here’s a website to pass down to the PushButton developers: http://opensource.adobe.com/wiki/display/flexsdk/Coding+Conventions
So while I may think that I have 15ms of *EXTRA* time to waste, it’s really not about that.
Matt Bolt
26 Jun 09 at 10:20 pm
Isnt checking intersection between circles twice as fast without square root? Like this:
var r:Number = clip1.width / 2 + clip2.width / 2;
var r2:Number = r * r;
var dx:Number = clip2.x – clip1.x;
var dy:Number = clip2.y – clip1.y;
var dist:Number = dx * dx + dy * dy;
return (dist < r2);
tonypa
27 Jun 09 at 1:31 am
I will post my results of ttl ms too:
8-8-32-13-19-111-143-1146-966
Notice that last 4 functions (from checkBitmapDataHit to checkBitmapDataHitDynamic) give quite different results from yours.
Test run with FP 10.22, swf compiled with Flash CS3 (swf v9).
tonypa
27 Jun 09 at 1:42 am
Great idea, I should do the same!
There’s a LOT of room for optimizations in that collision code though.
Tonypa’s circle-circle collision code could be around 10 times faster (maybe more?).
It could be improved even more by replacing the
var r:Number = clip1.width / 2 + clip2.width / 2;
by
var r:Number = (clip1.width + clip2.width) * 0.5;
If instead of using DiplayObject.x, y, width or height you create a custom circle class with those properties it would improve a LOT more. DiplayObject.x and DiplayObject.y are slow, but DiplayObject.width and DiplayObject.height are EXTREMELY slow (seriously, ridiculously slow).
And if you really need speed, you can inline the code eliminating those 10000 function calls.
The same applies for many of the other checks!
Make sure you are not using the debug player in the tests! It gives awful results.
SP.
SP
27 Jun 09 at 12:43 pm
@tonya
Yeah, that should be faster, and is easy. Ill add another test using that.
@SP
The goal of this wasnt to super optimize everything, and find the absolute fastest way to do that (since that will largely depend on the application / content / game).
The goal was to give a baseline of relative performance between different high level APIs and techniques
mike chambers
mesh@adobe.com
mikechambers
27 Jun 09 at 2:07 pm
@SP
Feel free to rewrite the circle collision and Ill add it to the test.
Thanks…
mike chambers
mesh@adobe.com
mikechambers
27 Jun 09 at 4:17 pm
Quote: “If you can cache the BitmapData being compared, then BitmapData.hitTest performance is on par with the other techniques / APIs tested.”
Thats not completely true because speed of BitmapData.hitTest is largely depending on the size of objects. For objects with size of only couple of pixels, its lightning-fast. But try objects of hundreds or thousands of pixels and it gets so slow that it cant even finish this test.
Other collision techniques, like math-based or checking bounds, are not affected by the size.
So you cant just compare these results directly.
tonypa
28 Jun 09 at 11:55 pm
I also tested checkGetColorBoundsRect method, it does not perform too well compared to BitmapData.hitTest (2x slower on 20px objects, ~20-25 times slower on 100 px objects).
tonypa
29 Jun 09 at 12:26 am
About your conclusion #4 (MovieClip at author time vs runtime). I think the issue is the use of cacheAsBitmap = true on the runtime objects. If you set the same property in author time (Properties -> Display -> check “Cache as bitmap”) then it has the similar performance.
Renaun Erickson
2 Jul 09 at 7:20 am
@Renaun
You are exactly correct. Setting cacheAsBitmap = true on the author time clips brings the performance to the same level as the dynamic clips.
Here is the relevant section:
Ill update the post to reflect this. Good catch.
mike chambers
mesh@adobe.com
mikechambers
6 Jul 09 at 8:43 am
@tonypa
That is a good point. Here is the result with clips that are about 3 times larger:
Note, that is with cacheAsBitmap set to true.
mike chambers
mesh@adobe.com
mikechambers
6 Jul 09 at 8:54 am
@Matt Bolt:
Sure, Box2D actually does the right thing w.r.t collision (and PushButton is integrated with it out of box). Even if you don’t care about the physical response part, the algorithms that Box2D uses to _detect_ collisions are smart and would get you the performance improvement I described.
Before we go 1.0 we are going to do a major code style update to match Flex style (http://code.google.com/p/pushbuttonengine/issues/detail?id=56) as well as reorganize the codebase to make it easier to work with… Our bad. :)
Ben Garney
6 Jul 09 at 9:59 am
fyi, I have been playing around with this and if you optimize the circle test, you can get performance approaching the built in hitTest:
private function i_hitTestCircle2(clip1:Sprite, clip2:Sprite):Boolean { var dx:Number = clip2.x - clip1.x; var dy:Number = clip2.y - clip1.y ; var radii:Number = ((clip1.width * .5) + (clip2.width * .5)); return ((dx * dx) + (dy * dy) < radii * radii); }
Here are the results:mike chambers
6 Nov 09 at 10:56 pm
I know this post is super-old, but it’s still relevant-ish (Flash Player keeps changing things). So I just wanted to mention an optimization that will turn all those numbers around:
var irect:Rectangle = rect.intersection(rect2);
Then use irect for the clipRect property of draw(), after some coordinate compensation (and after irect is found to be larger than 1×1). This will make Flash draw ONLY the portion of the clips we’re concerned with, drastically reducing draw time, in most cases (especially when testing big clips against small clips).
Besides calling “new”, draw() has the biggest impact on performance (sometimes more-so, depending on the size of the clip to draw), which is why the gain is so large.
Corey von Birnbaum
13 Dec 10 at 8:03 pm
Your Rectangle.intersects() test isn’t fair. It’s definitely getBounds() that’s slowing down the test. In all my tests, even with early bail out, Rectangle.intersects() blows away manual comparisons of the same rectangles (possibly due to the property nature of things like .left, .top, .right, etc.).
Sarah
14 Jul 11 at 3:08 pm