WFC（重叠模型）：C1 条件与"拼不出来"

全课题骨架：程序化生成 = 不摆位置、只定规则 —— 同一颗种子 + 同一个规则，必须长出同一片内容。 上一课的规则是人写出来的（4 张瓦片 + 一张邻接表）。可很多时候你手里只有一张图，没有"瓦片"这个概念。
这一课换一种来源：规则从样例图里自己数出来 —— 输出里出现的每一个 N×N 小方块，都必须是样例里见过的。 README 把它写成两条：(C1) 输出里只许出现输入里有的 N×N 图案、(Weak C2) 图案的分布也要像。
于是全部内容只有三行：① 把样例图上每个 N×N 窗口取下来，去重、记权重；② 两个图案能接上 ⟺ 重叠部分逐格相同； ③ 剩下的交给上一课那台机器。
四段路：从样例里数图案（15.1）→ 图案之间怎么接（15.2）→ 拼出来并逐窗口验 C1（15.3）→ 边界接起来就拼不出来（15.4）。
★ 本页的样例是两色的（黑/白），于是 一个 N×N 图案就是一枚 N² 位的二进制数 —— 图案集合可以逐个列出来、每条判据都能拿笔核。参考实现支持任意色数，本页只用 2 色，如实标注。保真度：真机可证（可测） —— 算法真的在本页跑，四张表、十条判据、画面上的每一格都出自同一份 buildPatterns() / agrees() / propagate()。本页没有 GPU 成分（重叠模型是纯 CPU 算法），所以不涉及着色与可见面判据。

分段：

图案边长 N：｜取样窗口第 1 个 ← 15.1 的旋钮

接的方向： ← 15.2 的旋钮

输出尺寸： ← 15.3 的旋钮

边界： ← 15.4 的旋钮

（四张表与十条判据在后台跑）

（脚本启动中…）

定点观察：（脚本启动中…）

本帧的读数

（脚本启动中…）

（点「连跑 100 局」或「验一遍 C1」就在这里出数）

15.1 没有瓦片：从样例里数图案

本段只增加一样东西：图案（N×N 的局部小方块）与它的权重（旋钮是「图案边长 N」与「取样窗口」滑块）。
上一段的缺口：上一课的邻接表是人写出来的 —— 可是做一关地形、一块地板，你手里往往只有一张参考图，并没有"瓦片"这种东西。
重叠模型的做法只有一句话（README 算法步骤 1）：把样例图上每一个 N×N 窗口取下来，去重，记下每种出现几次。那个次数就是它的权重。本页的样例是一张 8×8 的两色砖墙（砖缝每 3 行一条、相邻砖行错开 2、砖宽 3 缝宽 1；所以水平周期 4、竖直周期 6）。
能拿笔核：采样窗口数 = (SX−N+1)(SY−N+1)。 N=2 时是 7×7 = 49 个窗口，去重后只有 9 种图案 —— 而"2×2 的两色图"一共只有 2⁴ = 16 种可能；N=3 时是 6×6 = 36 个窗口，去重后 12 种，而可能空间是 2⁹ = 512。
★ 顺带说清华丽数字背后的那件事：N 每加 1，"可能的图案"是平方级地涨（16 → 512），而样例能提供的还是那么几种（9 → 12） —— 这就是 C1 这条约束为什么随着 N 变得苛刻。
★ 两色还有一个好处：一个 N×N 图案就是一枚 N² 位的二进制数（下标沿用参考实现的 x + N*y），所以图案集合可以逐个列在表① 里、权重可以逐个数出来。参考实现支持任意色数（它的 hash() 是 C 进制打包），本页只用 2 色。
★ 一样要如实说：样例图要够大才数得全。本页的 8×8 裁片数出来的图案集合与 "整张墙"（把同一个规格铺到 96×96）上的逐图案相同（判据③ 逐位核过）；再小就会漏 —— 实测 4×6 的裁片在 N=2 下已经够（24 格），而 N=3 要 6×6（36 格）。

