Minesweeper in clojure

I have been working my way through the Coding Train Coding Challenges videos on YouTube. So far they have been quite informative and entertaining. There is something about combining math and graphics that has grabbed my attention and I have started to play around with building drawings and games using p5.js and clojurescript. Daniel Shiffman does an excellent job in presenting and producing these videos and I suggest you go and check them out.

Daniel typically does these challenges in a javascript object oriented style. I have been keen for a while to replicate these challenges using Functional Programming (via Clojure/Clojurescript) and this is the first attempt. In doing this I hope to 1. have fun and 2. get people excited about Clojure. Clojure has turned everything I believed about software on its head and I am a better developer because of it. I am also having lots of fun.

I'll be building a minesweeper clone. You should go and watch the minesweeper coding challenge as this will give you a nice idea of how the OO and FP paradigm differ. Below is a tiny demo of the game (shift click to flag) and you can go and play the full version here.

Update: This post made it to the front page of hackernews. Head there for some nice conversation in the comments section.

Let's build!

Clojure is a dynamic functional hosted lisp. The lisp syntax might be trippy if you come from curly bracket land, but in essence it is always(my-function arg1 arg2 ...) ... for everything ... ever. Clojure is functional and its core data structures are persistant, so we will be focusing on building the core minesweeper functionality using pure functions that operate on immutable data. Once this is done we will add a state handling mechanism and finally the drawing of the game on the screen. This is typically how we build functional applications. We have a stateful outer layer that calls into a functional inner layer. Like a metaphorical functional sandwich. Yummy!

Before I start writing any code I first want to talk about what I want my data to look like. Minesweeper is essencially just rows and columns of cells. Although I can identify each cell by its row and column, I would prefer to give each cell an index and have my entire board represented as a hash-map of indexes to cells. This allows me to easily do value lookups and updates. Because the basic board state does not change during the game, I can initialize the cells with all the information about their neighboring cells so I can avoid having to iterate the cells when I need to check bomb locations etc. My core grid data structure then ends up looking like this:

{0 {:i 0 :row 0 :col 0
    :type :empty
    :flagged? false
    :opened? false
    :neighbors [1 5 6]
    :bombs-touching 0
    }
 1 {:i 1 :row 0 :col 1 :type ..}
 2 {:i 2 :row 0 :col 2 :type ..}}

Now that I have an idea of what the data is going to look like, I can start creating and combining functions to build up the board state. The first thing I want to be able to do is to convert an index to a row and column and vice versa.

(defn position
  "given the grid width and index, returns a vector containing column and row"
  [col-count i]
  (let [col (mod i col-count)
        row (/ (- i col) col-count)]
    [col row]))

(defn index
  "given the grid width and the row and column, returns the index"
  [col-count row col]
  (+ col (* row col-count)))

With that out of the way we can write a simple function that, given a grid width and an index, will create an empty cell.

(defn cell [col-count i]
  (let [[col row] (position col-count i)]
    {:i        i :row row :col col
     :type     :empty
     :flagged? false
     :opened?  false}))

Creating the board

