撰写了文章更新于 2018-04-28 14:46:52

WaveFunctionCollapse源码阅读笔记

在牛关，你甚至可以学习〇〇

前言

去年，牛关有一个地牢生成的问题，在这个问题下的回答提到了一个 WaveFunctionCollapse 的 repo。我和认识的许多人在看到这个 repo 的介绍，尤其是电路板那里，无不眼睛一亮。它到底是如何运作的？自看到这个问题的第一天我就想找个机会读一下它的代码。

概览

整个代码行数不多，接近四位数。主要的类有三个

class            Model ~220行
class OverlappingModel ~230行
class SimpleTiledModel ~270行

其中后面两个继承自前者。 Model 类是整个程序的核心部分，有关生成的代码都在这里面。后两者提供的是实用上的功能补全，其中 OverlappingModel 自行处理给定的样例，稠密地划分许多 pattern ，并自动计算它们之间的连通性；而 SimpleTiledModel 则是读取给定的数个 pattern 以及描述了它们之间连通性的 xml 文件。它们处理好数据后，将数据赋给 Model 类中一些 protected 属性的域（或者说成员变量），随后就是调用 Model 类的相关流程去生成最终模型啦。

输入

现在我们来看看这些 protected 属性的域。

protected bool[][]  wave;
protected int[]     observed;
protected bool      periodic;

protected int       FMX, FMY, T;

protected int[][][] propagator;
protected double[]  weights;

protected Random    random;

wave 是程序的一个核心，但是它是 protected 属性是为了输出而不是输入。observed 同样。 periodic 描述的是最终模型的循环连通性，在此也不提（而 Model 类型也没有用到）

FMX 和 FMY 描述的是最终模型生成的大小，而 T 是可用的 pattern 的数量。这三个变量是最基础的三个。

propagator 描述了 pattern 之间的连通性，它的大小是 4 × T × 不确定。其中 4 显而易见地代表四个方向， T 则是对所有 pattern 的遍历，最后一个维度即这个 pattern 在某个方向上所有可能连接的 pattern 的列表。

weights 描述了 pattern 的权重。权重越大的 pattern 出现的几率越高。在 SimpleTileModel 中，权重是指定的，而在 OverlappingModel 中，权重根据出现次数计算，出现得越多，权重越大。下文中 weights 简称为 w。

random 则提供了一个随机器，没什么好说的。

核心方法

Model 的 run 过程如下

if (wave == null) Init();

Clear();
random = new Random(seed);

for (int l = 0; l < limit || limit == 0; l++)
{
    bool? result = Observe();
    if (result != null) return (bool)result;
    Propagate();
}

return true;

这里可以看到它描述了生成的全过程，涉及了四个方法 Init(), Clear(), Observe() 和 Propagate()。

Init() 和 Clear()

字面意思的初始化，联合 Clear() 方法来看，它们总共干了这么几件事：

生成大小为 (FMX * FMY) * T 的 bool 数组 wave，初始全部为 true； wave 数组描述的是最终模型的某个点在目前的阶段是否可以采用某一个 pattern，最开始当然是都可以啦。
生成大小为 (FMX * FMY) * T * 4 的 int 数组 compatible， compatible[i][t][d] 值为 i 位置采用第 t 个 pattern 在 d 这个方向上可用的 pattern 数，从 propagator 中获取。
计算大小为 T 的 weightLogWeights 数组（以下简称 wLW ），如字面意思。
- ```
wLW[t] = w[t] * log(w[t])
```
计算 sumOfWeights ，即对所有 w 求和，生成 sumsOfWeights 数组（下称sOW），全部初始化为 sumOfWeights 。
计算 sumOfWeightsLogWeights ，对所有 wLW 求和，生成对应数组（下称 sOWLW），同样全部初始化为求和结果。
计算 sumOfOnes，好吧，这玩意就等于T，同样生成数组（下称 sOO），全部初始化为T。
计算初始熵，startingEntropy = log(sOW) - sOWLW / sOW 同样生成对应数组。熵可以简单地理解成这个点的不确定性，选择性越多，不确定性越大，熵也就越大。
生成二元数对的栈 stack。

Observe()

初始化完成后，我们就进入了 Observe() 和 Propagate() 的循环中。

Observe() 首先挑选最终模型的某一个点，要求它必须有多个可选 pattern ，即这个点的 sOO >1，然后要求这个点的熵最小。在获取最小的时候，不会用直接的熵进行比较，而是还会加上一个 0~10^(-6) 的噪音。

然后，如果没有找到这样的点，说明最终模型已经收敛，返回 true 咯~

对于选择的点 p ，首先选择一个它可用的 pattern t，依赖于 w，如上文所述 w 越大选到的可能性越大。此时也就意味着将这个点收敛到这个pattern t。

随后对于所有非 t ，调用 Ban(p, t) 方法。

Ban(p, t)

Ban(p, t) 方法意味着 p 无法选择 t，要将它从各种 sumOf 中去除。具体的计算方式如下，看一看就好，更复杂的原理参见论文。

double sum = sumsOfWeights[i];
entropies[i] += sumsOfWeightLogWeights[i] / sum - Math.Log(sum);

sumsOfOnes[i] -= 1;
sumsOfWeights[i] -= weights[t];
sumsOfWeightLogWeights[i] -= weightLogWeights[t];

sum = sumsOfWeights[i];
entropies[i] -= sumsOfWeightLogWeights[i] / sum - Math.Log(sum)

此外，每 Ban 一对 (p, t) 就把他加入栈中， Propagate() 中会用到，同时它也会再次调用 Ban()。

Propagate()

Propagate() 是一个清栈的过程，所做的事情也十分简单：只要栈中有东西，就取出来。对于这样一个数对 (p, t) 意味着 p 点无法选择 pattern t，于是就要对应地处理 compatible 数组。由于 compatible 记录的是某个方向可以选择的 pattern 数，于是考察 p 临近的四个方向，如果有任何一个点对于某个 pattern 的 compatible 数为0，即说明它无法再选到这个 pattern 了，于是再次调用 Ban 方法。就这样，循环直至栈清空。

就这样不断循环，直到所有的点收敛到某个固定的 pattern 上。若发现某个点无法选到任何一个 pattern ，那就从头来一遍生成过程。在 Main.cs 中可以看到，它会进行数次尝试。

总结

总的来说，这个算法的原理还是非常容易理解的，基本上是根据既定规则生成模型，只不过在选择 pattern 时参考了波函数坍缩，提供了非常随机化的结果。主要思路也就是根据点的选择可能性计算“熵”，每次选择熵最小的点进行坍缩，看最后可否收敛。这个部分应有更为详细的论证过程，可以在论文中找到，此外论文中也提供了大量更复杂的实验结果。

WFC 模型其实非常抽象，可以用来生成很多东西。原 repo 下的 Notable ports, forks and spinoffs 板块提供了许多相关 repo ，比如这个通过相同原理来生成诗歌的。更多的用途就等待你去发掘啦~

你的游戏中有没有可以用到它的地方呢？