Random Algorithms in Games

When I have free time, I like to play some classic 2D web games. I found that many games need to randomly generate maps. For example, in Minesweeper, the mines should be randomly placed:

Or in the classic Bomberman game, the position of obstacles is also random:

These 2D games may look simple compared to modern 3D games, but they still use many interesting algorithm techniques. In this article, we will explore the algorithm for random map generation in 2D games.

The map of a 2D game can be represented as a 2D matrix. Take Minesweeper as an example. We can use the following class to represent the board:

class Game {
    int m, n;
    // 2D board with size m * n
    // true means there is a mine, false means no mine
    boolean[][] board;
}

At the start of the game, we need to randomly generate k mines on the board. That means we need to generate k different (x, y) coordinates in the board, and both x and y are random.

For this task, the first optimization is to "flatten" the 2D matrix into a 1D array:

class Game {
    int m, n;
    // 1D board with length m * n
    // true means there is a mine, false means no mine
    boolean[] board;

    // Convert 2D coordinates (x, y) to 1D index
    int encode(int x, int y) {
        return x * n + y;
    }

    // Convert 1D index to 2D coordinates (x, y)
    int[] decode(int index) {
        return new int[] {index / n, index % n};
    }
}

With this, picking a random number in [0, m * n) is the same as picking a random cell in the 2D board.

But now, we need to randomly select k different positions for the mines. You might say, just pick k random numbers in [0, m * n).

Yes, but this is actually a bit tricky, because it is hard to make sure the random numbers are all different. If you get a duplicate number, you have to pick again until you have k different numbers.

If k is small and m * n is large, the chance of duplicates is low. But if k is close to m * n, the chance of picking duplicates is very high, and the algorithm will become much slower.

So, is there a better way to solve this problem in linear time? Yes, there are several solutions.

Shuffle Algorithm

Reservoir Sampling Algorithm

Monte Carlo Verification Method

Further Exploration