WFC（瓦片模型）：约束怎么自己传开

全课题骨架：程序化生成 = 不摆位置、只定规则 —— 同一颗种子 + 同一个规则，必须长出同一片内容。 前两课把随机数变成了一张场、又把那张场拧成了山。可还有一整类内容不是"一个数在各处取多少"，而是 一块一块拼起来的东西：地板、墙、路、地块、房间。
这一课换一种规则写法：不说"相邻处要相似"，只说"相邻处必须是一对见过的搭配" —— README 把它叫 simple tiled model，并原话写明"这个模型的传播阶段就是邻接约束传播"。
于是全部内容只有三行：① 每格先留一叠"还可能是什么"；② 某格删掉一个值时，把这个消息传给四个邻居； ③ 挑"可能性最少"的那一格动手。
四段路：一格先留一叠（14.1）→ 约束怎么自己传开（14.2）→ 先削哪一格（14.3）→ 拼不出来是常态（14.4）。 每一段只增加一样东西，其余控件一个字不动。 保真度：真机可证（可测） —— 算法真的在本页跑，四张表、十条判据、画面上的每一格 都出自同一份 propagate() / observe()。本页没有 GPU 成分（瓦片模型是 CPU 算法）， 所以不涉及着色与可见面判据。

（脚本启动中…）

定点观察：先点「一格一张（贪心）」→ 看格与格之间那些亮着的小横杠 → 172 个接口里有 85.7 个接不上（49.8%，手算一半）；再切到「一叠可能」→ 那些接口全变成"待定"，一点判定都还没有。

本帧的读数

（脚本启动中…）

（点「连跑 100 局」就在这里出数）

14.1 别一格一格挑：一格先留一叠

本段只增加一样东西：格子上存的是什么 —— 从"一张瓦片"改成"一叠可能" （旋钮是「起点」两档，传播、观察顺序、网格都还没出现）。
上一段的缺口（本课起点）：要拼一张图，最直觉的做法是一格一格挑一张摆上去。 那就把它摆出来看：在 12×8 的网格上随机摆满（一共 172 个接口），接不上的有 85.7 个 = 49.8% —— 差不多每两个接口就有一个是错的。这不是"手气不好"，是没有任何东西能告诉你摆错了： 你摆到最后一格才发现，而当你只有"一张一张挑"这个动作时，回头也没有用。
能拿笔核：4 张瓦片在某一侧一共 16 种搭配，其中"接口对上"的恰好 8 种 （一侧开着还是关着，两边各两选一 ⇒ 2 × 2 × 2 = 8）⇒ 随机摆，正好一半接不上。实测 49.80% / 49.77% / 49.95%。
WFC 换了个出发点：不挑，先留一叠。每格先写上"四种都可能"，然后只做一件事 —— 把接不上的那些删掉。代价写在读数里：整张图 4⁹⁶ ≈ 6.28 × 10⁵⁷ 种摆法， 穷举不可能，所以唯一的出路是"删"。
★ 顺带说清本页为什么只用 4 张瓦片：真实的 WFC 图集常有几十张，但多出来的瓦片只是把邻接表加长， 算法一个字都不变；4 张的好处是下面每一条邻接规则都能拿笔核一遍。 另外本页的边界是非周期的，而且这个图集里没有一张瓦片会被边缘排除 （任何瓦片在任何方向都至少有一个合法邻居）—— 参考实现里边缘是会封边的（`Model.cs` 的 `Ban`）， 本页没有这一段，如实标注。

14.2 约束不是"检查"，是"传开"

