0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

说透游戏中常用的两种随机算法

算法与数据结构 来源:labuladong 作者:labuladong 2022-11-09 11:17 次阅读

没事儿的时候我喜欢玩玩那些经典的 2D 网页小游戏,我发现很多游戏都要涉及地图的随机生成,比如扫雷游戏中地雷的位置应该是随机分布的:

e7b652ca-5fdc-11ed-8abf-dac502259ad0.jpg

再比如经典炸弹人游戏,障碍物的位置也是有一定随机性的:

e7d12dac-5fdc-11ed-8abf-dac502259ad0.jpg

这些 2D 游戏相较现在的大型 3D 游戏虽然看起来有些简陋,但依然用到很多有趣算法技巧,本文就来深入研究一下地图的随机生成算法。

2D 游戏的地图肯定可以抽象成一个二维矩阵,就拿扫雷举例吧,我们可以用下面这个类表示扫雷的棋盘:

classGame{
intm,n;
//大小为m*n的二维棋盘
//值为true的地方代表有雷,false代表没有雷
boolean[][]board;
}

如果你想在棋盘中随机生成k个地雷,也就是说你需要在board中生成k个不同的(x, y)坐标,且这里面x, y都是随机生成的。

对于这个需求,首先一个优化就是对二维矩阵进行「降维打击」,把二维数组转化成一维数组

classGame{
intm,n;
//长度为m*n的一维棋盘
//值为true的地方代表有雷,false代表没有雷
boolean[]board;

//将二维数组中的坐标(x,y)转化为一维数组中的索引
intencode(intx,inty){
returnx*n+y;
}

//将一维数组中的索引转化为二维数组中的坐标(x,y)
int[]decode(intindex){
returnnewint[]{index/n,index%n};
}
}

这样,我们只要在[0, m * n)中选取一个随机数,就相当于在二维数组中随机选取了一个元素。

但问题是,我们现在需要随机选出k不同的位置放地雷。你可能说,那在[0, m * n)中选出来k个随机数不就行了?

是的,但实际操作起来有些麻烦,因为你很难保证随机数不重复。如果出现重复的随机数,你就得再随机选一次,直到找到k个不同的随机数。

如果k比较小m * n比较大,那出现重复随机数的概率还比较低,但如果km * n的大小接近,那么出现重复随机数的概率非常高,算法的效率就会大幅下降。

那么,我们有没有更好的办法能够在线性的时间复杂度解决这个问题?其实是有的,而且有很多种解决方案。

洗牌算法

第一个解决方案,我们可以换个思路,避开「在数组中随机选择k个元素」这个问题,把问题转化成「如何随机打乱一个数组」

现在想随机初始化k颗地雷的位置,你可以先把这k颗地雷放在board开头,然后把board数组随机打乱,这样地雷不就随机分布到board数组的各个地方了吗?

洗牌算法,或者叫随机乱置算法就是专门解决这个问题的,我们可以看下力扣第 384 题「打乱数组」:

e7eee2fc-5fdc-11ed-8abf-dac502259ad0.jpg

这个shuffle函数是算法的关键,直接看解法代码吧:

