我们处理波动函数崩溃算法

自DeBroglie和Tessera出现以来，我多次被要求解释它们的工作原理。生成可能看起来像魔术，但其背后的规则实际上很简单。

那么什么是波动函数崩溃（WFC）算法？它是由Maxim Gumin开发的，它基于简单的配置或图像样本来创建“平铺”图像。该算法可以做很多事情：浏览Maxim和Twitter提供的示例#wavefunctioncollapse，观看此视频。种类惊人。


README中的Maxim简要解释了WFC的工作，但在我看来，这个问题需要从最基础的角度进行更详细的披露。由于该算法与约束编程有关，因此本文的大部分内容都致力于解释约束编程的概念，最后我们将回到WFC。

受限编程是一种指示计算机的方法。与命令式编程不同，当您指定显式函数列表或函数式编程时，当您指定数学函数时，此处为计算机提供了对该问题的严格描述，并且计算机使用内置算法来查找解决方案。

注意：本指南介绍了各种概念，而不是方法和代码。如果您对实现更感兴趣，那么可以使用我的WFC开源库（github，documentation）。尽管最好从Maxim的实现开始研究。如果您使用Unity，则可以购买Tessera，这是我在此引擎中应用WFC的工具。

迷你数独

作为说明性任务，我选了一个迷你数独游戏。这是一个看起来像4×4网格的谜题，在某些单元格中带有数字。


目标是按照规则用1到4的数字填充每个空单元格：

• 从1到4的每个数字必须在一个副本中的每一行中出现。
• 单个副本中的每一列中必须存在1到4之间的每个数字。
• 单个副本中每个2×2角正方形中必须存在从1到4的每个数字。

根据这些规则，解决方案如下：


您可能已经轻松解决了这个难题。但是我们对计算机如何执行此操作感兴趣。该问题可分为两部分：计算机条件的描述，然后是使用算法的解决方案。

条件说明

通常，为此使用受限制的编程语言。有几种这样的语言，它们的作用原理相似。

首先，我们定义变量。在这里，它们与常规编程中的不同。在问题解决者的上下文中，变量是一个未知值，必须解决该未知值才能解决问题。在我们的数独示例中，我们将为所有空单元格创建变量。为方便起见，您还可以为填充的单元格创建变量。

然后，为每个变量定义一个域：一组可能的值。在我们的数独中，对于每个空单元格，域将为{1、2、3、4}。对于已经输入1的单元格，域将为{1}。

最后，我们设置约束：绑定变量的规则。在大多数编程语言中，已经存在具有限制的函数，该函数all_distinct(..)需要传递唯一值。因此Sudoku规则可以转换为12个约束all_distinct-每行和每列一个约束，以及2×2角正方形。我们只需要一种约束即可解决此问题，但是，用于满足约束的问题解决程序通常带有一个大型的库，其中包含各种类型的约束来描述您的问题。

注意：在实践中，编程语言在约束中支持数组，因此有更准确的方式来表达此任务。网上有很多关于解决数独问题的文章。

解决约束满足问题的算法

有几种不同的解决方案技术。但是，我将考虑其中最简单的方法来向您展示其工作原理。每个单元的域如下所示：


这些都是可变域中的所有可能值。

现在采取第一个限制。它要求第一行中的所有值都是唯一的。在一个单元格中，值4已被内接，因此，在该系列的其他单元格中，该值不能为。我们将其从这些细胞的域中删除。


对所有12个限制重复此过程。这称为限制传播，因为信息是通过限制从一个变量分发到另一个变量的。


瞧，我们有变量，在变量域中还剩一个值。这些应该是这些变量的正确解决方案。


似乎我们可以从限制的分配中获得更多的好处：新的红色单位表示我们将在单个域中拥有更多的变量，这也将有助于分配。重复该过程，直到解决难题。

我们使任务复杂化

不幸的是，并不是所有的逻辑难题都能这么快解决。这是一个大数独，其工作方式相同，不同之处在于，现在我们有9个不同的值，9行，9列和9 3×3正方形。


如果我们尝试应用上述技术，则会陷入困境：


现在所有限制都是通用的，但是仍然存在未定义的变量。

人将决定这一点，但是计算机算法将无法决定。人们的手册说，现在我们需要寻找越来越复杂的逻辑结论。但是我们不需要计算机算法来执行此操作，因为它很复杂，但是我们需要一种通用算法，该算法可以满足任何限制条件，而不仅仅是根据数独规则。