本段只增加一样东西：传播（旋钮是「传播 关／开」，起点仍是叠加态）。
上一段的缺口：每格都是一叠四张，可谁也没法从这一叠里删掉任何东西 —— 除非有人先"定下来"。
传播的规则只有一句话：某格删掉一个瓦片时，问它的四个邻居一句"你还撑得住吗"； 撑不住的值也跟着删，删完再往下一圈问。于是"接口"这条规则会自己走开，不需要谁来监督。
四个按钮让你把画面中央那一格钉死，看它传多远（钉「横」/「竖」/「弯」/「空」，网格 12×8）：
· 钉「横」在 (x, y) ⇒ 它右边整行都被钉成「横」，唯一确定的格数 = W − x
· 钉「竖」在 (x, y) ⇒ 它上方整列都被钉成「竖」，格数 = y + 1
· 钉「弯」在 (x, y) ⇒ 两条尺子同时使，格数 = y + W − x
· 钉「空」⇒ 一格都钉不动（只有它自己 1 格）
为什么是"右"和"上"？回到表①：只有 横 ⇒ 右邻唯一、竖 ⇒ 上邻唯一 这两条会掉到 1 种。 一个方向的形状，就决定了约束往哪个方向传。
★ 而且它传出来的形状不是圆：钉「空」形成的只是"左行 + 下列"两条臂 （21×21 网格上共削动 23 格、而且一格也没削成唯一）：钉「横」一边把右行钉死， 一边把整个右下象限削到 2 种（40×40 网格上共 143 格被削动、其中 19 格削成唯一）。 约束沿行、沿列走，不沿对角线。
★ 还有一件事值得单说：传播不是"重新检查一遍"。检查是"把 96 格全扫一遍"；传播是 只跟着变过的地方走（把"变过的格"压进一个栈，弹出来才去问它的四邻）—— 这正是参考实现的做法。所以"从空棋盘钉住一格"要弹出 72 次（钉「横」在 (0,3)）， 而一局平均下来每次观察只弹十几次：越往后，越没什么可传的。
★ 本页的传播跑到不动点才停（一直弹到栈空），这也是 AC-3 那个算法的终止条件； 判据② 会用"逐弧检查"这条独立路线复核它真的到了不动点。

14.3 先削哪一格：最小熵

本段只增加一样东西：观察顺序（旋钮三档；起点仍是叠加态、传播仍是开）。
上一段的缺口：传播只能削"已经有格子定下来"的地方 —— 而一开始 96 格一模一样（都是四张）， 没有任何东西能把第一刀砍下去。所以必须由我们挑一格、挑一张、钉下去。 挑哪一格，就是本段唯一的旋钮。
三档：① 均匀随机挑（在"还没定下来"的格里随便挑一个）； ② 最小熵 · 平局随机断（挑"还可能的值最少"的那一格 —— 权重全等时熵就是 log|D|， 所以这就是"域最小"；并列时随机挑一个）； ③ 最小熵 · 平局按扫描顺序（同上，但并列时取扫描顺序里最靠前的那一格）。
★ ③ 才是参考实现的写法：它的 Observe 用严格小于（entropy < min）， 所以并列时"第一个遇到的"赢 —— 我们照抄这个细节，并把它单列成第三档，因为它的后果很大。
实测（12×8、各 2000 局、同一颗种子起点）：失败率 7.50% → 0.65% → 0.00%。
★ 两件事值得注意。一、它省下来的全是失败，不是"少挑几格"：三档平均挑 11.7 / 14.1 / 9.6 格 —— ② 反而比 ① 挑得更多（① 常常挑到"域还很大"的格，一刀就把一大片随手定下来， 代价是把后面的路堵死了）。二、平局怎么断，和"挑哪一格"一样重要：③ 与 ② 只差并列时取哪一个， 失败率从 0.65% 掉到 0.00%（2000 局一次都没失败）。这一条参考实现从没承诺过 —— 它是"严格小于"的一个副作用，是我们量出来的。 ★ 我们不声称它"永不失败"：README 自己的原话是这个问题 NP-hard、 "run into contradictions surprisingly rarely"；我们只是在这张图集与这几个尺寸上没量到失败。
★ 表③ 是 ③ 档下一局棋的逐步账：8 步（正好等于网格高度），第 1 步钉在 (0,0) 得到「弯」， 一次级联弹出 96 次 —— 96 格里手工只挑了 8 格，剩下 88 格（91.7%）是约束自己传开的。 同一颗种子换 ② 档要 17 步、① 档 14 步（也在表③ 说明里）。

