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

公司 来源:IT之家   阅读量:13458    2022-06-08 08:42

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

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

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

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

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

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

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

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

基于马尔可夫算法的构造

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

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

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

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

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

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

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

推箱子游戏

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

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

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

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

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

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

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

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

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

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

3D迷宫看起来像这样

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

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

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

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

可以说非常好用。

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

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

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

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

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

项目地址:

免责声明:市场有风险,选择需谨慎!此文仅供参考,不作买卖依据。

友情合作