This is through the “minesweeper and algorithm” small procedures to explain the algorithm of the first chapter: how to randomize the mine, mainly introduced three not so good methods, hope that through these bad methods can let you understand the second chapter to explain the “shuffle algorithm” how awesome.

Addendum: Minesweepand Algorithms will be open source and posted on GitHub as soon as it’s finished.

Methods a

The most obvious method is to randomly find a point in the two-dimensional interval, the code is as follows:

for (var i = 0; i < mineNumber; i++) {
       var row = this.rangeRandom(0.this.rowCount - 1);
       var col = this.rangeRandom(0.this.colCount - 1);
       // Use the number 9 to indicate lightning in the area
       tmpMineMap[row][col] = 9;
 }
Copy the code

One drawback of this implementation logic is that mines will be laid again where they have already been laid, resulting in an insufficient number of mines for the entire area.

As shown above, the number of mines needed to be laid was five, but only four mines were laid in the last random laying process.

Method 2

Method 2 is an improvement on method 1: since it will bury mines repeatedly, it is only necessary to determine whether the location has been mined during the process of reburying mines.

  • If the location is empty, a mine is laid, and a new location is sought to lay the next mine
  • If the location is already mined, a new location needs to be generated to be mined

The code is as follows:

   for (var i = 0; i < mineNumber; i++) {
      // Keep searching through an endless loop until you have placed thunder
      while (true) {
        var row = this.rangeRandom(0.this.rowCount - 1);
        var col = this.rangeRandom(0.this.colCount - 1);
        // Use the number 9 to indicate that the area is mined, if the location is not mined, then it is placed
        if(tmpMineMap[row][col] ! =9) {
           tmpMineMap[row][col] = 9;
           // Break the loop
           break; }}}Copy the code

The use effect is as follows:

It seems to work well, but as some of you may have noticed, there is an infinite loop in the code above, which means that if the checkerboard is too big, the minefield is too big, and you are not lucky enough, you can keep executing the infinite loop, causing the program to freeze and crash.

Methods three

The third method is to place the mines first, and then constantly disrupt them.

The implementation code is as follows:

// Take the order first
for (var i = 0; i < mineNumber; i++) {
    var row = parseInt(i / this.colCount);
    var col = i % this.colCount;
    // Use the number 9 to indicate lightning in the area
    tmpMineMap[row][col] = 9;
}

// Define the number of swaps, the more the more chaotic random
var swapTime = 100;
for (var i = 0; i < swapTime; i++) {
    // random position 1
    var row1 = this.rangeRandom(0.this.rowCount - 1);
    var col1 = this.rangeRandom(0.this.colCount - 1);
    // random position 2
    var row2 = this.rangeRandom(0.this.rowCount - 1);
    var col2 = this.rangeRandom(0.this.colCount - 1);
    // Switch two positions
    var temp = tmpMineMap[row1][col1];
    tmpMineMap[row1][col1] = tmpMineMap[row2][col2];
    tmpMineMap[row2][col2] = temp;
}
Copy the code

One drawback of this method is that it is highly dependent on swapTime. If the number of interactions is set less, most of the thunder is still placed in the first order, and all the thunder is not randomly discharged.

The most important point is that the probability of placing a mine at each location is not equally likely, which means it cannot be randomized.

I have tried probability simulation on the small program, but every time stuck, later found that can optimize to continue to simulate the probability to make up.

conclusion

In most cases, method 2 and Method 3 can satisfy our randomization process, but method 2 May run stuck and crash, and the probability of placing mines in each position of method 3 is not equally possible.

❤️ Three things to watch:

If you find this article inspiring, I’d like to invite you to do me three favors:

  • Like, so that more people can see this content (collection does not like, is a rogue -_-)
  • Follow me and the column and make it a long-term relationship
  • Pay attention to the public number “five minutes to learn the algorithm”, the first time to read the latest algorithm article, the public number back to 1024 send you 50 algorithm programming books.