comSysto bei XING

22
.
03
.
2016

Sweeping mines with clojure Part II

The second part of the minesweeper series is about adding the missing game features in order to create a fully working game. Main topics are placing mines randomly, finding nice neighbours and auto-clearing cells using a recursive flood fill algorithm.

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 fully playable version on top of blog post 1 including a simple swing UI. To checkout the source code this blog post relies on:

github:87452cde61bb50164b93

If you want to sweep some mines, simply hit

lein run

on the commandline or alternatively

lein repl

to start the REPL with all discussed sources included.

Placing the mines on the board

Choosing a nice mine placement is actually a hard problem, as Richard Kaye pointed out in his paper "Minesweeper is NP-complete". The ultimate goal is to have a configuration that is challenging while it is still possible to solve the game without the need to guess. In this blog post though, I'll distribute the mines randomly on the board, thus:

  1. create an indexed sequence in the size of the board
  2. remove the index of the first cell explored
  3. shuffle the elements of the sequence
  4. take the first n elements
  5. set the mines using the given indexes

as demonstrated in the following code snippet:

github:edb1b0e72586251c1ed6

Another way to approach this problem is to have a fixed set of nicely fashioned boards (the most famous one is called "Dream Board") and to shift and rotate them around on the grid on every new game. This  may be something for another blog post though.

Choose your neighbours wisely

In order to find out how many mines reside in the adjacent fields, we need a function that provides the surrounding indexes for a given cell. Assuming that the given cell is the center, the surrounding cells can be expressed like this:

github:7172382b21feb79ef240

The following higher-order function takes a vector of coordinates and applies them to the current coordinates, taking the boards dimension into account. By specifying a pattern, we are able to project any given shape on the board.

github:6e676eefd982d2afd110

In case only the north, east, south, west neighbours are required instead, a different set of coordinates will do the trick:

github:2711d06963943a9792b9

Since we are able to separate good neighbours from the bad ones, the next step is to place some warnings on the board.

github:307cc090f41afa613f2a

First of all, the neighbours of all mined cells are gathered, using the previously described functions. As a second step, the frequencies of all these cell indexes are calculated and assigned to the warnings vector using reduce.    

Unfolding areas without mines

Whenever a new cell is explored, all adjacent areas that do not contain any mines should be automatically unfolded. The basic procedure is a variant of the flood fill algorithm:

  1. mark the current cell as explored
  2. collect all surrounding cells if none of them contains a mine and unveil them
  3. recursively repeat the procedure until no cells remain that satisfy 2.

Although the JVM currently does not support tail recursion, it's important that the recursive function call is the last statement in order to profit from the a tail-call optimization.

github:fb778a2e78870c84857d
github:aeeec66e3783beefe0ba

To find out which areas are suitable to auto-clear, we again use the neighbours function.

Wiring everything together

The core game mechanics (randomly set mines, place warnings, auto-clear fields) are done, now the last missing step is to add a function that puts together the discussed pieces and leaves us with a nicely prepared board.

github:502d0140fa7295f2cb70

Three more helper functions to do some condition checking on the board

github:279dddeb75ff9096c661

and the minesweeper game is ready! In order to try out the game, we can start the clojure REPL from the commandline by executing lein repl and play around on your own

github:196de64861117fc9dc65

or alternatively type lein run and start sweeping mines in the swing application.

smwcp2-wiring.png

What's next?

As I am quite lazy from time to time, a logical next step would be to implement an algorithm that solves the game automatically by either referring to well-known solving patterns or to try out some machine learning mechanics instead.

As long as there is nothing to solve it automatically, have fun playing or digging around in the code!

Themen:

Kommentare?

comSysto Logo