14.4 拼不出来是常态

本段只增加一样东西：失败之后怎么办（旋钮是「失败后 停下／重开」与「网格尺寸」）。
上一段的缺口：最小熵把失败率压到了 0（在这张图集上），可为什么会有失败，还没有答案。
答案可以在钉下去之前就算出来：相邻两格随机取值，合法搭配只有 8/16 = 一半 ⇒ 距离 1 的两格，矛盾概率 = 1 − 1/2 = 50.0%（实测也正是 50.0%）。再往外散： 距离 2 → 31.3%、距离 4 → 21.9%、距离 10 → 16.3%、距离 24 → 13.6%（实测曲线在表④ 说明里）。 所以"拼不出来"不是实现出错，是约束本身无解 —— 而它离得越远越难撞上，恰恰因为那条"规则"传不了那么远。
网格越大越容易撞上：随机挑档的失败率 7.50% → 13.70% → 20.70% → 31.00% → 40.67% （12×8 → 16×12 → 24×16 → 32×24 → 48×32，表④ 现场跑出来）。
参考实现遇到这件事怎么办？一手源的原话是不回溯 —— "Unlike many constraint solvers, the reference implementation of WFC does not employ backtracking. When it encounters a contradiction, it restarts from the beginning, giving up if it fails too many times (by default, the limit is ten attempts)." 本页的两个按钮就是这两种处置：停下（把那个被削空的格子用白色叉标出来）与 重开（换一颗种子重来，最多 10 次 —— 面板上会写"第几次重开"）。
★ 本页只做瓦片模型（规则 = 邻接），所以"拼不出来"只来自"接口接不上"这一条。 下一课换重叠模型，规则变成"输出里出现的每个 N×N 局部图案都必须来自输入"（README 的 C1 条件）—— 那时"拼不出来"会换一副面貌，而 C1 的好处是它可以逐图案机器验证，比这里的"失败率"硬得多。

这一课带走了什么

整课的三个动作，就是 WFC 的全部：① 每格留一叠；② 某格删一个值时，把这个消息传给四个邻居； ③ 挑"可能性最少"的那一格动手。剩下的东西（权重、对称性、几十张瓦片、3D、边界封边、重叠模型） 都只是把这三行加长，没有换掉任何一行。
它还解释了几件工业上的事：为什么 WFC 一跑起来就"好看"（传播把 85%～97% 的格子自己定下来了， 人只挑十几格）；为什么"挑哪一格"这种细节会被单独写进论文（它是唯一真正影响成败的旋钮）； 为什么这类算法永远要给一个"失败上限"（约束无解是内在的，不是 bug）； 以及为什么它至今仍被当成"能看的过程"（每一步都在删东西，读者能跟着看）。
下一课指针：这一课的规则是"相邻两格必须是一对见过的搭配"。下一课换一种写法 —— "输出里出现的每一个 N×N 局部图案都必须来自输入"（README 的 C1 条件），也就是 重叠模型。规则从"两格"变成"N×N 的一块"，好处是 C1 可以逐图案机器验证 —— 我们可以真的去数"输出里有没有出现过输入里没有的图案"，这个数必须是 0。

本页用到的做法，出处在哪

