Sign in to follow this  
CzarKirk

Randon Placement of Mines

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
- 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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.
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.

Share this post


Link to post
Share on other sites
This method places n mines in a 1D array with an even distribution. You can easily extend it to 2D.
    bool mines[ ARRAY_SIZE ];

// Initialize the array

...

// Place the mines at the beginning

for ( int i = 0; i < n; ++i )
{
mines[i] = true;
}

// Randomly distribute the mines

for ( int i = 0; i < n; ++i )
{
int pos = i + rand() % ( ARRAY_SIZE - i );
std::swap( mines[i], mines[pos] );
}


Antheus, unless I misinterpreted your algorithm, it doesn't work. I think mine is similar to what you were trying to describe.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
Quote:
Original post by JohnBolton
This method places n mines in a 1D array with an even distribution. You can easily extend it to 2D.


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.)

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by JohnBolton
This method places n mines in a 1D array with an even distribution. You can easily extend it to 2D.


bool mines[ ARRAY_SIZE ];

std::fill(mines, mines + n, true);

std::random_shuffle(mines, mines + ARRAY_SIZE);


The advantage to my method is that you don't have to create extra data. You just shuffle the mines directly. Of course, it doesn't work very well if the elements contain other data which cannot be moved.

I didn't suggest std::fill simply because I rarely use it (old dog, new tricks ...).

I didn't suggest std::random_shuffle because there is no need to shuffle the entire array.


Share this post


Link to post
Share on other sites
Thanks for all the suggestions. I have decided to go with DvDmanDT's suggestion, because it seems the simpliest and easiest!


srand((unsigned)time(0));
vector<uint> placementlist(size);
setall(placementlist, i, size);
random_shuffle(placementlist.begin(), placementlist.end());
forall(i, mines)
mine[placementlist[i]] = true;

setall is a macro to set all elements of the array to i, and forall is a macro to go from 0 to mines with i (because I get fed up with writing out for loops all the time!)

Share this post


Link to post
Share on other sites
Quote:
Original post by CzarKirk
setall is a macro to set all elements of the array to i


Don't do that. The standard library provides std::generate() for a reason.


// put this in "your library" instead of the macro (modified very slightly
// from the SGI docs):
#include <algorithm>

template <typename T>
struct counter {
typedef T result_type;
result_type n;

public:
counter(result_type start = result_type()) : n(start) {}
result_type operator()() { return n++; }
};

// Now you can do this, without any of the usual problems with macros:
std::generate(placementlist.begin(), placementlist.end(), counter<bool*>(mine));
// Notice that I actually store pointers to positions of the mine array,
// rather than integers. This helps with the second step...
// (Also notice that for example if the map were stored in a std::list - a
// horrible idea, but you can imagine a similar task where a std::list is the
// appropriate storage and we have to randomly distribute values within it -
// then we could generate() a vector of list::iterators with no problem, since
// list::iterators support that post-increment.)



Quote:
and forall is a macro to go from 0 to mines with i


Don't do that. The standard library provides std::for_each() for a reason.


// put this in "your library":
template <typename Iterator, typename Value>
class assign_at : public unary_function<void, Iterator> {
Value v;
public:
assign_at(const Value& v) : v(v) {}
void operator()(Iterator iterator) { *iterator = v; }
};

// Now you can use std::for_each to replace this particular kind of for-loop:
std::for_each(placementlist.begin(), placementlist.end(), assign_at(true));



In general, for loops can be factored out in this sort of way; where it doesn't seem worth the effort (because the class isn't easily designed for reuse), you're almost certainly still going to be better off writing the for loop manually than using a macro. Macros are text-substitution hacks that don't have any understanding of the language, and can cause strange things to go wrong. Using them requires a better reason than this - it basically requires "ordinary language features simply can't do what's needed".

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this