Skip to content

Instantly share code, notes, and snippets.

Created November 5, 2016 23:46
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
(defn neighbors
([size yx] (neighbors [[0 0] [1 1] [-1 -1] [-1 1] [1 -1] [-1 0] [1 0] [0 -1] [0 1]] size yx))
([deltas size yx]
(filter (fn [new-yx]
(every? #(< -1 % size) new-yx))
(map #(vec (map + yx %))
(defn density [matrix y x]
(let [neighbors (map #(get-in matrix %) (neighbors (count matrix) [y x]))
full-neighbors (:full (frequencies neighbors))]
(max 1 (* full-neighbors full-neighbors))))
(defn drunkards-walk
[grid num-empty-cells]
(let [height (count grid)
width (count (first grid))]
; Guard against impossible demands.
(when (<= num-empty-cells (* width height))
(loop [grid grid
; Step 1: pick a random cell.
x (rand-int width)
y (rand-int height)
empty-cells 0]
; Step 2: if we're done, return the grid.
(if (= empty-cells num-empty-cells)
(let [cell-was-full? (= (get-in grid [y x]) :full)
; Step 3: walk one step in a random direction.
weights {:north (density grid (dec y) x)
:south (density grid (inc y) x)
:east (density grid y (inc x))
:west (density grid y (dec x))}
direction (rand-nth (flatten [
(repeat (weights :north) :north)
(repeat (weights :south) :south)
(repeat (weights :east) :east)
(repeat (weights :west) :west)
; Step 4: back to step 2.
(recur (assoc-in grid [y x] :empty)
(case direction
:east (bound-between (inc x) 0 (dec width))
:west (bound-between (dec x) 0 (dec width))
(case direction
:north (bound-between (dec y) 0 (dec height))
:south (bound-between (inc y) 0 (dec height))
(if cell-was-full?
(inc empty-cells)
(-> (full-grid 200 200)
(drunkards-walk 5000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment