程序化内容生成：Wave Function Collapse

可视化演示

交互展示WFC算法从超position初始化到约束传播逐格坍缩的完整流程及瓦片邻接规则定义。

算法起源：量子灵感的种子

在织布机发明之前，织布全靠工匠一梭一梭地排线。手里明明有一块漂亮的碎花布，想复制同样的花纹，却只能埋头苦干几天几夜。Wave Function Collapse 就是一台“会看样学样”的织机：你递进去一小块碎布，它自己提取花纹规律，转眼织出一整匹风格统一的布。

2016 年，Maxim Gumin 发布了这个开源项目，名字直接取自量子力学。在量子世界里，一个粒子在被观测前可以同时处于多个位置——这叫“叠加态”；观测的瞬间，它才“坍缩”为一个确定状态。WFC 把这套语言借了过来：每个格子一开始“既是草地又是森林又是水”，生成的过程就是逐个观测它、让它坍缩，直到整张地图尘埃落定。

程序化内容生成（PCG）在游戏里并不新鲜，Perlin 噪声、随机砖块都能生成地图。但传统方法很难复刻美术风格：你给它看一张手绘村庄，它学不会村庄的模样。WFC 的核心价值正在于“样子驱动生成”——只要有一张手工小样，就有机会用同样的风格变出无穷地图。独立游戏《Townscaper》就是这套思路的代表作。

碎花布再美，也要有人读懂花纹才能复制。WFC 学会了量子力学的语言，它就把“读懂”变成了可计算的流程——这正是我们从下一节开始逐层拆解的零件。

核心概念：一根线的叠加态

织一匹布时，每一根纬线在穿过经线之前，都可以是任意颜色——它“叠加”了所有颜色在身。织布匠的手一落，它才“坍缩”成一种颜色。更重要的是，这根线的颜色一旦定下来，旁边的线就不能随便选了，必须符合花纹规律，否则布面就会乱成一团。

WFC 里对应的四个核心词可以这样记：格子就是布面上的一个位置；格子里的“可能性列表”就是叠加态；从列表里选定一个结果，就是坍缩；确定后清理邻居的不可能选项，就是约束传播。还有一个度量叫“熵”：可能列表越短，信息熵越低，代表这块地方越接近“板上钉钉”。

为什么熵很重要？想象你面前有两个格子：一个还剩 10 种可能，一个只剩 2 种。聪明的织布匠一定会先处理只剩 2 种的格子——它几乎已经明确了，先定下来几乎不会错。WFC 每一轮都优先挑选熵最低的格子，这正是算法稳定不崩的秘密之一。

一根线悬在半空时，谁也不知道它是什么颜色；织布匠落手之后，它才从“无数可能”变成“一个事实”。WFC 的每一步，都是在重复这个朴素动作。

核心流程：织布的四个动作

有经验的织布匠不会从左到右硬织，而是先找花纹最清晰、最没悬念的区域落手，再像水面涟漪一样向外扩散。先定“铁板钉钉”的，再顺藤摸瓜——WFC 的主循环正是这么设计的。

整个流程可以拆成四步。第一步是初始化：每个格子都持有全部候选模式，也就是所有格子都处于叠加态。第二步是选择：找出熵最低、最接近确定的那个格子。第三步是坍缩：按权重随机给它一个确定答案。第四步是传播：把新答案带来的约束传递给上下左右邻居，把邻居中不可能出现的模式清扫出去。如果扫到某个格子的候选列表变成空的，说明出现了矛盾，算法就要回退或换随机种子重来。

这个“选择—坍缩—传播”的循环会一直进行，直到所有格子都有了明确答案。优先选择熵最低的格子，就像先拼拼图里图案最明显的那几块——确定性强，出错概率小，后面的约束也会更顺畅。

织布匠落手快，但绝不乱落：越是常见的花纹越容易织出来。这一份“按经验出牌”的随机，就是 WFC 风格统一的底气。

邻接规则：花纹的语法

碎布上的“红花旁边一定配绿叶”，就是花纹的语法。如果你记住了这一句，就能推理出一块更大的花布大致应该长什么样。WFC 的邻接规则，就是给机器学语法用的。

具体做法用一个词概括：滑窗提取。拿一个 2×2 的小窗口，从样例图的左上角滑到右下角，每滑到一处就记下一个“模式块”，同时统计它出现的次数。接着检查每两个模式块能否左右相邻或上下相邻：如果它们的接缝像素完全吻合，就在邻接表里记一笔“合法”。

有了这张邻接表，生成阶段就简单了：每次某个格子确定了一种模式，就去查表，把邻居中所有不合法的模式划掉。这张表是单向的还不够，实战中往往还要额外建立反向邻接表，让约束既能从“我”流向“右边”，也能从“右边”流回“我”，四方向传播才跑得起来。

邻接表就是织布匠脑子里那本“花纹词典”。每落一梭，他都要悄悄翻一页词典；每翻一页词典，一整片布面的命运就被悄悄改写了。

参数调优：织布匠的旋钮

一台好的织布机必须有几个顺手的旋钮：图案单元多大、要不要对称变换、布边要不要无缝衔接、换一个种子是不是又能织出新花样。WFC 的参数调优，本质上就是调这些旋钮。

最基础的是输出尺寸，也就是你想织多大一块布；其次是模式尺寸 S×S——S 越小，生成越自由但花纹容易碎；S 越大，纹样越保真但几乎是在“复读”样例。许多成熟方案会给模式增加旋转和镜像变体，让一个“红花”变成四个朝向，多样性立刻翻四倍。