classSolution{
privateint[]nums;
privateRandomrand=newRandom();

publicSolution(int[]nums){
this.nums=nums;
}

publicint[]reset(){
returnnums;
}

//洗牌算法
publicint[]shuffle(){
intn=nums.length;
int[]copy=Arrays.copyOf(nums,n);
for(inti=0;i< n; i++) {
            //生成一个[i,n-1]区间内的随机数
intr=i+rand.nextInt(n-i);
//交换nums[i]和nums[r]
swap(copy,i,r);
}
returncopy;
}

privatevoidswap(int[]nums,inti,intj){
inttemp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}

洗牌算法的时间复杂度是 O(N),而且逻辑很简单,关键在于让你证明为什么这样做是正确的。排序算法的结果是唯一可以很容易检验的,但随机乱置算法不一样,乱可以有很多种,你怎么能证明你的算法是「真的乱」呢?

分析洗牌算法正确性的准则:产生的结果必须有n!种可能。这个很好解释,因为一个长度为n的数组的全排列就有n!种,也就是说打乱结果总共有n!种。算法必须能够反映这个事实,才是正确的。

有了这个原则再看代码应该就容易理解了:

对于nums[0],我们把它随机换到了索引[0, n)上,共有n种可能性;

对于nums[1],我们把它随机换到了索引[1, n)上,共有n - 1种可能性;

对于nums[2],我们把它随机换到了索引[2, n)上,共有n - 2种可能性;

以此类推,该算法可以生成n!种可能的结果,所以这个算法是正确的,能够保证随机性。

水塘抽样算法

学会了洗牌算法,扫雷游戏的地雷随机初始化问题就解决了。不过别忘了,洗牌算法只是一个取巧方案,我们还是得面对「在若干元素中随机选择k个元素」这个终极问题。

要知道洗牌算法能够生效的前提是你使用数组这种数据结构,如果让你在一条链表中随机选择k个元素,肯定不能再用洗牌算法来蒙混过关了。

再比如,假设我们的扫雷游戏中棋盘的长和宽非常大,已经不能在内存中装下一个大小为m * nboard数组了,我们只能维护一个大小为k的数组记录地雷的位置:

classGame{
//棋盘的行数和列数(非常大)
intm,n;
//长度为k的数组,记录k个地雷的一维索引
int[]mines;

//将二维数组中的坐标(x,y)转化为一维数组中的索引
intencode(intx,inty){
returnx*n+y;
}

//将一维数组中的索引转化为二维数组中的坐标(x,y)
int[]decode(intindex){
returnnewint[]{index/n,index%n};
}
}

这样的话,我们必须想办法在[0, m*n)中随机选取k个不同的数字了。

这就是常见的随机抽样场景,常用的解法是水塘抽样算法(Reservoir Sampling)。水塘抽样算法是一种随机概率算法,会者不难,难者不会。

我第一次见到这个算法问题是谷歌的一道算法题:给你一个未知长度的单链表,请你设计一个算法,只能遍历一次,随机地返回链表中的一个节点。

这里说的随机是均匀随机(uniform random),也就是说,如果有n个元素,每个元素被选中的概率都是1/n,不可以有统计意义上的偏差。

一般的想法就是,我先遍历一遍链表,得到链表的总长度n,再生成一个[0,n-1)之间的随机数为索引,然后找到索引对应的节点。但这不符合只能遍历一次链表的要求。

这个问题的难点在于随机选择是「动态」的,比如说你现在你已经遍历了 5 个元素,你已经随机选取了其中的某个元素a作为结果,但是现在再给你一个新元素b,你应该留着a还是将b作为结果呢?以什么逻辑做出的选择,才能保证你的选择方法在概率上是公平的呢?

先说结论,当你遇到第i个元素时,应该有1/i的概率选择该元素,1 - 1/i的概率保持原有的选择。看代码容易理解这个思路:

/*返回链表中一个随机节点的值*/
intgetRandom(ListNodehead){
Randomr=newRandom();
inti=0,res=0;
ListNodep=head;
//while循环遍历链表
while(p!=null){
i++;
//生成一个[0,i)之间的整数
//这个整数等于0的概率就是1/i
if(0==r.nextInt(i)){
res=p.val;
}
p=p.next;
}
returnres;
}

对于概率算法,代码往往都是很浅显的,但是这种问题的关键在于证明,你的算法为什么是对的?为什么每次以1/i的概率更新结果就可以保证结果是平均随机的?

我们来证明一下,假设总共有n个元素,我们要的随机性无非就是每个元素被选择的概率都是1/n对吧,那么对于第i个元素,它被选择的概率就是:

e80b8b14-5fdc-11ed-8abf-dac502259ad0.png

i个元素被选择的概率是1/i,在第i+1次不被替换的概率是1 - 1/(i+1),在第i+2次不被替换的概率是1 - 1/(i+2),以此类推,相乘的结果是第i个元素最终被选中的概率,也就是1/n。因此,该算法的逻辑是正确的。

同理,如果要在单链表中随机选择k个数,只要在第i个元素处以k/i的概率选择该元素,以1 - k/i的概率保持原有选择即可。代码如下:

/*返回链表中k个随机节点的值*/
int[]getRandom(ListNodehead,intk){
Randomr=newRandom();
int[]res=newint[k];
ListNodep=head;

//前k个元素先默认选上
for(inti=0;i< k && p != null;i++){
res[i]=p.val;
p=p.next;
}

inti=k;
//while循环遍历链表
while(p!=null){
i++;
//生成一个[0,i)之间的整数
intj=r.nextInt(i);
//这个整数小于k的概率就是k/i
if(j< k) {
            res[j] = p.val;
        }
        p = p.next;
    }
    returnres;
}

对于数学证明,和上面区别不大:

e81eac12-5fdc-11ed-8abf-dac502259ad0.png

虽然每次更新选择的概率增大了k倍,但是选到具体第i个元素的概率还是要乘1/k,也就回到了上一个推导。

类似的,回到扫雷游戏的随机初始化问题,我们可以写一个这样的sample抽样函数:

//在区间[lo,hi)中随机抽取k个数字
int[]sample(intlo,inthi,intk){
Randomr=newRandom();
int[]res=newint[k];

//前k个元素先默认选上
for(inti=0;i< k; i++) {
        res[i] = lo + i;
    }

    inti=k;
//while循环遍历数字区间
while(i< hi - lo) {
        i++;
        //生成一个[0,i)之间的整数
intj=r.nextInt(i);
//这个整数小于k的概率就是k/i
if(j< k) {
            res[j] = lo + i - 1;
}
}
returnres;
}

这个函数能够在一定的区间内随机选择k个数字,确保抽样结果是均匀随机的且只需要 O(N) 的时间复杂度。

蒙特卡洛验证法

上面讲到的洗牌算法和水塘抽样算法都属于随机概率算法,虽然从数学上推导上可以证明算法的思路是正确的,但如果你笔误写出 bug,就会导致概率上的不均等。更神奇的是,力扣的判题机制能够检测出这种概率错误。

那么最后我就来介绍一种方法检测随机算法的正确性:蒙特卡洛方法。我猜测力扣的判题系统也是利用这个方法来判断随机算法的正确性的。

记得高中有道数学题:往一个正方形里面随机打点,这个正方形里紧贴着一个圆,告诉你打点的总数和落在圆里的点的数量,让你计算圆周率。

e8484e00-5fdc-11ed-8abf-dac502259ad0.png

这其实就是利用了蒙特卡罗方法:当打的点足够多的时候,点的数量就可以近似代表图形的面积。结合面积公式,可以很容易通过正方形和圆中点的数量比值推出圆周率的。

当然,打的点越多,算出的圆周率越准确,充分体现了大力出奇迹的道理。

比如,我们可以这样检验水塘抽样算法sample函数的正确性:

publicstaticvoidmain(String[]args){
//在[12,22)中随机选3个数
intlo=12,hi=22,k=3;
//记录每个元素被选中的次数
int[]count=newint[hi-lo];
//重复10万次
intN=1000000;
for(inti=0;i< N; i++) {
        int[]res=sample(lo,hi,k);
for(intelem:res){
//对随机选取的元素进行记录
count[elem-lo]++;
}
}
System.out.println(Arrays.toString(count));
}

这段代码的输出如下:

[300821,299598,299792,299198,299510,300789,300022,300326,299362,300582]

当然你可以做更细致的检查,不过粗略看看,各个元素被选中的次数大致是相同的,这个算法实现的应该没啥问题。

对于洗牌算法中的shuffle函数也可以采取类似的验证方法,我们可以跟踪某一个元素x被打乱后的索引位置,如果x落在各个索引的次数基本相同,则说明算法正确,你可以自己尝试实现,我就不贴代码验证了。

拓展延伸

到这里,常见的随机算法就讲完了,简单总结下吧。

洗牌算法主要用于打乱数组,比如我们在快速排序详解及运用中就用到了洗牌算法保证快速排序的效率。

水塘抽样算法的运用更加广泛,可以在序列中随机选择若干元素,且能保证每个元素被选中的概率均等。

对于这些随机概率算法,我们可以用蒙特卡洛方法检验其正确性。

最后留几个拓展题目:

1、本文开头讲到了将二维数组坐标(x, y)转化成一维数组索引的技巧,那么你是否有办法把三维坐标(x, y, z)转化成一维数组的索引呢?

2、如何对带有权重的样本进行加权随机抽取?比如给你一个数组w,每个元素w[i]代表权重,请你写一个算法,按照权重随机抽取索引。比如w = [1,99],算法抽到索引 0 的概率是 1%,抽到索引 1 的概率是 99%,答案见我的这篇文章

3、实现一个生成器类,构造函数传入一个很长的数组,请你实现randomGet方法,每次调用随机返回数组中的一个元素,多次调用不能重复返回相同索引的元素。要求不能对该数组进行任何形式的修改,且操作的时间复杂度是 O(1),答案见我的这篇文章

审核编辑 :李倩


声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92844
  • 生成器
    +关注

    关注

    7

    文章

    315

    浏览量

    21003
  • 数组
    +关注

    关注

    1

    文章

    417

    浏览量

    25940

原文标题:说透游戏中常用的两种随机算法

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    苹果正在打造专为iOS用户设计的游戏中

     10月23日,据国外媒体报道,苹果公司正致力于开发一款新型应用程序,意在将App Store与Game Center的功能融为一体,打造一个专为iOS用户设计的游戏中心。
    的头像 发表于 10-23 16:00 858次阅读

    噪声传导的两种模式

    噪声传导有两种模式,一为差模传导,一为共模传导。
    的头像 发表于 10-15 11:33 286次阅读
    噪声传导的<b class='flag-5'>两种</b>模式

    晶闸管的阻断状态有两种是什么

    晶闸管(Thyristor)是一半导体器件,具有单向导电性,广泛应用于电力电子领域。晶闸管的阻断状态有两种:正向阻断状态和反向阻断状态。以下是对这两种阻断状态的分析。 正向阻断状态 正向阻断状态
    的头像 发表于 08-14 16:49 688次阅读

    PCBA加工中常见的两种焊接方式详解

    ,在PCBA行业中经常被使用。接下来深圳PCBA加工厂家为大家详细介绍PCBA加工手工焊接的两种方式,为您揭秘行业内的威廉希尔官方网站 细节。 PCBA加工过程中常用焊接方式 第一方式是传统手工焊接。这种方式主要依靠威廉希尔官方网站 工人的手动操作进行焊
    的头像 发表于 06-14 09:18 537次阅读

    轻松搞懂传和非传的区别

    传和非传是数据通信中的两种不同模式,各自有其适用场景和优势。传模式简单、高效,适用于数据完整性要求高的场景;非传模式则通过数据处理提
    的头像 发表于 06-05 12:03 9635次阅读
    轻松搞懂<b class='flag-5'>透</b>传和非<b class='flag-5'>透</b>传的区别

    充电桩为什么有直流与交流两种接口?

    充电桩设计有直流(DC)和交流(AC)两种接口,主要是为了适应不同类型的电动汽车(EV)充电需求以及电池的充电特性。
    的头像 发表于 04-30 15:33 1592次阅读

    Xbox应用新增“游戏中心”功能

    微软 Xbox 体验高级产品经理 Dylan Meade表示,“游戏中心”便于玩家追踪游戏进展,发现游戏最新内容和扩展包,与友人联机竞技,接收开发商的最新新闻等。
    的头像 发表于 02-27 14:02 678次阅读

    gis中常用的空间分析方法

    GIS中常用的空间分析方法 GIS(地理信息系统)是一用于收集、存储、处理、分析和展示地理数据的威廉希尔官方网站 。空间分析是GIS的核心部分,它包括一系列方法和威廉希尔官方网站 ,用来研究地理空间数据之间的关系和模式。本文
    的头像 发表于 02-25 13:44 5509次阅读

    异或门两种常见的实现方式

    两种实现方式都能够实现异或门的功能,具体的选择取决于设计需求和逻辑门的可用性。实际构建异或门时,可以使用离散电子元件(如晶体管、二极管等)或整合电路芯片(如 TTL、CMOS 等)来实现。
    的头像 发表于 02-04 17:30 1.2w次阅读
    异或门<b class='flag-5'>两种</b>常见的实现方式

    双绞线接法的标准有哪两种 双绞线使用什么端接头

    双绞线是一常用的网络传输介质,其接法标准有两种:直通接法和交叉接法。双绞线通常使用RJ45接头。 第一双绞线接法标准是直通接法,也称为直通连接。该连接方式使用相同的引脚对线缆的
    的头像 发表于 02-03 11:11 4482次阅读

    半导体存储器有哪些 半导体存储器分为哪两种

    半导体存储器(Semiconductor Memory)是一电子元件,用于存储和检索数据。它由半导体材料制成,采用了半导体威廉希尔官方网站 ,是计算机和电子设备中最常用的存储器。 半导体存储器可以分为两种
    的头像 发表于 02-01 17:19 3017次阅读

    想知道淮安掼蛋游戏中的RFID威廉希尔官方网站 有什么作用吗?

    在淮安,有一深受群众喜爱的扑克游戏,名为掼蛋。它是一融合了升级、跑得快等多种玩法的扑克游戏,具有极高的趣味性和竞技性。近年来,随着科技的不断发展,RFID威廉希尔官方网站 也开始在淮安掼蛋
    的头像 发表于 01-26 17:01 576次阅读

    加速度传感器常用的有哪两种

    加速度传感器常用的有两种,一是基于压电效应的压电式加速度传感器,另一是基于微机电系统(MEMS)威廉希尔官方网站 的微型加速度传感器。 压电式加速度传感器是利用压电晶体的压电效应来测量加速度的。
    的头像 发表于 01-15 15:27 1024次阅读

    分享两种简单的平衡电桥设备设计

    本文给出了两种简单的平衡电桥设备设计,借此即可对个电感进行高精度的比较。LED指示器或高阻抗电话耳机用作不平衡指示器。
    的头像 发表于 01-05 09:31 878次阅读
    分享<b class='flag-5'>两种</b>简单的平衡电桥设备设计

    电子电路中常用的元器件

    电容器、三极管和二极管是电子电路中常用的元器件,它们可以搭配使用以实现各种功能。下面将详细介绍它们的搭配使用方法和使用规范。 一、电容器 电容器是一能够存储电荷的被动元件,主要用于储存
    的头像 发表于 12-29 14:47 813次阅读