这是一个简单的游戏，你可以在一个无限延申的城市里行走，这个城市是用波函数塌缩算法从一堆blocks中生成的。

  你可以在marian42.itch.io/wfc上下载该游戏，在 github.com/marian42/wavefunctioncollapse 下载该游戏的源代码。

The algorithm

  插槽（slot）表示3D网络中可以可以包含方块（block，也可为空）的位置，模块（module）表示可以嵌入到slot中的block。

  波函数塌缩算法为游戏世界中每个插槽选择合适的模型。slots数组被视作是一个不可观测状态下的波函数。这意味着每个插槽都对应着一组可能的、可匹配的模块。用量子力学术语描述，可以说“插槽是所有模块的量子叠加态（The slot is in superposition of all modules）”。

  世界起始于未被观察状态中，此时每个模块都有可能出现在任意的插槽中（概率相等）。一个接一个，每个插槽都会塌缩成确定状态。这意味着，模块是随机挑选出来的。接下来的步骤是加上一个约束传播：

• 对每个模块，只允许将其一个子集放置在附近。一个插槽不论何时塌缩，其模块子集仍可以在需要更新的插槽中使用。

  约束传播步骤是算法中计算量最大的部分。

  波函数塌缩算法的核心就是选择哪一个插槽会发生塌缩。该算法总是选择具有最小熵的插槽进行塌缩：

• 即该插槽的可选择项最少（或混乱度）；

• 如果所有模块具有相同的概率，则可能模块数量最小的插槽的熵最小。

• 一般来说，每个模块都有不同的被选择概率。一个拥有两个相同概率的模块的插槽比拥有一个大概率和一个小概率的模块的插槽有更多的选择（更大的熵）。

About blocks, prototypes and modules

  这个游戏由100个左右的blocks生成，由blender制作。从几个block开始，逐渐形成整个城市。

  算法需要知道哪些模块可以相邻放置。每个模块有6个可能的邻居列表，每个方向一个。但我不想手工创建这个列表。我还想找到一种自动生成块的旋转变量的方法。    

  两者都可以通过使用我称之为模块原型（module prototypes）的方法来实现。这是一个可以在Unity编辑器中方便地编辑的MonoBehaviour。模块以及允许的邻域列表和旋转变量都是从这些模块中自动创建的。

  一个难点是如何建模邻接信息来使这套自动方法行之有效。我的方法是：

  为每个block的每个面设置一个连接器，连接器有一个数字id。水平连接器可以翻转、不翻转或对称旋转。垂直连接器的旋转索引在0和3之间（屏幕截图中为b、c、d），或者它们被标记为无法旋转的。

  基于此，我可以自动检查哪些模块允许相邻。相邻模块必须具有相同的连接器编号。并且它们的对称性必须匹配（垂直方向相同的旋转索引，水平翻转和不翻转的一对），否则它们必须对称/不变。

  此外，还设置了一些排除规则，来禁止掉那些拼接起来不太好看的blocks。以下是不使用排除规则生成的地图的示例：

Reaching infinity

  原始的波函数塌缩算法只能生成有限的地图，这里我要地图随着玩家的走动而实时、无限生成。

  我的第一种方法是生成有限大小的块，并使用相邻块的连接器作为约束。如果生成了块，并且已经生成了相邻的块，则只允许与现有模块相匹配的模块存在。这种方法的问题是，当一个插槽塌缩时，约束传播会限制之后的所有可能性，即使是在几个距离之外的插槽。在改图中，您可以看到仅仅因为塌缩了一个插槽就影响到所有的位置：

  当一次只生成一个块时，约束不会传播到相邻块。但这会导致当模块在一个插槽中被选中的时候就无法在其他地方被考虑，最终导致算法的下一次生成失败（找不到解决方案）。

  我没有使用块（chunks）来生成，而是将地图（数据）存储在一个字典中，它将一个插槽位置映射到一个插槽中。它只在需要时增添数据。

  算法的某些部分需要对此进行调整。当选择要塌缩的插槽时，并不是所有的插槽都可以考虑在内。取而代之的是，当玩家到达地图时，只会同时生成地图的一小部分区域。约束仍然传播到此区域之外。

  在某些情况下，这种方法行不通。假设有这么一个模块，在屏幕截图的上方有一个直线隧道段，但是没有隧道入口。如果算法选择这样一个隧道模块，这就预先确定了一个无限的隧道。约束传播在每一步都会在这里产生一个插槽，导致无限重复。我设计了模块组来避免这个问题。

Boundary constraints

  有两个重要的边界约束：地图顶部的面必须具有“空气”连接器。地图底部的面必须有“地面”连接器。如没有这两个约束条件，地面上就会出现空洞，建筑物的屋顶也会缺失。

  在有限地图中，这很容易做到：对于顶层和底层的所有插槽，移除所有带有不需要的连接器的模块。然后使用约束传播删除不再有效的其他模块。

  在无限地图中，这不起作用，因为在顶层和底层有无限多个插槽。我只会在创建插槽后删除顶层和底层的这些模块。然而，在一个顶层插槽中移除一个模块会影响到其相邻插槽束。这将导致级联效应，从而再次无限地分配插槽。

  我通过创建一个1×n×1的地图来解决这个问题，其中n是高度。此地图使用world wrapping来传播约束。这就像Pacman一样，你在右边离开关卡，在左边进入。现在在这个地图上我可以应用所有的边界约束。无论何时在无限的地图中创建一个新的插槽时，它会被地图上相对应的模块集中的位置数据初始化。

Error states and backtracking

 有时，WFC算法会遇到插槽没有模块可用的状态。在有限世界的应用程序中，您可以放弃结果并重新开始。在无限的世界里，这是行不通的，因为世界的一部分已经展示给玩家了。最初我选择在出错的地方生成一个白色块来解决这个问题。

  我目前的解决方案是回溯。将插槽塌缩的顺序和约束传播相关的一些信息作为历史数据存储起来。如果WFC算法失败，则某些历史操作会被取消。这在大多数情况下都是可行的，但有时错误识别得很晚，这会导致许多步骤被回溯。在极少数情况下，玩家所在的插槽会被重新生成。在我看来，这种局限性使得WFC算法生成无限世界的方法不适合商业游戏。

Outlook

  当我看到Oskar Stålberg用WFC算法在Bad North游戏中生成地图时，我就开始研究这个问题。大多数基础功能都是在procjam实现的。

  该项目已开源并遵循MIT开源协议，你可以用它来实现你自己的想法！

文章来源：https://marian42.de/article/wfc/

github地址：https://github.com/marian42/wavefunctioncollapse

翻译不易，若转载请注明出处。