定点观察：拖「取样窗口」滑块走遍样例 → 盯住样例图上那个框与旁边放大出来的那一枚图案 → 同一个图案会被很多个窗口取到（表① 的"权重"就是它被取到几次）；再把 N 从 2 切到 3：窗口数从 49 变 36，图案数从 9 变 12，而"可能的图案"从 16 暴涨到 512。

表① 从样例数出来的图案（当前 N 的那一列）。「编号」是它们在图案表里的下标，「值」是那枚 N² 位二进制数对应的十进制（下标 `i = x + N*y`：N=2 时 b0=(0,0)、b1=(1,0)、b2=(0,1)、b3=(1,1)）。
★ 两处可以拿笔核：**权重之和 = 窗口数**（49 / 36）；**N=3 时每种恰好出现 3 次**（36 ÷ 12 = 3）。
★ 「右邻 / 上邻」两列是 15.2 要用的：这一枚图案在这一方向上**能与几种图案接上**。N=2 时右邻合计 21 （81 个有序对里）—— 15.2 会给出这条的手算方法。
★ 深色小方块 = 1（实体），浅色 = 0。
编号	值	N² 位二进制	缩略图	权重	右邻	上邻

15.2 图案之间怎么接：重叠部分逐格相同

本段只增加一样东西：相容判据 agrees（旋钮是「接的方向」两档；N、尺寸、边界都不动）。
上一段的缺口：图案收集齐了，可"哪两枚能左右相邻"还没有定义 —— 而这一步不能再靠人写，否则又回到了上一课。
参考实现的定义只有一句（agrees(p1, p2, dx, dy, N)）： 把两枚图案按 (dx, dy) 错开摆好，凡是重叠到的像素，必须逐格相同。就这一条。
于是邻接表自己就长出来了：对每一枚图案、每一个方向，把"能接上"的那些枚记下来。 N=2 时这条判据可以拿笔算：左右相邻就是 "右列 == 左列"，而一枚 2×2 图案的右列是 (b1, b3)、左列是 (b0, b2)（下标见表① 说明）。按右列把 9 枚图案分成 4 组，组内两两都能接： (1,1) 组 2 枚 → 4 对、(0,0) 组 3 枚 → 9 对、(1,0) 组 2 枚 → 4 对、(0,1) 组 2 枚 → 4 对，合计 21 —— 与参考实现的 agrees 数出来的 21 逐对一致（判据① 把 81 对全核了一遍，0 处不符）。
★ 四方向都数一遍（表②）：N=2 是 21 / 21 / 21 / 21（81 个有序对里的 25.9%）、 N=3 是 16 / 12 / 16 / 12（144 个里的 11.1%）—— 注意 N=3 时横向比纵向松，因为砖墙的横向周期（4）比纵向（6）短。
★ 这一段的旋钮「接的方向」就是把其中几个方向"放开"（不写约束），看会发生什么： 只连横向时，输出的每一行都还像砖墙的一行，但行与行之间随便接 —— 用 N=2 的尺子量，命中率从 100% 掉到 59.42%（判据②/定点观察会给这条）。"像"要求两个方向同时对。

定点观察：把「接的方向」从「四向都用」切到「只连横向」→ 盯住读数行里"用 N=2 的尺子"那一项 → 命中率从 100% 掉到 59.42%：只连横向时每一行都像砖墙的一行，可行与行之间随便接，于是有 40% 的 2×2 窗口是"样例里没见过"的。表② 的 N=2 那一行能拿笔核：21 / 81。

表② 四个方向上的合法有序对数（"合法"= `agrees` 说这两枚能接上）。
★ **手算核对列**：N=2 的左右相邻就是"右列 == 左列"，按右列把 9 枚图案分成 4 组（组内图案见括号），组内两两都能接 ⇒ 组内配对数相加。实测与手算**逐对一致**（判据① 核了全部 81 对）。
★ 「只连横向」的后果：其余两个方向被"放开"（任何图案都能接），于是约束只剩一半。
方向	M² 个有序对	合法对数	占比	手算核对（N=2）

15.3 拼出来，并逐窗口验 C1

