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

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

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

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

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

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

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

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

Keras的作者也对这种概率编程语言相当感兴趣:

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

基于马尔可夫算法的构造

据作者介绍，这套概率编程语言借鉴了马尔可夫算法。

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

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

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

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

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

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

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

推箱子游戏

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

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

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

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

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

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

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

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

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

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

根据作者的说法，使用这个规则，一行代码可以随机生成2D或3D迷宫。

3D迷宫看起来像这样

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

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

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

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

作者认为，只要灵活运用这些规则，MarkovJunior就可以随机生成各种建筑和图片。

可以说非常好用。

著名的WFC算法的作者。

马克西姆·顾敏，这种概率编程语言的作者，是一个独立的游戏开发者。

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

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

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

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

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

项目地址:

郑重声明：此文内容为本网站转载企业宣传资讯，目的在于传播更多信息，与本站立场无关。仅供读者参考，并请自行核实相关内容。