Minesweeper in Perl/Tk

Abstract

This document makes use of Unicode. Please, make sure you have a decent browser and fontsIE and Firefox are usually OK but, sometimes, Webkit based browsers are flaky on the Unicode side.DejaVu Fonts have a very good Unicode support.

What's Minesweeper?

Minesweeper is a game that needs very little introduction. It dates back to the 1960s as one of the very first games to be implemented on computers. It is a (conceptually) easy game: there is a board filled with tiles, under some tiles there are mines and the player must identify which tiles contain mines. Every time that a player clicks on a tile, if there was a mine, the game ends and the player lose, if there was no mine the tile and the adjacent ones clear and leave some hints about the possible positions of the mines: an uncovered tile which is adjacent to one mine will show up the number 1, one adjacent with two mines the number 2 and so on and so forth. The player needs to put flags on the tiles he believes hide mines. Once all the mines are flagged, the game ends and the player wins. In either the win and lose case, the board is uncovered showing the player where the mines were.

The most famous incarnation of the game is the one distributed together with Microsoft Windows and referred as Microsoft Minesweeper. Originally this version was born on OS/2 but ported to Windows in 1990 and part of Windows, officially, since Windows 3.1 in 1992.

High Level Idea

First thing: I am not an UI guy. The maximum of my skills in implementing UIs is doing some scripts in Perl using the Tk library… and that's exactly what I will present today.

As stated before, since I am not an UI guy, I know little of it and essentially basic stuff: buttons, labels, scrollbars… Just to start. The field is just a grid of some dimension (n×n). Each time is a Button while covered and it becomes a Label when uncovered: this makes things simple: a tile can be pressed, and Buttons are very good at that, and when it is uncovered it can be blank or just show an hint on the number of surrounding mines. I am no artist either and then, instead of using nice icons to represent mines…, I will just use some Unicode chars in order to represent the graphical elements: ⚑ to represent a flag over a discovered mine, ☀ to represent unexploded mines (when the game ends) and ☠ to represent the mine that the player clicked by error making him lose.

Aside from the UI, the game needs some data-structures to keep track of: ① where the mines are, ② what is the status of the tiles (covert or uncovered) and ③ a data-structure to keep track of the UI widgets. ② and ③ could be collapsed in the same data-structure (Button ⇒ covered and Label ⇒ uncovered) but I prefer to keep the two things disjoint. Moreover, I will need also a data-structure to keep track of the flags that were placed by the user.

Other pieces needed: once a player clicks on a tile, if this one was neither a mine one nor adjacent to one, the application must start uncovering all the tiles starting from that one stopping only at the tiles adjacent to mines. This will use a classic percolation algorithm. Initially in my implementation, the percolation was recursive. When I started increasing the size of the field, the algorithm was reimplemented in a iterative way.

Some Implementation Details

In this section, I will describe the interesting pieces of the code and not "all of it". For that, you can refer to the last section of this document from where you can download the full code.

Let's start from the "main" part of the script:

...
my $mw = MainWindow->new;
$mw->title("Minesweeper");
$mw->configure(-background => 'white');
$mw->resizable(0,0);

$mw->protocol('WM_DELETE_WINDOW', sub {
                my $answer = $mw->messageBox(-title => 'Why do you want to leave me?',
                                             -message => "Did I do anything wron? Press 'no' to stay \x{263A}",
                                             -type => 'yesno', -icon => 'info', -default => 'Yes');

                if($answer eq 'Yes') {
                  $mw->destroy;
                  exit 0;
                }
              });

InitGame();

MainLoop;
...

Very simple and basic things, create the MainWindow object, set title and color of the window, tell the system that it cannot be resized.

Interesting piece if the call to $mw->protocol('WM_DELETE_WINDOW', sub {…}) as it defines an handle to intercept when the user wants to close the application clicking on the close button on the top of the window.

The InitGame() call actually does almost everything else… calling other functions:

sub InitGame {
  $mw->withdraw;
  Configure();
  InitField();
  InitUI();
  $mw->deiconify;
}

Before going into the details of the other functions there are two things to notice: $mw->withdraw; and $mw->deiconify;. Those two calls hide first, and show to the uses after, the main window containing the field in such a way that it is not show during configuration and creation phases.

The Configure() function takes care of asking the user about preferences and setting up the basic variables of the game: the size of the field ($x and $y) and the number of mines ($n):

sub Configure {
  # destroy old field before picking up the new size...
  my $it = AllPairs([0..$x-1], [0..$y-1]);
  while(my ($i, $j) = $it->()) {
    $widgets{$i}{$j}->destroy() if(exists $widgets{$i}{$j} && defined $widgets{$i}{$j});
  }

  # ask for new size and config grid
  my $sizeBox = $mw->DialogBox(-title => "Field size?", -buttons => [map {$_.'x'.$_} @numbers]);
  $sizeBox->transient(undef);
  my $response = '';
  while(!defined($response = $sizeBox->Show(-popover => $mw))) { }
  ($x, $y) = ($response =~ /(\d+)x(\d+)/);

  for my $i (0..$x-1) { $mw->gridColumnconfigure($i, -pad => 2); }
  for my $i (0..$y-1) { $mw->gridRowconfigure($i, -pad => 2); }

  # ask for how many mines should be in the field
  my $mineBox = $mw->DialogBox(-title => "How many mines?", -buttons => [map { $_ } @numbers]);
  $mineBox->transient(undef);
  while(!defined($n = $mineBox->Show(-popover => $mw))) { }
}