本段只增加一样东西：C1 的独立验证（滑窗查集合）（旋钮是「输出尺寸」，其余不动）。
上一段的缺口：邻接表有了，图也拼出来了 —— 可"输出里每个窗口都来自输入"这句话，还没有被验过。
验法就是把 C1 逐字读一遍：拿一个 N×N 的框在输出上滑一遍，每个位置都把框里的 N² 个像素打成一枚整数，查它是不是在样例的图案集合里。注意这个验法完全不读 wave（不看"每格放了什么图案"）—— 它只看最后那张图，所以它是一条独立路线。
实测：生成的图，0 个窗口不在集合里（24×16 一共 345 个完整窗口；最大的一批扫到 291400 个窗口也是 0）。这不是巧合，可以推：窗口 (x,y) 的第 (i,j) 格 = 放在 (x+i, y+j) 那枚图案的 (0,0) 像素，而由 agrees 一路串下来，它恰好等于放在 (x,y) 那枚图案的第 (i,j) 格 —— 所以窗口 (x,y) 就等于那一枚图案本身，当然在集合里。
★ 对照才有意思（表③）：随机涂一张 24×16 的图，命中率只有 56.42%（N=2 尺子）／2.37%（N=3 尺子） —— 而这两个数可以手算：图案数 ÷ 可能的图案数 = 9/16 = 56.25% 与 12/512 = 2.34%。
★★ 本段最值钱的一条在表③ 的第二列：换一把大一号的尺子去量同一张图。 N=2 跑出来的图，用 N=2 的尺子是 100%，用 N=3 的尺子只剩 24.03% —— 它每一个 2×2 窗口都合法，可 3×3 一看就露馅；而 N=3 跑出来的图两把尺子都是 100%。同一件事还有两个读数：一局要手工挑几格（N=2 是 159 格，N=3 是 1 格）、 输出里图案的分布与输入的总变差（0.1401 → 0.0024，这就是 README 的"弱条件 C2"）。 C1 是"每个局部都合法"，不是"整体像"；N 越大，局部条件就越能把整体钉死。

定点观察：按「验一遍 C1」→ 盯住读数行里的"不在集合里的窗口" → 生成的图是 0 个（345 个窗口全过）；再点「一格一张」不行的话就换种子多跑几局， 每一次都是 0。★ 然后把「图案边长 N」从 2 切到 3：用 N=3 的尺子去量那张 N=2 的图，命中率掉到 24.03%；量那张 N=3 的图还是 100%。换一把尺子，同一张图立刻换了结论。

表③ 换尺子量同一张图（24×16，**345 个完整窗口**）。两列是"用哪把尺子"：把 N×N 框滑一遍、查框里的像素组合在不在那个 N 的图案集合里。
★ **手算基准**：随机涂的图命中率 ≈ 图案数 ÷ 可能的图案数 = 9/16 = **56.25%** 与 12/512 = **2.34%** （实测 56.42% / 2.37%，各 200 张图平均）。
★ 「N=2 的图」那一行是本表的正题：**100% 对 24.03%** —— 它在 2×2 这个尺度上完全合法，在 3×3 的尺度上四分之三都不合法。而 N=3 的图两把尺子都是 100%。
★ 「样例 8×8 直接平铺」那一行说明另一件事：样例是 8 行的裁片、而墙的竖直周期是 6， **8 不是 6 的倍数 ⇒ 每 8 行会多出一段砖**，N=2 看不出来（100%），N=3 一看就露馅（85.71%）。
图	用 N=2 的尺子	用 N=3 的尺子	说明

15.4 边界接起来就拼不出来

