Randomly Generate Mines On A Grid

$.25 & Bytes

Webmastering & Programming
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
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
 Joined
 Aug 24, 2004
 Letters
 2,700
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
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 notgenerate 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 valuei 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
 #6
 Joined
 Jun 1, 2004
 Messages
 484
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
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
# 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, performancewise) 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
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
...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]ardDCer of the Month  May 2006
 Joined
 Jun 26, 2004
 Letters
 12,776
This won't requite y'all exactly that number of mines; if that bothers you, then fixup by quitting when y'all take enough mines, or keeping a list of nonmine squares to reconsider if you terminate without placing enough.
 #15
mikeblas
[H]ardDCer of the Month  May 2006
 Joined
 Jun 26, 2004
 Messages
 12,776
So, you've got 100 squares and want to place 90 mines.
You visit the getgo 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 lesserright corner.
O
for the win!
 #16
 Joined
 Jan 9, 2001
 Messages
 6,413
 #17
mikeblas
[H]ardDCer 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, fiftyfifty 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]ardDCer of the Month  May 2006
 Joined
 Jun 26, 2004
 Letters
 12,776
{
{ 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.
 #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 10x10 grid of ninety mines.
So the random number generator works eh?=)
 #21
mikeblas
[H]ardDCer of the Month  May 2006
 Joined
 Jun 26, 2004
 Messages
 12,776
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/needadviceonrandomlyplacingmines.963130/