crn.io   codes and curiosities

To write this in Clojure, I first needed to get a list of cells that I might be erasing. I don’t currently have a good way to count how many exits a cell has, so I wrote a function called open-count.

(defn open-count [square]
  (reduce +
          (map
           #(if (dir-open? square %) 1 0)
           [north east south west])))

This isn’t my favorite code I’ve written. Still, it works. I iterate through the directions, using the dir-open? function I wrote previously to tally up how many exits I have.

Erasing a cell by removing all exits from it ended up being way harder than I’d imagined. Removing all exits from the cell wasn’t hard: that just meant resetting the cell to the base value of 0. Because corridors are two-way, though, I had to follow the one exit the cell had to the next cell and then remove that corridor from that next cell.

First, I had to find the coordinates of the next cell.

(defn coords-at-direction
  "Given a set of coordinates and a direction, 
   return a set of coordinates one space in that direction."
  [coords direction]
  (condp = direction
    north (map + coords [-1 0])
    south (map + coords [1 0])
    west (map + coords [0 -1])
    east (map + coords [0 1])
    coords))

This is at least the third time I’ve written a condp either converting a direction into an instruction or converting sets of coordinates into a direction. There has got to be a way to abstract this. I’m going to tackle refactoring this mess in a later post. Also, I’m not checking for illegal coordinates here.

Once I got the coordinates of the next cell, then I had to update it.

(defn trim-maze [maze size]
  (let [locations
        (filter #(= 1 (open-count (get-in maze %)))
                (for [x (range 0 size) y (range 0 size)] [x y]))
        alter-maze (fn [maze coords square]
                     (assoc-in maze coords square))]
    (loop [locations locations
           maze maze]
      (if (empty? locations)
        maze
        (let [coords (first locations)
              square (get-in maze coords)
              directions (cond
                          (north-open? square) [north south]
                          (south-open? square) [south north]
                          (west-open? square) [west east]
                          (east-open? square) [east west])
              direction (first directions)
              other-direction (nth directions 1)
              new-coords (coords-at-direction coords direction)            
              new-coords-square (get-in maze new-coords)
              maze (alter-maze maze coords 0)]
          (recur (rest locations)
                 (alter-maze
                  maze
                  new-coords
                  (bit-xor other-direction new-coords-square))))))))

This is an absolute monster of a function. Although it’s uglier than anything I’ve written so far, I have to say that it was really easy to write. Writing my previous Clojure code, I felt like I didn’t know what step to take next. This felt intuitive, although it doesn’t read that way.

Let me try to explain it.

1. We get the locations available to erase because they have only one exit, and we define a utility function to alter the maze.
2. Then we look to see if we have any locations to erase. If not, we return the maze; if so, continue to step 3.
3. We define a bunch of values. Getting the coordinates off the top of the locations list makes sense, as does looking up the value stored in those coordinates. directions, direction, and other-direction are clunky and store the two ends of the corridor we’re eliminating. Note that this is now a fourth cond involving directions. new-coords and new-coords-square point to the other cell we have to eliminate the corridor from, and maze is our maze with the current location we’re erasing clearer out.
4. We alter the maze, removing the other end of the corridor. If we have more locations to erase, we go back to step 2.

I feel like this should be broken up, but unlike with other languages I already know well, I don’t see the natural seams yet in Clojure. Seeing those seams and cleanly extracting functionality along them is a valuable skill that I know well in Ruby, but need to practice with Clojure.

This was definitely easy, but had one tricky part.

(defn trim-maze-repeatedly [maze size amt]
  (if (zero? amt)
    maze
    (recur (trim-maze maze size) size (dec amt))))

The tricky part was that I tried to use dotimes at first. It returns nil, though, which I should have realized.

And here’s a 10×10 maze trimmed three times:

dungeon.core> (println (print-maze
                        (trim-maze-repeatedly
                         (make-maze 10) 10 3)))