因此，计算机做的最愚蠢的事情是：它们假设。首先，我们记录拼图的当前状态。然后，我们选择一个任意变量并将其设置为可能的值之一。假设我们将值1分配给中央单元格。

现在我们可以进一步扩展限制。这是我在中心栏得到的：


蓝色值是我们在假设之后得出的结论。如您所见，发生了一些事情。我们放下了一些变量，但看看中间的上部单元格。它是空的：在其域中，没有满足限制的可能值（不能为5，因为该值已经存在于相同的3×3正方形中，并且所有其他数字已经在此列中）。

如果我们获得的变量的域为空，则意味着我们无法为其分配任何值。即，难题无法解决。事实证明，我们的假设是错误的。

面对这样的矛盾，我们执行退货搜索流程（回溯）。首先，我们恢复假设之前的状态。然后，从域中删除用作假设的值-它不再是正确的答案。


许多工作已经完成，但是他们已经前进了。但是，即使从中央单元格中排除了1，我们仍然处于死角。现在该一次又一次地做一个假设。

这里没有很多算法动作。每次我们无法分发限制时，我们都会做一个假设并继续前进。而且由于您在遇到矛盾之前可能会多次陷入困境，因此您将积累一些保存的状态和假设。

每次迭代都返回一个结果，您就将域至少减少了一个变量，因此，尽管回滚次数众多，该算法最终仍将完成工作。

这个主题比我描述的要广泛得多。在实践中，诸如假设选择，了解何时分发以及何时做出更复杂的逻辑结论之类的优化可能会对程序执行产生巨大影响。而且由于约束的问题通常呈指数增长，因此您可以在明天或5000年后得到答案。

我们回到波动函数的崩溃

波动函数的崩溃是一项棘手的任务，但有一个局限性：存在成千上万种可能的解决方案。如果我们随机进行假设，那么我们将使用生成器而不是求解器。同时，它仍将遵守所有给定的限制，也就是说，它将比大多数其他程序生成器更易于管理。

WFC算法的任务是用图块填充单元，以使图块上的图像相互组合。在上面使用的术语中，每个图块是一个值，每个单元格是一个变量，放置图块的规则是约束。

WFC的作者马克西姆（Maxim）发现，通过合理选择图块和适当的随机化，您几乎不必使用带有返回的破坏，因此无法执行此过程。因此，WFC的本质如下：

• 为每个单元格创建一个布尔数组，该数组表示此变量的域。域每个图块包含一个记录，并且所有域都使用value初始化true。如果值相等，则图块进入域true。
• 同时，有些单元格中的域包含多个元素：
  
  • 使用“最小熵”的启发式方法选择随机单元。
  • 从单元域中选择一个随机磁贴，然后从其中删除所有其他磁贴。
  • 基于此新信息更新其他单元的域是单元限制的传播。必须重复进行此操作，因为单元格的更改可能会产生进一步的后果。

注意：我的条款与Maxim的条款不同。他称域阵列为波，选择随机图块是一种观察。也就是说，用量子力学来类比。但是比较是肤浅的，因此我们将忽略它。

上述原理有许多补充，为算法增加了宽限度和性能。但是，让我们先来看一下所描述的步骤。

例

假设我们需要用四种类型的图块填充3 x 3网格：


限制是：相邻图块的颜色必须彼此匹配。

就像数独示例一样，我将用单色图像说明域的内容。当域中仅剩一个元素时，我将其大小增加并以颜色显示。

首先，在每个单元中，可以放置任何类型的图块：


运行主WFC循环。随机选择一个单元格，例如左上方。现在，在域中选择一个图块，然后删除所有其他图块。


分发限制。唯一规则适用于相邻的图块，因此我们需要更新两个单元：


鉴于域缩小，我们可以更新其他图块吗？是! 尽管我们不确定第一个图块的选择，但我们看到其余的选项指向右边。也就是说，某些类型的图块不能放在右上角。左下角也一样。


我们不再能够分配限制，因此我们重复主循环：单元选择，图块选择和分配。这次我们取中间的上单元格：


另一个循环：取左中间格。在中央单元的限制扩散之后，一个可能的值仍然存在。


一般来说，您了解这个想法。您可以自己填写其余单元格。

如果您想尝试一个更复杂的交互式示例，建议您使用此示例。

最小熵

选择下一个要填充的单元格时，某些选项将是更可取的。如果您从网格中的任意位置随机选择，则可能会在同时填充网格的不同区域时出现这种情况。这可能会导致问题：根据可用的图块，无法连接填充区域。因此，最好选择将来不太可能导致此类问题的电池。换句话说，您需要获取域中具有最少数量的可能值的单元格（但不少于两个值）：