• 瓦片模型的规则 —— Maxim Gumin，WaveFunctionCollapse 官方仓库 README： "If we simplify it even further by storing not the probabilities of pairs of colors but the probabilities of colors themselves, we get what we call a "simple tiled model". The propagation phase in this model is just adjacency constraint propagation."； 以及它与重叠模型的关系："The overlapping model relates to the simple tiled model the same way higher order Markov chains relate to order one Markov chains."： github.com/mxgmn/WaveFunctionCollapse
• 观察 / 传播 / 矛盾三步 —— 同一份 README： "Find a wave element with the minimal nonzero entropy…"、 "On each propagation step new information gained from the collapse on the previous step propagates through the output."、 "It may happen that during propagation all the coefficients for a certain pixel become zero. That means that the algorithm has run into a contradiction and can not continue."； NP-hard 的原话也在同一段："The problem of determining whether a certain bitmap allows other nontrivial bitmaps satisfying condition (C1) is NP-hard, so it's impossible to create a fast solution that always finishes. In practice, however, the algorithm runs into contradictions surprisingly rarely."
• 最小熵启发式的出处 —— 同一份 README 的「Used work」自己点的名： "We introduce the lowest entropy heuristic that removes the directional bias in generated results" （Merrell 的 Model Synthesis 用的是带方向偏置的 AC-3）。README 里关于它为什么有效的原话是 "I noticed that when humans draw something they often follow the minimal entropy heuristic themselves."
  ★ 一处如实标注：把"最小熵启发式"等同于 AI 教材里的 MRV（minimum remaining values / fail-first） 这个说法，我们没有找到任何一份一手原文逐字这么写 —— 两者分别写作 "minimal entropy heuristic"（Gumin）与 "minimum remaining values (MRV)"（Russell & Norvig, AIMA 第 5 章）， 语义确实对应，但本页只把两者并列摆出，不声称前者"就是"后者： aima.cs.berkeley.edu/newchap05.pdf
• arc consistency 与 AC-3 的定义、终止条件 —— AIMA 第 5 章与 MIT 6.034 讲义： "X_i is arc-consistent with respect to another variable X_j if for every value in the current domain D_i there is some value in the domain D_j that satisfies the binary constraint on the arc (X_i, X_j)."； 队列法"一直做到没有弧在队列里"即为不动点： courses.csail.mit.edu/6.034s/handouts/spring11/supplement-arc.pdf； ★ 一处版本差异：README 说参考实现用的是 AC-4（Mackworth 1977 提出 AC-3，Mohr & Henderson 1986 的 AC-4）， 而本页用的是 AC-3 那条"只跟着变过的地方走"的队列写法 —— 两者到达的不动点完全一样， 差别只在"每次重算哪些支撑"的工程细节上，如实标注。
• 不回溯、遇矛盾重开 —— Adam M. Smith & Isaac Karth（FDG 2017 与 IEEE ToG 2021）： "Operationally, WFC implements a non-backtracking, greedy search method."； "Unlike many constraint solvers, the reference implementation of WFC does not employ backtracking. When it encounters a contradiction, it restarts from the beginning, giving up if it fails too many times (by default, the limit is ten attempts)."： adamsmith.as/papers/tog-wfc.pdf、 escholarship.org/content/qt1f29235t
• 局部约束可满足性是 NP-complete —— Marcin Kopczyński, Hyperbolic Minesweeper is in P： "In general finding out whether such constraints can be satisfied is NP-complete (although this does not happen in typical PCG applications)."： arxiv.org/pdf/2002.09534v2.pdf
• 瓦片模型的数据结构（邻居表 / 权重 / symmetry / 边界） —— 参考实现源码： SimpleTiledModel.cs 里的 propagator[d][t1]（稀疏邻接表）、 weightList（权重）、symmetry（按 D4 展开旋转反射）、 以及基类 Model.cs 里的 periodic（边界是封边还是环面）： SimpleTiledModel.cs、 Model.cs
• ★ 两处诚实标注：① "矛盾率（contradiction rate）"这个术语没有找到一手出处 —— 能找到的最接近的可量化陈述就是上面那句"失败太多就放弃（默认 10 次）"。 所以本页表④ 的"失败率"是本页自己定义并现场跑出来的数，我们不声称它是行业规范指标。 ② 本页的"③ 熵·扫描平局"在 2000 局里一次都没失败 —— 这是实测事实， 不是"永不失败"的承诺（README 自己的原话是 NP-hard、"surprisingly rarely"）。 表④ 的局数逐格写在最右列，读者可以自己重跑。