+--+--+--+--+--+--+--+--+--+--+
|..|        |..|              |
+--+  +--+  +--+  +--+--+--+  +
|..|  |..|  |..|     |     |  |
+--+  +--+--+--+--+  +  +  +  +
|..|  |..|..|..|..|  |  |     |
+--+  +--+--+--+--+--+  +--+--+
|        |..|..|..|..|     |..|
+--+--+  +--+--+--+--+--+  +--+
|..|..|        |..|  |     |..|
+--+--+  +--+  +--+  +  +  +--+
|        |     |..|  |  |     |
+  +--+--+  +--+--+  +  +--+  +
|        |     |..|        |  |
+--+--+  +--+  +--+--+--+  +  +
|..|..|  |..|              |  |
+--+--+  +--+--+--+--+--+--+  +
|        |..|     |..|     |  |
+--+--+--+--+--+  +--+  +  +  +
|..|..|..|..|..|        |     |
+--+--+--+--+--+--+--+--+--+--+

I’ve gotten as far in this as I can without a good refactoring. I think I need to drop the bit field and use a set of keywords to eliminate the back and forth lookup I keep having to do. The other idea I’ve had is to quit tracking values of cells and instead track corridors, so I can avoid having to update twice to eliminate a corridor, but that’s less figured out in my head yet.

See the full code listing at GitHub. I’ve made a few minor changes based off suggestions from my co-worker Luke.

To simplify things, I just used a square grid.

(defn create-grid [size]
  (vec (replicate size
                  (vec (replicate size 0)))))

(create-grid 3)
;=> [[0 0 0] [0 0 0] [0 0 0]]

Figuring out how to make a grid was easy. replicate generates a list made up of x number of copies of a thing. Deciding what to put in the grid was harder. I decided to go with a bit field. Each cell can be open on one to four sides (three sides in a proper maze), and I could use bits to show which sides were open. Having all sides closed at first, each cell should start with the value 0.

(def north 1)
(def east 2)
(def south 4)
(def west 8)

(defn dir-open? [square dir]
  (not (= 0 (bit-and square dir))))

(defn north-open? [square]
  (dir-open? square north))

(defn east-open? [square]
  (dir-open? square east))

(defn south-open? [square]
  (dir-open? square south))

(defn west-open? [square]
  (dir-open? square west))

(defn visited? [square]
  (not (= 0 square)))

I’ve defined each direction as a power of two. dir-open does a bitwise AND on the value of the grid cell and the value of the direction to determine whether that direction is open. visited? is a method I’ll need later to know if the cell has been visited, which I can determine by seeing if it’s open in any direction.

I have a distinct feeling this is the first place I went wrong. Using a proper Clojure data structure instead of a bit field might have been a better idea.

Picking a random cell is easy.

(defn random-coords [size]
  [(rand-int size) (rand-int size)])

I’m not marking it visited yet because I’m (probably unwisely) tying together the concept of being visited and having an exit.

Specifically:

From the current cell, pick a random direction (north, south, east, or west). If
(1) there is no cell adjacent to the current cell in that direction, or (2) if
the adjacent cell in that direction has been visited, then that direction
is invalid, and you must pick a different random direction. If all directions
are invalid, pick a different random visited cell in the grid and start this step over again.

This is where it got hard. First, I had to find the neighbors of the current cell. I pretty much copied this code straight from The Joy of Clojure. Finding valid neighbors took a little more work. I had to take all the neighbors of the current coordinates, look them up in the grid, and then eliminate any that have already been visited.

