Geekly articles weekly

波函数崩溃：受量子力学启发的算法

图片

Wave Function Collapse算法会生成局部类似于输入位图的位图。

局部外观意味着

  • （C1）输出中每个NxN像素的模式应在输入中至少出现一次。
  • （条件C2弱）输入中NxN个图形的分布应该与大量输出中NxN个图形的分布相似。 换句话说，某个模式在输出中满足的概率应该接近输入中这种模式的密度。





在示例中，N的标准值为3。


WaveFunctionCollapse（WFC）算法将输出位图初始化为完全不可观察的状态，其中每个像素的值是输入位图的颜色的叠加（因此，如果输入图像是黑白的，则不可观察的状态将显示为不同的灰色阴影）。 这些叠加的系数是实数，而不是虚数，因此该算法不使用实数量子力学，而是受其启发。 然后程序进入观察传播周期：

  • 在观察的每个阶段，在未观察到的空间中，选择具有最低Shannon熵的NxN区域。 然后，该区域的状态根据输入数据中NxN个图形的系数和分布崩溃为确定状态。
  • 在分发的每个阶段，根据输出传播在上一个阶段崩溃期间获得的新信息。

在每个阶段，总熵都减小，最后我们得到一个完全可观测的状态，波动函数的崩溃结束了。

可能发生在传播过程中，特定像素的所有系数都等于零。 这意味着该算法已经出现矛盾，无法进一步执行。 确定给定位图是否提供满足条件（C1）的其他非平凡位图的任务是NP难的，因此不可能创建始终完成算法的快速解决方案。 但是，实际上，该算法很少会遇到矛盾。

波函数折叠算法在C ++ ， Python ， Kotlin ， Rust ， Julia ， Haxe ， JavaScript中实现，并适用于Unity 。 官方可执行文件可以从itch.io下载或在浏览器中运行 。 WFC在Bad North ， Cads of Qud ， 几个 较小的游戏以及许多原型中生成关卡。 它的创造导致了一项新的 研究 。 有关其他 相关 工作 ， 说明 ， 交互式演示 ， 指南 ， 教程和示例，请参见端口，分支和附带内容部分。

在YouTube上观看WFC算法的演示： https : //youtu.be/DOQTr2Xmlz0

演算法


  1. 读取传入的位图并计算NxN个模式的数量。
    1. （可选）使用旋转和反射的图案补充图案数据。
  2. 创建一个具有输出数据大小的数组（在源中称为“ wave”）。 此数组的每个元素指示输出中大小为NxN的区域的状态。 NxN区域的状态是具有布尔系数的输入数据的NxN个图案的叠加（即，输出中像素的状态是实系数的输入颜色的叠加）。 系数False表示相应的模式已被禁止，系数true表示相应的模式尚未被禁止。
  3. 将波初始化为完全不可观察的状态，即所有布尔系数均为真。
  4. 重复以下步骤：
    1. 观察：
      1. 找到具有最小非零熵的波元素。 如果没有这样的元素（如果所有元素的熵均为零或不确定），则完成循环（4）并转到步骤（5）。
      2. 根据其系数和输入数据的NxN个模式的分布，将此元素折叠为确定的状态。
    2. 传播：传播在上一个观察步骤中获得的信息。
  5. 在这一点上，波的所有元素要么具有完全可观察的状态（除一个系数外，所有系数均等于零），要么处于矛盾状态（所有系数均等于零）。 在第一种情况下，返回输出。 在第二种情况下，退出而不返回任何内容。

磁贴卡生成


该算法最简单的平凡情况是模式NxN = 1x2（更确切地说是NxM）。 如果我们进一步简化它，而不是保留颜色对的概率，而是保留颜色本身的概率，那么我们将得到所谓的“简单图块模型”。 该模型中的传播阶段只是邻居依赖性的传播。 使用图块及其邻域数据（可将邻域数据视为大量的非常小的样本）而不是采样位图来初始化简单图块模型很方便。

GIF | GIFV

实际图块集中所有可能的相邻图块对的列表可能会很长，因此为了缩短枚举，我为图块实现了一个对称系统。 在此系统中，必须为每个图块分配其对称类型。


注意，图块与分配给它们的字母具有相同的对称性（换句话说，二面体组D4的动作对于图块和相应的字母是等距的）。 多亏了这个系统，仅列出对称对的相邻图块对就足够了，对于具有许多对称图块的图块集，它的邻居列表缩短了几倍（即使在夏季地形的图块中，尽管图片不对称，系统仍认为此类图块是对称的）。