(defn init-cells [row-count col-count]
  (let [size (* row-count col-count)]
    (->> (range size) ; => (0 1 2 ... size-1)
         (map #(cell col-count %)) ; => ({:i 0 :row ..} {:i 1 :row ..} ...)
         (map (juxt :i identity))
         (into {}) ; => {0 {:i 0 :row ..} 1 {:i 1 :row ..} ...})))

(defn place-bombs [bomb-count cells-map]
  (loop [bomb-count  bomb-count
         empty-cells (set (keys cells-map))
         result      cells-map]
    (if (<= bomb-count 0)
      result
      (let [random-index (rand-int (count empty-cells))
            bomb-index   (nth (vec empty-cells) random-index)]
        (recur
         (dec bomb-count) ; bomb-count - 1
         (disj empty-cells bomb-index) ; remove index from empty cells
         (assoc-in result [bomb-index :type] :bomb) ; update cell at index
)))))

(defn neighbors
  "Calculates the indexes of a cell' neighbors"
  [row-count col-count cell]
  (let [{:keys [i row col]} cell
        row- (dec row)
        row+ (inc row)
        col- (dec col)
        col+ (inc col)
        neighbors [[col- row-] [col row-] [col+ row-]
                   [col- row]             [col+ row]
                   [col- row+] [col row+] [col+ row+]]]
    (->> neighbors
         (filter (fn [[col row]] ; remove out of bounds cells
                   (and (>= row 0) (>= col 0)
                        (< row row-count) (< col col-count))))
         (map (fn [[col row]] ; get the neighbor cell index
                (index col-count row col))))))

(defn set-neighbors
  "Calculates bomb adjacent cell totals and updates cell types if bomb adjacent"
  [row-count col-count cells-map]
  (->> cells-map
       (map (fn [[i cell]]
              (let [neighbors (neighbors row-count col-count cell)
                    bombs-touching (->> neighbors ; count adjacent bombs
                                        (filter #(= :bomb (get-in cells-map [% :type])))
                                        count)]
                [i
                 (assoc cell
                        :neighbors neighbors
                        :bombs-touching bombs-touching
                        :type (cond
                                (= :bomb (:type cell)) :bomb
                                (> bombs-touching 0)   :bomb-adjacent
                                :else                  (:type cell)))])))
       (into {})))

(defn board [row-count col-count bomb-count]
  (->> (init-cells row-count col-count)
       (place-bombs bomb-count)
       (set-neighbors row-count col-count)))

Handling game actions

(defn not-opened-non-bomb-cell? [cell]
  (and (false? (:opened? cell)) (not= :bomb (:type cell))))

(defn win? [board]
  (->> board
       vals
       (filter not-opened-non-bomb-cell?)
       empty?))

(defn toggle-cell-flag [board i]
  (update-in board [i :flagged?] not))

(defn open-adjacent-cell [board i]
  (assoc-in board [i :opened?] true))

(defn detonate [board {:keys [i] :as cell}]
  (->> board
       (map (fn [[i cell]]
              [i (assoc cell :opened? true)]))
       (into {})))

(defn adjacent-open-cells
  [board i]
  (loop [cells-to-check #{i}
         cells-checked  #{}
         cells-to-open  []]
    (if (empty? cells-to-check)
      cells-to-open
      (let [i (first cells-to-check)
            {:keys [neighbors opened?] :as cell} (get board i)
            t (:type cell)
            should-open? (and (not= :bomb t) (not opened?))]
        (if-not should-open?
          (recur (disj cells-to-check i)
                 (conj cells-checked i)
                 cells-to-open)
          (let [cells-not-to-check (into cells-checked cells-to-check)
                neighbors-to-add  (when (= :empty t)
                                     (filter #(not (contains? cells-not-to-check %))  neighbors))]
            (recur (into (disj cells-to-check i) neighbors-to-add)
                   (conj cells-checked i)
                   (conj cells-to-open i))))))))


 (defn open-empty-cell [board i]
  (reduce
   (fn [b i] (open-adjacent-cell b i))
   board
   (adjacent-open-cells board i)))

(defn open-cell [{:keys [board] :as game} i]
  (let [cell   (get board i)
        bomb?  (= :bomb (:type cell))
        empty? (= :empty (:type cell))
        next-board
        (cond
          bomb?  (detonate board cell)
          empty? (open-empty-cell board i)
          :else  (open-adjacent-cell board i))
        win?   (win? next-board)]
    (merge game
           {:board next-board
            :dead? bomb?
            :win?  win?})))

(defn new-game [rows cols bombs]
  {:board (board rows cols bombs)
   :win?  false
   :dead? false
   :rows  rows
   :cols  cols
   :bombs bombs
   :size  35})

Taking a step back

(defn run-game
  "Recursively open cells from index 0 until a bomb is found"
  []
  (loop [index 0
         game (new-game 10 10 10)]
    (if (:dead? game)
      (str "You died at index " index)
      (recur
       (inc index)
       (open-cell game index)))))

(run-game) ; => You died at index 9

Can haz side effects?

(defonce *state (atom nil))


(defn reset-game []
  (let [{:keys [rows cols bombs]} @*state]
    (reset! *state (new-game rows cols bombs))))


(defn mouse-clicked []
  (let [{:keys [rows cols size]} @*state
        mx                       js/mouseX
        my                       js/mouseY
        in-bounds?               (and (pos? mx) (pos? my) (< mx (* size cols)) (< my (* size rows)))
        col                      (js/Math.floor (/ mx size))
        row                      (js/Math.floor (/ my size))
        i                        (index cols row col)
        shift-pressed?           (= 16 (when (js/keyIsDown 16) js/keyCode))
        dead?                    (:dead? @*state)
        win?                     (:win? @*state)
        f                        (cond
                                   (or dead? win?)  #(reset-game)
                                   (not in-bounds?) identity
                                   shift-pressed?   #(update % :board toggle-cell-flag i)
                                   :else            #(open-cell % i))]
    (swap! *state f)))


(defn easy-game []
  (reset! *state (new-game 10 10 10)))

(easy-game)

(defonce *canvas (atom nil))

(defn setup
  []
  (easy-game)
  (let [{:keys [rows cols size]} @*state
        canvas (js/createCanvas (+ 1 (* cols size)) (+ 1 (* rows size)))]
    (.parent canvas "game")
    (js/rectMode "CENTER")
    (js/noStroke)
    (reset! *canvas canvas)
    (add-watch *state "redraw" #(js/redraw))))

(defn draw-initial-cell
  []
  (if (:win? @*state) (js/fill 0 255 0) (js/fill 240))
  (let [{:keys [size]} @*state]
    (js/rect 0 0 size size)))

(defn draw-flagged-cell
  []
  (draw-initial-cell)
  (js/fill 255 150 0)
  (js/noStroke)
  (let [{:keys [size]} @*state]
    (js/ellipse (/ size 2) (/ size 2) (/ size 3) (/ size 3))))

(defn draw-empty-cell
  []
  (js/fill 150)
  (let [{:keys [size]} @*state]
    (js/rect 0 0 size size)))

(defmulti draw-cell :type)

(defmethod draw-cell :empty [_] (draw-empty-cell))

(defmethod draw-cell :bomb
  [_]
  (draw-empty-cell)
  (js/fill 255 0 0)
  (js/noStroke)
  (let [{:keys [size]} @*state]
    (js/ellipse (/ size 2) (/ size 2) (/ size 2) (/ size 2))))

(defmethod draw-cell :bomb-adjacent
  [cell]
  (draw-empty-cell)
  (js/noStroke)
  (js/fill (* 50 (:bombs-touching cell)) 0 0)
  (js/textSize 15)
  (let [{:keys [size]} @*state]
    (js/text (str (:bombs-touching cell)) (/ size 2.2) (/ size 1.5))))

(defn draw
  []
  (let [{:keys [size board cols rows]} @*state]
    (.resize @*canvas (inc (* cols size)) (inc (* rows size)))
    (doseq [[i {:keys [row col flagged? opened?] :as cell}] board]
      (js/push)
      (js/stroke 180)
      (js/translate (* col size) (* row size))
      (cond opened? (draw-cell cell)
            flagged? (draw-flagged-cell)
            :else (draw-initial-cell))
      (js/pop)))
  (js/noLoop))

(doto js/window
  (aset "setup" setup)
  (aset "draw" draw)
  (aset "touchStarted" mouse-clicked))

Conclusion

The source code for this post is available on github