Skip to content

Instantly share code, notes, and snippets.

@cgrand
Created January 24, 2011 08:02
Show Gist options
  • Save cgrand/792959 to your computer and use it in GitHub Desktop.
Save cgrand/792959 to your computer and use it in GitHub Desktop.
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
Copy link

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