Bounding Box vs. Bounding Circle Collision Detection Performance AS3
Posted November 17, 2010 by Nick Vogt in Programming
Before doing more complex collision detection in a game, it is useful to first check and make sure a larger bounding area is colliding. This is so that only one calculation needs to be done for each collision detection most of the time, and then further collision detections are only done if objects are close and potentially colliding.
The higher-level bounding collision detection is often done with either a bounding box or a bounding circle (for 2D). The question is, which is faster? With bounding boxes you are checking all four sides of the boxes to see if they overlap. With bounding circles you are checking the distance between two circles and comparing it to their combined radiuses (radii).
Update:
Following a comment from "C coder" below, I found that my previous method for checking bounding box collision was not optimized. Previously I had checked all 4 sides in one "if statement". After further testing, it turns out that checking each side individually is faster. This is because if the first bounding box's right side is less than the other bounding box's left side, there can be no collision and there's no use in checking the other sides after that.
So my original unoptimized performance check was this (Actionscript 3):
That took 289 milliseconds on average to process. Now here is the optimized test:
That took 203 milliseconds on average to process. And the most surprising result is that it is faster even though the bounding boxes do collide! When I inputted x and y coordinates for the two boxes that did not collide, the resulting process time went down to 141 milliseconds
Now back to my original test: Here is the performance using bounding circles:
(r1 and r2 are the radiuses for the circles)
The above run took 164 milliseconds.
While my original conclusion was that bounding circles were faster, it now looks like bounding boxes are faster when there is no collision, while bounding circles are faster when there is a collision. So it really comes down to the nature of your game. If objects are collision checked often and are usually not colliding (such as a projectile flying through the air), it is probably faster to use bounding box checks.
One last note. If you store the squared radius of each object, instead of calculating it each time, you can speed it up a bit. I haven't ran that test, though I imagine it could put the distance-based collision back ahead of the bounding box.
The higher-level bounding collision detection is often done with either a bounding box or a bounding circle (for 2D). The question is, which is faster? With bounding boxes you are checking all four sides of the boxes to see if they overlap. With bounding circles you are checking the distance between two circles and comparing it to their combined radiuses (radii).
Update:
Following a comment from "C coder" below, I found that my previous method for checking bounding box collision was not optimized. Previously I had checked all 4 sides in one "if statement". After further testing, it turns out that checking each side individually is faster. This is because if the first bounding box's right side is less than the other bounding box's left side, there can be no collision and there's no use in checking the other sides after that.
So my original unoptimized performance check was this (Actionscript 3):
var i:int = 0;
var x1:int = 44, y1:int = -12, w1:int = 100, h1:int = 100;
var x2:int = -20, y2:int = 27, w2:int = 100, h2:int = 100;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if(x1 + w1 > x2 && x1 < x2 + w2 && y1 + h1 > y2 && y1 < y2 + h2)
{
// Collision!
}
}
var time2 = new Date();
trace(time2 - time1);
var x1:int = 44, y1:int = -12, w1:int = 100, h1:int = 100;
var x2:int = -20, y2:int = 27, w2:int = 100, h2:int = 100;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if(x1 + w1 > x2 && x1 < x2 + w2 && y1 + h1 > y2 && y1 < y2 + h2)
{
// Collision!
}
}
var time2 = new Date();
trace(time2 - time1);
That took 289 milliseconds on average to process. Now here is the optimized test:
var i:int = 0;
var x1:int = 44, y1:int = -12, w1:int = 100, h1:int = 100;
var x2:int = -20, y2:int = 27, w2:int = 100, h2:int = 100;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if(x1 + w1 > x2)
{
if(x1 < x2 + w2)
{
if(y1 + h1 > y2)
{
if(y1 < y2 + h2)
{
// Collision!
}
}
}
}
}
var time2 = new Date();
trace(time2 - time1);
var x1:int = 44, y1:int = -12, w1:int = 100, h1:int = 100;
var x2:int = -20, y2:int = 27, w2:int = 100, h2:int = 100;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if(x1 + w1 > x2)
{
if(x1 < x2 + w2)
{
if(y1 + h1 > y2)
{
if(y1 < y2 + h2)
{
// Collision!
}
}
}
}
}
var time2 = new Date();
trace(time2 - time1);
That took 203 milliseconds on average to process. And the most surprising result is that it is faster even though the bounding boxes do collide! When I inputted x and y coordinates for the two boxes that did not collide, the resulting process time went down to 141 milliseconds
Now back to my original test: Here is the performance using bounding circles:
var i:int = 0;
var x1:int = -68, y1:int = 26, r1:int = 100;
var x2:int = 151, y2:int = -44, r2:int = 60;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) < (r1 + r2) * (r1 + r2))
{
// Collision!
}
}
var time2 = new Date();
trace(time2 - time1);
var x1:int = -68, y1:int = 26, r1:int = 100;
var x2:int = 151, y2:int = -44, r2:int = 60;
var time1 = new Date();
for(i = 0; i < 10000000; i ++)
{
if((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) < (r1 + r2) * (r1 + r2))
{
// Collision!
}
}
var time2 = new Date();
trace(time2 - time1);
(r1 and r2 are the radiuses for the circles)
The above run took 164 milliseconds.
While my original conclusion was that bounding circles were faster, it now looks like bounding boxes are faster when there is no collision, while bounding circles are faster when there is a collision. So it really comes down to the nature of your game. If objects are collision checked often and are usually not colliding (such as a projectile flying through the air), it is probably faster to use bounding box checks.
One last note. If you store the squared radius of each object, instead of calculating it each time, you can speed it up a bit. I haven't ran that test, though I imagine it could put the distance-based collision back ahead of the bounding box.
| Series | ActionScript 3 Tutorials |
|---|---|
| Tags | actionscript 3 tutorial |
Comment on this post
Legacy Comments (5)
C coder | December 29, 2010 | 1:58 PM PST
Quick response! I appreciate it. I've been working on the exact same problem myself for a bullet-hell style shooter I'm attempting to write - quick collision testing is a must!
I've now done the same tests, but in C. The only notable difference is that I generate 5000 test cases at the start of the run, then test all cases 10000 times in a loop.
After a few runs on my little Eee PC, the average time for box testing was 2.6 seconds, and for circle testing was 3.8 seconds. So box testing takes about 68% of the time circle testing takes - a considerable saving!
I've now done the same tests, but in C. The only notable difference is that I generate 5000 test cases at the start of the run, then test all cases 10000 times in a loop.
After a few runs on my little Eee PC, the average time for box testing was 2.6 seconds, and for circle testing was 3.8 seconds. So box testing takes about 68% of the time circle testing takes - a considerable saving!
Nick | December 29, 2010 | 9:25 AM PST
Some very interesting results. Breaking the conditional checks into 4 separate lines was quicker than a single line, even when the objects did collide. And it was quicker yet when they didn't collide. I'll update the post to reflect this.
Nick | December 29, 2010 | 9:18 AM PST
That is a good observation you make. I will run some tests to see if breaking the 4 conditional checks into 4 separate checks speeds it up.
C coder | December 29, 2010 | 8:45 AM PST
(continued...)
Also, if it does, you'd need to change the values of x, y etc. to make this a better test. IMHO you should probably do this anyway, just to make sure - at present you're only testing how fast _one_particular_ case can be tested. There may be unforeseen issues that could cause one or both methods to perform differently under different conditions.
Interesting stuff though, thanks. :)
Also, if it does, you'd need to change the values of x, y etc. to make this a better test. IMHO you should probably do this anyway, just to make sure - at present you're only testing how fast _one_particular_ case can be tested. There may be unforeseen issues that could cause one or both methods to perform differently under different conditions.
Interesting stuff though, thanks. :)
C coder | December 29, 2010 | 8:44 AM PST
Does AS bail out early from logical operations? I mean that say you test for
function_that_returns_false() && function_that_returns_true()
will it evaluate function_that_returns_false() and realise there's no need to evaluate function_that_returns_true()? (I've heard some languages work like that, but I forget which ones and where I heard it... make of that what you will).
If not, your bounding box method could be improved upon: Test one axis first, then the other, instead of both in one statement. This could greatly reduce the number of comparisons that need to be processed.
function_that_returns_false() && function_that_returns_true()
will it evaluate function_that_returns_false() and realise there's no need to evaluate function_that_returns_true()? (I've heard some languages work like that, but I forget which ones and where I heard it... make of that what you will).
If not, your bounding box method could be improved upon: Test one axis first, then the other, instead of both in one statement. This could greatly reduce the number of comparisons that need to be processed.