什么是程序生成？

程序生成包括许多生成算法，其原理不是手动创建数据，而是通过算法：不是手动制造我们要创建的内容（地图，音乐，地形...），而是编写了一种算法，该算法可以成功创建各种示例而无需多次执行相同的过程。 这种方法在可以随机生成整个地图或关卡的视频游戏中特别有用（例如，Minecraft，Terraria或Factorio中的地图，或大多数无赖游戏中的关卡方案）。

波动函数崩溃算法及其适用范围

在本文中，我们检查了 Maxim Gumin提出的波动函数折叠算法（WaveFunctionCollapse，WFC） （他的Twitter收集了其他开发人员使用此算法创建的惊人内容！）用于通过创建与输入图像局部相似的图像来生成图像或地形给定大小的网格中的图像。

该算法基于逐步创建完成图像的想法，并跟踪哪个图块“对应”于已经部分构建的图像。 要研究该算法的详细描述，建议您参考Github上的原始WFC存储库，以及文章“ WaveFunctionCollapse是约束在野外求解 ”的第四部分。


程序生成的种子图像的示例

除了创建相似的图像外，WFC算法的另一个应用领域是生成拼贴卡。 平铺地图的生成将是本文的主要主题，因为它更易于使用来清晰地解释我们的想法。 除了示例图像之外，您只能存储可以相互连接的磁贴和成对的磁贴。 在这种情况下，该算法可用于创建类似于以下所示图像的图像。


随机生成的图块示例

挑战与我们的解决方案

我们承担了根据棋盘游戏Carcassonne （“ Carcassonne”）生成磁贴卡的任务，在该游戏中，玩家是由玩家“手动”（请参见下面的动画）从必须相互组合的磁贴生成该场的。


令人惊讶的是，从概念上讲，这与WFC算法非常相似，该算法通过在不完整的解决方案中添加新零件来创建任意拼贴卡。 由于WaveFunctionCollapse可用作拼贴卡生成器，因此它也可以生成“ Carcassonne”字段！

但是，在游戏本身中，有太多不同的图块，因此对所有比例进行编码对于24小时黑客马拉松来说是一项非常繁琐的任务。 因此，我们决定播放非常简化的“卡尔卡松”版本，没有城堡和河流，只有道路，草地和修道院。 因此，我们获得了6个可能的图块，这些图块具有旋转和对称性。 但是即使在这样的条件下，结果看起来也很漂亮，看起来像是在卡尔卡松的真实游戏！


卡尔卡松场算法填充的可视化


算法中引入的规则示例

上图包含添加到算法中的输入规则的示例。 但是，我们仍然需要控制字段外观的某些方面。 该算法是否应该从充满修道院的道路和类似于城市的道路上创建“街道”，还是应该由草地和周围散布着村庄的土地组成？ 在原始算法中，无法控制这些条件（就像其他条件一样），但是出于控制的可能性，有可能进行简单的改进。

贝叶斯先验概率分布

如上所述，在每个步骤中，算法都会向字段中添加新的图块，以便与已放置的图块匹配，但是我们没有说如果可以在所选位置放置几个不同的图块会发生什么（我们也没有谈论如何通常选择这个地方，但是在本文中我们不会考虑它！）。 在原始算法中，均匀地随机选择任何合适的图块。 但是，在我们的决定中，我们更喜欢特定的瓷砖，例如草，这样它在田间更经常出现。 这可以通过创建不均匀的“概率先验”地砖分布来实现，如果可以使用两种类型的地砖，则与道路相比，使用草的机会更大。 这让人联想到贝叶斯技术。 在草和道路这两个选项之间进行选择的简化情况下，我们可以添加概率为p> 0.5的草，而不是通常概率为0.5的草。 通过为每个图块分配一个优先级值并使用该值将概率设置为一个值，该值除以所有可能图块的值之和即可轻松地概括该任务。 下图显示了两个系数值非常不同的合适解决方案，使您可以了解算法的敏感性。


不同的初始先验概率分布的不同解决方案

另一个例子：条件概率和分组

您可以扩展这个想法，并举例说明，我们将生成Minecraft矿石的二维地图，而不是Carcassonne字段。 Minecraft中通常会在大型地层中发现不同类型的矿石，因此，在设置每种矿石的概率的同时，我们将使概率取决于已放置在地图上的邻居。 即使在煤旁边，已经放置的煤旁边，铁的排列没有“禁止”，对另一种煤也给予较高的优先权。

尽管在下面的图像中没有考虑到这一点，但是在游戏中，概率还取决于图块的高度，因此图像中的位置也会影响图块概率的分布条件。


WFC创建的Minecraft矿石图块地图示例

结论

程序生成是一个值得拥有的强大工具。 特别是WFC在世界范围内得到了积极的应用，值得考虑的是新图块的分布可能不均匀并且可能受其他因素影响的可能性，例如，已放置在地图上的邻居，新图块和图像中的位置。 我们创建了一个非常简单的应用程序，但是开发的可能性几乎是无限的！