The code starts destroying the old field if present as the player can play one game after the other… nothing particularly interesting. The other two blocks just ask the user for the size of the field (limited to some combinations) and the number of mines.

The only two things to notice are: ① the call to transient(undef) for both DialogBoxes and ② the use of the function AllPairs(·,·). The call to transient(undef) is necessary because we have hidden the main window in the body of the InitGame() function. This method tells the windowing system to detach the behavior of the DialogBox from whatever was the behavior of the MainWindow, i.e., without this call, the DialogBox would have been created but never shown to the player.

AllPair is an example of personal taste and laziness. Since the field is a matrix and I did not want to write for $i (…) { for $j (…) { … } }, I wrote an iterator:

sub AllPairs {
  my ($A, $B) = @_;
  my @values = ();
  for my $i (@$A) {
    for my $j (@$B) {
      push @values, $i;
      push @values, $j;
    }
  }

  # create the closure that iterates on the pairs...
  my $i_ = 0;
  my $j_ = 1;
  return sub { return unless($i_ < @values);
               my $x_ = $values[$i_]; $i_ += 2;
               my $y_ = $values[$j_]; $j_ += 2;
               return ($x_, $y_);
             }
}

An iterator is just a function which returns the values and to create this function, we need an iterator-factory function which takes in input the collection(s) to iterate and returns a closure that at each invocation returns the next value. The AllPairs function is our iterator-factory function which unfolds all the pairs of the two array references passed as arguments and then returns an anonymous function returning a different element at each invocation.

In the code, there is an analogous function that given a tile in the field returns an iterator on the neighbor tiles:

sub Neighbors {
  my ($i,$j) = @_;
  my @neighbors = ();

  # create the list of all the neighbors that make sense
  my $offsets = AllPairs([-1..1],[-1..1]);
  while(my ($s, $t) = $offsets->()) {
    # i.e., skip the cell itself and deal
    # only with cells inside the board
    if(($s != 0 || $t != 0) &&
       ($i+$s >= 0) && ($i+$s < $x) &&
       ($j+$t >= 0) && ($j+$t < $y) ) {
      push @neighbors, $i+$s;
      push @neighbors, $j+$t;
    }
  }

  # create the closure that iterates on the neighbors...
  my $i_ = 0;
  my $j_ = 1;
  sub { return unless($i_ < @neighbors);
        my $x_ = $neighbors[$i_]; $i_ += 2;
        my $y_ = $neighbors[$j_]; $j_ += 2;
        return ($x_, $y_);
  }
}

The InitField and InitUI are simple function that initialize the board, place the mines, compute the hints to be displayed when a cell adjacent to one of more mines is uncovered and create the widgets to render the GUI.

Something more interesting is the Percolate function. As I said before, initially it was implemented recursively:

sub Percolate {
  my ($i, $j) = @_;

  return if(exists $uncovered{$i}{$j});

  my $value = $values{$i}{$j};

  if($value != -1) {
    UncoverTile($i,$j);

    if($value == 0) {
      my $neighbor = Neighbors($i,$j);
      while(my ($s, $t) = $neighbor->()) {
        Percolate($s,$t);
      }
    }
  }
}

The function UncoverTile(·,·) just changes a Button into a Label to uncover it. The check if($value == X) is actually used to check what is under a tile: the value -1 indicates that it is a mine and the value 0 that it is an empty cell not adjacent to a mine. All the other values are used as the hints to be provided to the player as the number of adjacent mines (they all are precomputed at initialization time). The iterative version is less elegant but more efficient:

sub Percolate {
  my ($i, $j) = @_;

  my @stack = ();
  push @stack, [$i, $j];

  while(@stack > 0) {
    my ($a, $b) = @{pop @stack};

    # process only if not uncovered yet...
    if(!exists $uncovered{$a}{$b}) {
      my $value = $values{$a}{$b};

      UncoverTile($a,$b);

      # will need to uncover neighbors...
      if($value == 0) {
        my $neighbor = Neighbors($a,$b);
        while(my ($s, $t) = $neighbor->()) {
          push @stack, [$s, $t];
        }
      }
    }
  }
}

It uses the classical recursive ⇒ iterative transformation introducing a stack to keep track of where to go back instead of returning as in the recursive version.

Those were the tasty bits but I encourage you to read the full code and — maybe — provide some feedback… by the way, here it is the way it looks like:

     

You can play that extremely large as well (I love the 33×33 with only 9 mines ☺):

Conclusion and Downloads

Being stuck at home for one day can be not-that-bad™ after all. A bit of Perl, a nice idea and — more important of all — having fun coding!

Download Minesweeper.pl (MIT License)