2018年4月

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 = Math.Log(sumOfWeights) - sumOfWeightLogWeights / sumOfWeights

同样生成对应数组。
生成二元数对的栈 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 ,比如这个通过相同原理来生成诗歌的。更多的用途就等待你去发掘啦~

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

浅谈艺术欣赏与创作的关系

  欣赏是艺术活动的核心,对作品的理解程度则取决于审美能力。而对于创作的学习来说,审美能力则更为重要——你不仅要通过欣赏来评估自己的作品,也需要用来发现并理解别人作品中有价值的部分。而创作能力的提升也能帮助你更好地提升审美能力,因为有些东西你需要通过实践才能理解得更透彻,创作者的视角和纯粹欣赏者的视角是不尽相同的。因此,创作的学习也是创作能力和审美能力螺旋式上升的过程。
  这是很自然的结论,却常常被人忽视。在初学创作的时候,最常见的情况是几乎不去提高审美,完全靠自己的经验来评判。这种情况下,创作会很快陷入瓶颈,创作能力也会受到审美能力的限制无法继续提升。往往到了这个阶段,人们才会意识到审美能力的重要性。需要明确的是,欣赏者是创作者的超集,绝不存在不是优秀欣赏者的优秀创作者——除非你把乱涂乱画却画出了绝妙作品的猴子也称作创作者。
  在音乐领域,角色要更加细化。听众是演奏者的超集,而演奏者是创作者的超集。这里的演奏者,不同于一般意义上严格的乐器演奏者,而是更广义的、能把握声响细节的人。传统的乐器演奏者是,歌唱者也是,甚至只经过了良好的视唱练耳训练的人也是。这三者在实际的艺术活动中的顺序则要反过来——创作者将脑海中的声音转换成乐谱记录下来,演奏者将乐谱还原成声音,最后传达给听众。于是包含关系就很清晰了:演奏者需要先会听,才能保证自己演奏的是自己想传达给听众的;创作者需要会演奏,才能保证写下的乐谱是能被演奏者理解并还原自己想法的。
  成熟的艺术形式是一定会有足够的理论来支撑整个体系的。理想中的理论能解释这种艺术形式中的一切东西,然而这种级别的理论往往并不存在。即便如此,许多古老的艺术形式都有着庞大而丰富的理论,足够所有爱好者学习理解上好一阵子。这些理论往往包含的是一些常见的规律、指南,更像是一种经验的总结。学习理论,也正是学习这些前人的经验总结,以让自己的欣赏的时候除了感性,还能用理性去发掘更多的东西。典型的例子比如巴赫(J.S.Bach),巴赫的作品的巨大价值并不直接体现在听觉上,而是需要通过对谱子进行细致的分析得出。因此一直以来都有很多人去研究巴赫的谱子,大到曲式,小到音符,几乎到处都有可以挖掘的东西。这种分析,其实是基于理性的、更为细致的欣赏活动,而它显然需要相当程度的理论知识支撑。而感性的欣赏活动,也有需要学习的东西,典型的比如无调性音乐,一般作为听惯了调性音乐的人,刚接触无调性都会产生“这都什么玩意”的想法,纯粹的感性在欣赏无调性音乐的时候也需要一定的学习乃至训练。
  当然以上仅为我个人观点,我知道的通俗音乐界有很多不屑于学习现成理论,用自己的理解来重构整个体系的,而且也有人确实能写出不错的作品。这个我只能说见仁见智,我也没资格评判不同的想法,只能说一下我自己的理解。
  本来还想谈一谈游戏方面,不过我感觉自己在游戏方面就是那种几乎完全没学习过理论,纯粹靠臆想来作为自己欣赏的理论基础的人,所以还是作罢。我也有一阵子没关注太多东西了,就连“游戏界目前主流的还是依赖纯粹的经验去设计”的结论也不敢说。不过我觉得这些东西在电子游戏也是相通的,它会是很奈斯如果有大佬可以说一下自己的感受。