波函数坍缩

这个程序可以生成和输入图像局部相似的图像

局部相似意味着：

• (C1) 输出图像中，每个NxN范围的像素图案，都至少在输入图像中出现一次。
• (Weak C2) 输入图像中各个像素图案的分布方式，应该和输出图像中的大量分布保持相识。换句话说，输出图像中某个图案的出现概率应该和输入图像一样。

在范例中，N一般是3。

WFC(波函数坍缩，下同) 以一种完全的“未被观察”的状态初始化输出图象，每个像素的值是输入图像的多种颜色的叠加（因此，如果输入的是黑白图像，那么“未被观察”的状态就是灰度中的某一级）。这种叠加态的系数都是实数，而不是复数，所以它不包含真的量子力学，但是这个算法受其启发。接下来，程序进入了 “观测-传播” 的循环：

• 每一个“观察”步骤，我们从未被观察的区域中选择一个NxN的区域，要保证这个区域有最小的香农熵(Shannon entropy).这个区域的状态根据它的系数和输入图像中各个图案的分布概率因此坍缩成一个有限的状态。

• 每个一个“传播”的步骤，上一个观察步骤得到的新的信息，将会在输出图像中传播。

每经过一个步骤，总体的熵将会减少，最后我们会有一个完全观察过的状态，波函数就坍缩。

有可能发生的情况是，在传播的过程中，某个像素的所有系数可能都会变成0。这意味着算法走进了一个死路。要想判定一个输入图像是否能够产生与其完全不同的图像，是一个NP困难的问题，所以不可能找到一个快速的，在有限的时间内完成的算法。但是在实践中，这个算法出人意料的极少陷入自我矛盾的情况。

请观看一个视频讲解: https://youtu.be/DOQTr2Xmlz0

算法

1. 读取输入图像然后对图案进行计数。

   1. (可选) 用旋转和翻转来增强图案数据。

2. 根据输出图像的大小创建一个数组（被称为“波”）。每个元素代表输出图像中一个NxN区域的状态。这个状态是每个输入图像NxN图案的bool系数（所以输出图像中每个像素的状态就是输入图像的各个颜色与实数系数的叠加）。系数为假时，表示对应的图案不能放置在这里，系数为真，表示对应的图案尚有可能出现在这里。

3.初始化“波”数组为，完全未被观察的状态，也就是所有的bool值为真。

4. 重复一下步骤:

   1. 观察:
      1. 寻找一个具有最小非零熵值的“波”元素。如果没有这样的元素 (就是所有的元素都只有0或未定义的熵) 那么就退出循环(4)并到步骤（5）。
      2. 利用这个元素的系数和图案的分布概率，把这个元素坍缩成有限状态.
   2. 传播: 把观察步骤里的产生的新的信息，传播到周围的元素。

5. 现在，所有的“波”数组的元素，要么在一个完全的被观测的状态（只有一个系数是真），或者出一个自相矛盾的状态（所有的系数都是假）。第一种情况，返回结果，第二种情况，完成程序但是不返回结果。

地砖生成

这个算法所能产生的最简单不平凡解的情况是当NxN为1x2时。如果我们把它进一步简单化为不去储存颜色对的概率而是颜色值本身的概率，我们就得到一个“简单地砖模型”。这个模型里的传播步骤仅仅是近邻限制的传播。可以很方便的把这个模型初始化为一个砖块的列表以及他们的相邻性数据（相邻性数据可以被看成是很多小样本的大集合）而不是一个简单的位图。

GIF | GIFV

在实际的地砖集合中，列出所有的可能的相邻的砖块的列表可能会非常长，所以我们构建了一个对称系统来减少枚举种类。这个系统中，每个地砖都有一个对应的枚举值。

要注意的是，这些砖块都有和他们被赋予的字母相同的对称类型（换句话说，D4的动作对于砖块及其各自的字母是同构的）。这个系统中，仅用对称度来给各种砖块赋予枚举值是足够用的，这样使得枚举列表短了好几倍（有些砖块并不对称但是系统依旧把他们当作对称的砖块）。

注意，没有边缘限制的孤立砖块，对于WFC来说没有太大的兴趣，因为你总是能把他们摆下。这种图集对于WFC来说是“简单”的。王氏砖块是“简单”的。没有特殊的启发，简单的图集不会产生有趣的全局图案，因为砖块的相关性随着距离快速的消失。

很多有趣的王氏砖块可以在这个地址找到cr31's site。

更高的维度

WFC 在更高的维度与二维的情况完全一样, 尽管运行性能可能是个问题。这些体素模型是在N=2的情况下，使用5x5x5和5x5x2的砖块模型生成的（还考虑了高度，密度，曲率等）。

高清图片链接: 1, 2, 3.

WFC生成体素模型和其他相关算法会在另一个单独的repo里。

有限制的生成算法

WFC算法支持预先限制。因此, 它可以和其他的生成算法相结合。

这是一个WFC自动完成一个由人类开始设计的关卡过程：

GIF | GIFV

ConvChain algorithm satisfies the strong version of the condition (C2): the limit distribution of NxN patterns in the outputs it is producing is exactly the same as the distributions of patterns in the input. However, ConvChain doesn't satisfy (C1): it often produces noticeable artefacts. It makes sense to run ConvChain first to get a well-sampled configuration and then run WFC to correct local artefacts. This is similar to a common strategy in optimization: first run a Monte-Carlo method to find a point close to a global optimum and then run a gradient descent from that point for greater accuracy.

P. F. Harrison's texture synthesis algorithm is significantly faster than WFC, but it has trouble with long correlations (for example, it's difficult for this algorithm to synthesize brick wall textures with correctly aligned bricks). But this is exactly where WFC shines, and Harrison's algorithm supports constraints. It makes sense first to generate a perfect brick wall blueprint with WFC and then run a constrained texture synthesis algorithm on that blueprint.

