crn.io   codes and curiosities

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.