Random Algorithms in Games

In my free time, I enjoy playing those classic 2D web games, and I've noticed that many of these games involve random map generation. For instance, in Minesweeper, the placement of mines is randomly distributed:

Similarly, in the classic Bomberman game, the placement of obstacles also has a degree of randomness:

Although these 2D games may seem simple compared to modern large-scale 3D games, they still employ many interesting algorithmic techniques. This article will delve into the algorithms for random map generation.

The map of a 2D game can certainly be abstracted into a two-dimensional matrix. For example, in Minesweeper, we can use the following class to represent the game board:

class Game {
    int m, n;
    // a two-dimensional chessboard of size m * n
    // the places with value true represent mines, false means no mines
    boolean[][] board;
}

If you want to randomly generate k mines on a chessboard, it means you need to generate k different (x, y) coordinates in the board, where both x and y are randomly generated.

For this requirement, the first optimization is to "reduce dimensions" of the two-dimensional matrix, converting the 2D array into a 1D array:

class Game {
    int m, n;
    // a one-dimensional chessboard of length m * n
    // places with the value true represent mines, false means no mines
    boolean[] board;

    // convert the coordinates (x, y) in the
    // two-dimensional array to the index in the
    int encode(int x, int y) {
        return x * n + y;
    }

    // convert the index in the one-dimensional array to
    // the coordinates (x, y) in the two-dimensional
    int[] decode(int index) {
        return new int[] {index / n, index % n};
    }
}

This way, by choosing a random number from [0, m * n), it's equivalent to randomly selecting an element from a two-dimensional array.

However, the challenge is that we need to randomly select k unique positions to place mines. You might think, "Just pick k random numbers from [0, m * n)?"

Yes, that's true, but it's a bit tricky in practice because ensuring the random numbers are unique is difficult. If you get duplicate random numbers, you have to pick again until you find k unique ones.

If k is small and m * n is large, the probability of getting duplicate random numbers is low. But if k is close to m * n, the probability of duplicates is very high, significantly reducing the algorithm's efficiency.

Is there a better way to solve this problem in linear time complexity? The answer is yes, and there are several solutions available.