I’ve been interested in Clojure for a while, and even attended this year’s ClojureConj, but haven’t felt like I really knew what I was doing with it yet. The holidays have left me with some spare time, so I’m trying to really learn this thing.
If you don’t know what Clojure is or why you might want to learn it, go read a different blog post.
I find it impossible to really learn a language without a project, and have never found one that got me excited about Clojure before. I’ve always wanted to make a random dungeon generator, though, and for some reason, Clojure seems like an interesting language to do random generation.
I remembered an article I read long ago by Jamis Buck about a random dungeon generator he wrote, and managed to find it using the Internet Wayback Machine. His first point was that a dungeon is a maze, and he goes on to explain how to generate a dungeon map by starting first with a maze map. Here’s the algorithm he describes to generate a maze:
- Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.
- Pick a random cell in the grid and mark it visited. This is the current cell.
- 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.
- Let’s call the cell in the chosen direction C. Create a corridor between the current cell and C, and then make C the current cell. Mark C visited.
- Repeat steps 3 and 4 until all cells in the grid have been visited.
Given this description, I then proceeded to write the worst Clojure code in the world. Considering I work with some of the greatest minds in Clojure, I’m embarrassed to post this code, but that’s how you learn, I guess.
Start with a rectangular grid
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.
Pick a random cell in the grid and mark it visited
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.
From the current cell, pick a valid new cell
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.
Create a corridor between the current cell and the next cell
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 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
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.
Repeat until all cells in the grid have been visited
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.