1. 最有可能的是，它们将在已经填充的单元格旁边。
2. 如果我们将它们留给未来使用，那么可能会遇到困难，因为可用的值已经很少了。

如果所有图块均具有相同的可能性，则最小域方法会很好地工作。但是，如果您从加权随机分布中进行选择，则需要考虑其他因素。Maxima建议“最小熵”，即选择一个最小化的单元：

$$

$$entropy = — \sum p_{i}log(p_{i})$$

这是该域中图块的总和 $$$p_{i}$-此图块的概率。

高效计算

尽管我不想详细介绍，但是有两个优化使我可以提高速度，以至于不能忽略它们。

由于我们的唯一规则与相邻的图块相关，因此我们只能检查那些可以得出与先前结果不同的限制。也就是说，在更新单元格时，我们将其添加到等待决策的单元格队列中。然后，我们从队列中删除一个单元，每次检查其相邻单元。如果这种检查导致其他单元的更新，它们也将进入队列。重复此过程，直到队列为空，我们确保检查所有限制。但是，直到与这些限制相关联的至少一个单元格的域发生变化，我们才会检查它们。

此外，要检查邻接约束，我们需要回答以下问题：“考虑到单元A域中的图块，如果单元相邻，在单元B域中可能有哪些图块？”

有时，此问题称为单元A的“支持”。对于域B中的给定图块“ b”，很容易计算域A中图块的周期。如果A具有至少一个可以放置在“ b”旁边的图块，则“ b”仍然适用，至少适用于相关问题。如果在A中没有这样的图块，那么您将不能放置域B中的图块“ b”，我们可以将其丢弃。

循环使在代码中轻松实现这一点变得非常容易，但是循环将非常缓慢。而且，如果我们将信息存储在其他数据结构中，则可以根据需要快速回答该问题。新数据是一个大型数组，每个单元格的每一侧和每个图块都有条目。在我们的示例中，有9个像元，每个像元具有4个面和4种类型的图块。所以我们需要9 * 4 * 4记录。我们将在阵列中保存支持计数器：对于每个单元格/图块/侧面，我们计算相邻单元域中可以放置在所讨论图块旁边的图块数。如果计数器降为零，则无法放置此图块，因为没有人可以与其相邻。

算法扩展

因为WFC基于对约束问题的更一般的了解，所以有很多方法可以通过更改所使用的约束来扩展算法。

明显的变化之一是，没有人强迫我们使用正方形单元。 WFC在六角形电池，三维甚至更多不寻常的表面上都可以很好地工作。




您可以引入其他限制：修复某些磁贴，或从多个单元格创建“模块”。

从实用的角度来看，附加限制的引入可以发挥非常重要的作用。由于WFC仅限制相邻的图块，因此它很少生成大型结构以提供高水平的同质性，并且看起来不寻常。该算法在选择图块时效果最佳，但要使用某些大型结构，最好使用其他技术或引入其他限制。

在另一篇文章中，我谈到了如何从WFC中获得最佳结果。

重叠的WFC

该算法的有趣扩展之一是“重叠” WFC。在以上示例中，主要限制与成对的相邻图块有关。这足以确保线的连接并创建简单的结构（例如洞穴，房间等）。但是同时，丢失了很多信息。例如，如果我们需要红色的块始终位于蓝色的旁边，但从不与其相邻，那么仅凭连续性就很难表达这一点。

Maxim提出了重叠WFC的概念：我们用新的约束替换了邻接约束，该约束立即影响多个图块。例如，在输出处，每组3×3单元对应于网格样本中的3×3组。样本中存在的模式将在输出端以不同的变化反复进行：


此限制比“简单”邻接限制敏感得多。并且由于它取决于给定的样本，因此非常适合解决某些艺术任务。到目前为止，我还没有遇到任何有趣的事情。可能是因为这样的算法更难以实现，或者算法运行更慢，或者有时它不能很好地再现原始样本，这导致某种自然性和自然性丧失。

下一步是什么？

有限制地解决问题是计算机科学领域的一个积极而广阔的发展领域，而我只涉及到它。就像其他解决约束问题的程序生成算法一样，WFC仍然是新的。我建议阅读r / proceduralgeneration，#wavefunctioncollapse，@exutumno和@osksta以了解最近的用例。

您也可以阅读我有关WFC的文章，尝试使用我的开源库或Unity工具。不要忘记我有关程序生成的其他文章。