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

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

本文经AI新媒体量子位（公众号ID:QbitAI）授权转载，转载请联系出处。

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

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

现在，一个“横空出现”的概率编程语言 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