探索游戏中的迷宫很有趣，但是玩多了就没有“新鲜感”了吗？没错，如果游戏迷宫相差不大，时间久了很容易熟悉地图，会降低探索的乐趣。现在，“凭空出现”的概率编程语言MarkovJunior解决了这个问题：利用马尔可夫算法随机生成batch迷宫，每一个迷宫都不重复，你永远不知道下一个迷宫长什么样子：不仅2D迷宫，但即使是3D迷宫，需要搭建好几层地图也可以随机生成：这个项目一出，立马登上GitHub热榜，不到一个小时就已经收获了2.6kStars星期。有网友感叹，使用这种编程语言可以直接生成RPG游戏或动作游戏的建筑。Keras的作者对这种概率编程语言也很感兴趣：让我们看看它的原理是什么，它是如何随机生成各种迷宫的。基于马尔可夫算法的构建据作者介绍，这套概率编程语言借鉴了马尔可夫算法（Markovalgorithms）。（MarkovJunior这个名字也是以提出马尔可夫算法的数学家AndreyMarkov命名的。）具体来说，这套概率编程语言由一系列特定的规则（RewriteRules，重写规则）组成，它们是一个有序列表。在生成（迷宫）模型的过程中，它会使用马尔可夫算法实现“随机生成”，然后通过制定一系列特定的规则来确定生成模型的类别，比如迷宫、地形图、或电路图。马尔可夫链具有“无记忆”的特性，即下一状态的概率分布只能由当前状态决定，时间序列中它之前发生的事件与其无关。那么，这些具体规则是什么样的呢？例如，最简单的规则之一是将“黑色”色块重写为“白色”色块，直到最终填充整个模型：例如，将“白-黑”色块执行为“白-白””色块规则，结合马尔可夫算法，可以得到一个概率生成模型：再比如，根据“推箱子游戏”的规则，△推箱子游戏可以利用这批小红点随机“携带”白色方块”到指定位置：还有很多像这样的特定规则，都包含在MarkovJunior中。那么，我们如何使用这些规则来生成随机（迷宫、电路图等）模型呢？2D/3D迷宫、地形图、电路图均可绘制首先，以随机生成的2D迷宫为例：从图中可以看出，该迷宫算法会自动生成一个“起点”红点，随机探索并改写路径，以及最终填满整个地图，完成一个有起点、终点和岔路口的“迷宫”。这样的随机迷宫，MarkovJunior很容易做出来，只需要根据两条规则：第一条规则，将“红-黑-黑”色块随机改写成“绿-绿-红”色块。第二条规则，当第一条规则“卡住”，即没有符合条件的选项时，自动执行随机重写“红-绿-绿”色块为“白-白-红”色块.这样算法就可以通过第一条规则生成一条随机路径，利用第二条规则回溯没有经过的路径，生成分岔路口，最后遍历整个黑图，生成一组“二维迷宫””。还有一个更简单的思路，把所有的“白-黑-黑”换成“白-A-白”，其中A是中间状态，不作为起点，在迷宫生成后换成白色。据作者介绍，使用这个规则，1行代码可以随机生成一个2D或3D迷宫。▲3D迷宫就是基于这种思路，改变规则组合方式，也可以生成随机地形图。例如，如果你尝试生成河流的地形图，你只需要使用上面的生成模型方法并添加一些其他的重写规则来创建随机河流图：除了地形图，简单的2D/3D迷宫，而且更复杂的3D建筑也可以做，只需要在两个2D“迷宫”之间的随机位置生成一批“楼梯”：嗯，连电路图都可以画出来。。。据作者介绍，只要这些灵活运用规则，你可以用MarkovJunior随机生成各种建筑物和图片。可以说是非常受用了。同样是著名的WFC算法的作者，MaximGumin，这种概率编程语言的作者，是一名独立游戏开发者。他做过的最著名的项目应该是一组叫做“WaveFunctionCollapse”（WFC）的东西，目前在GitHub上有18.7kStars。这套WFC算法是他受量子力学中“波函数坍缩”概念启发而创造的。它已经被应用到一些游戏中，例如《城镇叠叠乐》（Townscaper）。MaximGumin并没有透露更多关于他自己的信息，但我们可以在他的主页上看到，这位老人称自己为“概率模型之王，程序生成的救世主，驯服马尔可夫链的人……”（手动狗head）从GitHub的角度来看，这些年来他一直专注于将各种数学算法应用到程序化生成中，做出各种有趣的模型。也许你玩过的一些游戏已经使用了他开发的算法。项目地址：https://github.com/mxgmn/MarkovJunior
