Rants and opinions about game AI and programming

I’m going to steal a function from Miguel Gomez’s article on intersection tests for games as an example of what NOT to do. Yes this code is 12 years old, but it’s still the number one result when you google ‘aabb sweep test.’ Also, it’s not like you haven’t seen code written in 2011 that looks like this.

#include "aabb.h"

//Sweep two AABB's to see if and when they first
//and last were overlapping

const bool AABBSweep(
        const VECTOR&	Ea,	//extents of AABB A
        const VECTOR&	A0,	//its previous position
        const VECTOR&	A1,	//its current position
        const VECTOR&	Eb,	//extents of AABB B
        const VECTOR&	B0,	//its previous position
        const VECTOR&	B1,	//its current position
        SCALAR&	 u0,	//normalized time of first collision
        SCALAR&	 u1	//normalized time of second collision
    )
{
    const AABB A( A0, Ea );//previous state of AABB A
    const AABB B( B0, Eb );//previous state of AABB B
    const VECTOR va = A1 - A0;//displacement of A
    const VECTOR vb = B1 - B0;//displacement of B
    //the problem is solved in A's frame of reference

    VECTOR v = vb - va;
    //relative velocity (in normalized time)

    VECTOR u_0(0,0,0);
    //first times of overlap along each axis

    VECTOR u_1(1,1,1);
    //last times of overlap along each axis

    //check if they were overlapping
    // on the previous frame
    if( A.overlaps(B) )
    {
        u0 = u1 = 0;
        return true;
    }

    //find the possible first and last times
    //of overlap along each axis
    for( long i=0 ; i<3 ; i++ )
    {
        if( A.max(i)<B.min(i) && v[i]<0 )
        {
            u_0[i] = (A.max(i) - B.min(i)) / v[i];
        }
        else if( B.max(i)<A.min(i) && v[i]>0 )
        {
            u_0[i] = (A.min(i) - B.max(i)) / v[i];
        }

        if( B.max(i)>A.min(i) && v[i]<0 )
        {
            u_1[i] = (A.min(i) - B.max(i)) / v[i];
        }
        else if( A.max(i)>B.min(i) && v[i]>0 )
        {
            u_1[i] = (A.max(i) - B.min(i)) / v[i];
        }
    }

    //possible first time of overlap
    u0 = MAX( u_0.x, MAX(u_0.y, u_0.z) );

    //possible last time of overlap
    u1 = MIN( u_1.x, MIN(u_1.y, u_1.z) );

    //they could have only collided if
    //the first time of overlap occurred
    //before the last time of overlap
    return u0 <= u1;
}

So my immediate reaction to this was:

Reading through the comments (thank god for them) it started making some more sense. However there’s absolutely no reason in 2011 to write code that ever looks even remotely like this, nor should it ever be considered forgivable. Yes, back in the ye ol’ days of programming when all you had was a crt, vi and a Huey Lewis and the News cassette, writing this style of code was normal, and even good practice (because it actually affected how the code compiled). Even in the 90′s it was considered “job security” to write code only you could understand. However, with formatting standards, code reviews, pair programming, constant maintenance, and tools like Intellisense, it doesn’t fly these days. Writing code like this is needlessly error prone and utterly asinine in every way.

Exhibit A:

        const VECTOR&	Ea,	//extents of AABB A

He’s declaring a parameter that describes the extents of the AABB ‘A’ along each axis from it’s centroid. Fair enough. Why not something like this:

        const VECTOR& inFirstAABBExtents,

or

        const VECTOR& inAABBoxAExtents,

This solves a few issues. First, just by reading the name of the variable, I know exactly what it represents. I know which AABB it relates to. I know the conceptual meaning of the values it contains. I also know it’s a parameter and not a local because it has the ‘in’ prefix. I also know (via intellisense) its type. I can know everything about this parameter just by reading the name (and the Intellisense mouseover text). It’s immensely more descriptive than the previous version, and reads like plain English. Let’s do another more interesting one:

 SCALAR& u0, //normalized time of first collision

Okay so at first glace, it’s obvious that u0 does not make me think of anything having to do with collisions, time, or normalized values. In fact, if you track down what this variable actually is, it’s the normalized time of the start of a potential collision. I’m going to suggest that it be renamed to “normalizedCollisionStartTime.” Yes that’s a mouthful, but it describes exactly what it is and what its purpose is. Some of you may argue it’s more typing, but you’d be typing that description in the comment anyway, and there’s no reason not to take advantage of Intellisense’s autocomplete.

Next is the issue of a prefix for the variable name. It’s not immediately apparent whether u0 is input, output, or both, but I bet you’re a step ahead of me and thought ‘well if it’s not const, then its value is changed in the function.’ After all, isn’t that the point of const-correctness? Yes, this is an output parameter, but you wouldn’t know that unless you read through every instance where it was used to see when it was assigned to and when it was referenced. Just by looking at this one line, there’s no way to tell if its initial value will change the function’s behavior. It is also entirely plausible that this function is not completely const-correct (hell, maybe some intern wrote it) and this is just some random parameter that happens to be passed as a non-const reference for no good reason. We can do better than this. If it was both an input and an output parameter, I’d use “io” but since it’s only an out parameter (the first thing this function does with the parameter is assign it a value), we’ll use “out.” Putting this together gives us:

        SCALAR&	 outNormalizedCollisionStartTime,