评论

为何选择最小的熵值？我注意到人类自己画东西总是跟随着最小熵值的地方去画。这也是为什么这个算法的过程很好看。

The overlapping model relates to the simple tiled model the same way higher order Markov chains relate to order one Markov chains.

Note that the entropy of any node can't increase during the propagation phase, i.e. possibilities are not arising, but can be canceled. When propagation step can not decrease entropy further, we activate observation step. If the observation step can not decrease entropy, that means that the algorithm has finished working.

WFC's propagation phase is very similar to the loopy belief propagation algorithm. In fact, I first programmed belief propagation, but then switched to constraint propagation with a saved stationary distribution, because BP is significantly slower without a massive parallelization (on a CPU) and didn't produce significantly better results in my problems.

Note that the "Simple Knot" and "Trick Knot" samples have 3 colors, not 2.

One of the dimensions can be time. In particular, d-dimensional WFC captures the behaviour of any (d-1)-dimensional cellular automata.

引用

This project builds upon Paul Merrell's work on model synthesis, in particular discrete model synthesis chapter of his dissertation. Paul propagates adjacency constraints in what we call a simple tiled model with a heuristic that tries to complete propagation in a small moving region.

It was also heavily influenced by declarative texture synthesis chapter of Paul F. Harrison's dissertation. Paul defines adjacency data of tiles by labeling their borders and uses backtracking search to fill the tilemap.

值得关注的fork，port和衍生

• Emil Ernerfeldt made a C++ port.
• Max Aller made a Kotlin (JVM) library, Kollapse.
• Kevin Chapelier made a JavaScript port.
• Oskar Stalberg programmed a 3d tiled model, a 2d tiled model for irregular grids on a sphere and is building beautiful 3d tilesets for them: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
• Joseph Parker adapted WFC to Unity and used it generate skateparks in the Proc Skater 2016 game and fantastic plateaus in the 2017 game Swapland.
• Martin O'Leary applied a WFC-like algorithm to poetry generation: 1, 2, 3, 4.
• Nick Nenov made a 3d voxel tileset based on my Castle tileset. Nick uses text output option in the tiled model to reconstruct 3d models in Cinema 4D.
• Sean Leffler implemented the overlapping model in Rust.
• rid5x is making an OCaml version of WFC.
• I published a very basic 3d tiled model so people could make their own 3d tilesets without waiting for the full 3d repository.
• I made an interactive version of the overlapping model, you can download the GUI executable from the WFC itch.io page.
• Brian Bucklew built a level generation pipeline that applies WFC in multiple passes for the Caves of Qud game: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.
• Danny Wynne implemented a 3d tiled model.
• Arvi Teikari programmed a texture synthesis algorithm with the entropy heuristic in Lua. Headchant ported it to work with LÖVE.
• Isaac Karth made a Python port of the overlapping model.
• Oskar Stalberg made an interactive version of the tiled model that runs in the browser.
• Matt Rix implemented a 3d tiled model (1, 2, 3, 4) and made a 3-dimensional tiled model where one of the dimensions is time (1, 2, 3, 4).
• Nick Nenov made a visual guide to the tile symmetry system.
• Isaac Karth and Adam M. Smith wrote a research paper where they formulate WFC as an ASP problem, use general constraint solver clingo to generate bitmaps, experiment with global constraints, trace WFC's history and give detailed explanation of the algorithm.
• Sylvain Lefebvre made a C++ implementation of 3d model synthesis, described the thought process of designing a sample and provided an example where adjacency constraints ensure that the output is connected (walkable).
• I generalized 3d WFC to work with cube symmetry group and made a tileset that generates Escheresque scenes.
• There are many ways to visualize partially observed wave states. In the code, color values of possible options are averaged to produce the resulting color. Oskar Stalberg shows partially observed states as semi-transparent boxes, where the box is bigger for a state with more options. In the voxel setting I visualize wave states with per-voxel voting.
• Remy Devaux implemented the tiled model in PICO-8 and wrote an article about generation of coherent data with the explanation of WFC.
• For the upcoming game Bad North Oskar Stalberg uses a heuristic that tries to select such tiles that the resulting observed zone is navigable at each step.
• William Manning implemented the overlapping model in C# with the primary goal of making code readable, and provided it with WPF GUI.
• Joseph Parker wrote a WFC tutorial for Procjam 2017.
• Aman Tiwari formulated the connectivity constraint as an ASP problem for clingo.
• MatveyK programmed a 3d overlapping model.
• Sylvain Lefebvre, Li-Yi Wei and Connelly Barnes are investigating the possibility of hiding information inside textures. They made a tool that can encode text messages as WFC tilings and decode them back. This technique allows to use WFC tilings as QR codes.
• Mathieu Fehr and Nathanael Courant significantly improved the running time of WFC, by an order of magnitude for the overlapping model.

如何编译

WFC is a console application that depends only on the standard library. Build instructions from the community for various platforms can be found in the relevant issue. Casey Marshall made a pull request that makes using the program with the command line more convenient and includes snap packaging.

致谢

Some samples are taken from the games Ultima IV and Dungeon Crawl. Circles tileset is taken from Mario Klingemann. Idea of generating integrated circuits was suggested to me by Moonasaur and their style was taken from Zachtronics' Ruckingenur II. Cat overlapping sample is taken from the Nyan Cat video, Qud sample was made by Brian Bucklew, Magic Office + Spirals samples - by rid5x, Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City overlapping samples - by Arvi Teikari. Summer tileset was made by Hermann Hillmann. Voxel models were rendered in MagicaVoxel.