1 行代码生成随机迷宫，概率编程语言登 GitHub 热榜，作者曾开发著名 WFC 算法

探索游戏中的迷宫很有趣，然而玩多了就没啥“新鲜感”了？

没错，如果游戏迷宫差别不大，时间一久就容易熟悉地图，降低了探索的乐趣。

现在，一个“横空出现”的概率编程语言 MarkovJunior 解决了这一问题：

利用马尔科夫算法，随机生成批量迷宫，没有一个是重复的，你永远也不知道玩到的下一个迷宫长什么样子：

不仅是 2D 迷宫，就连需要搭建好几层地图的 3D 迷宫，也能随机生成：

这个项目一出，立刻上了 GitHub 热榜，不到一周就已经收获 2.6k Star。

有网友感叹，用这个编程语言就能直接给 RPG 游戏或动作游戏生成建筑了。

Keras 的作者也对这个概率编程语言挺感兴趣：

来看看它的原理究竟是什么、又是如何随机生成各种迷宫的。

基于马尔科夫算法构造

据作者介绍，这套概率编程语言借鉴了马尔科夫算法（Markov algorithms）。

（MarkovJunior 这个名字，也是以提出马尔科夫算法的数学家 Andrey Markov 命名）

具体来说，这套概率编程语言由一系列特定规则（Rewrite Rules，重写规则）组成，是一个有序列表。

它在生成一个（迷宫）模型的过程中，会利用马尔科夫算法实现“随机生成”，再通过制定一系列特定规则，决定生成模型的类别，例如是迷宫、地形图，还是电路图等。

马尔科夫链具有“无记忆”性质，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

所以，这些特定规则究竟长啥样？

例如，一个最简单的规则，就是将“黑色”色块重写为“白色”色块，直到最终填满整个模型：

又例如，执行将“白-黑”色块重写为“白-白”色块的规则，结合马尔科夫算法，就能得到一个概率生成模型：

再例如，基于“推箱子游戏”的规则，

△ 推箱子游戏

就能用这批小红点随机将白色方块“搬运”到指定地点：

像这样的特定规则还有很多，都包含在 MarkovJunior 中。

那么，我们究竟要怎么利用这些规则，来生成一个随机（迷宫、电路图等）模型呢？

2D / 3D 迷宫、地形图和电路图都能画

先以随机生成一个 2D 迷宫为例：

从图片中来看，这个迷宫算法会自动生成一个“起始点”红点，在一块黑色地图中随机探索并重写路径，最终填满整个地图，完成一个有始有终、也有分岔口的“迷宫”。

这样的随机迷宫，MarkovJunior 随手就能做出一大把，只需要基于两个规则：

第一个规则，将“红-黑-黑”色块随机重写为“绿-绿-红”色块。

第二个规则，在第一个规则被“卡住”，也就是没有符合条件的可选项时，自动执行将“红-绿-绿”色块随机重写为“白-白-红”色块。

这样一来，算法就能通过第一个规则生成随机路径，并通过第二个规则回溯还没有经过的路径、生成岔路口，最终遍历整个黑色地图，生成一套“2D 迷宫”。

还有更简单的思路，将所有“白-黑-黑”替换成“白-A-白”，其中 A 是一个中间态，不作为起点，在迷宫生成完成后被替换为白色。

据作者表示，利用这个规则，1 行代码就能随机生成 2D 或 3D 迷宫。

▲ 3D 迷宫长这样

基于这样的思路，换套规则组合方法，还能生成随机地形图。

例如，试图生成一块河流地形图，就只需要利用上面的生成模型方法，再添加一些其他的重写规则，就能搞出一个随机河流图来：

除了地形图、简单的 2D / 3D 迷宫，更复杂的 3D 建筑也能搞定，只需要在两层 2D“迷宫”之间的随机位置生成一批“楼梯”：

嗯，连电路图都能画……

据作者介绍，只要灵活运用这些规则，就能用 MarkovJunior 随机生成各种各样的建筑和图画。

可以说是非常好用了。

还是著名 WFC 算法的作者

这个概率编程语言的作者 Maxim Gumin，是一名独立游戏开发者。

他搞过最有名的项目，应该是一套叫做“波函数坍缩算法”（WaveFunctionCollapse，WFC）的东西，目前在 GitHub 上已经有 18.7k Stars。

这套 WFC 算法是他受量子力学中“波函数坍缩”概念的启发自创出来的，目前已经被应用到一些游戏中，如《城镇叠叠乐》（Townscaper）等。

Maxim Gumin 并未透露更多自己的信息，但我们能在他的主页上看到，这位老哥自称“概率模型之王，程序化生成の弥赛亚，驯服马尔科夫链的人……”（手动狗头）

从 GitHub 来看，这些年他一直专注于将各种数学算法应用于程序化生成中，做出各种有意思的模型。

说不定你玩过的游戏中，有一些已经用过他开发的算法了。

项目地址：

https://github.com/mxgmn/MarkovJunior

广告声明：文内含有的对外跳转链接（包括不限于超链接、二维码、口令等形式），用于传递更多信息，节省甄选时间，结果仅供参考，IT之家所有文章均包含本声明。