本段只增加一样东西：边界（不接 / 接成环）（旋钮是「边界」两档；其余不动）。
上一段的缺口：那个"0 个不在集合里"是在不接的边界上量的 —— 棋盘的边缘就是终点，没有任何东西跨过去。如果把边界接起来（左右相接、上下相接，像一张环面），会发生什么？
答案是：能不能拼出来，第一次真正变成了一个问题。不接边界时，本页所有尺寸、所有种子都成功（判据⑨ 扫过）；接成环之后，N=3 只在特定尺寸下成功。
实测的规律（表④，16 个尺寸全中）： W ≡ 0 (mod 4) 且 H ≡ 0 (mod 6) ⟺ 成功；只要有一个不满足，就是 40/40 全失败。那两个数正是样例墙的两个周期（水平 4、竖直 6）—— 道理可以一句话说清： 边界一接上，整张图就成了一张环面；而样例墙本身要能密铺到环面上，前提是环面的两个方向都是它周期的整数倍。 12×18、24×18、24×24、28×12 都行；16×16、12×10、12×14、14×18、18×12 都不行。
★ 有意思的是 N=2 几乎不受影响（24×16 是 0/40、24×18 才 3/40）：因为 N=2 的图案集合太松，它能靠"错缝"把环面硬接上 —— 代价就是 15.3 里那个 24.03%。
★ 这件事有分量，是因为它不是"本页的小脾气"：README 自己写着 "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."，而"给定一组图案能不能密铺平面"在二维上一般不可判定（Berger 1966）。
★ 但要如实标两条：① README 只给了 NP-hard 这个结论，没有证明、也没有归约到 Wang 铺砌 / 二维有限型子移位； ② 本页那条"两个模数"的充要条件是在本页这张样例墙上实测出来的，不是通用定理 —— 换一张样例，那两个模数就是那张样例的周期。

定点观察：把「边界」切到「接成环」，尺寸停在「24×16」，按「自动跑完本局」→ 盯住读数行里"本局"那一项 → 它拼不出来（H mod 6 = 4 ⇒ 环面闭合不了）。再把尺寸换成「24×18」→ 一次就成功（W mod 4 = 0、H mod 6 = 0）。 ★ 按「连跑 100 局」能把这条对照变成数：不符合条件的尺寸 100% 失败，符合的 一局都不失败。

表④ 接成环之后，能不能拼出来（N=3，每格 40 局）。
★ 规律：**成功 ⟺ W ≡ 0 (mod 4) 且 H ≡ 0 (mod 6)** —— 16 个尺寸全中（判据⑨ 现场扫一遍再断言）。
★ 那两个模数就是样例墙的周期（砖宽 3 + 缝 1 = 4；砖高 2 + 缝 1 = 3、相邻砖行错开 ⇒ 6）。
★ 注意 **N=2 几乎不受影响**：它的图案集合松到能"错缝"把环硬接上（代价见表③ 的 24.03%）。
输出尺寸	W mod 4	H mod 6	失败局数	与规律一致？

这一课带走了什么

重叠模型的三行，全部在采集与判据上，一行都没动上一课的机器：① 把样例图上每个 N×N 窗口取下来、去重、记权重；② 两枚图案能接 ⟺ 重叠部分逐格相同；③ 剩下的交给"留一叠 / 传开 / 挑最小熵"那三步。
代价与收益都在这三行里：收益是不用再手写瓦片与邻接表，给一张图就能续画；代价是"N 每加 1，可能的图案平方级地涨"（16 → 512），于是 C1 这条约束越来越苛刻 —— 也正因为苛刻，N=3 时一次观察就把整张图钉死了（159 格 → 1 格），输出连分布都对得上（总变差 0.24%）。
还有一件必须记住的事：C1 是"每个局部都合法"，不是"整体像"。 N=2 的图每个 2×2 窗口都来自样例（100%），可换把 3×3 的尺子一量只剩 24.03%；样例自己的 8 行平铺也是 100% / 85.71%（因为 8 不是竖直周期 6 的倍数）。 要判"像不像"，先想清楚用多大的窗口去量。
下一课指针：这两课讲的都是"规则怎么来、怎么传、什么时候拼不出来"。而真正把它们用到工程里的那一步 —— 把约束钉到具体的内容上（边缘封边、固定几个关键格、分层生成、给不同区域不同权重）—— 才是让它产出"能玩的地图"而不是"好看的图案"的地方；附件 A2 会把"关卡连通性"这类硬要求展开。

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

