Purely Functional Retrogames, Part 1

When I started looking into functional languages in 1998, I had just come off a series of projects writing video games for underpowered hardware: Super Nintendo, SEGA Saturn, early PowerPC-based Macintoshes without any graphics acceleration. My benchmark for usefulness was "Can a programming language be used to write complex, performance intensive video games?"

After working through basic tutorials, and coming to grips with the lack of destructive updates, I started thinking about how to write trivial games, like Pac-Man or Defender, in a purely functional manner. Then I realized that it wasn't performance that was the issue, it was much more fundamental.

I had no idea how to structure the most trivial of games without using destructive updates.

Pac-Man is dead simple in any language that fits the same general model as C. There are a bunch of globals representing the position of Pac-Man, the score, the level, and so on. Ghost information is stored in a short array of structures. Then there's an array representing the maze, where each element is either a piece of the maze or a dot. If Pac-Man eats a dot, the maze array is updated. If Pac-Man hits a blue ghost, that ghost's structure is updated to reflect a new state. There were dozens and dozens of Pac-Man clones in the early 1980s, including tiny versions that you could type in from a magazine.

In a purely functional language, none of this works. If Pac-Man eats a dot, the maze can't be directly updated. If Pac-Man hits a blue ghost, there's no way to directly change the state of the ghost. How could this possibly work?

That was a long time ago, and I've spent enough time with functional languages to have figured out how to implement non-trivial, interactive applications like video games. My plan is to cover this information in a short series of entries. I'm sticking with 8-bit retrogames because they're simple and everyone knows what Pac-Man looks like. I don't want to use abstract examples involving hypothetical game designs. I'm also sticking with purely functional programming language features, because that's the challenge. I know that ML has references and that processes in Erlang can be used to mimic objects, but if you go down that road you might as well be using C.

The one exception to "purely functional" is that I don't care about trying to make I/O fit a functional model. In a game, there are three I/O needs: input from the user, a way to render graphics on the screen, and a real-time clock. Fortunately, these only matter at the very highest level outer loop, one that looks like:

repeat forever {
   get user input
   process one frame
   draw everything on the screen
   wait until a frame's worth of time has elapsed
}

"Process one frame" is the interesting part. It takes the current game state and user input as parameters and returns a new game state. Then that game state can be used for the "draw everything" step. "Draw everything" can also be purely functional, returning an abstract list of sprites and coordinates, a list that can be passed directly to a lower level, and inherently impure, function that talks to the graphics hardware.

An open question is "Is being purely functional, even excepting I/O, worthwhile?" Or is it, as was suggested to me via email earlier this year, the equivalent of writing a novel without using the letter 'e'?

Part 2

permalink April 12, 2008

Purely Functional Retrogames, Part 1

previously

archives