H3XED

Bounding Box vs. Bounding Circle Collision Detection Performance AS3

Nov 17, 2010   Programming   Nick Vogt   Comments (1)
Please note that this post is over a year old and may contain outdated information.
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):

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);

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);

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);

(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.
Share This Post
Twitter

Comments (1)

Maciej Sidorczuk   May 20, 2017
Nice article but you're wrong at the last paragraph - the formulae has a squared sum of 2 radii, not a sum of squared radii. Other than that It was pretty helpful so cheers to that.
Share This Post
Twitter
H3XED © Nick Vogt   RSS   Policies   Twitter