Some months ago I started to write my own little minesweeper game to practice clojure a bit. After I had my first working solution ready, I started to discuss the underlying data structure with a friend of mine and since then the code has undergone several rewrites. This post provides a minimal playable version in the REPL, a fully working solution will follow in one of the subsequent blog posts.
As I am far from being a clojure expert, any feedback is highly appreciated! To checkout the source code this blog post relies on:
If you'd rather sweep some mines on a working GUI first, you could also switch to the tag 1.0.0 and hit lein run in the commandline.
Finding the right data structure
The first approach I came up with was a vector (rows) of vectors (columns) of maps (cell state, e.g. mine set, explored etc.). This decision was clearly influenced by my object-oriented daily routine. I guess, I already had an OOD solution in my mind and tried to squeeze it into a clojure data structure.
From the start, I always found this data structure a bit awkward and over-complicated, though. After some discussions and reading The Joy Of Clojure, I decided to try out a single vector approach instead. My intention was to keep the data structure as simple as possible and apply the appropriate functions to generate a certain representation/view of the data (e.g. a n x m board) when needed.
The key of this approach is the pos->idx function which maps a given coordinate (x,y) to an index in the vector. I favor this approach over the my first attempt but I also had to abuse the vectors first element to store static game information (board's width). Over time, this element would become pretty bloated.
After some more thoughts, I changed the data structure into a map. It holds the different cell states as separated layers, represented by a vector of 1s' (set) and 0s' (not set) each. The only exception is the warnings vector that holds the number of adjacent mines.
The cell/game state is now clearly separated from the static game data. In case further game information is required (e.g. players name), an additional entry in the map will do the trick without interfering with other elements.
Create and update the board
The game starts with an empty board of a given width, height and the number of mines that will be placed on the board.
Given the fact that all common data structures provided by clojure are immutable by default, it's sufficient to create a single empty vector with pre-assigned 0s' and assign it to the different game states (:explored, :flags, :mines, :warnings). Any update operation will create a "new" immutable vector - no need to take care about mutating state.
Let's create an empty board and place some mines and warnings on it.
Getting rid of the boilerplate
Currently all update functions all look kind of the same to me. So what do these functions have in common? All of them
- transform a xy-position into an index
- modify a single element in one of the state vectors
- depend on board and pos as parameters
In order to group the common functionality together, a higher order funciton is a nice way to go. Instead of an concrete value, it returns another function.
Now the cell-modifer* function takes care of updating the chosen state vector at the given index. The state to choose the right vector and the modifier function are encapsulated in the cell-modifier* function.
The core functions on the other hand simply define the state they operate on and a variadic function to update the given element.
Winning and losing
Two additional functions are required to find out if the game is lost or won already. The game is
- lost, when at a given index a 1 is set in both the mine and the explored vector
- won, when at any given index a 1 is set either in the mine or the explored vector
as determined by the following code snippet:
Wiring everything together
I'd suggest to follow the instructions in the first listing and afterwards enter lein repl in the commandline. This will start Clojure's Read-Eval-Print Loop and load all necessary resources to try out the discussed code.
In addition to the game.clj (the functions discussed), there is another file display.clj for pretty printing the board and a main.clj as the application's entry point with some more helper functions.
A big advantage of the REPL is the ability to replace every function at any given time. In case you are not happy with one of the suggested functions, just type-in your version and hit ENTER. The REPL will automatically pick up your change and apply it.
The next blog post will focus on the remaining core game functions (placing mines and warnings automatically, main game loop etc.)