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:
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=> (-> {}
           (add-to-trie [:a :b :c])
           (add-to-trie [:a :d :e]))
{: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 (-> {}
                     (add-to-trie [:a :b :c])
                     (add-to-trie [:a :d :e])))
#'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 {}}

Culling and Reading Tries

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.

Screenshot from 2015-06-05 23:11:58

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))
                               ;; truncate segments to radius
                               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))

Let’s throw in some random blocking cells.
Screenshot from 2015-06-05 23:38:10

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.

You can also download the jar 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)))))