Clojure Programming - Maze Generation

maze.org

Willson’s Maze Generation Algorithm

1. 랜덤하게 위치를 고르고 방문됨 이라고 표시한다.
2. 2-1. 방문됨 이라고 표시되지 않은 위치를 랜덤하게 고른다. (ㄱ) 2-2. 만약 없다면 미로를 반환한다.
3. (ㄱ)에서 방문됨 이라고 표시된 위치를 만날때까지 랜덤하게 걷는다. 만약 랜덤하게 걷는 동안 한 위치를 두 번 이상 지나간다면 원래 걸었던 방향을 지우고 새로운 방향을 만든다.
4. 랜덤하게 걷는 동안 지나간 모든 위치를 방문됨 이라고 표시하고 가장 최근의 탈출 방향에 따라서 벽을 지운다.
5. 2로 돌아가서 반복한다.

데이터 구조들

위치 : [ x y ] 방문된 위치들 : #{ 방문된 위치들 } 벽: #{ 위치1 위치2 } 걷기 : [ 위치1 위치2 위치3 … ] 탈출 방향 : [ 탈출한 위치 , 새롭게 들어간 위치 ]

코드 분석

(defn maze
  [walls]
  (let [paths (reduce (fn [index [a b]]
                          (merge-wiwth into index {a [b] b [a]}))
                      {}
                      (map seq walls))
        start-loc (rand-nth (keys paths))]
    (loop [walls walls
           unvisted (disj (set (keys paths)) start-loc)]
      (if-let [loc (when-let [s (seq unvisted)] (rand-nth s))]
        (let [walk (iterate (comp rand-nth paths) loc)
              steps (zipmap (take-while unvisted walk) (next walk))
              walk (take-while identity (iterate steps loc))
              steps (zipmap walk (next walk))]
          (recur (reduce disj walls (map set steps))
                 (reduce disj unvisted (keys steps))))
        walls))))

참고할 것들

• zipmap은 중복되는 키가 있을 때에 마지막 것을 선택한다.
• 지금 걸을 때에는 미로의 경로를 그리고 있는 것이다.

(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 1.5 1.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)))

(doseq [_ (range 2)]
  (future (draw 40 40 (maze (grid 40 40)))))

육각형 미로

(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}))))

(hex-grid 3 3)

(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 (inc w)) (* 20 (+ 0.5 h))))))
    .pack
(.setVisible true)))

(hex-draw 40 40 (maze (hex-grid 40 40)))