Robinson – 2015.08.06

Robinson is an open world survival roguelike. It focuses on exploration and crafting and doesn’t take itself too seriously. Fight creatures, build your camp, and survive, but most importantly – get off the damn island!

gameplay gif

You can track development on GitHub.

Try the pre-release version.

Robinson-2015.08.06-21.46.20-bfb9cee.zip

(27.5MB)

Updates

Adjusted harvestable cell generation.
Added splash screen.
Changed Windows font and character use to be more accessible.
Updated crafting screen to indicate which items the player does not have for a recipe.
World topography is more “noisy”.
Added “large flint stone” drops.
Added sand dune and rocky shore cell types.
Player is slowed on surf and sand dunes.
Added diagonal harvesting.
Added “days survived” to game over screen.
Adjusted monster spawning probabilities.
Added monster health description to “look” mode menu.
Added flint axe blade recipe and adjusted flint axe recipe to require it.
Added blood splatters.

Fixes

Fixed font width issue on Windows.
Fixed game over typo.
Faster world generation.

The Poor Man’s Debugging Toolkit: Source Reloading

A little more than three years ago I watched Notch live coding a game called 0x10c. What fascinated me was his use of hot-swapping code while the game was running. It closed the feedback loop of game development and left a lasting impact on me. When the development feedback loop is less than one second amazing things start to happen.

The Effects of Reloading Code

When a developer gets feedback in real time s/he can narrow down the problem space by doing instead of thinking. Don’t get me wrong; thinking is great. The hardest problems have been solved by thinking. But thinking is slower than doing, and when we’re doing something we tend not to think of there being a problem at all.

Constants

Manipulating constant values is one of the first things that becomes noticeably easier. If I want to change the color of a game object, my workflow is almost the same, but orders of magnitude faster.

The old workflow:
1. Edit the value.
2. Save the file.
3. Compile/Start the game and wait some time for it to finish. (slow!)
4. View the results.

Becomes this:
1. Edit the value.
2. Save the file.
3. View the results.

Step three in the old workflow is by far the slowest step. A compile and restart of the game, even if it takes 20 seconds, is at least ten times slower than the other steps combined. Having both the editor and game visible allows the developer to edit and save while viewing the results without having to switch windows. Have two monitors? Even better!

Behavior

Adding and changing game logic both become easier in a tight feedback loop. Designing menus, new character actions, and crafting recipes are all things I’ve finished faster because of a fast feedback loop. When creating menus, sizing panes, placing text, and wiring up keyboard controls are all faster when I can immediately interact with the changes. Adding a character action is a matter of manipulating the game state transition table and adding a method to accept the old game state and spit out a new game state with the right changes. Finally, creating crafting recipes is just a matter of adding a new recipe to the recipe list while having the crafting menu open and viewing the output as I save the source files.

You might be asking, “What about the repl? This is what the repl is for! Use the repl.” The repl is fine. I like testing out code in the repl, but the repl does not automatically reload code when a source file is changed. Sure, I could use (use '... :reload) to reload individual namespaces, but the fact that I have to do it by hand lengthens the feedback loop too much. I usually have a repl open for testing out snippets. But that’s it.

Setup

From a high level, we need a few parts. The first part is to track when source files have been changed. The second part is to perform an action when a change is detected. The last part is to add a level of indirection so that the game loop can refer to the new function definitions when the code is reloaded.

Let’s start with tracking namespace changes. start-nstracker will look for changes in the paths src, and target/generated-src/cljbecause we’re using cljx to target both Clojure and ClojureScript. The function ns-tracker, returns a function we bind to the variable track. When track is called it returns a list of changed namespaces. We just call check-namespace-changes in an infinite loop in a background thread.

(defn start-nstracker []
 (let [track (ns-tracker ["src" "target/generated-src/clj"])]
   (doto
     (Thread.
       #(while true
         (check-namespace-changes track)))
     (.setDaemon true)
     (.start))))

Our function check-namespace-changes invokes track and for each changed namespace, we reload it. We’ll also sleep a little so that the background thread doesn’t hog resources.

(defn check-namespace-changes [track]
 (try
   (doseq [ns-sym (track)]
     (log/info "Reloading namespace:" ns-sym)
     (require ns-sym :reload)
     (log/info "Done."))
   (catch Throwable e (log/error e)))
   (Thread/sleep 500))

The game loop looks like this.

