Randomly Generate Mines On A Grid

  • $.25 & Bytes

  • Webmastering & Programming

You are using an out of appointment browser. It may not brandish this or other websites correctly.
You should upgrade or use an culling browser.

Need communication on randomly placing mines


  • Thread starter
    JohnleMVP

  • Start engagement

  • #1
Joined
May twenty, 2001
Letters
v,255


So I have a minesweeper game and desire to identify mines randomly on the board. The basic way of doing this is to generate a random x and a random y and checking to encounter if the space is empty earlier you place the mine and if its not empty try again (new random # ). This method works well until you take a low ratio of spaces to mines. Say you accept 90 mines and 100 spaces its going to be ho-hum.

My question is what other ways tin can I go about this to make it faster no matter how many mines at that place are?

One idea I had was after you get to a certain indicate (say 40% filled) put the remaining spots into some sort of list/array and randomly pick form that.

  • #2

r00k

Joined
Aug 24, 2004
Letters
2,700


Why non

generate x numbers randomly from 0 to 99 ( or 1 to 100 depending on how you call up)
utilise a counter to add i to itself until it reaches 99
each increase check to see if its current value is == to one of those numbers
if it is not equal to any of those, place a mine in that location
if it is equal to 1 of those 10, don’t place a mine,
move on to next value

i know this is crude, but the thought of the algorithm is at that place.

edit: in vb (for example) this would lend itself very well to the employ of an assortment x by 10 spaces where the spaces are preplaced

  • #3
Joined
Apr 11, 2005
Messages
179


Uncomplicated, there are two ways to practice this. Simple may depend on your language of choice.

1. Create an list of pointers to every square. Randomly pick 1 (rand mod listing size or something like). Set the square information technology points to to be a mine and remove it from the list. Repeat until y’all have placed the proper number of mines.

ii. Set the start ten squares to be mines. Randomly selection any two squares and bandy their mine values. Repeat until deemed sufficiently shuffled (your call).

Both of these operations will have a predetermined runtime (roughly, the rng can provide variance of a few cycles) given grid size x and mine count y. Option 1 will probably run faster, and can easily support special squares (ones that can’t have mines for case) while Option 2 may exist simpler to implement.

  • #iv
Joined
Apr 11, 2005
Messages
179


Why not

generate x numbers randomly from 0 to 99 ( or 1 to 100 depending on how you recollect)
use a counter to add together one to itself until it reaches 99
each increase check to see if its electric current value is == to one of those numbers
if it is not equal to any of those, identify a mine in that location
if it is equal to 1 of those x, don’t place a mine,
movement on to adjacent value

i know this is rough, but the idea of the algorithm is there.

edit: in vb (for instance) this would lend itself very well to the use of an array 10 past 10 spaces where the spaces are preplaced

This is essentially the same algorithm the OP was using, you still take to worry about duplicates from the random number generator. A simpler interpretation of this is:

If less than 50% will be mines, use OP’due south algorithm, else presume all are mines and utilise OP’s algorithm to determine places without mines.

  • #5
Joined
Mar ix, 2004
Messages
iii,322


Fill your board with ten mines and so shuffle the board?

  • #6
Joined
Jun 1, 2004
Messages
484


A C# Example. (I didn’t exercise much fault checking)

                            using System; using Organisation.Collections.Generic; using System.Text;  namespace ConsoleApplication1 {     class Program     {         private const int WIDTH = 10;         private const int Acme = x;         individual const int NUM_MINES = 10;          static void Main(string[] args)         {             List< Pair<int, int> > choices = new List< Pair<int, int> >();               // Generate all possibilities             for (int i = 0; i < HEIGHT; i++)                 for (int j = 0; j < WIDTH; j++)                     choices.Add(new Pair<int, int>(i, j));              // Print them out             foreach (Pair<int, int> p in choices)                 Console.WriteLine(p);                          // Randomize. I opted to only go up to NUM_MINES             // to save on the number of swaps you lot accept to do.             // This is besides bold that NUM_MINES is less than             // the number of available choices.             Random rnd = new Random();             for (int i = 0; i < NUM_MINES; i++)             {                 int idx = rnd.Next(i, choices.Count);                                  // Swap 'i' and 'idx'                 Pair<int, int> tmp = choices[i];                 choices[i] = choices[idx];                 choices[idx] = tmp;             }              // Impress out the Mine Locations             for(int i = 0; i < NUM_MINES; i++)                 Console.WriteLine(choices[i]);                    }     }      form Pair<T1, T2>     {         public T1 first;         public T2 2nd;          public Pair(T1 f, T2 s)         {             first = f;             2nd = southward;         }          public override string ToString()         {             return Cord.Format("({0}, {1})", outset, 2d);         }         } }
                          

[edit] I really should refresh before I post. Still, even even so it’s a rough implementation of Earp’s #2 pick. Also, it’s similiar to the above poster’due south implementation equally well. [ /edit]

  • #7
Joined
Oct 24, 2002
Letters
47


ane. Create an listing of pointers to every square. Randomly pick one (rand modern listing size or something similar). Set the square it points to to be a mine and remove it from the listing. Repeat until you have placed the proper number of mines.

.:)

  • #8
Joined
May 20, 2001
Messages
5,255


Cheers for all your help. I make up one’s mind to go with the pointers in a list.

Earps #two is a pretty adept idea likewise, only I wasn’t certain how random it would cease up. (depends on how long I do it of grade)

  • #9
Joined
Jan 9, 2001
Letters
6,413


1. Create an list of pointers to every foursquare. Randomly option one (rand mod list size or something similar). Ready the square it points to to be a mine and remove it from the list. Repeat until you have placed the proper number of mines.

This seems like the manner to get to me – put all the squares in a ‘pocketbook’ and draw notwithstanding many you want out. It works for Bingo & Lotto…

  • #ten
Joined
Apr 11, 2005
Messages
179


Cheers for all your help. I decide to go with the pointers in a listing.

Earps #2 is a pretty good idea as well, but I wasn’t certain how random it would end upwardly. (depends on how long I do it of course)

Algorithm #i should be faster, especially when there are few mines. It would by my personal option, just because I tend to be a performance Nazi
:)

Algorithm #ii should provide a sufficiently shuffled grid if you shuffled three or 4 times the total number of tiles.

  • #11
Joined
Jun 29, 2004
Messages
11,455


I had a sort of like situation to #two for a shuffle program I wrote (take entries from a playlist and randomize the club), hither’s Perl for that:

                            # Make an @list to be shuffled my %pair; for $item (0..$#list)  { # Make map of randval -> listpos pairs   $pair{$item} = rand(1);  } foreach $key (sort { $pair{$a} <=> $pair{$b} } keys %pair)  { #  print "$central = $pair{$cardinal}\n";   push @temp, $primal;  } for (0..$#temp)  {   print # $temp[$_], " ",         $list[$temp[$_]];  }
                          

This is sort of the elongated version; it’due south possible (and probably desirable, performance-wise) to do information technology without and so many temps. The RNG can generate dupes if information technology wants to; other entries merely go sorted around the duplicates, and the pairs of duplicates still happen in random order, so information technology’s still pretty good in terms of not generating the same combinations twice.

  • #12
Joined
May 31, 2005
Messages
864


how bout starting at a random location, and so incrementing the position till you find a spot that isn’t chosen? i’m not sure what adverse furnishings this will yeild in terms of randomness, just it guarantees a number of iterations rougly equal to the number of positions every time (although i suppose each iteration now has a worse case of 99-i operations, 1 for every possible position).

come to call up of information technology, this sounds strikingly similar to a particular data construction unremarkably used in C++, i just can’t remember what. a cyclical linked list? i dont recollect, simply i exercise recall a slight amending of the method i suggested which greatly reduced the amount of clumping (thus increasing the randomness of the algorithm). perhaps someone more than versed in the subject can fill in the details.

  • #thirteen
Joined
Dec 12, 2003
Messages
943


I don’t call back much OOP, but how about something like this… (Assuming a 10×10 grid as an example)

…basically nosotros try to randomly select as few places every bit possible. So instead of randomly selecting 90 places to put mines, we select 10 places (100 places – 90 mines = 10 clear places) to clear of mines… Nosotros should hopefully not run into randomly selecting a place that is already “placed” and forces us to endeavour again since the worse instance is odds of placement being 49:100 (one or 99 mines) instead of 1:100 (99 mines).

Definitions:
You have a part to articulate the unabridged board of mines…and set a “mines” variable to false.
You have a office to fill the entire board with mines…and set a “mines” variable to true.
Yous have a part to randomly toggle a square’s “landmine” variable…but information technology checks the “mines” variable to determine if it should toggle the square or not.

To set a board with mines (1):
You have an if..else structure such that…
…if in that location are >50 mines to identify information technology uses the function to fill the board with mines.
…if there are <50 mines to place it uses the function to articulate the board of mines.

To set a lath with mines (2):
Your function to randomly toggle a foursquare’s “landmine” variable goes and does its chore while checking the squares against a “mines” variable to encounter if that square was set or not.

  • #14

mikeblas

[H]ard|DCer of the Month – May 2006

Joined
Jun 26, 2004
Letters
12,776


If y’all know at that place are south squares and m mines, then you lot know the probability of a particular square having a mine is yard/southward. So for each mine, become a floating-point real between 0 and one and see if information technology is greater than m/s. If so, place a mine, else clear the mine.

This won’t requite y’all exactly that number of mines; if that bothers you, then fix-up by quitting when y’all take enough mines, or keeping a list of non-mine squares to reconsider if you terminate without placing enough.

  • #15

mikeblas

[H]ard|DCer of the Month – May 2006

Joined
Jun 26, 2004
Messages
12,776


Hrm. Or, just adjust the ratio.

So, you’ve got 100 squares and want to place 90 mines.

You visit the get-go site, and your random number is 0.92. That’s greater than xc/100, and so you don’t place a mine. You decrement the denominator merely.

Yous visit the next site, and your random number is 0.85. That’due south less than xc/99, so you identify a mine. You decrement the numerator and the demoniator.

If your fraction ever reaches 1.0, then you lot ever place a mine.

And so on. This means the last few sites you visit are more likely to accept the “catch upwards” mines, so maybe y’all should kickoff walking the cells at a random location so the “end” isn’t always the lesser-right corner.

O(n)
for the win!

  • #16
Joined
Jan 9, 2001
Messages
6,413


merely, as you said, you terminate upward with clusters of mines towards the end of the run. Occassionally running into big clusters is OK (and to be expected from a random distribution) just, if you lot consistantly accept big clusters, fifty-fifty if the location of the clusters varies, I think that would detract from playability.

  • #17

mikeblas

[H]ard|DCer of the Month – May 2006

Joined
Jun 26, 2004
Messages
12,776


only, equally you said, you stop up with clusters of mines towards the finish of the run. Occassionally running into large clusters is OK (and to be expected from a random distribution) merely, if you consistantly have large clusters, fifty-fifty if the location of the clusters varies, I think that would backbite from playability.

Any solution is going to be but as adept as its random number generator.

I’1000 not positive I’m correct about the clusters. If the distribution is even throughout the rest of the field, so the last few sections will be just as distributed. A perfectly even distribution isn’t random, anyhow.

Thinking of the algorithm I suggested, it constantly has an even distribution of the remaining mines over the remaining squares. Does that mean at that place’s a clump on the bottom right? Only if all the squares previously populated are sparse.

I implemented what I suggested; when I get dorsum dwelling, I tin can test it out and see how the distribution works out.

  • #xviii

mikeblas

[H]ard|DCer of the Month – May 2006

Joined
Jun 26, 2004
Letters
12,776


I ran a 1000000 iterations, summing the count of mines in each jail cell, for a 10×10 filigree of 90 mines. Hither’due south the numbers:

{
{ 9001534, 8999409, 9000132, 8999815, 9000070, 8999747, 9000520, 8997190, 9000360, 9000654},
{ 8998988, 8999812, 9001305, 8998712, 8998874, 8999717, 8999464, 9000025, 8999757, 9000480},
{ 9000089, 8999368, 9000401, 9001594, 8999262, 9000085, 9000679, 8999005, 9000063, 8998238},
{ 9000415, 9001502, 9001073, 8999024, 8999926, 8999923, 9000441, 9000175, 8998499, 8997773},
{ 9000659, 9000307, 9000290, 8999689, 8999796, 9001319, 8999963, 9000357, 8999860, 8999673},
{ 8999987, 9000229, 9000311, 9001449, 9000711, 8999758, 9000216, 9000500, 8998005, 8998579},
{ 9000633, 9001910, 9000101, 8999929, 9001305, 9000340, 8999469, 9001648, 8999535, 9000232},
{ 9000264, 8999821, 8998345, 9000348, 9000287, 9000398, 8998938, 8999635, 8999023, 8999398},
{ 8999158, 8998666, 8998805, 9000922, 9001221, 8999471, 8998870, 8999152, 8998844, 9000249},
{ 9001544, 9000776, 9000237, 9001003, 8999724, 9000786, 9000148, 8999977, 9001126, 9002004},
}

And here’due south the graph; sorry it’due south so crappy — it’due south my beginning 3d chart in Mathematica. The lesser right two squares are loftier, but not abnormally high compared to other alpine spots on the graph.

MineDistribution.jpg

  • #19
Joined
April 11, 2005
Messages
179


come to think of it, this sounds strikingly similar to a particular data structure commonly used in C++, i only can’t remember what. a cyclical linked list? i dont remember, but i do remember a slight alteration of the method i suggested which greatly reduced the amount of clumping (thus increasing the randomness of the algorithm). perhaps someone more versed in the subject area can fill in the details.

Yous’re thinking of an implementation of a Hashtable. The variance is to use a quadratic office (i think) instead of simply incrementing. Yet, this variance requires that the length of the assortment be prime, so that yous tin can reach every cell. This would non exist possible for a square map.

  • #20
Joined
Mar 9, 2004
Messages
3,322


I ran a million iterations, summing the count of mines in each cell, for a 10×10 grid of ninety mines.

So the random number generator works eh?=)

  • #21

mikeblas

[H]ard|DCer of the Month – May 2006

Joined
Jun 26, 2004
Messages
12,776


Sorry if I wasn’t articulate; the bespeak was that my algorithm works, without a clump at the end as I had originally feared. It runs in anticipated, O(n)
time over the cells.

Funny thing is, the generator I used was this:

double d = rand() / double(RAND_MAX);

and if you accept a expect at the distribution of that part (using the VC++ rand function) you’ll detect that information technology ends upward existence pretty poor. I don’t think it would exist hard to researh lawmaking for a more appropriate generator, if not a better 1.

  • #22
Joined
May 31, 2005
Messages
864


You’re thinking of an implementation of a Hashtable. The variance is to use a quadratic function (i call back) instead of simply incrementing. However, this variance requires that the length of the array exist prime, so that you tin can accomplish every cell. This would non be possible for a square map.

ahh, in that location we become. thanks.

  • Bits & Bytes

  • Webmastering & Programming


Source: https://hardforum.com/threads/need-advice-on-randomly-placing-mines.963130/

Check Also

Will Dogecoin Go Up In Value

Will Dogecoin Go Up In Value

On Dec. 6, 2013, Billy Markus and Jackson Palmer decided to combine their dearest of …