Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.