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

游戏里探索迷宫很好玩，玩多了就没什么新了。

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

现在，概率编程语言MarkovJunior解决了这个问题:

使用马尔可夫算法，批量迷宫随机生成，无一重复。你永远不知道你玩的下一个迷宫会是什么样子:

它不仅是一个2D迷宫，还是一个3D迷宫，有几层地图，可以随机生成:

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

有网友感叹，这种编程语言可以直接为RPG游戏或者动作游戏生成建筑。

我们来看看它的原理是什么，如何随机生成各种迷宫。

基于马尔可夫算法的构造

具体来说，这种概率编程语言由一系列特定的规则组成，是一个有序列表。

在生成模型的过程中，它会利用马尔可夫算法实现随机生成，然后制定一系列特定的规则来确定生成模型的类型，比如迷宫，地形图或者电路图。

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

那么，这些具体的规则到底是什么样子的呢。

例如，最简单的规则之一是将黑色色块重写为白色色块，直到它最终填充整个模型:

例如，通过实现将白—黑色块重写为白—白色块的规则，并结合马尔可夫算法，可以得到一个概率生成模型:

再比如，基于推箱游戏的规则，

推箱子游戏

可以用这批小红点随机运送白方到指定地点:

像这样的具体规则还有很多，都包含在MarkovJunior里面。

那么，我们如何使用这些规则来生成随机模型呢。

2D/3D迷宫，可以绘制地形图和电路图。

以随机生成2D迷宫为例:

这样一个随机的迷宫，MarkovJunior手边能做出一把，只基于两条规则:

第一个规则是将红—黑—黑色块随机改写成绿—绿—红色块。

第二条规则，当第一条规则被卡住，即没有符合条件的选项时，自动执行，将红绿绿色块随机改写为白—白—红色块。

这样，算法可以通过第一条规则生成随机路径，回溯没有经过的路径，通过第二条规则生成分叉，最后遍历整个黑图生成一组2D迷宫。

有一个更简单的想法将所有白—黑—黑替换为白—A—白，其中A为中间状态，不作为起点，迷宫生成后替换为白色

3D迷宫看起来像这样

基于这一思想，通过改变规则组合方法，可以生成随机地形图。

比如尝试生成一个河流地形图，只需要使用上面的生成模型方法，再加上一些其他的重写规则，就可以得出一个随机的河流图:

除了地形图和简单的2D/三维迷宫，更复杂的三维建筑也可以做。只需要在两个2D迷宫之间的任意位置生成一批楼梯:

嗯，连电路图都能画出来…

可以说非常好用。

他做过最著名的项目应该是一套叫波函数坍缩算法的东西目前，GitHub上有18.7kStars

这个WFC算法是他受量子力学中波函数坍缩概念的启发而创造的，目前已经应用到一些游戏中，比如小镇折叠乐等等。

马克西姆·顾敏没有透露更多关于自己的信息，但我们可以在他的主页上看到，这位大哥自称概率模型之王，程序化的一代弥赛亚，马尔可夫链的驯服者。

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

可能你玩过的一些游戏已经用上了他开发的算法。

项目地址: