GameDev math recipes: Collision detection using an axis-aligned bounding box part 2.

In a prior recipe, we looked at how to handle collisions using an axis aligned bounding box, but there was one major problem. If our bounding box is axis aligned, how do we handle rotation? As you can probably tell by gigantic spoiler of a rotating jet to our right, the answer is we resize the bounding box to match the new extents of the rotated sprite. Let’s look at how:

Just the Math

if(createjs.Bitmap.prototype.getBoundingRect == null){

createjs.Bitmap.prototype.getBoundingRect = function(){

var bb = new createjs.Rectangle(

this.x – this.image.width/2,

this.y – this.image.height/2,

this.image.width,

this.image.height);

var corners = new Array();

corners[0] = new createjs.Point(bb.x,bb.y); //Top left

corners[1] = new createjs.Point(bb.x + bb.width,bb.y); //Top right

corners[2] = new createjs.Point(bb.x,bb.y + bb.height); // Bottom Left

corners[3] = new createjs.Point(bb.x + bb.width,bb.y + bb.height); //Bottom Right

var midPoint = new createjs.Point(this.x,this.y);

for(var i = 0; i < corners.length; i++){

corners[i] = rotatePoint(corners[i],midPoint,this.rotation);

}

var minX,minY,maxX,maxY;

minX = maxX = corners[0].x;

minY = maxY = corners[0].y;

for(var i =1; i < corners.length; i++){

if(corners[i].x < minX) minX = corners[i].x;

if(corners[i].x > maxX) maxX = corners[i].x;

if(corners[i].y < minY) minY = corners[i].y;

if(corners[i].y > maxY) maxY = corners[i].y;

}

bb.width = maxX – minX;

bb.height = maxY – minY;

bb.x = this.x – bb.width/2;

bb.y = this.y – bb.height/2;

return bb;

}

Controls:
Click on the box to focus and press B to toggle the blue box from being displayed.

Description

That code excerpt makes it look more complicated than it actually is, not the version at the bottom of this post in the Complete Code section is more heavily commented.

Essentially as our underlying sprite rotates, the bounding box around it changes in size. Now when we are creating our bounding box, we have to take the rotation into consideration. Please note, there are a number of opportunities to optimize this code for performance, I favoured readability over performance, although I did note a few of the opportunities for improvement in the code comments.

First thing we have to do is get the original, untranslated bounding box of the sprite. This is simply the image dimensions of our source sprite. Unfortunately EaselJS doesn’t provide a mechanism for defining a rectangle about it’s mid point, like we have with our sprite, so we need to calculate the x and y values of our bounding box, which is at the top left corner of the rectangle. This value is calculated by subtracting half the sprites width and height from it’s location ( at it’s mid point ). If your library of choice allows you to specify a rectangle using it’s mid point, width and height, you can remove some of this ugliness.

Now that we have our untranslated bounding box, we want to apply the sprite’s rotation to each corner of the sprite. We accomplish by applying a rotation around the centre of the sprite to each corner of the bounding box, see the See Also section for more details about rotation. Note, this is one of those areas you could easily optimize for performance down the road.

Now that all 4 corners have been rotated, we need to figure out what the smallest rectangle that will encompass our translated points is. To determine this, we loop through each point in our array, looking for the largest and smallest values in the X and Y axis. Once we have determined what the new boundaries our, we construct our newly resized bounding box using these values. Once again, we can’t specify a rectangle using it’s centre point in EaselJS, so once again we need to calculated the top left corner using the same logic as before.

If you turn off the blue debug lines I’ve drawn around the translated shape ( click the window and press B to toggle ), you will notice there is a ton of empty space as the sprite rotates, making it easy for collisions to appear to happen even though the space is actually empty. You are very correct, and this is one of the biggest downsides to using AABBs. There are however options for dealing with this, some of which we will discuss later on.

When looking at the complete code below, realize that a great deal of it is for rendering debug information on screen and wouldn’t normally be required in your collision detection code.

Complete Code

<!DOCTYPE html>

<html>

<head>

var jetSprite;

var stage;

// Actual bounds is the Shape used to store the drawn blue bounding lines

var actualBounds;

// hideActualBounds is a toggle for making the debug lines visible or not

var hideActualBounds = false;

document.addEventListener(‘DOMContentLoaded’, demo,false);

document.onkeydown = function(e){

switch(e.keyCode)

{

case 66: // up arrow

hideActualBounds = !hideActualBounds;

break;

}

function rotatePoint(point, center, angle){

angle = (angle ) * (Math.PI/180); // Convert to radians

var rotatedX = Math.cos(angle) * (point.x – center.x) – Math.sin(angle) * (point.y–center.y) + center.x;

var rotatedY = Math.sin(angle) * (point.x – center.x) + Math.cos(angle) * (point.y – center.y) + center.y;

return new createjs.Point(rotatedX,rotatedY);

}

if(createjs.Rectangle.prototype.intersects == null){

createjs.Rectangle.prototype.intersects = function(rect){

return (this.x <= rect.x + rect.width &&

rect.x <= this.x + this.width &&

this.y <= rect.y + rect.height &&

rect.y <= this.y + this.height);

}

if(createjs.Bitmap.prototype.getBoundingRect == null){

createjs.Bitmap.prototype.getBoundingRect = function(){

var bb = new createjs.Rectangle(

this.x – this.image.width/2,

this.y – this.image.height/2,

this.image.width,

this.image.height);

// Get the 4 corners of the bounding box, order doesn’t matter since they can potentially change

// Note, you could optimize this two only require the top left and bottom right corners

var corners = new Array();

corners[0] = new createjs.Point(bb.x,bb.y); //Top left

corners[1] = new createjs.Point(bb.x + bb.width,bb.y); //Top right

corners[2] = new createjs.Point(bb.x,bb.y + bb.height); // Bottom Left

corners[3] = new createjs.Point(bb.x + bb.width,bb.y + bb.height); //Bottom Right

var midPoint = new createjs.Point(this.x,this.y);

// Now apply the rotation of the sprite to the corners of the bounding box

// This loop could be merged with the min/max loop for optimization purposes

// But for readability I keep it separate for now.

for(var i = 0; i < corners.length; i++){

corners[i] = rotatePoint(corners[i],midPoint,this.rotation);

}

// Draw the rotated shape for debug reasons

// This draws a rectangle as 4 lines around the actual rotated image bounding area

if(actualBounds){

stage.removeChild(actualBounds);

}

if(!hideActualBounds){

var g = new createjs.Graphics();

g.setStrokeStyle(1);

g.beginStroke(createjs.Graphics.getRGB(0,0,255));

g.moveTo(corners[0].x,corners[0].y);

g.lineTo(corners[1].x,corners[1].y);

g.lineTo(corners[3].x,corners[3].y);

g.lineTo(corners[2].x,corners[2].y);

g.lineTo(corners[0].x,corners[0].y);

actualBounds = new createjs.Shape(g);

stage.addChild(actualBounds);

}

// These variables hold the smallest and largest X and Y values found in the Point array

var minX,minY,maxX,maxY;

// Small optimization here, start assuming first point is correct to eliminate a loop iteration

minX = maxX = corners[0].x;

minY = maxY = corners[0].y;

// Loop through Points determining the boundaries of our newly rotated rectangle

for(var i =1; i < corners.length; i++){

if(corners[i].x < minX) minX = corners[i].x;

if(corners[i].x > maxX) maxX = corners[i].x;

if(corners[i].y < minY) minY = corners[i].y;

if(corners[i].y > maxY) maxY = corners[i].y;

}

// We now have the four extreme points of our new bounding box, update bb with new box dimensions

bb.width = maxX – minX;

bb.height = maxY – minY;

bb.x = this.x – bb.width/2;

bb.y = this.y – bb.height/2;

return bb;

}

// This function is responsible for actually drawing the bounding box on screen

function updateBoundingBox(){

// Draw the bounding rect and create a new Shape with it

var g = new createjs.Graphics();

g.setStrokeStyle(1);

g.beginStroke(createjs.Graphics.getRGB(255,255,255));

var bb = jetSprite.getBoundingRect();

g.drawRect(bb.x,bb.y,bb.width,bb.height);

if(jetSprite.boundingBox){

stage.removeChild(jetSprite.boundingBox);

}

jetSprite.boundingBox = new createjs.Shape(g);

stage.addChild(jetSprite.boundingBox);

}

function demo(){

stage = new createjs.Stage(“theCanvas”);

jetSprite = new createjs.Bitmap(“jetsprite.png”);

jetSprite.boundingBox = null;

actualBounds = null;

stage.addChild(jetSprite);

// Add a Image load handler, as image.width and image.height are meaningless until

// load is done and DOMContentLoaded doesn’t seem to take into account dynamic images

jetSprite.image.onload = function(e){

jetSprite.y = 200;

jetSprite.x = 200;

jetSprite.regX = jetSprite.image.width/2;

jetSprite.regY = jetSprite.image.height/2;

updateBoundingBox();

}

//And go…

stage.update();

// onFrame will be called each “tick”. Default is 50ms, or 20FPS

createjs.Ticker.addListener(onFrame);

}

function onFrame(elapsedTime) {

// Convert from milliseconds to fraction of a second

var delta = elapsedTime /1000;

jetSprite.rotation = jetSprite.rotation + 1;

if(jetSprite.rotation > 360) jetSprite.rotation = 0;

updateBoundingBox();

stage.update();

}

</script>

</head>

<body>

</body>

</html>