Purely functional game programming with State Machines

I read with great interest the articles by James Hague about purely functional (retro)game programming. For a guy with a OOP background like myself, the idea of writing games with “no state” comes out as absurdly fascinating, hence deserving further attention. So, in addition to the ideas presented there, here’s another tool of the trade: state machines.

Defining state machines’ states as static collections of {trigger, action, newstate} tuples, we can rethink the “Pac Man problem” as:

[{
    start_state,
    {
        {start_trigger, do_init, normal_play_state}
    }
 },
 {
    normal_play_state,
    {
        {ate_dot_trigger, calc_score, normal_play_state},
        {ate_powerpill_trigger, promote, can_eat_ghosts_state},
        {touched_ghost_trigger, die, killed_state},
        ...
    }
 },
 ...
]

We can have a separate process that receives state changing messages, and depending on the message it processes a corresponding action, such as promote(), calc_score(), etc. Supposing we use Erlang, we could exploit its messaging feature (which strictly speaking I suppose it’s not a purely functional concept yet it feels “clean” — certainly more than doing imperative programming in Common Lisp), and write something like:

compute(start_state) ->
    receive
        start_trigger ->
            do_init(),
            NewState = normal_play_state;
        _ ->
            NewState = start_state
    end,
    compute(NewState);

compute(normal_play_state) ->
    receive
        ate_dot_trigger ->
            calc_score(),
            NewState = normal_play_state;
        ate_powerpill_trigger ->
            promote(),
            NewState = can_eat_ghosts_state;
        touched_ghost_trigger ->
            die(),
            NewState = killed_state;
        ...
        ...
        _ ->
            NewState = normal_play_state
    end,
    compute(NewState);
...

Then, inside our game loop, if at the current frame we found that Pac Man ate a powerpill, a `ate_powerpill_trigger’ is sent to the state machine, making it transition to a new state:

...
ComputePID ! ate_powerpill_trigger
...

So instead of having a class with a PacMan::atePowerPill flag, we “moved” that state info into the state machine definition.  The actual “state” is maintained on the stack, effectively overwritten via tail recursion.

A state machine of this sort will have a (very) long list of states, and for each state it will need to handle many different kinds of game events. In fact, theoretically speaking, we could have a single giant state machine that will recompute large portions of the game state at each transition. Alternatively, one could divide et impera, therefore having multiple state machines (one for each actor?) talking to each other.

This is pretty awkward to the OOP mindset. I can’t deny that representing it in terms of (e.g.) a pac-man object and a few ghosts objects seems straightforward. State is king, partly because we’re so used to reason in certain terms. But I can also imagine thinking in terms of “flow” instead of state, so to speak. In other words, a class can easily describe the current state in all its details, but not explicitly how it got to that state. A state machine can better describe the history across time, yet less directly describes the details.

technorati: 9GVT9D9CNX98