algorithm to search empty cells in minesweeper

Question

hi Guys,

Im creating a minesweeper and just wondering what is the best algorithm to search all the empty cells when the user press the empty cell then grow and limit to the border until it reaches the bomb cell. I planning to use recursive search but probably it will slow the process.

Thanks.

Answer 1

If you're graphically depicting the detection I'd say it would be best to do it multiple steps (grow the border as you suggest):

1. Reveal the clicked on square, find all nearby entries that are obviously handled.
2. Reveal those squares, find all entries near those that are obviously handled.
3. Repeat from step 2.

That way the user can see it happen which is always good. Mix in some animation and it could be something cool that makes someone hope for it to happen.

Answer 2

Epsilon Prime's solution is a good way to implement it.

You can do it with a queue.

Example:

push the first empty cell/point
LOOP until queue non empty 
   pop.head cell and reveal it
   push the empty surrounding cells of it (8 at maximum)
     (you must flag the cells so you don't push them again,  
      ie dont push the cells that are already revealed)

Answer 3

From an algorithmic perspective, you can't go wrong with Breadth-First Search or Depth-First Search. Nick D's answer basically describes Breadth-First Search, but in general the solution you want is going to be "while you're still looking at squares, reveal the square; if the square has no bomb neighbors, then for each of its eight neighbors that are not visited yet, mark them as visited and add them to the list of squares you're looking at". repeat that until the list of squares you're looking at is empty, and start with the square the user clicks.