C1 / C2 的定义、算法步骤 1–3、NP-hard —— Maxim Gumin，WaveFunctionCollapse 官方仓库 README：开篇 "This program generates bitmaps that are locally similar to the input bitmap. Local similarity means that (C1) The output should contain only those NxN patterns of pixels that are present in the input. (Weak C2) Distribution of NxN patterns in the input should be similar to the distribution of NxN patterns over a sufficiently large number of outputs."；步骤 1–3 "1. Read the input bitmap and count NxN patterns. … 2. Create an array with the dimensions of the output (called "wave" in the source)… 3. Initialize the wave in the completely unobserved state…"； 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."： github.com/mxgmn/WaveFunctionCollapse
相容判据与 propagator 的构造 —— 参考实现源码 OverlappingModel.cs： static bool agrees(byte[] p1, byte[] p2, int dx, int dy, int N)（本页件一逐字照抄的就是这一段），以及 propagator[d][t] 由"对所有 t2 判 agrees"建出；图案的索引与权重也在这里（patternIndices / weightList， hash() 把图案按 C 进制打包成一个整数）： OverlappingModel.cs
重叠模型 vs 瓦片模型、约束是"从样例推断"的 —— Isaac Karth & Adam M. Smith， WaveFunctionCollapse is Constraint Solving in the Wild（FDG 2017）： "In the simple tiled version of the algorithm, the patterns are specified as explicit tile constraint relationships. In the overlapping version, the constraints are inferred from the source image, constructing a set of the unique N×N patterns from subimages."；同一篇文章把 C1 写成 "…by ensuring every local window of the output occurs somewhere in the input."，并把相容语义写成 "…compatible in terms of exact matches for the pixels in which their associated local windows overlap."：escholarship.org/content/qt1f29235t （作者主页副本 adamsmith.as/papers/…） ★ 它的可执行形式是 ASP/Clingo 的一条完整性约束： :- adj(X1,Y1,X2,Y2,DX,DY), assign(X1,Y1,P1), not 1 { assign(X2,Y2,P2):legal(DX,DY,P1,P2) }.
重叠 = 高阶马尔可夫链 —— README 的 Comments 段： "The overlapping model relates to the simple tiled model the same way higher order Markov chains relate to order one Markov chains."
边界：periodicInput / periodic —— 同一份源码：构造函数签名 OverlappingModel(string name, int N, int width, int height, bool periodicInput, bool periodic, int symmetry, …)、采样时 int xmax = periodicInput ? SX : SX - N + 1;、渲染时 if (!periodic && (sx + N > MX || sy + N > MY || sx < 0 || sy < 0)) continue;。 ★ 本页把出界处理放在传播那一层（照抄同一条思路）：不接就跳过这一侧、接成环就取模绕回去。
二维有限型子移位（2D SFT）的非空性一般不可判定 —— "it is formally undecidable whether a 2D subshift of finite type is empty or not. This undecidability problem is closely related to the existence of nonempty shifts of finite type without periodic points, or, equivalently, the existence of Wang tile sets…"（Chazottes & Shinoda， arXiv:2010.08998）；以及 Berger 1966 的历史与"Wang 猜想被推翻"（Gopalkrishnan 讲义， courses.cs.duke.edu/…/tilings.pdf）。 ★ 顺带纠正一个常见说法："Wang 铺砌可判定、高维 SFT 不可判定"是错的 —— 一个 Wang 瓦片集恰好对应一个 2D SFT，"给定瓦片集能否密铺平面"与"给定 SFT 是否非空"是同一个问题，两个在一般情形下都不可判定；真正的分界在维数（一维可判、二维及以上不可判）。
★ 三处诚实标注：① C1 这个记号出自 Gumin 的 README，不是那两篇论文（论文全文没有用"C1"，但它们把同一件事操作化成了 ASP 的完整性约束）； ② README 只给了 NP-hard 这个结论，没有证明、也没有归约到 Wang 铺砌 / 2D SFT，我们没有找到把重叠模型的 C1 显式归约过去的一手文献，所以本页只把这条并列摆出， 不声称"WFC 的 C1 就是不可判定的"； ③ 本页那条"接成环成功的充要条件是 W ≡ 0 (mod 4) 且 H ≡ 0 (mod 6)" 是在本页这张样例墙上实测出来的规律（16 个尺寸全中），不是通用定理 —— 换一张样例，那两个模数就是那张样例的周期。

运行时自检 等待脚本…