Skip to content

Instantly share code, notes, and snippets.

# cgrand/maze.clj Created Jan 24, 2011

A maze generator (Wilson's algorithm) which can work with any topography (hextiles, torus variants, teapot etc.)
 ; http://groups.google.com/group/clojure/browse_thread/thread/974e2c7f89e27231/5f4bff3e58dfa36f ; output images http://i.imgur.com/gSASS.png (square maze) ; http://i.imgur.com/uEqaq.png (hex maze) ;; generic Wilson's algorithm implementation (defn maze "Returns a random maze carved out of walls; walls is a set of 2-item sets #{a b} where a and b are locations. The returned maze is a set of the remaining walls." [walls] (let [paths (reduce (fn [index [a b]] (merge-with into index {a [b] b [a]})) {} (map seq walls)) start-loc (rand-nth (keys paths))] (loop [walls walls unvisited (disj (set (keys paths)) start-loc)] (if-let [loc (when-let [s (seq unvisited)] (rand-nth s))] (let [walk (iterate (comp rand-nth paths) loc) steps (zipmap (take-while unvisited walk) (next walk))] (recur (reduce disj walls (map set steps)) (reduce disj unvisited (keys steps)))) walls)))) ;; square grid specific (defn grid [w h] (set (concat (for [i (range (dec w)) j (range h)] #{[i j] [(inc i) j]}) (for [i (range w) j (range (dec h))] #{[i j] [i (inc j)]})))) (defn draw [w h maze] (doto (javax.swing.JFrame. "Maze") (.setContentPane (doto (proxy [javax.swing.JPanel] [] (paintComponent [^java.awt.Graphics g] (let [g (doto ^java.awt.Graphics2D (.create g) (.scale 10 10) (.translate 0.5 0.5) (.setStroke (java.awt.BasicStroke. 0.4)))] (.drawRect g -1 -1 w h) (doseq [[[xa ya] [xb yb]] (map sort maze)] (let [[xc yc] (if (= xa xb) [(dec xa) ya] [xa (dec ya)])] (.drawLine g xa ya xc yc)))))) (.setPreferredSize (java.awt.Dimension. (* 10 (inc w)) (* 10 (inc h)))))) .pack (.setVisible true))) ;; draw a maze: (draw 40 40 (maze (grid 40 40))) ;; hex-grid specific (defn hex-grid [w h] (let [vertices (set (for [y (range h) x (range (if (odd? y) 1 0) (* 2 w) 2)] [x y])) deltas [[2 0] [1 1] [-1 1]]] (set (for [v vertices d deltas f [+ -] :let [w (vertices (map f v d))] :when w] #{v w})))) (defn- hex-outer-walls [w h] (let [vertices (set (for [y (range h) x (range (if (odd? y) 1 0) (* 2 w) 2)] [x y])) deltas [[2 0] [1 1] [-1 1]]] (set (for [v vertices d deltas f [+ -] :let [w (map f v d)] :when (not (vertices w))] #{v (vec w)})))) (defn hex-draw [w h maze] (doto (javax.swing.JFrame. "Maze") (.setContentPane (doto (proxy [javax.swing.JPanel] [] (paintComponent [^java.awt.Graphics g] (let [maze (into maze (hex-outer-walls w h)) g (doto ^java.awt.Graphics2D (.create g) (.scale 10 10) (.translate 1.5 1.5) (.setStroke (java.awt.BasicStroke. 0.4 java.awt.BasicStroke/CAP_ROUND java.awt.BasicStroke/JOIN_MITER))) draw-line (fn [[[xa ya] [xb yb]]] (.draw g (java.awt.geom.Line2D\$Double. xa (* 2 ya) xb (* 2 yb))))] (doseq [[[xa ya] [xb yb]] (map sort maze)] (draw-line (cond (= ya yb) [[(inc xa) (+ ya 0.4)] [(inc xa) (- ya 0.4)]] (< ya yb) [[(inc xa) (+ ya 0.4)] [xa (+ ya 0.6)]] :else [[(inc xa) (- ya 0.4)] [xa (- ya 0.6)]])))))) (.setPreferredSize (java.awt.Dimension. (* 20 (+ 2 w)) (* 20 (inc h)))))) .pack (.setVisible true))) ;; draw a maze: (hex-draw 40 40 (maze (hex-grid 40 40)))

### jeregrine commented Jan 27, 2011

 Wow, where was this when I was doing the wumpus world, or 8x8 ai. I have learned so much from reading this.... Thanks!
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.