programming in the
twenty-first century

It's not about technology for its own sake. It's about being able to implement your ideas.

Don't Be Afraid of Special Cases

In the body of work on low-level optimization, there's a heavy emphasis on avoiding branches. Here's a well-known snippet of x86 code which sets eax to the smaller of the two values in eax and ecx:

sub ecx, eax
sbb edx, edx
and ecx, edx
add eax, ecx

At the CPU hardware level, branches are indeed expensive and messy. A mispredicted branch empties the entire instruction pipeline, and it can take a dozen or more cycles to get that pipeline full and ticking along optimally again.

But that's only at the lowest level, and unless you're writing a code generator or a routine that's hyper-sensitive to instruction-level tweaks, like movie compression or software texture mapping, it's doubtful that going out of your way to avoid branches will be significant. Ignoring efficiency completely, there's still the stigma that code with many conditionals in it, to handle special cases, is inherently ugly, even poorly engineered.

That's the programmer's code-centric view. The user of an application isn't thinking like that at all. He or she is thinking purely about ease of use, and ugly is when a program displays "1 files deleted" (or even "1 file(s) deleted"), or puts up a dialog box that crosses between two monitors, making it unreadable.

In 1996-7 I wrote a game called "Bumbler" for the Mac. (Yes, I've brought this up before, but that's because I spent 18 months as a full-time indie game developer, which was more valuable--and probably just as expensive--as getting another college degree.) Bumbler is an insect-themed shooter that takes place on a honeycomb background. When an insect is killed, the honeycomb behind it fills with honey. Every Nth honeycomb fills with pulsing red "special honey," which you can fly over and something special happens. Think "power-ups."

The logic driving event selection isn't just a simple random choice between the seven available special honey effects. I could have done that, sure, but it would have been a lazy decision on my part, one that would have hurt the game in noticeable ways. Here are some of the special honey events and the special cases involved:

Create hole. This added a hole to the honeycomb that insects could crawl out of, the only negative special honey event. During play testing I found out that if a hole was created near the player start position, the player would often collide with an insect crawling out of it at the start of a life. So "create hole" was disallowed in a rectangular region surrounding the player start. It was also not allowed if there were already a certain number of holes in the honeycomb, to avoid too much unpredictability.

Release flowers. This spawned bonus flowers from each of the holes in the honeycomb. But if there were already many flowers on the screen, then the player could miss this entirely, and it looked like nothing happened. If there were more than X flowers on the screen, this event was removed from the list of possibilities.

Flower magnet. This caused all the flowers on the screen to flash yellow and home on in the player. This was good, because you got more points, but bad because the flowers blocked your shots. To make this a rare event, one that the player would be surprised by, it was special-cased to not occur during the first ten or so levels, plus once it happened it couldn't be triggered again for another five levels. Okay, that's two special cases. Additionally, if there weren't any flowers on the screen, then it looked like nothing happened, and if there were only a few flowers, it was underwhelming. So this event was only allowed if there were a lot of flowers in existence.

All of these cases improved the game, and play testing supported them. Did they make the code longer and arguably uglier? Yes. Much more so because I wasn't using a language that encourages adding special cases in an unobtrusive way. One of the advantages to a language with pattern matching, like Erlang or Haskell or ML, is that there's a programing assistant of sorts, one that takes your haphazard lists of special cases--patterns--and turns then into an optimal sequence of old-fashioned conditionals, a jump table, or even a hash table.

permalink May 25, 2008


twitter / mail

I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.

Where are the comments?