Randon Placement of Mines
Author
For my C++ Minesweeper game I have a problem when placing mines into an emtpy board. I've tried picking, say, 20 random squares but the problem is what happens if the square is already occupied? A quick fix would be to simply reselect again but it seems a rather unsatisfying solution. I'm struggling to think of a more efficent method. Can anyone enlighten me? For now the mines are simply stored in a long 1d array, but the fact that it's a 2d board doesn't make any difference to their placement.
Thanks.
Hi!
My question is: why do you want a more efficient way of doing this? Reselecting when a field is already selected is a perfectly working solution. Use it imo, and try other solutions only if this one is not working satisfyingly (which I'm almost sure won't be the case here)
Just my two cents.
My question is: why do you want a more efficient way of doing this? Reselecting when a field is already selected is a perfectly working solution. Use it imo, and try other solutions only if this one is not working satisfyingly (which I'm almost sure won't be the case here)
Just my two cents.
- Create an array containing all possible locations
To get random elements without duplicates:
- Let n be number of elements in array
repeat the following as needed:
- Pick a random number between 0 and array size
- Put mine at location at the index you just selected
- Swap just chosen element with last element in array
- Decrease n by 1
Note: For your case, this algorithm is redundant. But it comes handy when you're dealing with other selection problems, or when you need to find empty space in an otherwise heavily occupied board.
After construction, this guarantees you O(n) performance for picking n elements.
The initial array will get more and more unordered as you use it, but it doesn't matter. You want random numbers, and this way you only need to initialize the array once.
To get random elements without duplicates:
- Let n be number of elements in array
repeat the following as needed:
- Pick a random number between 0 and array size
- Put mine at location at the index you just selected
- Swap just chosen element with last element in array
- Decrease n by 1
Note: For your case, this algorithm is redundant. But it comes handy when you're dealing with other selection problems, or when you need to find empty space in an otherwise heavily occupied board.
After construction, this guarantees you O(n) performance for picking n elements.
The initial array will get more and more unordered as you use it, but it doesn't matter. You want random numbers, and this way you only need to initialize the array once.
You could use a set.
Fill it from 0 to Max Number
Generate a random number from 0 to Set.Size()
Use that number as an index into the set
Remove that number from the set
Generate a random number from 0 to Set.Size()
Repeat until you have all your numbers.
Fill it from 0 to Max Number
Generate a random number from 0 to Set.Size()
Use that number as an index into the set
Remove that number from the set
Generate a random number from 0 to Set.Size()
Repeat until you have all your numbers.
Another option:
Let's assume you have a board that is m x n, and thus have m·n, or p cells. You want q of those p cells to be mines.
Assume that random(a, b) below returns a random number between a and b, inclusively. Also assume that all cells are initialized to be mine-free.
Basically, you go through each cell, and determine if it should be a mine or not, based on how many cells you have left to go through, and how many mines you have left to lay. If you ever get to the point where remainingCells > 0 and remainingMines == 0, then you can quit early, since you've laid all your mines. If you ever get to the point where remainingCells == remainingMines and both are greater than 0, then random(1, remainingCells) will always be less than or equal to remainingMines, and all the rest of the cells will end up being mines. You'll never end up with a situation where you lay less or more than q mines.
Let's assume you have a board that is m x n, and thus have m·n, or p cells. You want q of those p cells to be mines.
Assume that random(a, b) below returns a random number between a and b, inclusively. Also assume that all cells are initialized to be mine-free.
unsigned int remainingCells = p;unsigned int remainingMines = q;unsigned int cellIndex = 0;while (remainingMines > 0){ if (random(1, remainingCells) <= remainingMines) { cell[cellIndex].HasMine = true; --remainingMines; } --remainingCells; ++cellIndex;}Basically, you go through each cell, and determine if it should be a mine or not, based on how many cells you have left to go through, and how many mines you have left to lay. If you ever get to the point where remainingCells > 0 and remainingMines == 0, then you can quit early, since you've laid all your mines. If you ever get to the point where remainingCells == remainingMines and both are greater than 0, then random(1, remainingCells) will always be less than or equal to remainingMines, and all the rest of the cells will end up being mines. You'll never end up with a situation where you lay less or more than q mines.
This method places n mines in a 1D array with an even distribution. You can easily extend it to 2D.
Antheus, unless I misinterpreted your algorithm, it doesn't work. I think mine is similar to what you were trying to describe.
bool mines[ ARRAY_SIZE ]; // Initialize the array ... // Place the mines at the beginning for ( int i = 0; i < n; ++i ) { mines = true; } // Randomly distribute the mines for ( int i = 0; i < n; ++i ) { int pos = i + rand() % ( ARRAY_SIZE - i ); std::swap( mines, mines[pos] ); } Antheus, unless I misinterpreted your algorithm, it doesn't work. I think mine is similar to what you were trying to describe.
Or, you could just create an array with all the possible locations, then shuffle it and pick the 20 first from it.
Your original algorithm is kinda bad, because even if it's unlikely, it could theoreticly go on forever. If not forever, it could go on for quite some time if you attempt to pick a large number of locations from a slightly larger set (for example, if you tried to pick 99 of 100). However, I think Antheus solution is better for your purpose (however, n should be used instead of array size in step 3, and element at position n should be used instead of last element in the last step).
Your original algorithm is kinda bad, because even if it's unlikely, it could theoreticly go on forever. If not forever, it could go on for quite some time if you attempt to pick a large number of locations from a slightly larger set (for example, if you tried to pick 99 of 100). However, I think Antheus solution is better for your purpose (however, n should be used instead of array size in step 3, and element at position n should be used instead of last element in the last step).
Quote:Original post by JohnBoltonmines in a 1D array with an even distribution. You can easily extend it to 2D.
This method places n
I like it. It seems to be exactly backwards (instead of shuffling references-to-positions and then assigning mines to the first few, you assign mines to the first few locations and then shuffle them), but it's actually logically equivalent (as long as you accept that the inverse of a random permutation is just as validly random a permutation).
That said, though... if we're going to use std::swap, why not go all the way with the standard algorithms? :)
bool mines[ ARRAY_SIZE ];std::fill(mines, mines + n, true);std::random_shuffle(mines, mines + ARRAY_SIZE);Quote:Antheus, unless I misinterpreted your algorithm, it doesn't work. I think mine is similar to what you were trying to describe.
What he means is to have a vector of positions, and remove a position each time it is used for a mine (so that the remaining positions will be used with equal probability for the next selection). Except that he implements the "removal of position" by swapping the last element of the vector into the "hole" - a common trick.
Agony's way is also interesting, and unique. (I think you can prove the validity of it by induction, but I'm not about to try). It reminds me of something Larry Wall once advocated for pulling a random line out of a fortune file, so that you don't have to read the whole file (just up to the line you pick) or store the whole file in memory. His algorithm was basically the special case of Agony's for one "mine": for each line, pick it with probability 1/(remaining lines in file including the current one). Of course, you still have to count the lines in the file, so...
(Unfortunately, random_sample_n didn't make the cut for C++. But then, that would just give you a sequence of mine positions and you'd still have to place them, so it isn't quite appropriate here anyway.)
I'm not sure why I didn't think of this before, but you don't have to initialize your cells before using my algorithm. Just modify it a bit like so:
unsigned int remainingCells = p;unsigned int remainingMines = q;unsigned int cellIndex = 0;while (remainingCells > 0){ if (random(1, remainingCells) <= remainingMines) { cell[cellIndex].HasMine = true; --remainingMines; } else { cell[cellIndex].HasMine = false; } --remainingCells; ++cellIndex;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
