1行代码生成随机迷宫，这个概率编程语言登GitHub热榜，作者曾开发著名WFC算法萧箫发自凹非寺量子位|公众号

萧箫发自凹非寺
量子位|公众号QbitAI
探索游戏中的迷宫很有趣，然而玩多了就没啥“新鲜感”了？
没错，如果游戏迷宫差别不大，时间一久就容易熟悉地图，降低了探索的乐趣。
现在，一个“横空出现”的概率编程语言MarkovJunior解决了这一问题：
利用马尔科夫算法，随机生成批量迷宫，没有一个是重复的，你永远也不知道玩到的下一个迷宫长什么样子：

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

文章图片
这个项目一出，立刻上了GitHub热榜，不到一周就已经收获2.6kStar 。
有网友感叹，用这个编程语言就能直接给RPG游戏或动作游戏生成建筑了。
Keras的作者也对这个概率编程语言挺感兴趣：

文章图片
来看看它的原理究竟是什么、又是如何随机生成各种迷宫的。
基于马尔科夫算法构造
据作者介绍，这套概率编程语言借鉴了马尔科夫算法（Markovalgorithms）。
（MarkovJunior这个名字，也是以提出马尔科夫算法的数学家AndreyMarkov命名）
具体来说，这套概率编程语言由一系列特定规则（RewriteRules ，重写规则）组成，是一个有序列表。
它在生成一个（迷宫）模型的过程中，会利用马尔科夫算法实现“随机生成” ，再通过制定一系列特定规则，决定生成模型的类别，例如是迷宫、地形图，还是电路图等。
马尔科夫链具有“无记忆”性质，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。
所以，这些特定规则究竟长啥样？
例如，一个最简单的规则，就是将“黑色”色块重写为“白色”色块，直到最终填满整个模型：

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

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

文章图片
△推箱子游戏
就能用这批小红点随机将白色方块“搬运”到指定地点：
像这样的特定规则还有很多，都包含在MarkovJunior中。
那么，我们究竟要怎么利用这些规则，来生成一个随机（迷宫、电路图等）模型呢？
2D/3D迷宫、地形图和电路图都能画
先以随机生成一个2D迷宫为例：

文章图片
从图片中来看，这个迷宫算法会自动生成一个“起始点”红点，在一块黑色地图中随机探索并重写路径，最终填满整个地图，完成一个有始有终、也有分岔口的“迷宫” 。
这样的随机迷宫， MarkovJunior随手就能做出一大把，只需要基于两个规则：
第一个规则，将“红-黑-黑”色块随机重写为“绿-绿-红”色块。
第二个规则，在第一个规则被“卡住” ，也就是没有符合条件的可选项时，自动执行将“红-绿-绿”色块随机重写为“白-白-红”色块。
这样一来，算法就能通过第一个规则生成随机路径，并通过第二个规则回溯还没有经过的路径、生成岔路口，最终遍历整个黑色地图，生成一套“2D迷宫” 。