Wavefunction Collapse Algorithm教导计算机即兴创作。 在输入处，它接收原型数据并创建与原始数据类似的程序生成数据。
（ 来源 ）它通常用于创建图像，但它也可以用于建造
城市 ，
滑板场和撰写
可怕的诗歌 。
（ 来源 ）波动函数的崩溃是一个非常独立的算法，几乎不需要外界的帮助或指示。 您只需要举例说明您想要实现的样式，其余的工作将由他完成。 尽管自给自足，他却出奇的简单。 它不使用任何神经网络，随机森林或任何其他类似于机器学习的东西。 如果您处理好这个主意，它对您将变得非常容易理解和直观。
wave函数崩溃的大多数实现和解释都是该算法的完整，速度优化版本。 当然，它们都是重要且必要的，但是很难从头开始理解它们。 在本文中，我将以我理解的一种简单语言来解释所有内容，重点是Wavefunction的受限版本，我将其称为
Even Simpler Tiled Model 。 另外，我
在Github上发布
了ESTM的示例实现 。 其中的代码效率低下且速度慢，但是非常易于阅读和详细注释。 一旦您了解了ESTM的基础技术，您就将更接近了解该算法的更复杂版本。 如果您想了解波动函数折叠算法，那么本文将是一个不错的开始。
让我们从故事开始。
婚礼
想象一下，您正在计划婚礼。 除了选择珠宝和音乐外，您还需要为晚餐的客人创建一个座位计划。 您的家人喜欢吵架和调皮，因此可能很困难。 父亲不能比母亲坐在两张桌子旁边。 如果一个堂兄不和另一个堂兄坐着，她就会变得孤独。 而且最好不要将罗伊叔叔种植在伴侣家庭的环保成员旁边。 仍然只有5小时才能到达食物，因此您决定使用wave函数折叠算法来攻击这项顽固的任务。
您从一长串规则和空座位计划开始。
您创建计划的原始
波动函数 。 她将每把椅子与可以坐在椅子上的人的名单相关联。 任何人都可以坐在任何椅子上。 坐客的波动函数从每种可能方案的完全
叠加 （该概念是从量子物理学借来的）开始的。
Schrödinger的猫同时死了还活着，直到有人打开箱子检查了一下。 您的计划同时是所有可能的计划，直到您整理好一切。 完全重叠是有用的理论构架，但不会帮助您祖母弄清楚她需要坐在哪里。 您需要将访客位置的波动函数带到一个特定的状态，然后可以将其转换为普通的非量子名片。
我们首先通过对一张椅子执行
wave函数的
折叠来开始执行此操作。 我们选择一把椅子，查看可以坐在椅子上的人的名单，然后将其随机分配给其中一位。 在这种情况下，大便的波动功能会减弱。
这种选择的结果会扩展到其余椅子的波动功能。 如果罗伊叔叔坐在表2上，表弟弗兰克和米歇尔·奥巴马（伴侣的家人的朋友）肯定不会和他在一起。 如果米歇尔不在表2的位置，那么巴拉克也不会在他后面。 我们正在通过从可能的候选人列表中删除人员来更新位置图的wave函数。
一旦振动消除，我们将重复此过程。 我们选择了另一把椅子，并选择了几种可能的椅子并折叠其波动函数，并随机选择其中一名可接受的椅子。 同样，我们将这种选择所引起的振动扩展到计划的其余部分，如果人们不再能够坐在椅子上，则不再使用椅子的波动功能。
我们重复此过程，直到波动函数崩溃（即其中仅剩下一个就座的人）为止，或者直到达到
矛盾为止。 矛盾是没有人可以坐的椅子，因为上次选举都将他们开除。 该矛盾使得不可能整个波函数崩溃。
如果您遇到了矛盾，那么最简单的方法就是重新开始。 舍弃所有先前的工作，找到一个新的空计划，然后再次启动算法，从而完成另一把椅子的波动函数的折叠。 您还可以实施回溯系统，该系统允许您取消特定选择，而不是立即放弃所有内容（“如果Sheila转移到椅子54会怎样？”）。
经过几次错误的开始之后，您最终将陷入完全崩溃的状态，在这种状态下，每把椅子都被精确分配给一个人，并且遵循所有规则。 做完了！
从婚礼到位图
这不是理论上的例子。 您确实可以实现wave功能崩溃的变体，这将为婚礼的客人创建一个座位计划。 但是，在更传统的Wavefunction Collapse中，我们通常不尝试在婚礼上让人们坐下，而是在输出图像中排列像素。 但是，过程将非常相似。 我们教该算法一组输出应满足的规则。 我们初始化wave函数。 我们执行一个元素的折叠，并将结果扩展到波动函数的其余部分。 而且，我们将继续这样做，直到波动函数完全消失，或者直到出现矛盾为止。
波动函数的传统塌陷与婚礼塌陷的区别在于我们向算法传授必须遵循的规则的方式。 在婚礼版本中，我们必须自己写下规则。 但是在传统版本中，我们只是给该算法提供示例图像，然后基于该图像创建其余图像。 他解析了一个示例，分析了其模式，并找出像素或
图块应如何对齐。
让我们通过查看一个简单的特殊情况开始研究波动函数的实际折叠，这种特殊情况被
ExUtumno （算法的创建者）称为
简单平铺模型 。
简单平铺模型
在简单图块模型中，输入和输出图像是由少量预定义的图块构成的，并且输出图像中的每个正方形都仅限于其四个最近的邻居。 例如，假设我们为具有顶视图的二维游戏生成随机世界。 我们可以拥有用于陆地，海岸和海洋的瓷砖，以及一系列规则，例如“海岸可以靠近海”，“土地可以靠近海岸”和“海可以与另一海相邻”。
简单平铺模型考虑了其平铺的对称性和旋转性。 例如，陆地可能位于海岸附近，但方向正确。
这种对称处理可提供更好的输出图像，但会使代码复杂化。 为了使事情简单，让我们看一个更简单的wave函数崩溃的视图，我称它为
Even Simpler Tiled Model 。
更加简单的平铺模型
甚至更简单的图块模型（“甚至更简单的图块模型”）都类似于简单图块模型，但是其图块不具有对称性。 每个图块都是一个相同颜色的像素，也就是说，我们将无法以任何方式混淆其边缘。
甚至更简单的图块模型规则也可以确定哪些图块可以彼此相邻放置以及以哪种方向放置。 每个规则是一个由三个元素组成的元组（3个元组）：两个图块和一个方向。 例如，
(SEA, COAST, LEFT)表示
SEA图块（海）可以比
COAST图块（海岸）
COAST 。 该规则必须附带另一条以
COAST表示情况的规则-
(COAST, SEA, RIGHT) 。
如果您希望
SEA贴不仅位于
，还位于
COAST贴的
。 那么他们需要其他规则：
(SEA, COAST, RIGHT)和
(COAST, SEA, LEFT) 。
就像我上面说的，我们不需要自己创建所有这些规则的列表。 wave函数的折叠可以通过解析示例图像并收集其中包含的所有三元组的列表，为甚至更简单的平铺模型创建一组规则。
检查了上面显示的示例图像后，Even Simpler Tiled Model注意到，海图块只能在海岸图块的下方或侧面，或其他海图块附近的任何位置。 她还指出，海岸瓦片可以位于陆地，海洋或其他海岸瓦片旁边，但只能位于海洋瓦片之上和之下。 她没有尝试得出任何更复杂的规则，例如，“海图块应至少靠近一个海图块”或“每个岛必须至少包含一个海图块”。 没有一种瓷砖可以影响以下事实：某些类型的瓷砖可以或不能位于距它们两个或多个正方形的位置。 这类似于婚礼计划模型，其中唯一的规则是：“ X可以坐在Y旁边”。
在分析传入的图像时，我们还需要记录每个图块相遇的频率。 以后，当选择正方形的波动函数时，必须使用这些数字作为权重，必须对其进行折叠，并且在选择折叠后分配给正方形的图块时也可以使用这些数字。
了解了输出图像必须遵守的规则后，我们就可以构建输出图像的波动函数的崩溃了。
倒塌
就像在婚礼示例中一样，我们使用波函数开始折叠过程，在该函数中，输出图像的每个正方形都与每种类型的图块重叠。
我们从选择一个其波函数将崩溃的正方形开始。 在婚礼示例中，这种选择是偶然的。 但是，正如
ExUtumno指出的那样，人们通常以不同的方式处理这些任务。 相反，他们寻找
熵最低的正方形。 熵是不确定性和无序性的量度。 通常，具有高熵的正方形是在其波函数中保留许多可能的图块的正方形。 尚不清楚他最终倒在哪个瓷砖上。 低熵平方是波动函数中具有尽可能少的图块的平方。 他所塌陷的一组瓷砖已经非常有限。
例如，在“甚至更简单的图块模型”中，没有有关周围正方形的信息的正方形是无限的，并且可以成为任何图块。 因此，它具有很高的熵。 但是一个周围已经折叠了几个正方形的正方形只能选择2个图块。
上图中中心正方形的波动函数并未完全崩溃，但我们已经知道它不可能是地砖。 但是，它已经受到限制，这意味着它的
熵低于右上角的正方形，后者仍然可以是陆地，海洋或海岸。
人们通常在手动解决此类问题时会注意这种具有低熵的有限磁贴。 即使您不使用wave的折叠功能来创建用于在婚礼上放置客人的计划并自行制定，也要专注于计划中已经存在最大限制的区域。 您不会将Dwayne放在表1上，然后随机跳转以使Katie到达表7（到目前为止是空的）。 首先放置Dwayne，然后确定谁可以坐在他旁边，然后谁可以坐在此人旁边，依此类推。 我还没有看到任何理由，但是我的直觉说，使用这种
最小熵的启发法可能会产生比如果您随机选择要折叠的正方形更少的
矛盾 。
香农公式被用作波动函数崩溃算法中的熵公式。 它使用在上一步中从传入图像中解析的图块的权重：
# Sums are over the weights of each remaining # allowed tile type for the square whose # entropy we are calculating. shannon_entropy_for_square = log(sum(weight)) - (sum(weight * log(weight)) / sum(weight))
在计算出具有最小熵的波动函数的平方后，我们将其收缩。 为此，我们随机选择一个仍可用于正方形的图块，并按从传入图像中解析出的图块的权重对其进行加权。 使用权重是因为它提供了更逼真的输出图像。 假设正方形的波动函数报告它可以是陆地或海岸。 我们不一定总是选择概率为50％的选项之一。 如果输入图像的地块多于海岸，那么我们应该在输出图像中体现这一优势。 使用简单的全局权重即可实现。 如果在示例图像中有
20陆地图块和
10海岸图块，则该正方形以
2/3的概率塌陷为土地，而在海岸中以
1/3的剩余概率崩溃。
然后，我们将选择的结果扩展到输出的其余波函数（“如果该图块被证明是海，则该图块不能是陆地，也就是说，这不能是海岸”）。 当所有这些震颤都消除后，我们使用最小熵试探法重复该过程，以选择下一个崩溃的图块。 我们重复这个崩溃传播循环，直到输出图像的整个波动函数完全崩溃并且可以返回结果为止，或者直到出现矛盾并返回错误为止。
结果，我们创造了一个世界（或错误）。
接下来要去哪里
处理了甚至更简单的平铺模型之后，您就可以攀登算法的功能和复杂性的阶梯。 从我们在本文开头提到的简单平铺模型开始，然后继续进行完整的重叠模型。 在重叠模型中，图块或像素会相互影响。 如果您了解这种情况，则
ExUtumno注意到简单平铺模型类似于1阶马尔可夫链，而更复杂的模型类似于较大阶的链。
Wavefunction Collapse甚至可以考虑其他限制，例如“此图块必须是海”或“此像素必须是红色”或“输出中只能有一个怪物”。 所有这些都在
主项目的
自述文件中进行了描述。 您还可以研究对完整实现进行的速度优化。 不必在每次迭代中重新计算每个正方形的熵，并且可以更快地完成通过波动函数的信息传播。 随着输出图像尺寸的增加，这些方面变得越来越重要。
wave函数的崩溃是一个美丽而强大的工具，值得精通。 下次计划婚礼或建立程序世界时，请考虑一下。