谈谈游戏中的随机算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 382. Linked List Random Node | 🟠 |
| 384. Shuffle an Array | 🟠 |
| 398. Random Pick Index | 🟠 |
In my free time, I enjoy playing classic 2D web games. I've noticed that many of these games involve random map generation. For example, in Minesweeper, the positions of the mines should be randomly distributed:
Similarly, in the classic Bomberman game, the placement of obstacles also has a certain degree of randomness:
Although these 2D games may seem simple compared to modern 3D games, they still employ many interesting algorithmic techniques. In this article, we will delve into the algorithms used for random map generation.
The map of a 2D game can certainly be abstracted as a two-dimensional matrix. Taking Minesweeper as an example, we can use the following class to represent the Minesweeper 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 one-dimensional array
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 array
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.