周期模式是另一个常用旋钮：打开后，布匹的左边和右边缝合，上边和下边缝合，生成结果是能无限平铺的无缝贴图。种子则控制整台机器的随机序列：同一套参数、同一个种子，可以复现同一块布；换颗种子，又得到一块风格相同但纹路各异的料子。

旋钮调得好，织出来是桌布窗帘；调得不好，就是一团乱线头。WFC 的工程魅力，就在于同一个核心算法配不同参数，能适配截然不同的美术风格。

应用实践：从碎布到大千世界

当你终于能织出平整又有风格的一匹布，下一步自然是织更大的东西：2D 像素地图是“平面织法”，3D 场景就是“立体编织”。WFC 的实际应用，正是沿着这个维度一路外推的。

在 2D 像素时代，最常见的是平台跳跃关卡：拿一小块手工绘制的关卡切片当样例，让 WFC 生成一整张岩石、砖块、陷阱和金币分布合理的关卡。在 3D 场景里，把 2×2 模式升级为 2×2×2 体素模式，邻接表从四方向扩展到六方向，就能生成建筑群落、洞穴和室内家具布局。

但游戏关卡不是“好看”就够，还要能玩：必须有通路、有敌人、有补给，难度曲线要合理。每一个设计规则都是一个约束集合，真正可玩的地图，必须落在所有约束集合的交集里。这也是 WFC 与纯美术生成工具最大的不同——它输出的每一个方案，都要被你叠加的规则反复检验。

从一块碎花布到一整座城堡，WFC 用一条朴素的道理贯穿始终：先有规则，再有世界。你递给它的每一块碎布，都在替你说出——这个世界应该长成什么样。

AI 应用场景

Python 演示

import random T = [[0, 0, 0, 1],     [0, 0, 1, 1],     [0, 0, 1, 2],     [0, 0, 1, 2]]S, W = 2, 6 def extract():    pats, cnt = [], {}    for i in range(3):        for j in range(3):            p = tuple(T[i+x][j+y] for x in range(S) for y in range(S))            if p not in cnt:                pats.append(p)            cnt[p] = cnt.get(p, 0) + 1    return pats, cnt pats, cnt = extract()weights = [cnt[p] for p in pats] def build_adj(pats):    P = len(pats)    right = [set() for _ in range(P)]    down = [set() for _ in range(P)]    for a in range(P):        for b in range(P):            if pats[a][1] == pats[b][0] and pats[a][3] == pats[b][2]:                right[a].add(b)            if pats[a][2] == pats[b][0] and pats[a][3] == pats[b][1]:                down[a].add(b)    left = [set() for _ in range(P)]    up = [set() for _ in range(P)]    for a in range(P):        for b in right[a]:            left[b].add(a)        for b in down[a]:            up[b].add(a)    return right, down, left, up right, down, left, up = build_adj(pats)DIRS = [(1, 0, right), (-1, 0, left), (0, 1, down), (0, -1, up)] def run(seed):    random.seed(seed)    wave = [[list(range(len(right))) for _ in range(W)] for _ in range(W)]    stack = []     def prop():        while stack:            r, c = stack.pop()            prev = wave[r][c]            for dr, dc, adj in DIRS:                nr, nc = r + dr, c + dc                if 0 <= nr < W and 0 <= nc < W:                    ok = set()                    for p in prev:                        ok |= adj[p]                    nxt = [p for p in wave[nr][nc] if p in ok]                    if nxt != wave[nr][nc]:                        wave[nr][nc] = nxt                        stack.append((nr, nc))     while True:        cells = [(r, c, len(wave[r][c]))                 for r in range(W) for c in range(W)                 if len(wave[r][c]) > 1]        if not cells:            break        r, c, _ = min(cells, key=lambda t: t[2])        chosen = random.choices(            wave[r][c], weights=[weights[p] for p in wave[r][c]])[0]        wave[r][c] = [chosen]        stack.append((r, c))        prop()        if any(not x for row in wave for x in row):            return None    return wave wave = Nonefor s in range(30):    wave = run(s)    if wave is not None:        break if wave is None:    print("生成失败：请调整样例图或模式尺寸")else:    for r in range(W):        print(' '.join(str(pats[wave[r][c][0]][0]) for c in range(W)))

1. p = tuple(T[i+x][j+y] for x in range(S) for y in range(S))用 2×2 滑窗在样例图上提取一个模式块。
2. cnt[p] = cnt.get(p, 0) + 1统计每个模式块出现的次数，作为后续抽签的权重。
3. weights = [cnt[p] for p in pats]把模式列表映射成权重列表，出现越多越容易被选中。
4. if pats[a][1] == pats[b][0] and pats[a][3] == pats[b][2]:判断模式 B 的左边一列能否接在 A 的右边一列上。
5. for b in right[a]: left[b].add(a)由“右邻”表反推出“左邻”表，让约束能向四个方向传播。
6. cells = [(r, c, len(wave[r][c])) ... if len(wave[r][c]) > 1]找出所有处于叠加态、还没确定的格子。
7. r, c, _ = min(cells, key=lambda t: t[2])选择熵最低（候选模式最少）的格子优先处理。
8. chosen = random.choices(wave[r][c], weights=[weights[p] for p in wave[r][c]])[0]按权重随机坍缩，保留样例的风格倾向。
9. nxt = [p for p in wave[nr][nc] if p in ok]用邻接表修剪邻居的候选模式，这就是约束传播。
10. if any(not x for row in wave for x in row): return None一旦有格子的候选清空，说明矛盾，立即返回失败让上层换种子重试。

常见误区

面试题