Search code examples
algorithmminesweeper

Minesweeper mine generation algorithm

I am making a minesweeper clone. My current algorithm for mine generation is just: pick a coordinate, if it has no mine, place a mine, else try again. I think this is not an efficient algorithm, especially in high density minefields. I am looking at some other options like: Fisher-Yates shuffle and the likes, but I think it has a long running time for much larger grids. I am thinking of using Linked Lists. Any suggestions?

Solution

  • If you have a list/array where you can get size of list in constant time you may give a try to following:

    list = List of all fields
N = number of mines
N.times do
  index = random(list.size)
  pick list[index]
  list.remove(index)
end

    This way:

    • you don't need to shuffle whole list
    • you avoid picking up same fields 2 times

    In short it will be just drawing random field from list and removing it from list to avoid collision on next draw.