[程式] Wave Function Collapse 随机地图产生

楼主: dklassic (DK)   2020-12-24 13:17:29
因为自己在做游戏的缘故,开始研究各种省钱(?)的开发手段,趁等待的空档打一篇教
学文简易积积阴德。其中最重要的一个就是关卡编辑与自动化关卡产生。
总之因为没有时间与人力制作从头制作关卡,所以不如想个办法自动化产生关卡。
这部分目前最实用的手段就叫做 Wave Function Collapse。
可能很多人的印象最深刻的例子是来自这个 Github:
https://github.com/mxgmn/WaveFunctionCollapse
我个人则是从 Oskar Stalberg 2018 年的演讲入坑的:
https://www.youtube.com/watch?v=0bcZb-SsnrA
从这边听个大概,似懂非懂很难理解,剩下很多片段都是在实作过程中才理解。
最后得到的结论就是 Wave Function Collapse 听起来很厉害,但具体意义就是“有设定
好条件的暴力解”,只要掌握这个精随什么都很好实作。
以下是具体的实作方法。
总之 Wave Function Collapse 比较简单的做法是对规则形状的物件做。
为了方便举例就以方形举例。
1. 定义单位方块的属性
例如在我的实作测试中作了一个简单的墙壁、地板组合,单元如下:
https://imgur.com/KnZSeeI
接着要详细实作规则定义,基本上就是定义要有怎样的 Tag 的物件才能接上。
https://imgur.com/bGUxUDk
以这边的例子来说就是要把墙壁的区域对接、地板的区域对接。
就写个 Script 来定义这些属性。
2. 生成环境
首先当然是产生一些 Empty Game Object 来存放各个单元。
就把预先做好的单元在每个格子都塞好一份:
https://imgur.com/rhw1pOb
https://imgur.com/uXcaEj1
上图塞四份是因为我懒得纪录各个单元的旋转版本,所以就直接复制四份。
虽然应该算是没效率四倍,但是因为好写又没有即时的需求就这样做了。
也因为复制四倍这种因素,产生过程中都直接把 Renderer 关好关满。
3. 开始崩塌(Collapse)
这边是个循环,基本过程就是
3a. 寻找熵(Entropy)最低的格子
简单来说就是可选选项最少的格子。
如果机率都一样的话就用随机。
3b. 崩塌该格
基本上是随机崩塌,也就是从可选选项中随机选一个出来用。
3c. 更新邻居的熵
因为将一格的未来确定之后,附近邻居可以与该格接起来的选项就变少了。
所以要更新选项、熵值。
所以每做一个循环就会像这样:
https://imgur.com/bcqgiEc (执行前)
https://imgur.com/srRPTd5 (执行后)
会崩塌一格,并且让周边邻居的可能性变少。
接着就无限执行循环直到每一格的未来都决定好:
https://imgur.com/bQCUMnL.mp4 (崩塌全程录影)
实作上就是如此的朴实无华。
此外的延伸议题有:
1. 错误应对
简单来说根据你单块选项、衔接规则的设计,可能会出现某个位置完全没有选项能与周边
衔接。这时候有两种做法。
1a. 正解-回溯变更
简单来说就是既然有问题,就试着让前一步变成别的方块看看。
这部分最好多一些辅助,像是“随着错误次数越多,回溯的步数也增加”。
根据随机机率,早晚会生出一个可以完全解开的版本。
1b. 懒人-错误侦测与重来
简单来说就是只侦测错误,而撞到错误就重来。
这个方法实作上比较简单,但是比较没效率。而且根据规则写得完备程度越差,撞到错误
而必须重来的次数可能也会增加,是个危险的做法。
而随着方块的总量越多,单次产生所需要的时间也越来越长,为了避免大量的时间都被浪
费在重新产生,写个踏实的历史步骤纪录系统也比较重要。
2. 可用程度侦测
根据关卡需求,可能要写一些自动化的条件来侦测关卡的可用程度。
例如说各方块通行区域的连通程度等等,加深自动化的有效性。
也同样可以在可用程度过低的时候直接重新产生,不用浪费时间,更不用人力检查。
3. 预先设计条件加强可用程度
以我游戏需求,我只写了确保边缘一定是墙壁的机制。
但延伸可以考虑的面向就包含:
a. 整张地图的连通程度(有没有房间被隔开无法通行)
b. 可通行区域的面积
这些当然都是写侦测比较简单,要写出可靠的解法比较难。
就看专案需求来决定要走好写但是产生过程比较困难,或者是确保可以产生出来但比较难
写的版本。
4. 三维化
目前我写的版本只用了两维,不过其实三维的概念也是一模一样的,只是边界衔接条件精
细度可能要写比较多。事前准备稍微复杂点但概念还是一致。
5. 多核心化
老实说我还不太确定怎样平行化比较好 XD
总之大概是这样,老实说整个过程做起来还是很简单,我弄出第一个可以产生的程式只花
了十个小时左右。不过过程中还是各种想要寻求细节实作的部分都没在网络上看到。
因此顺便在板上献一点微薄之力。
另一个我虽然没有开来看但是有开源的专案或许值得参考一下:
https://github.com/marian42/wavefunctioncollapse
因为有人问,所以我简单写了一个 Pseudo Code 提供参考:
https://pastebin.pl/view/2b6f80ed
之一的内容也就是基础产生,之二应该会讲如何把场景精细化的实用经验。
作者: wyvernlee (wyvernlee)   2020-12-24 13:27:00
强!
作者: ZooseWu (N5)   2020-12-24 14:44:00
好像挺好玩的
作者: oopFoo (3d)   2020-12-24 17:50:00
蛮有趣的,但一直用不上。
作者: johnny94 (32767)   2020-12-24 21:13:00
推推
作者: cmcer (lazyman)   2020-12-24 23:00:00
Diablo-like或不思议迷宫类型很容易会用到
作者: yukari8 (林檎)   2020-12-25 09:43:00
推个
作者: a82611141   2020-12-26 17:24:00
作者: megah321   2020-12-29 10:28:00
作者: wangm4a1 (水兵)   2020-12-29 17:18:00
作者: MaxWei (想下象棋可以找我喔~)   2020-12-30 08:59:00
感谢分享,虽然现在还没用到但一直满有兴趣这题目的
作者: rickkcir (多果汁)   2019-01-05 19:31:00
感谢分享,看起来很酷
作者: yellowd54321 (YellowD)   2019-01-23 00:18:00
推 随机地图真的有趣

Links booklink

Contact Us: admin [ a t ] ucptt.com