哈Ha！
作为俄罗斯市场上
Unity的 立法者 ，我们为您提供有关WFC（波动函数崩溃）算法实际使用的有趣研究报告，该算法建立在量子力学众所周知的原理的图像和相似之处上，非常便于在游戏中生成关卡的过程。 早在Habré上，有关该算法的
详细故事已经发布。 今天的文章的作者玛丽安·克莱恩伯格（Marian Kleineberg）在三维图形和无休止的城市生成的背景下考虑了该算法。 祝您阅读愉快！
我们将讨论一种游戏，在该游戏中，您会穿越无尽的城市，而这个城市是随着移动而生成的。 使用WFC算法（波动函数折叠）从一组街区构建城市。
可播放的程序集可从
itch.io网站上下载。 您也可以
在github上获取
源代码 。 最后，我提出一个
视频，在其中我漫步于由此产生的城市。
演算法
我将“单元”一词称为3D体素网格元素，它可以包含一个块或为空。 我将称呼“模块”一词为一个可以占据这样一个单元的块。
该算法决定在游戏世界的每个单元中选择哪个模块。 单元阵列被认为是不可观察形式的波函数。 因此，每个单元对应于可能出现在其中的许多模块。 就量子力学而言，可以说“该单元是所有模块的叠加”。 世界的存在是以完全不可观察的形式开始的，每个单元中都可以存在任何模块。 此外，所有细胞都崩溃了。 这意味着对于每个单元，从所有可能的单元中随机选择一个模块。
下一步是约束传播。 对于每个模块，选择允许与其相邻的模块子集。 每次模块崩溃时，都会更新其他模块的子集，但仍允许与其相邻。 就计算能力而言，限制的传播阶段是该算法最耗资源的部分。
该算法的重要方面是确定要崩溃的单元格。 该算法总是使具有
最小熵的单元崩溃。 这是一个允许进行最少选择的单元（即，随机性最小的单元）。 如果所有模块的崩溃概率都相同，则具有最小数量可能模块的单元将具有最低的熵。 通常，对于各种可用模块，被选择的概率是不同的。 与具有两个模块的模块相比，具有两个可能模块的模块具有相同的概率提供了更大的选择范围（更大的熵），对于其中一个模块，落入选择范围的概率非常高，而对于另一个模块而言，概率很小。
（由
ExUtumno在Github上发布的Gif）
在此处可以找到有关波动函数塌陷算法的更多详细信息，以及许多漂亮的示例。 最初，提出了该算法用于基于单个样本生成2D纹理。 在这种情况下，根据示例中模块和邻接规则的出现来确定它们的概率指示符。 本文手动提供此信息。
这是一个演示该算法的
视频 。
关于模块，原型和模块
世界由其中约100个街区组成的集合产生。 我使用Blender创建了它们。 刚开始时，我只有几个街区，当我认为必要时，我会一点一点地添加它们。
该算法需要知道哪些模块可以彼此相邻放置。 对于每个模块，都有6个可能的邻居列表，每个方向一个。 但是，我希望避免手动创建此类列表。 另外，我想为每个模块自动生成旋转选项。
使用所谓的原型模块可以解决这两个任务。 本质上，这是
MonoBehaviour ，在Unity编辑器中使用起来很方便。 基于此类原型，将自动创建模块以及有效的相邻元素列表和旋转选项。
建模邻接信息会引起一个复杂的问题，因此该自动过程可以正常工作。 这是我得到的：
每个块有6个触点，每个面一个。 联系人有一个电话号码。 另外，水平触点可以颠倒，不颠倒或对称。 垂直触点的旋转指数在0到3的范围内，或者标记为
旋转不变的 。
基于此，我可以自动检查允许哪些模块组合在一起。 相邻的模块必须具有相同的引脚号。 它们的对称性也必须重合（相同的垂直旋转指数，一对反向和非反向水平触点），或者模块必须对称/不变。
有一些排除规则可以禁止默认情况下允许的邻居选项。 一些带有匹配联系人的街区在附近看起来很难看。 这是在不应用异常规则的情况下生成的映射的示例：
通往无限的方式
原始的波函数塌陷算法生成有限尺寸的图。 我想建立一个随着您的前进而不断扩展的世界。
最初，我尝试生成有限大小的片段，并使用相邻片段的接触作为限制。 如果生成了一个片段，并且还生成了一个与其相邻的片段，则仅允许此类模块适合于现有模块。 通过这种方法，会出现以下问题：每当一个单元崩溃时，限制的传播都会减少机会，即使距离多个单元也是如此。 下图显示了折叠单个单元格的效果：
如果在算法的每个步骤中仅生成一个片段，则限制不适用于相邻片段。 在这种情况下，在片段内选择了这样的模块，如果考虑其他片段，这将是不可接受的。 结果，当算法尝试生成下一个片段时，它找不到单个解决方案。
现在，我不再使用片段，而是将地图存储在字典中，该字典显示单元在单元上的位置。 仅在必要时才填充单元格。 考虑到这一点，应调整算法的某些元素。 选择应该折叠的单元格时，如果单元格的数量是无限的，则不可能考虑所有单元格。 相反，一旦玩家到达地图，我们一次只会生成一小部分地图。 在这一地区之外，限制继续蔓延。
在某些情况下，这种方法不起作用。 从上图考虑隧道直段的一组模块-隧道没有入口。 如果算法选择了这样的隧道模块，那么根据定义，该隧道将是无限的。 在分配限制的阶段，程序将尝试分配无限数量的像元。 我开发了一组特殊的模块来解决此问题。
边界条件
有两个重要的边界条件。 地图顶层的所有面孔都必须具有“空中”接触。 地图底部的所有面孔都必须具有“固定”接触。 如果不满足这些条件，则在地图上地面上将有孔，并且某些建筑物将没有屋顶。
在有限大小的地图上，此问题将很容易解决。 对于处于最高和最低级别的所有单元，有必要删除所有接触不良的模块。 然后开始分发限制并删除不再适合我们的其余模块。
在无限大小的地图上，这是行不通的，因为无论在最高级别还是最低级别，我们都有无限数量的像元。 最幼稚的解决方案是在所有不适当的单元格出现时立即删除它们。 但是，在上级卸下模块时，限制条件适用于与其相邻的那些单元。 有雪崩效应，再次导致细胞的无限选择。
我通过创建1×n×1地图（其中n是高度）解决了这个问题。 这张地图使用世界包装来散布限制。 该机制的作用与游戏《吃豆人》中的游戏一样：超出地图的右边缘，角色由于左边缘而返回到地图。 现在，我可以对地图应用任何限制了。 每次您在无限地图上创建新的单元格时，都会使用一组对应于地图上特定位置的模块来初始化此单元格。
错误条件和返回搜索
有时，WFC算法达到一种状态，其中该单元不对应于任何可能的模块。 在我们要处理的世界有限的应用程序中，您可以简单地重置结果并重新开始。 在无限的世界中，这是行不通的，因为已经向玩家展示了世界的一部分。 首先，我确定了一个解决方案，在该解决方案中，发生错误的位置用白色块填充。
我目前正在使用退货搜索。 单元崩溃的顺序和有关限制分布的一些信息以历史记录的形式存储。 如果WFC算法失败，则部分历史记录将被取消。 通常，这是可行的，但是有时错误识别得太晚了，返回搜索涉及很多步骤。 在极少数情况下，会重新生成播放器所在的单元。
我认为，由于此限制，具有无限世界的WFC算法的应用不适用于商业游戏。
背景知识
在观看了
奥斯卡·斯泰尔伯格（Oscar Stelberg）关于他如何使用该算法在游戏Bad North中生成关卡
的演讲后，我开始着手这项任务。 通常，我的算法是在
procjam的一周内
实现的 。
我有一些进一步完善此算法的想法，但不确定是否有一天会添加游戏性。 而且，如果我聚在一起-当然，这将不是您已经想象的那样史诗般的策略。 但是，如果您想检查自己喜欢的游戏机制如何使用此算法，请自己尝试！ 最后，源代码是公开可用的，并由MIT许可。