Elegant Flow for the Suave Roguelike

You’ve been plugging away at your roguelike, adding bits here and there. As you give the player more options the switch statement that controls movement got nested in an if statement. Wait! Now you need to nest another switch statement in a case statement. Sheesh! Another if/else! It’s too much. It’s too complicated!

I want to let you know there is a better way. You don’t have to code like this. There is a solution and it’s called a finite state machine.

The Concept

Finite state machines solve the problem of deciding what the player can do given the current state of the game. A single state machine can replace a huge, deeply nested set of switch and if/else statements with a table of easy to edit values.

A Definition

There are a few ways to define a finite state machine, we’ll be using a one dimensional state transition table. A state transition table is just a list of entries. Each entry has four values: the current state, input, action, and next state. The state state transition table reads like a truth table — find the current state and user input, then perform the action and change the state to the next state.

We’ll also have to initialize the machine with a starting state. The finite state machine will keep advancing with each input and when it reaches a state (or states) deemed to be final states, the machine will stop.

Give Me The Code

Let’s define a game state object. The game state will hold the current state accessible by the key :current-state. We’re leaving everything else out of the game state object. Normally it would hold the world, player, npcs, and items. However we can leave them out for the purpose of this example.

user=> (def initial-gamestate {:current-state :a})
#'user/initial-gamestate

The State Transition Table

Let’s define a simple state transition table with two states: a, and b. If the input value is 0 then maintain the same state, and if the input is 1 switch to the other state (a->b, or b->a). We will also print out the current state and input during each transition.

(def state-transition-table
  {:a {0 [(partial println "a 0") :a]
       1 [(partial println "a 1") :b]}
   :b {0 [(partial println "b 0") :b]
       1 [(partial println "b 1") :a]}})

Update-State

We just need a function which accepts a game state and an input value and returns a new game state.

(defn update-state [gamestate input]
  (let [current-state              
          (get gamestate :current-state)
        [transition-fn next-state] 
          (get-in state-transition-table 
                  [current-state input])
        next-game-state            
          (assoc (transition-fn gamestate input) 
                 :current-state 
                  next-state)]
    next-game-state))

Easy! It gets the current state from the game state. Then it looks up the transition function and next-state in the transition table and then passes the gamestate and input through the transition function. Finally it associates the new state in the new game state and returns the updated game state.

Here’s how the example looks in practice. First we accept 0 as input. Remember that 0 maintains the current state. You’ll see that the transition function is invoked, printing out "a 0" and then the game state and input.

user=> (update-state initial-gamestate 0)
a 0 {:current-state :a} 0
{:current-state :a}

Accepting 1 transitions the state to :b.

user=> (update-state initial-gamestate 1)
a 1 {:current-state :a} 1
{:current-state :b}

Let’s accept several input values sequentially by applying update-state to gamestate in succession.

user=> (reduce update-state initial-gamestate [0 1 1 0 1])
a 0 {:current-state :a} 0
a 1 {:current-state :a} 1
b 1 {:current-state :b} 1
a 0 {:current-state :a} 0
a 1 {:current-state :a} 1
{:current-state :b}

A More Elegant Machine

One more thing that is useful is providing a default transition function for a state. Our input alphabet is potentially quite large (the alphabet upper and lower case plus numbers and possibly punctuation) so enumerating all possibilities for each input value will make the transition table impossibly large. Let’s define a function to apply as an “else” case. We’ll need to update the transition table first.

(def state-transition-table
  {:a {0     [(partial println "a 0") :a]
       1     [(partial println "a 1") :b]
       :else [(partial println "a else") :a]}
   :b {0     [(partial println "b 0") :b]
       1     [(partial println "b 1") :a]
       :else [(partial println "b else") :b]}})

The update-state function now looks like this.

(defn update-state [gamestate input]
  (let [current-state
          (get gamestate :current-state)
        [transition-fn next-state]
          (get-in state-transition-table
                  [current-state input]
                  (get-in state-transition-table
                          [current-state :else]))
        next-game-state
          (assoc (transition-fn gamestate input)
                 :current-state
                 next-state)]
    next-game-state))

We can just use get-in‘s default value to include a lookup for :else and use that. Yay!

Using the same example before, but passing through additional input values and types the output looks like this.

user=> (reduce update-state initial-gamestate [0 1 1 0 1 :a :nil 4 \a []])
a 0 {:current-state :a} 0
a 1 {:current-state :a} 1
b 1 {:current-state :b} 1
a 0 {:current-state :a} 0
a 1 {:current-state :a} 1
b else {:current-state :b} :a
b else {:current-state :b} :nil
b else {:current-state :b} 4
b else {:current-state :b} a
b else {:current-state :b} []
{:current-state :b}

Conclusion

The trick here is to map out all of the game’s states and consider the effects of transitioning from one to the other. The tangled mess of conditional expressions transforms into thinking more about what states exist within the game and how moving from one to another affects the game state.

The code for Robinson’s finite state machine looks like this. As you can see it is quite long, but each individual entry in the table is easy to reason about and change. And it’s so much better than a huge nested if/cond/case expression.

You’ll notice some additional features in Robinson’s state machine.

1. It’s useful for some transition functions to decide what the next state will be rather than encoding it in the transition table. An example is quaffing. Robinson allows the player to quaff items from inventory or from adjacent water cells. Pressing \q passes the game state through a quaff-select transition function which changes the game state to :quaff-inv-or-adj, :quaff-adj, :quaff-inv, or does nothing depending on the availability of quaffable items or cells. To support this the state transition table will accept either keywords or functions as values for the next state. In the case of keywords, update-state uses the keyword as the next state, and in the case of a function it passes the current state through the new-state fn and uses the result as the next state. The identity function is used to indicate that the transition function changes the state and just use that value instead.

2. Sometimes the game should advance time and update npcs, items, heal the player, increase hunger, update visibility, etc while other times, like when accessing inventory it should not. While one could make a call to an advance-time function in each transition function, it’s easier to mark each entry in the transition table with a flag indicating if time should be advanced. If the flag is true, then the game state can be passed through the advance-time function before being returned from update-state.

Go out there and clean up your update functions. You’ll be able to spend the leftover brainpower on things that really matter, like making your game.