Friday, January 27, 2012

bounding rectangles 101

I'm very psyched to be doing the Global Game Jam for the fourth time-- all around the world people form small teams in order to make interesting games, all over one-48-hour weekend.

Something that comes up often in game programming is the question "did this thing hit this other thing?" Often, the easiest way of figuring that out is using "bounding rectangles", changing the question to the simpler-to-code "does the box corresponding to this thing's outline overlap the box corresponding to this other thing's outline?" (Even if you need to do a finer-grained collision detection, it's often more efficient to start with this question.)

But even with this simplification, it's not a trivial thing to code. If you code like I do, you'll be having two objects, each with an x,y coordinate for their top corner, and a width and a height (referred to now from w and h).  My class in (processing/processing.js) to represent that is something like this:

```class boxish{
float w,h,x,y;
color c;

boxish(float px,float py,float pw,float ph,color pc){
x = px;
y = py;
w = pw;
h = ph;
c = pc;
}

void draw(){
fill(c);
rect(x,y,w,h);
}
}```

that lets me create a box, give it a color, and then ask it do draw itself.

So now what?

The first simplification of "do these boxes overlap?" can be "do these boxes overlap horizontally AND vertically"? Because two boxes could be around the same x-coordinate, but if one is way higher than the other one, they won't overlap-- and vice versa for the y-coordinate. By breaking down the problem this way, we're turning our 2 dimensional issue into a 2 1 dimensional ones... much easier!

The trivial code for this is

```boolean overlapBox(boxish b1, boxish b2){
if(overlapHoriz(b1,b2) && overlapVert(b1,b2)){
return true;
} else {
return false;
}
}```

Ok. Lets start with the Horizontal 1D problem. We have 2 line segments, and we need to know if they touch each other. There are 6 possibilities, outline here in this crude diagram:

I don't know about you, but my takeaway was this: there are more ways for two lines to overlap than for them not to... therefore, we're going to just test for the two cases where they don't - namely where both of line1's points are to the left of line 2's left or both the points are to the right of line 2's right.

So my code was:
boolean overlapHoriz(boxish b1, boxish b2){
float b1left = b1.x;
float b1right = b1.x+b1.w;
float b2left = b2.x;
float b2right = b2.x+b2.w;
if(b1left < b2left && b1right < b2left) return false;
if(b1left > b2right && b1right > b2right) return false;
return true;
}

overlapVert() should be pretty obvious from that.

So that's it. I put together the following little test program that changes color when the moving box overlaps one of the static ones:

You can see the full psj sourcecode here.

1. First off, why check the left point, if it will always be to the left of the right point?

if(b1left < b2left && b1right < b2left) return false;
//should be
if(b1right < b2left) return false;

An interesting question though. As an exercise, I wondered if "1d Sphere-based collision detection" would offer any improvements on complexity or processor usage.

"Spheres, in 1 dimension?"

Yeah man. You've already got the diameter of each line, and that's all you need. (I worked it out using the radius first; way more complicated than it should have been). Just get the diameter and the positions. You don't even need the center of the 'sphere', as long as you're only checking one dimension of said sphere.

float b1diameter = b1.w;
float b2diameter = b2.w;

float b1position = b1.x;
float b2position = b2.x;

Then you return false if the spheres aren't touching in either direction, adding in the diameter where necessary.

if(b1position+b1diameter < b2position) return false;
if(b1position > b2position+b2diameter) return false;

In retrospect, it seems like the same thing you just typed, just visualized in a different manner... Either way, I saved you two comparisons, and two "and" booleans. :)

2. that's pretty cool!