Wednesday, October 26, 2016

Minesweeper for Linux (just for fun)

Much time has been passed since I last played minesweeper on my Windows machine in the campus... A lot has been changed since that time. Now I use Linux and I'm not in the campus any more :) I just thought: why not to implement this cool game on my own...

Here's what I have now (sources and README):


In this post I would like to share with some interesting moments I faced with during implementation.

Random generation and counting of mines

Here I use one-dimensional array which is initially filled in by '0's (empty cells) and '-1's (mines). Shuffling the array allows me to distribute mines randomly.

1
2
3
4
5
6
7
const int totalCellCount = rowCount * colCount;
  int* cells = new int[totalCellCount];
  std::fill_n(cells, totalCellCount, 0);
  std::fill_n(cells, mineCount, -1);

  size_t seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::shuffle(cells, cells + totalCellCount, std::default_random_engine(seed));

To count how many mines are there around an empty cell I use shift-arrays which describe all the neighbors of the given cell.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static const int shiftCount = 8;
  static int rowShifts[shiftCount] = {-1, -1, 0, 1, 1, 1, 0, -1};
  static int colShifts[shiftCount] = {0, 1, 1, 1, 0, -1, -1, -1};

  for (int i = 0; i < totalCellCount; i++)
  {   
    if (cells[i] < 0)
    {   
      int row = i / colCount;
      int col = i % colCount;
      for (int k = 0; k < shiftCount; k++)
      {   
        int rowShift = row + rowShifts[k];
        int colShift = col + colShifts[k];
        if (rowShift >= 0 && static_cast<size_t>(rowShift) < rowCount
            && colShift >= 0 && static_cast<size_t>(colShift) < colCount
            && cells[rowShift * colCount + colShift] >= 0)
        {   
          cells[rowShift * colCount + colShift]++;
        }   
      }   
    }   
  }


Opening empty cells

There is useful and interesting case in the original minesweeper when you open an empty cell without neighboring mines. Opening such a cell leads to opening all the connected empty cells and the first non-empty cells which form a sort of border.

I use Breadth-first search (BFS) to find all such connected cells which can be opened at once. BFS works in linear time which makes this algorithm really fast.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool** seen = new bool*[rowCount];
  for (size_t row = 0; row < rowCount; row++)
  {
    seen[row] = new bool[colCount];
    std::fill_n(seen[row], colCount, false);
  }
  std::deque<std::pair<int, int> > queue;
  queue.push_back({pressedRow, pressedCol});
  seen[pressedRow][pressedCol] = true;

  while (!queue.empty())
  {
    std::pair<int, int> cell = queue.front();
    int row = cell.first;
    int col = cell.second;
    queue.pop_front();
    front[row][col] = back[row][col];

    for (int k = 0; k < shiftCount; k++)
    {
      int nextRow = rowShifts[k] + row;
      int nextCol = colShifts[k] + col;

      if (nextRow >= 0 && static_cast<size_t>(nextRow) < rowCount
          && nextCol >= 0 && static_cast<size_t>(nextCol) < colCount
          && !seen[nextRow][nextCol]
          && back[nextRow][nextCol] != Clip::CELL_MINE
          && back[row][col] == Clip::CELL_PRESSED
          && front[nextRow][nextCol] == Clip::CELL_INIT)
      {
        seen[nextRow][nextCol] = true;
        queue.push_back({nextRow, nextCol});
      }
    }
  }


GUI style customization

When you run minesweeper it looks like the classic one. Somewhere in the internet I found this sprite:


To make minesweeper's style customizable I singled out sprite description into a separate file. Now I can give a config file as an input to the game and the magic happens :)

Here's how a config file looks like for a customized sprite:

1
2
3
4
5
mines=99
field_rows=16
field_cols=30
sprite_img=resources/rd.png
sprite_txt=resources/rd.txt

where sprite_txt is the path for a text description of the image sprite. Here's a custom sprite and it's description:


#x y w h
0 0 20 42 #digit 0
21 0 20 42 #digit 1
42 0 20 42 #digit 2
63 0 20 42 #digit 3
84 0 20 42 #digit 4
105 0 20 42 #digit 5
126 0 20 42 #digit 6
147 0 20 42 #digit 7
168 0 20 42 #digit 8
189 0 20 42 #digit 9
0 44 43 44 #smile init
45 44 43 44 #smile pressed
90 44 43 44 #smile wonder
135 44 43 44 #smile win
180 44 43 44 #smile lose
0 89 26 26 #cell init
27 89 26 26 #cell pressed
54 89 26 26 #cell flag
81 89 26 26 #cell flag pressed
108 89 26 26 #cell question mark
135 89 26 26 #cell question mark pressed
162 89 26 26 #mine
189 89 26 26 #mine lose
215 89 26 26 #mine wrong
0 116 26 26 #cell 1
27 116 26 26 #cell 2
54 116 26 26 #cell 3
81 116 26 26 #cell 4
108 116 26 26 #cell 5
135 116 26 26 #cell 6
162 116 26 26 #cell 7
189 116 26 26 #cell 8

You have to follow the format and the ordering of the elements as shown in the example above when describing your own sprite. That's it.


What is not implemented
  • menu bar with options to change game field configuration
  • win statistics

P.S.: it is the most pleasant feeling in the world when you enjoy playing the game you wrote by yourself!

P.P.S.: C++ is not my major language, it is more like a hobby, so if you have any notes about the code you're very welcome to share with them.

1 comment:

  1. Thank you so much for this! I loved playing the windows-style minesweeper on Linux. I even put music I used to listen to when I was still in school while playing :)

    ReplyDelete