Purely Functional Retrogames, Part 4

(Read Part 1 if you missed it.)

By the definition of functional programming, functions can't access any data that isn't passed in. That means you need to think about what data is needed for a particular function, and "thread" that data through your program so a function can access it. It sounds horrible when written down, but it's easy in practice.

In fact, just working out the data dependencies in a simple game is an eye-opening exercise. It usually turns out that there are far fewer dependencies than you might imagine. In Pac-Man, there's an awful lot of state that makes no difference to how the ghosts move: the player's score, whether the fruit is visible or not, the location of dots in the maze. Similarly, the core movement of Pac-Man, ignoring collision detection, only relies on a handful of factors: the joystick position, the location of walls in the maze (which are constant, because there's only one maze), and the current movement speed (which increases as mazes are completed).

That was the easy part. The tricky bit is how to handle functions that affect the state of the world. Now of course a function doesn't actually change anything, but somehow those effects on the world need to be passed back out so the rest of the game knows about them. The "move Pac-Man" routine returns the new state of Pac-Man (see Part 3 for more about how entity state is represented). If collision detection is part of the "move Pac-Man" function, then there are more possible changes to the world: a dot has been eaten, a power pill has been eaten, fruit has been eaten, Pac-Man is dead (because of collision with a non-blue ghost), a ghost is dead (because of a collision with a powered-up Pac-Man).

When I first mused over writing a game in a purely functional style, this had me stymied. One simple function ends up possibly changing the entire state of the world? Should that function take the whole world as input and return a brand new world as output? Why even use functional programming, then?

A clean alternative is not to return new versions of anything, but to simply return statements about what happened. Using the above example, the movement routine would return a list of any of these side effects:

{new_position, Coordinates}
{ate_ghost, GhostName}
{ate_dot, Coordinates}
ate_fruit
killed_by_ghost

All of a sudden things are a lot simpler. You can pass in the relevant parts of the state of the world, and get back a simple list detailing what happened. Actually handling what happened is a separate step, one that can be done later on in the frame. The advantage here is that changes to core world data don't have to be painstakingly threaded in and out of all functions in the game.

I'd like to write some concluding thoughts on this series, to answer the "Why do this?" and "What about Functional Reactive Programming?" questions--among others--but wow I've already taken just about a month for these four short entries, so I'm not going to jump into that just yet.

(I eventually wrote the follow-up.)

permalink May 11, 2008

Purely Functional Retrogames, Part 4

previously

archives