# 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.

# An Introduction to Pre-Computed Visibility Tries

Robinson is a roguelike I am working on. It’s written in Clojure – a functional programming language. I want to describe how Clojure makes computing field of view simple, but first we need to brush up on tries.

## Tries

A trie is a data structure that describes a class of trees where each node is a set of (key, value) pairs mapping a key to a sub-tree. Tries are useful when the paths from the root to the leaves have a logical relationship. The most often use for a trie is to store strings. Each character in the string is a key and the characters that follow form a  sub-tree. Strings with common prefixes are stored efficiently and branch into different sub-trees when their suffixes differ. A trie usually stores full entries in its terminal nodes, but for our purposes this isn’t needed so the examples and code do not follow this practice. Instead, we will use an empty value to indicate terminal nodes.

Example trie with the words a, an, all, adverse, advice, aloud, allow, and allowed:

Error generating Graphviz image: Graphviz generation failed: Directory `/var/www/html/wp-content/tfo-graphviz` is either not writable, not a directory or not creatable

## Tries in Clojure

Clojure’s maps are sufficient for our purposes. They are an associative heterogeneous data structure with dynamic size. An empty map {} represents an empty trie.

Adding a sequence to a trie is simple. Let’s define `add-to-trie`.

```user=> (defn add-to-trie [trie sequence]
(assoc-in trie sequence {}))```

Let’s try it out. First we will add the sequence `[:a :b :c]`[:a :b :c], and `[:a :d :e]`.

```user=> (-> {}
{:a {:d {:e {}}, :b {:c {}}}}```

Empty sub-tries, like empty tries, are represented by the empty map `{}`.

### Walking Tries

We can use zippers to walk over tries, so let’s define a trie zipper. Given a trie, return a zipper for the trie.

```user=> (defn trie->zipper [trie]
(z/zipper ;; branch?
map?
;; children
vals
;; make node
#(zipmap (keys %1) %2)
;; root
trie))```

This zipper does not support modifying the trie, but it will allow navigating using `z/next` and `z/node`. We won’t be modifying our tries, so this definition is adequate for our purposes.

```user=> (def trie (-> {}
#'user/trie
user=> (-> (trie->zipper trie)
z/node)
{:a {:d {:e {}}, :b {:c {}}}}

user=> (-> (trie->zipper trie)
z/next
z/node)
{:d {:e {}}, :b {:c {}}}

user=> (-> (trie->zipper trie)
z/next
z/next
z/node)
{:e {}}
```

We need two more trie operations: culling sub-tries, and extracting the keys back out of a trie. Let’s modify the `trie->zipper` function to include a predicate: `exclude-subtrie?`. The predicate will be invoked for every key `k` in the trie in pre-order traversal. If `(exclude-subtrie? k)` returns true, then the sub-trie associated with `k` will be culled (ie: replaced with an empty trie `{}`).

```user=> (defn trie->zipper [exclude-subtrie? trie]
(z/zipper ; branch?
map?
; children
(fn [node]
(reduce-kv (fn [children k subtree]
(if (exclude-subtrie? k)
children
(conj children subtree)))
[]
node))
; make node
#(zipmap (keys %1) %2)
; root
trie))```

The function `trie-zipper->keys` walks a trie zipper and collects all of the keys in a set. This will be useful later when we store 2d points in the trie and want to collect the set of all of the points in the trie.

```user=> (defn trie-zipper->keys [trie-zipper]
(loop [t  trie-zipper
ks #{}]
(cond
(z/end? t) ks
(empty? (z/node t)) (recur (z/next t) ks)
(z/branch? t)
(let [new-keys (set (keys (z/node t)))]
(recur (z/next t) (clojure.set/union new-keys ks)))
:leaf
(log/info "got leaf" (z/node t)))))```

## Field of Vision

In roguelikes, the term “field of view” (FoV) refers to calculating the portion of the map that can be seen by the player. There are many field of view algorithms, each with pros and cons. The naive approach to FoV is to iterate over a set of potentially visible points. For each step in the iteration, a ray is cast from the player to the point being tested. If no points along the line block visibility, then the point being tested is visible. The naive approach is conceptually simple, but it is not efficient because it tests the points closer to the player many more times than needed. Pre-computed visibility tries (PCVT) is an efficient algorithm to calculate field of view that is idiomatic Clojure.

PCVT makes one assumption:

The points (xi, yi) on a path from the player at (x0, y0) to a point (xn, yn) form a sequence S such that each path s from (x0, y0) to (xi, yi) a prefix of S.

For example, the line from (0, 0) to (5, 5) is form the sequence ((0, 0) (1, 1) (2, 2) (3, 3) (4, 4) (5, 5)) S. Each of the paths

```((0, 0))
((0, 0) (1, 1))
((0, 0) (1, 1) (2, 2))
((0, 0) (1, 1) (2, 2) (3, 3) (4, 4))
((0, 0) (1, 1) (2, 2) (3, 3) (4, 4) (5, 5))```

is a prefix of S. Furthermore, this implies that if (2,2) blocks visibility that the points (3, 3), (4, 4) and (5, 5) are not visible and do not need to be checked. More formally, in the sequence S, if the element si blocks visibility, then the points sn such that i<n are not visible.

