五月份的时候,差不多就是在比赛开始前吧,云杰说他刚学了一个做肉鸽随机地图生成很好的算法交波坍缩(也就是波函数坍缩)算法.他甚至写了个小demo来实现这个算法,唉,为什么我就做不到呢,就算是A*寻路算法也是看别人的面经提到说Unity NaviMesh用的算法是A*才去学了,就这也只是三脚猫功夫罢了根本就没有实操一下.

不发牢骚了,我先学学波坍缩

1.啥是波函数坍缩

波函数坍缩是一个量子力学上的概念,但是计算机领域借鉴了这个算法的思路,从而有了计算机上的波函数坍缩生成算法.

它是一种利用局部的现有信息随机外推到全局,形成一种随机的确定状态集合的方法.这种通过已有的信息推到全局的思路有点像动态规划或者贪心,它们的应用场景也是有重叠的.

简单来说,最开始的时候所有的状态都是不确定的,但是通过给定或者随机确定一些局部的而信息,和这些一直信息相关的单元的状态可以被确定,或者是更加靠近被被确定的状况.描述一个单元的状态确定程度的参数叫做"熵",这同样是借鉴了热物理的概念:熵是对混乱程度的描述.

b站上有个搬运视频讲的很好https://www.bilibili.com/video/BV19z4y127BJ 这个up主也贴心地附上原视频地址,就是不知道他搬运的时候有没有获得许可.

举个例子,数独大家都玩过,它其实就是波坍缩算法最好的应用场景,最开始每个格子上都有9种可能出现的数字,但是最初给定的几个数字限制了其中的一些可能,比如说,如果某个格子的数字是4,那么和它同行/列的所有格子都不可能出现4,这就是发生了塌缩,这些格子的熵降低了.

熵越低的单元,确定性越大,就越容易给定状态,所以我们确定状态时总会从熵低的单元开始,到数独里面就是,我们会从已有数字更多的行/列上的空格子填数字.一旦某个单元塌缩到确定的状态,那它就可以作为给定状态去影响和它有关的其他单元,或许会造成连锁反应.不断地确定更多状态,最终全局的所有状态都能确定,这时就算是完成塌缩了.

2.波函数坍缩在游戏中的应用

我能想到的最适合应用波坍缩的地方是随机地图生成.4月面4399的时候,周末加班的面试官问了我一个问题:对于神庙逃亡那样的跑酷游戏,它的每一段地图都是随机生成的,请你设计一种算法实现段地图生成,要求不允许出现死角.所谓死角就是在玩家无法认为躲避的区域,比如说,如果玩家必须跳过一个障碍,但是在障碍的落脚点处有一个陷阱,那么玩家无论如何都会死在这里,这就是死角.

当时我给出的算法是基于贪心 ,首先单元化道路,如果以神庙逃亡为例,那么用数据表现道路的话可以用一个num[3][x]二维数组表示,因为一般陷阱都是出现在左1/3,右1/3或者是中间1/3的.在(可能是随机)给定陷阱数量之后,在一条没有任何机关陷阱的道路上添加陷阱,每添加一种陷阱,就会将因该陷阱而产生的死角区域从二维数组中禁用,所以每次添加陷阱的可选择区域会越来越少,但是永远不会出现死角.

//我觉得我回答的挺好的啊,咋一面就挂了呢

现在想想,这种思路和波坍缩是共通的,在随机给出部分陷阱以后,和这些陷阱有关的区域,其可能选择的状态就坍缩成"平地"这一种状态了.所以,虽然波坍缩听起来很牛逼但本质上也是一种启发式的生成算法,没有听着那么高深莫测

另外一个例子是肉鸽地图生成,利用规则为地图单元提供约束,在给定初始数据(比如说种子)以后就能不断降低全局的熵,从而最终得到一个随机生成的确定状态地图.

3.实战:从1开始的基于波函数坍缩算法的随机地图生成器

为什么从1开始,因为我不是0(开个玩笑,我是直男)

设计一个使用若干瓦片组成的地图,地图中的元素只有道路,道路端点和草坪,要求是:所有的道路都必须有头有尾,不能中断,这句话是说,任何一条道路,无论它如何分叉,每一个尽头都要有一个端点,看看下面的瓦片和我的效果图就明白了:

下面6个瓦片是我要用到的素材,按照它们的特征,用他们四个方向的状态命名,如0100表示上右下左四个方向里,右边这个方向是道路,其他的是草坪

从图中可以看出来所有的道路都被灰色的端点限制住.

由于仅作学习,我没有严格的使用规范或是框架来规范化编码,所以只写了两个文件,我会尽可能解释的清楚一些的

3.1代码

• Slot.ts

每个瓦片单元的数据结构,需要注意的是,这个数据结构没有继承component,这是因为这个类被SlotManager类管理,生成对应的Node是由Manager负责,Slot在这里只是数据载体.

• SlotManager.ts

管理类,生成器的主逻辑都在这里

3.2效果展示

在cocos中设置好预制体,在节点上挂载脚本,然后启动即可

效果如下

最后我想说,虽然看起来挺简单的,不过想要在三维空间设计更加完善,精妙,生成效果更好的算法,其具体实现,比如约束,状态选择算法等会复杂的多,这里只是一个简单的尝试