谈谈游戏中的随机算法
原创约 4261 字
Note
网站新增大量习题,新增排序算法专题及可视化,具体请查看 网站更新日志~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
382. Linked List Random Node | 382. 链表随机节点 | 🟠 |
384. Shuffle an Array | 384. 打乱数组 | 🟠 |
398. Random Pick Index | 398. 随机数索引 | 🟠 |
没事儿的时候我喜欢玩玩那些经典的 2D 网页小游戏,我发现很多游戏都要涉及地图的随机生成,比如扫雷游戏中雷的位置应该是随机分布的:
再比如经典炸弹人游戏,障碍物的位置也是有一定随机性的:
这些 2D 游戏相较现在的大型 3D 游戏虽然看起来有些简陋,但依然用到很多有趣算法技巧,本文就来深入研究一下地图的随机生成算法。
2D 游戏的地图肯定可以抽象成一个二维矩阵,就拿扫雷举例吧,我们可以用下面这个类表示扫雷的棋盘:
class Game {
int m, n;
// 大小为 m * n 的二维棋盘
// 值为 true 的地方代表有雷,false 代表没有雷
boolean[][] board;
}
如果你想在棋盘中随机生成 k
个雷,也就是说你需要在 board
中生成 k
个不同的 (x, y)
坐标,且这里面 x, y
都是随机生成的。
对于这个需求,首先一个优化就是对二维矩阵进行「降维打击」,把二维数组转化成一维数组:
class Game {
int m, n;
// 长度为 m * n 的一维棋盘
// 值为 true 的地方代表有雷,false 代表没有雷
boolean[] board;
// 将二维数组中的坐标 (x, y) 转化为一维数组中的索引
int encode(int x, int y) {
return x * n + y;
}
// 将一维数组中的索引转化为二维数组中的坐标 (x, y)
int[] decode(int index) {
return new int[] {index / n, index % n};
}
}
这样,我们只要在 [0, m * n)
中选取一个随机数,就相当于在二维数组中随机选取了一个元素。
但问题是,我们现在需要随机选出 k
个不同的位置放雷。你可能说,那在 [0, m * n)
中选出来 k
个随机数不就行了?
是的,但实际操作起来有些麻烦,因为你很难保证随机数不重复。如果出现重复的随机数,你就得再随机选一次,直到找到 k
个不同的随机数。
如果 k
比较小 m * n
比较大,那出现重复随机数的概率还比较低,但如果 k
和 m * n
的大小接近,那么出现重复随机数的概率非常高,算法的效率就会大幅下降。
那么,我们有没有更好的办法能够在线性的时间复杂度解决这个问题?其实是有的,而且有很多种解决方案。