(defn -main []
  (let [default-setup-fn (constantly {})
        default-tick-fn  (fn [state] (log/info "default tick fn") (Thread/sleep 5000) state)
        get-setup-fn     (fn [] (if-let [f (resolve 'robinson.main/setup)] f default-setup-fn))
        get-tick-fn      (fn [] (if-let [f (resolve 'robinson.main/tick)] f default-tick-fn))]
    (start-nstracker)
    ; loop when setup-fn changes
    (loop [setup-fn     (get-setup-fn)
           setup-fn-var (var-get setup-fn)]
      ; start with initial state from setup-fn
      (setup-fn
        (fn [state]
          (go-loop [state state]
            ; start with initial state from setup-fn
            ; setup function changed? restart with new setup
             (when (identical? (var-get (get-setup-fn)) setup-fn-var)
              (if (nil? state)
                ;; nil state, exit
                (do
                  (log/info "Got nil state. Exiting.")
                  (async/>! done-chan true)
                  (System/exit 0))
                ; tick the last state through the tick-fn to get the new state
                (let [new-state (try
                                  (let [keyin (if (= (rw/current-state state) :sleep)
                                                  \.
                                                (let [key-chan (aterminal/get-key-chan (state :screen))]
                                                  (log/info  "waiting for key-chan")
                                                  (async/<! key-chan)))]
                                     (if keyin
                                       ((get-tick-fn) state keyin)
                                       state))
                                  (catch Throwable e
                                    (log/error e)
                                    state))]
                    (recur new-state)))))))
      ; setup function changed, restart with new setup
      (let [setup-fn  (get-setup-fn)
            setup-var (var-get setup-fn)]
        (log/info "(Re)starting loop with new setup-fn")
        (recur setup-fn setup-var)))
        (async/<!! done-chan)
        (log/info "Core exiting")))

Before the game loop starts, we need to we need to define a few functions to resolve our setup, and tick functions. The outer loop iterates when the setup function changes and the game restarts with a new initial state. We’ll call (start-nstracker) and (setup-fn) to start tracking namespace changes and to generate the initial game state before entering the game loop.

The setup-fn function takes a callback that accepts the initial game state. The inner go-loop is the game loop. The tick function takes a game state and keyboard input and returns a new game state. Inside the game loop, we can call ((get-tick-fn) state keyin) to pass the game state through the tick function to get a new game state.

When the source changes in the background, the game loop won’t miss a beat, the new definitions will be available for use immediately so the developer can see the changes taking effect.

Caveats

There are a few cases that aren’t covered by this framework.

If a function that is called by the setup function the change will be detected, but it won’t trigger a reinitialization of the game state. I have to trigger an in-game death and start a new game. I have a hotkey that does this, so it doesn’t require an application restart, but it isn’t automatic.

When the changes make presumptions about the layout of data in the game state, the game state has to be reinitialized. Again this doesn’t require an application restart, but the developer may have to recreate a particular game state again. This comes down to what is essentially a versioning and migration issue. If the original code depends on the player record having a field named :hp and the code is changed to use :health-points, the game state will not be converted to use the new convention.

Technically, it’s possible to add a bit of migration code that performs the conversion on the next tick, but it’s rarely worth it in practice so it is easier to just reinitialize the game state with the new code.

Take Away

It’s interesting to program in what amounts to a live coding session. The great part about tracking files and automatically reloading them is that the code on disk matches what’s being executed. If the game crashes or the computer freezes, short of drive failure, no work is lost. I will usually give the feature a final test outside the auto-reloading environment, and then it’s just a matter of committing the changes. It really is that easy.

The Poor Man’s Debugging Toolkit: Using Clojure.inspector

When debugging a problem in Robinson, I will often print out values to the log. I can try to see the values of variables at certain points during execution. Often, these values will be some subset of the game state.

I’d like print the whole game state to the log, but it’s too much data to process visually. So I find myself printing small parts of the game state trying to hone in on the right part to show the problem. It takes far too long and it’s frustrating. I have to guess and check until I find the right data.

Enter Clojure.inspector

I stumbled on Adam Bard’s Clojure.core: Batteries (almost) included writeup on useful Clojure libraries. There is a small reference to clojure.inspector in the forward that caught my eye.

Clojure.inspector is a very small namespace of just three documented functions: inspect, inspect-table, and inspect-tree. The functions all display a GUI showing data — inspect is for viewing objects, inspect-table for viewing sequences, and inspect-tree for hierarchical data.

Wait, the game state is hierarchical data!

This is perfect.

Solution

Given the right tool, all problems are trivial. Let’s add inspector as a required namespace to Robinson’s update namesapce so that we can trigger inspection when a key is press.

(ns robinson.update
  (:require 
    ...
    clojure.inspector
    ...

And then we can wire up the keyboard so that when 5 is pressed we can inspect the game state. This snippet lies in the middle of a state machine definition mentioned in this post.

...
\5 [(fn [state]
      (clojure.inspector/inspect-tree (get state :world))
    :normal
    false]
...

That’s it. It was almost too easy.

The inspector window looks like this and it’s so useful. I’ve already caught at least one bug just by examining values.
Screenshot of inspector

Use it!

Since game states are passed to almost every logic related function in Robinson, I’ll have many opportunities to apply inspect-tree during future debugging sessions and in the meantime, I can always press 5 to peek under the hood.

If you find yourself trying to cherry-pick values to print to the log, try using clojure.inspector. It’s a big bang for your coding buck.

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:
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)))))