Skip to content
Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
442 lines (387 sloc) 20.7 KB
{:title "Minesweeper in clojure"
:description "As a fun experiment, and to show the basics of clojure development, I implemented a minesweeper clone using clojurescript and p5.js."
:tags ["clojurescript" "p5"]
:link (fn [k]
(let [links {:coding-challenge ["https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH" "Coding Train Coding Challenges"]
:p5 ["https://p5js.org/" "p5.js"]
:daniel ["https://twitter.com/shiffman" "Daniel Shiffman"]
:minesweeper ["https://www.youtube.com/watch?v=LFU5ZlrR21E" "minesweeper coding challenge"]
:mine-wiki ["https://en.wikipedia.org/wiki/Minesweeper_(video_game)" "minesweeper"]
:minesweeper-game [(sneakycode.config/url "/minesweeper") "play the full version here"]
:minesweeper-code [(sneakycode.config/url "/minesweeper") "minesweeper page"]
:clojure ["https://clojurescript.org/" "Clojure/Clojurescript"]}
[url text] (get links k)]
[:a {:href url :target "_blank"} text]))
:content
(fn [{:keys [slug link] :as post}]
[:div.content
[:p "I have been working my way through the "
(link :coding-challenge)
" 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 "
(link :p5)
" and clojurescript. "
(link :daniel)
" does an excellent job in presenting and producing these videos and I suggest you go and check them out."]
[:p "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 " (link :clojure) ") 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."]
[:p "I'll be building a " (link :mine-wiki)" clone. You should go and watch the " (link :minesweeper) " 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 " (link :minesweeper-game) "."]
[:div {:id "game" :style "display: inline-flex; box-shadow: 10px 14px 19px -9px rgba(0,0,0,0.15);"}]
[:br] [:br]
[:p
[:small
[:strong "Update: "]
"This post made it to the front page of "
[:a {:href "https://news.ycombinator.com/item?id=18363750" :target "_blank"} "hackernews"]
". Head there for some nice conversation in the comments section."]]
[:hr]
[:h4 "Let's build!"]
[:p "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"
[:code "(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!" ]
[:p "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:"]
(sneakycode.render/clj
"
{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 ..}}")
[:p "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."]
(sneakycode.render/clj
"
(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)))")
[:p "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."]
(sneakycode.render/clj
"
(defn cell [col-count i]
(let [[col row] (position col-count i)]
{:i i :row row :col col
:type :empty
:flagged? false
:opened? false}))")
[:hr]
[:h5 "Creating the board"]
(sneakycode.render/markdown
"At the start of each game we want to initialize a new board. This is done in three simple steps.
1. Initialize the grid with empty cells
2. Randomly place some bombs
3. Calculate the number of bombs each cell is touching
**Initializing** the grid is fairly simple. We simply calculate the number of cells, create a list of indexes from 0 to size-1 using `range`, map over this list and create an empty cell for each index and finally, using `juxt` and `into`, create the hash-map structure we defined above. The threading macro `->>` helps us keep the code nice and readable.
" )
(sneakycode.render/clj
"
(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 ..} ...})))")
(sneakycode.render/markdown
"To **randomly place bombs** on the existing grid, we will create a loop that counts down from the number of bombs to zero. For every iteration we will randomly pick one of the empty cells and set its type to `:bomb`. That cell gets removed from the set of empty cells and we go back to the start of the loop until all bombs are placed. Recursion is the functional/immutable worlds answer to for loops that update state as part of their body. We use recur for non-stack-consuming looping.")
(sneakycode.render/clj
"
(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
)))))")
(sneakycode.render/markdown
"For each cell, we want to know how many of their adjacent cells **contains bombs**. We will do this using two functions. The first function, `neighbors`, is a helper function that, given a cell, returns all the indexes of that cell's neighbors. The `set-neighbors` function will map over our cells and for each cell set its neighbors, count its adjacent bomb cells and change the type of the cell if it is bomb adjacent.")
(sneakycode.render/clj
"
(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 {})))")
(sneakycode.render/markdown
"Finally we can compose our above functions into a single, board generating, function.")
(sneakycode.render/clj
"
(defn board [row-count col-count bomb-count]
(->> (init-cells row-count col-count)
(place-bombs bomb-count)
(set-neighbors row-count col-count)))")
[:hr]
[:h5 "Handling game actions"]
(sneakycode.render/markdown
"Now that we have a board we want to be change the board state in a number of ways. We want to be able to:
* toggle a cell as flagged
* open a cell, which in turn will either
* detonate a bomb, causing us to lose the game
* open a cell that is bomb adjacent
* open an empty cell and recursively open all other non bomb cells that are adjacent
* check if we won the game
Let's start with the latter. We have **won the game** if all non-bomb cells have been opened:")
(sneakycode.render/clj
"
(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?))")
(sneakycode.render/markdown "**Flagging** a cell is pretty straight forward. We simply negate the flagged? field:")
(sneakycode.render/clj
"
(defn toggle-cell-flag [board i]
(update-in board [i :flagged?] not))")
[:div [:p [:strong "Opening "] "a cell that is adjacent to a bomb is also easy mode"]]
(sneakycode.render/clj
"
(defn open-adjacent-cell [board i]
(assoc-in board [i :opened?] true))")
(sneakycode.render/markdown "As is **detonating** a bomb. Detonating a bomb opens all cells to reveal the entire board")
(sneakycode.render/clj
"
(defn detonate [board {:keys [i] :as cell}]
(->> board
(map (fn [[i cell]]
[i (assoc cell :opened? true)]))
(into {})))")
(sneakycode.render/markdown
(str
"Opening a cell that is **not touching a bomb cell** is slightly less trivial. We want to recursively check the neighbors of this cell and the neighbors neighbors, and if they are not bombs, we want to open them. We use the `adjacent-open-cells` function to get all the cells we need to open and then we simply reduce that list over the board and open the cells. *(I'm sure a better way to do this exists, but I only have so many hours in the day " (sneakycode.render/snippet :emoji :shrug) " )*"))
(sneakycode.render/clj
"
(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)))")
(sneakycode.render/markdown
"And finally we compose all these functions together into a single function that allows us to open any cell.")
(sneakycode.render/clj
"
(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?})))")
(sneakycode.render/markdown
"You will notice that the `open-cell` function does not take a board hash-map as the other functions does, but a game hash-map. This is simply to allow us to define some general fields around our board that can be used by the consumer to determine various things. We call this state the `game` and we initialize a game using:")
(sneakycode.render/clj
"
(defn new-game [rows cols bombs]
{:board (board rows cols bombs)
:win? false
:dead? false
:rows rows
:cols cols
:bombs bombs
:size 35})")
[:hr]
[:h5 "Taking a step back"]
(sneakycode.render/markdown
"At this point, there are a few observations that I would like to make.
* The above code is enough to run a game of minesweeper. A very naive way would be to recursively open cells until a bomb is found:")
(sneakycode.render/clj
"
(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")
(sneakycode.render/markdown
"* All of the code above is expressed using pure functions, meaning that given an input we can always expect the same output. Nowhere are we mutating any state. All of the clojure data types we have used are immutable and persistent. This makes our code very easy to reason about and writing tests trivial.
* All the code is valid clojure and clojurescript, meaning it will run on the jvm, node and in the browser without us having to make any changes. Technically it will run on the clr too using clojureclr, but I have not tried it. This is the power of a hosted language.")
[:hr]
[:h5 "Can haz side effects?"]
(sneakycode.render/markdown
"Ultimately, any useful program will end up having some side effects, whether this is writing to disk or reacting to user input. Our game will be rendered in the browser using p5.js and the game state will be kept in a clojure atom. Every time the user clicks we will call a function that will run the current state through our functions and then save the new state in our atom. Our view render code can then simply query the state atom for the latest state. You can see in the `mouse-clicked` function how easily we interop with javascript and p5 by simply using `js/`. ")
(sneakycode.render/clj
"
(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)")
(sneakycode.render/markdown
"Finally we can render our game to the screen. We initialize the board inside of p5.js's draw function and then \"save\" it in the `*state` atom. Then in the p5 draw function we iterate the items in the grid and draw them to screen, we use multimethods to draw open cells based on the type of cell.")
(sneakycode.render/clj
"
(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))")
[:div [:p "To see the full implementation in one place you can jump over to the " (link :minesweeper-code) "."]]
[:hr]
[:h5 "Conclusion"]
(sneakycode.render/markdown
"Implementing minesweeper we have seen the simplicity of expressing code using a set of pure functions. We simply define some data and then transform that data. We are also free of weird side effects and bugs because we rely on immutable data structures. This results in a codebase that is clean, concise and easy to reason about and maintain. To make the code usable we wrap our functional code in a stateful shell, allowing us to easily run our code anywhere we like, whilst maintaining integrity.
I hope you have found my clojure ramblings useful and I hope that I have planted a small seed of interest/curiosity in your brain that will compel you to have a look at functional programming and at clojure. Personally I have fallen in love with clojure. It is such an elegant and thought through language. Since moving to clojure I have 10X more fun writing code as well as completed many more side projects than I ever manged before. I would encourage you to go and play with clojure. Simply trying out things that you are not familiar with (like lisp, FP and immutability) will make you a better programmer.
> note: I am pretty sure that the code above is not perfect, and if you are reading this as an experienced clojure developer, feel free to point that out in the comments below.")
[:br]
(sneakycode.render/snippet :source post)
;;;; Load minesweeper
(sneakycode.render/snippet :p5)
(sneakycode.render/snippet :cljs "minesweeper")
[:script "window.addEventListener('load', mine.core.phone_game)"]
])}
You can’t perform that action at this time.