So how does this help with fov? We can enumerate all of the sequences starting from the player’s position at (x0, y0) to the points on a circle such that the circle is centered on (x0, y0) and has a radius of r. All of these sequences can be stored in a trie and if a node in the trie blocks visibility, the points in the sub-trie are not visible!

## Pre-computed Visibility Tries

The algorithm is divided into two parts: a pre-calculation step which builds the trie, and a processing step which finds the visible cells by culling the trie and collecting the remaining points. We will be storing (x, y) points in the trie instead of characters, but the code will work just the same.

## Pre-calculation

The pre-calcuation step can occur offline or once during program start-up. We need to establish visibility relationships for all of the points in a region.
It would be impossible to store all the visibility tries for each player location so only the trie centered at point (0, 0) is generated and lines of sight extending outward radially. We will have to transform between player-space coordinates and world-space coordinates later, but the cost is negligible.

### Algorithm

We need to generate the set of all lines starting with the player at (0,0) and extending outward. Each cell in the field of view must be covered by at least one of these lines or it will not be present in the set of visible cells. Naively generating a set of lines from (0,0) to the points on a circle with radius r does not yield full coverage.

Instead, the lines from (0,0) to the points on a square (with sides of length r/2) does yield full coverage. Every cell with a distance > r can be eliminated. Drawing out the trie looks like this. It is hard to trace individual paths, but imagine lines radiating outward from the center following as straight a path as possible given the constraint of the grid.

### The Code

We’ll want to vary our view distance so let’s generate 30 visibility tries. One for each view distance from 1 to 30.

The function `paths->trie` forms a trie from a collection of sequences.

```(defn paths->trie [segments]
(reduce (fn [tree segment]
(assoc-in tree segment {}))
{}
segments))
```

Let’s define the visibility tries as a map from radius to a visibility trie encompassing that radius. I’ll leave `square-points`, `line-segment`, and `remove-points-beyond-radius` implementations up to the reader’s imagination, or you can view the definitions in the source in a link at the end of this post.

```(def r->trie
(apply hash-map (mapcat (fn [k]
(let [perimeter-points (square-points 0 0 k)
segments         (remove empty?
(map (fn [[x y]] (line-segment [0 0] [x y]))
perimeter-points))
segments (remove-points-beyond-radius 0 0 k segments)
num-segments (count segments)
trie         (paths->trie segments)]
[k trie]))
(range 30))))
```

Now the visibility trie contains all of the chains of points radiating outward from the center at (0,0) and ending at distance r.

## Finding Visible Cells

To find the coordinates of visible cells, we just need to put these pieces together.

```(defn visible-xys [r visible?]
(->> (get r->trie r)
(trie->zipper (complement visible?))
(trie-zipper->keys))
```

Strobing over the individual paths that make up the culled visibility trie looks like this.

## Conclusion

PCVT’s speed is inversely proportional to the number of visible cells. The more cells that block line of sight (especially near to the player) the faster the algorithm performs.

PCVT behaves most like precise permissive fov (3), though obviously it is not exactly the same.

Rogue Basin has an interesting comparison of FoV algorithms. The symmetry section is a little vague, and I’m not confident that I can reproduce identical test conditions. I analyzed outdoor symmetry by randomly assigning each cell a blocking or non-blocking attribute at the rate of 10%. Furthermore, I limited view distance in each of the tests. I assume that view distance was only limited by the bounds of the grid in the tests, but PCVT’s finite view distance is built in to the algorithm (through it can vary and be adjusted). By averaging 100 iterations, I arrived at these results:

```Distance:  Error:
20         12.91%
15          8.79%
10          8.08%
5          3.63%
```

Symmetry error is an interesting topic in its own right. A fast asymmetric algorithm can have benefits over a slow symmetric one.

## Source

The source for the demo application is available here.

## Appendix

### Getting Paths Back Out

The two functions `trie->zipper`, and `trie-zipper->keys` work well enough for calculating visibility, but they are not sufficient for extracting visibility paths from the trie zipper. This shortcoming arises from the zipper not making the key ↦ sub-trie mapping available at the node level. For this, we need to make each node a 2-tuple of (key, sub-trie). Note that the first node in the zipper will be the original map, so `z/next` will have to be called to get the first 2-tuple node in the zipper.

```(defn trie->zipper-ext [exclude-subtrie? trie]
(z/zipper
; branch?
(fn [x] (or (map? x) (map? (second x))))
; children
(fn [x] (seq
(reduce (fn [children [k subtree]]
(if (exclude-subtrie? k)
(conj children [k {}])
(conj children [k subtree])))
[]
(if (map? x)
(map vec x)
(second x)))))
; make node
(fn [x children]
(if (map? x)
(into {} children)
(assoc x 1 (into {} children))))
trie))
```

We then have the ability to define `trie-zipper-ext->paths` in this way.

```(defn trie-zipper-ext->paths [trie-zipper]
(loop [t     (z/next trie-zipper)
paths #{}]
(cond
(z/end? t)
paths
(empty? (z/node t))
(recur (z/next t) paths)
(z/branch? t)
(if (empty? (second (z/node t)))
(let [path (->> t z/path rest (map first))]
(recur (z/next t) (conj paths (conj (vec path) (first (z/node t))))))
(recur (z/next t) paths))
:leaf
(println "got leaf" (z/node t)))))
```