请注意，对于WFC算法，从节点（其中所有5个图块均有效）中设置的无限图块集是没有意义的，因为您无法进入无法放置图块的情况。 我们将具有此属性的图块称为“简单”。 没有复杂的试探法，简单的图块集不会创建有趣的全局结构，因为远处的简单图块集之间的相关性会迅速降低。 在cr31上可以找到许多简单的磁贴 。 看那里的双面“双”图块。 他如何创建节点（没有T形连接，即很难），同时又很简单？ 答案是它只能生成狭窄的节点类型，而不能创建任意节点。

还值得注意的是，Circuit，Summer和Rooms贴图集不是Van贴图。 即，不能从边缘的着色生成它们附近的数据。 例如，在“电路”拼贴集（集成电路）中，两个角不能相邻，尽管它们可以通过连接（连接）连接，对角线轨迹也不能改变方向。

更高尺寸


更高维度的WFC算法在两个维度上的工作原理完全相同，但此处的性能成为问题。 这些体素模型是在图块模型中的N = 2处生成的，并使用5x5x5和5x5x2块进行重叠，并使用其他启发式方法（高度，密度，曲率...）。


更高尺寸的屏幕截图： 1，2，3 。

使用WFC和其他算法生成的Voxel模型将位于单独的存储库中。

限制合成


WFC算法支持限制。 因此，它可以轻松地与其他生成算法或手动创建相结合。

WFC自动完成人员发起的级别的方法如下：

GIF | GIFV

ConvChain算法满足条件（C2）的严格形式：它创建的输出数据中NxN个模式的极限分布与输入数据中的模式分布完全相同。 但是，ConvChain不满足（C1）：通常会创建明显的工件。 逻辑上是先启动ConvChain以获取充分采样的配置，然后再启动WFC来更正本地工件。 这类似于优化中常用的策略：首先，我们运行蒙特卡洛方法来找到要点。 接近全局最优值，然后从这一点开始进行梯度下降以提高准确性。

P.F. Harrison的纹理合成算法比WFC快得多，但是存在关联时间长的问题（例如，该算法很难用正确构建的砖块来合成砖墙纹理）。 在这种情况下，WFC证明了其优越性，而Harrison的算法支持局限性。 首先使用WFC生成理想的砖墙方案，然后对该方案执行有限的纹理合成算法是有意义的。

留言


为什么使用最小熵试探法？ 我注意到，当人们画东西时，他们通常会自己遵循最小熵的启发法。 这就是为什么算法如此有趣的原因。

重叠模型对应于简单模型，其方式与高阶马尔可夫链对应于一阶马尔可夫链相同。

应该注意的是，任何节点的熵在传播阶段都不能增加。 概率不会增加，但是可以重置为零。 当传播阶段无法进一步减小熵时，我们激活观察阶段。 如果观察阶段无法减少熵，则意味着该算法已完成工作。

WFC算法中的传播阶段与循环置信传播算法非常相似。 实际上，我最初是对置信传播（BP）进行编程的，但是后来我切换到具有固定固定分布约束的传播，因为在没有大规模并行化的情况下（在CPU中）BP的速度要慢得多，并且对于我的任务而言并不会产生明显更好的结果。

请注意，“简单结”和“技巧结”样本不是2种颜色，而是3种颜色。

一个维度可能是时间。 特别地，d维WFC显示任何（d-1）维元胞自动机的行为。

参考文献


该项目基于Paul Merrell在模型综合方面的工作，特别是在其论文中有关模型的离散综合的章节中。 Paul在我们所谓的简单图块模型中扩展了邻域的局限性，并通过试探法来计算小移动区域中的扩展。

同样，我的项目受到Paul F. Harrison论文中有关纹理的声明性合成一章的极大影响。 Paul将数据设置在图块附近，标记了图块的边界，并使用返回搜索来填充图块地图。

组装方式


WFC是仅依赖于标准库的控制台应用程序。 下载适用于Windows，Linux或macOS的.NET Core并运行

 dotnet run WaveFunctionCollapse.csproj

或者，您可以在相应的期刊中使用针对不同平台的社区构建说明。 Casey Marshall创建了一个拉取请求 ，该请求简化了命令行程序的使用，并包含一个snap软件包。

有趣的港口，前叉和副产品



致谢


从《创世纪4》和《 地牢爬行》游戏中获取了一些示例。 Tileset圈子取自Mario Klingemann 。 Moonasaur提出了生成集成电路的想法，其风格取自Zachtronics的Ruckingenur II游戏。 猫重叠示例取自Nyan Cat视频，Qud示例由Brian Buckley创建，Magic Office +螺旋示例为rid5x，彩色城市+链接+链接2 +迷宫般+红点+微笑城市叠加示例为Arvi Teikari。 Tileset Summer由Hermann Hillmann创作。 Voxel模型在MagicaVoxel中渲染。


Source: https://habr.com/ru/post/zh-CN437604/

More articles:


All Articles