Long, but worlds better than ‘uO.’ Okay now for some more improvements:

    for( long i=0 ; i<3 ; i++ )

So it’s pretty obvious that this is looping three times, but it’s less obvious that it’s performing the same tests for each axis. Loop counters and iterators should describe what they’re looping over, especially when the value is used within the loop (as this case demonstrates). Something like “separationAxisIndex” or just “axisIndex” works much nicer than “i.” If this was an iterator I would name it something like “separationAxisIter.”

    for (long axisIndex = 0; axisIndex < 3; axisIndex++)

Just by renaming variables and removing/improving comments the code becomes much clearer and understandable:

#include "aabb.h"

// Sweep two AABB's to see if and when they first and last were overlapping.

const bool AABBSweep(
        const VECTOR&	inAABBoxAExtents,
        const VECTOR&	inAABBoxAInitialPosition,
        const VECTOR&	inAABBoxAFinalPosition,
        const VECTOR&	inAABBoxBExtents,
        const VECTOR&	inAABBoxBInitialPosition,
        const VECTOR&	inAABBoxBFinalPosition,
        SCALAR&	 outNormalizedCollisionStartTime,
        SCALAR&	 outNormalizedCollisionEndTime
    )
{
    const AABB AInitialState(inAABBoxAInitialPosition, inAABBoxAExtents);
    const AABB BInitialState( inAABBoxBInitialPosition, inAABBoxBExtents );
    const VECTOR ADisplacement = inAABBoxAFinalPosition - inAABBoxAInitialPosition;
    const VECTOR BDisplacement = inAABBoxBFinalPosition - inAABBoxBInitialPosition;

    // The problem is solved in A's frame of reference.
    VECTOR RelativeDisplacementOfB = BDisplacement - ADisplacement;

    VECTOR axisOverlapStartTimes(0,0,0);
    VECTOR axisOverlapEndTimes(1,1,1);

    // If the two AABB's were overlapping last frame.
    if (AInitialState.overlaps(B))
    {
        outNormalizedCollisionStartTime = outNormalizedCollisionEndTime = 0;
        return true;  // There was a collision.
    }

    // Find the start and end of a potential intersection along each axis.
    for (long axisIndex = 0; axisIndex < 3; axisIndex++)
    {
        if (AInitialState.max(axisIndex) < BInitialState.min(axisIndex) &&
			RelativeDisplacementOfB[axisIndex] < 0)
        {
            axisOverlapStartTimes[axisIndex] =
				(AInitialState.max(axisIndex) - BInitialState.min(axisIndex)) /
				RelativeDisplacementOfB[axisIndex];
        }
        else if (BInitialState.max(axisIndex) < AInitialState.min(axisIndex) &&
			RelativeDisplacementOfB[axisIndex] > 0)
        {
            axisOverlapStartTimes[axisIndex] =
				(AInitialState.min(axisIndex) - BInitialState.max(axisIndex)) /
				RelativeDisplacementOfB[axisIndex];
        }

        if (BInitialState.max(axisIndex) > AInitialState.min(axisIndex) &&
			RelativeDisplacementOfB[axisIndex] < 0)
        {
            axisOverlapEndTimes[axisIndex] =
				(AInitialState.min(axisIndex) - BInitialState.max(axisIndex)) /
				RelativeDisplacementOfB[axisIndex];
        }
        else if (AInitialState.max(axisIndex) > BInitialState.min(axisIndex) &&
			RelativeDisplacementOfB[axisIndex] > 0)
        {
            axisOverlapEndTimes[axisIndex] =
				(AInitialState.max(axisIndex) - BInitialState.min(axisIndex)) /
				RelativeDisplacementOfB[axisIndex];
        }
    }

    // Possible first time of overlap.
    outNormalizedCollisionStartTime =
		MAX(axisOverlapStartTimes.x,
			MAX(axisOverlapStartTimes.y,
				axisOverlapStartTimes.z));

    // Possible last time of overlap.
    outNormalizedCollisionEndTime =
		MIN(axisOverlapEndTimes.x,
			MIN(axisOverlapEndTimes.y,
				axisOverlapEndTimes.z));

    // If the start time of overlap occurred before the end time of overlap,
    //  then there was a collision.
    return (outNormalizedCollisionStartTime <=
		outNormalizedCollisionEndTime);
}

In conclusion, better variable names mean easier code to write, read, and understand. Following good naming conventions can help with debugging, maintenance, and encourages reuse. If another engineer can figure out how to use your function within 30 seconds, and only by glancing at your declaration in a header file, it’ll make them 2000% more likely to actually use it. This is integral to the OOP concept of “Programming to Interfaces.” I whole-heartedly believe in literate programming and self-documenting code, which I think shows through my passionate hatred for the antithesis. Code should be so well written that it reads like a book, instruction manual, or recipe. Unnecessary code obfuscation is entirely asinine and costs more time and headaches in the long run. In fact, there are a few undocumented assumptions and bugs in the sample code I used that were completely obfuscated by the variable naming (more on this later). Please take what I’ve said into consideration. There’s really no reason why your variables need to suck.