Minesweeper board "opening up"

Question

I am designing a Minesweeper game, yet I can't find the algorithm on how to board "opens up". If you have ever played Minesweeper, the first click or so will display lots of the tiles. What is the algorithm behind it?

Answer 1

You could use a flood-fill algorithm, but only for cells without any neighbouring bombs (would display a "0" or no value), and their surrounding cells.

Some pseudo-code:

floodFill(cell)
  if not cell.isOpen
    cell.open()
    if not cell.hasNeighbouringBombs
      for each neighbour n of cell
        floodFill(n)

Note how this is different from the 'normal' flood-fill algorithm:

floodFill(cell)
  if not cell.hasNeighbouringBombs and not cell.isOpen
    cell.open()
    for each neighbour n of cell
      floodFill(n)

The reason for the difference can be seen in this example:

1 1 2
2 0 3
1 2 3

The normal flood-fill algorithm would fill only the 0, but we want to fill all of the above, thus we should check hasNeighbouringBombs only after we open the current cell.

Note that if you start off clicking on a cell with a non-zero value, no other cells are opened up (at least on most versions of the game) - this would be taken care of with the above algorithm.