(defn neighbors [size coords]
  (filter (fn [new-coords]
            (every? #(< -1 % size) new-coords))
          (map #(map + coords %) [[-1 0] [1 0] [0 -1] [0 1]])))

(defn valid-neighbors [grid size coords]
  (let [candidates (neighbors size coords)]
    (filter (fn [candidate-coords]
              (not (visited? (get-in grid candidate-coords))))
            candidates)))

If I don’t have a valid neighbor, I’m going to have to pick a new cell from the visited cells. Remembering that it was the visited cells, not the unvisited ones, tripped me up for quite a while and left me wondering what the best way to debug Clojure is. My traditional break-and-print methods don’t work that well. Anyway, to get a list of coordinates to try, I needed a Cartesian product of the x and y sizes of the grid. for works to do this, but I had to read the code several times to get it.

(defn get-new-start [grid size]
  (let [candidates (for [x (range 0 size) y (range 0 size)] (vector x y))]
    (select-random
     (filter #(visited? (get-in grid %)) candidates))))

(defn next-coords [grid size current]
  (let [candidates (valid-neighbors grid size current)]
    (if (empty? candidates)
      (get-new-start grid size)
      (select-random candidates))))

next-coords is what I call to get the next coordinates to visit.

This is where a (perceived, see below) lack of state started to trip me up. It felt like the program did not keep information around when writing Clojure. I just moved from one cell to the other, but I didn’t know what direction it was, or if there were no valid directions and I had to start anew. In order to do that, I needed a new function to let me know what direction the new cell was from the old one.

(defn direction
  "Given a two sets of coordinates, determine if they are adjacent,
 and if so, what direction the second is from the first."
  [from to]
  (let [diff (map - to from)]
    (condp = diff
      [-1 0] :north
      [1 0]  :south
      [0 -1] :west
      [0 1]  :east
      :invalid)))

I actually wrote a comment in this function so I wouldn’t forget what I was doing. The function returns :invalid if the coordinates are not adjacent, which I use in the next function, used to update the grid.

(defn update-grid [grid current next]
  (let [alter-grid (fn [d1 d2]
                     (assoc-in
                      (assoc-in grid next (bit-or (get-in grid next) d2))
                      current (bit-or (get-in grid current) d1)))]

    (condp = (direction current next)
      :north (alter-grid north south)
      :south (alter-grid south north)
      :east  (alter-grid east west)
      :west  (alter-grid west east)
      grid)))

Note that I’ve defined alter-grid inside update-grid. alter-grid needs many of the same values as update-grid, but it felt verbose to add parameters since I was calling alter-grid 4 times inside the same method. By using let, I was able to use a closure to capture those values.

I’m not explaining each piece of this code, so you’ll have to look up what assoc-in and get-in are if you don’t know. Note, though, that assoc-in does not actually alter the grid passed to it, but instead returns a new grid with its changes. This is a major selling point of Clojure: things are immutable and copies are cheap. update-grid never actually updates the grid. It returns the next stage of the grid. Writing this helped me understand the Clojure position on state and identity better. I still feel lost on how to manage state, but a little less lost.

This part was fun and reminded me more of my experiments with Scheme than other parts of Clojure. In solving problems on 4Clojure, I’ve found knowing a little bit of Lisp or Scheme has hurt me in writing idiomatic Clojure. My Clojure code normally works, but is twice as long as it should be. In this part, I got to write a recursive function, which feels like Lisp to me.

(defn make-maze [size]
  (loop [grid (create-grid size)
         current (random-coords size)]
    (if (some #(not (visited? %)) (flatten grid))
      (let [next (next-coords grid size current)]
        (recur (update-grid grid current next) next))
      grid)))

This worked! I was kind of shocked and surprised.

The last thing I had to do was print my maze. I decided to just make an ASCII art maze, which let me write code that felt like Perl or Ruby, stuff I’m used to.

(defn print-row [row]
  (str
   (apply str
          (map #(if (north-open? %) "+ " "+--") row))
   "+\n"
   (apply str
          (map #(if (west-open? %) " " "| ") row))
   "|"))

(defn print-maze [grid]
  (str
   (apply str (interpose "\n" (map print-row grid)))
   "\n"
   (apply str (replicate (count grid) "+--"))
   "+"
   "\n"))

You’ll note I only check to see if a cell is open on the north or west sides. The other sides are irrelevant, as the neighboring cells will be open on the north or west sides if the current cell is open on the south or east side. On the edges, where there are no neighbors, those sides will be closed.

There has got to be a much better way to do this. Either Clojure code is still hard for me to read (likely) or I just wrote tremendously bad Clojure code (even more likely.) As I move on to the next step of generating a dungeon, hopefully I’ll clean up this code.

See the full code listing at GitHub.