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.