Post-Mortem of a Job Application

I applied for a job recently, and was asked to write a small clone of Arkanoid (aka Breakout) using C++/DirectX. My C++ was rusty and the last DirectX stuff I did was five years ago and in VB6, but I figured I might as well try. At least it would refresh my C++ and force me to learn some DirectX. Unfortunately, I never managed to finish the game (on time). My lack of familiarity caused difficulties but, looking back, I can see that familiarity was not the issue. Learning sucked up some time, but the real time sink came about because of a design decision made only three hours into the project: I decided to write a Rational class instead of using floating point values.

Since this was a job application, I didn't want to do the bare minimum. I came up with the idea to record 'ghosts', so you could race against yourself. If I had the time, I could even feed the ghost data in live from another game for some relatively simple networked multiplayer. Thinking about how I would implement this, I remembered that floating points are not reliable in terms of consistency. Small optimizations made by the compiler, and differences across machines, can make the results of even simple additions come out slightly differently. That could be a problem, so I decided to write a Rational class and use it instead of floating points. That way I could guarantee consistency across machines.

At the beginning, I was reaping benefits. The rationals weren't as fast as floats, since constructing one involved computing a gcd, but the game wasn't even close to taxing the CPU. They even made the physics nice and exact, because all the 2d vector operations I used are closed over the rationals (No rounding errors. At all!). For example, this code computes the *exact* intersection point and normal of a moving point into a line segment:

 
//[example note: Vector2 is an x/y pair  of Rationals. CollisionPoint is a location/normal pair which can be  empty for no collision]
CollisionPoint CollisionPoint :: PointIntoLine(const Vector2 p, const  Vector2 dp,
                                                const Vector2 q1, const  Vector2 q2) {
     assert(dp != Vector2(0, 0));
    assert(q1 != q2);
 
    //Useful  intermediate values
    Vector2 p1 = p;
    Vector2 p2 = p + dp;
    Vector2 dq = q2 - q1;
    Rational f1 = q1.Cross(q2);
    Rational f2 = p1.Cross(p2);
 
    //Intersection  point (of lines extended to infinity)
    Rational d = dp.Cross(dq);
    if (d  == 0) return CollisionPoint(); //no collision due to parallel lines
    Rational cx = (f1*dp.X() -  f2*dq.X())/d;
     Rational cy = (f1*dp.Y() - f2*dq.Y())/d;
    Vector2 intersectionPoint =  Vector2(cx, cy);
 
    //Confirm that the intersection  point is within the segments
    if  (Median(p1.X(), cx, p2.X()) != cx || 
        Median(p1.Y(), cy, p2.Y()) != cy  ||
         Median(q1.X(), cx, q2.X()) != cx ||
        Median(q1.Y(), cy, q2.Y()) != cy)  return CollisionPoint(); //missed
 
    //return the  point of impact and the normal of the line the at point of impact
    return  CollisionPoint(intersectionPoint, - dp.PerpOnto(q2 - q1));
}
 

The happy times continued until I hit an assert: "denominator < 0". I had decided that a rational's negative sign must always be on the numerator, and put an assert in the constructor to enforce this. Upon first seeing the error, I thought I had made some stupid error in one of the operator functions. Unfortunately, what had happened was far more insidious: integer overflow.

The thing to understand about rationals is that performing operations on them tends to make them 'share' their factors. If you add a/b and c/d, you get (ad + bc)/(bd), which almost always has a larger denominator and numerator even after removing the gcd. In the worst case each addition will square the numerator and denominator, and you only have to square five times to go from 2 to 2^32 and cause an overflow. Well guess what: a physics function involves way more than five additions, not to mention other operations.

I tried to smooth over the problem by rounding, but the problem kept happening. I rounded more aggressively, but it kept happening. Eventually I had rounding statements on practically every other line outside of the physics functions, but it still kept happening. Even my goat sacrifice to Apollo didn't work (maybe he doesn't like goats?). You could pick a physics function at random, give it touchy input, and cause an assertion. To make matters worse, all this tinkering and rounding kept introducing small bugs. Eventually I ran way over on time, and gave up.

If I had gone with the tried-and-true floating points, I would have finished with a potentially-maybe-slightly-out-of-sync ghost, instead of not finishing at all. The lesson I'm taking from all of this is that I shouldn't be experimenting with ideas when I'm on the clock, unless it's necessary. Sometimes they work, but when they don't the cost is too high. Perhaps, now that there's no time limit, I'll rewrite the rationals to use BigIntegers in order to guarantee there are no overflows. That could be an interesting side project.