Wave Function Collapse（WFC）是一种从单示例图像或瓦片集合生成新内容的程序化生成算法，其核心思想源自量子力学中的波函数坍缩概念。该算法由 Maxim Gumin 于 2016 年提出，至今已在游戏开发、像素艺术、关卡设计等领域获得广泛应用，包括《Caves of Qud》《Bad North》《Townscaper》等知名游戏均采用了这一技术。本文将从工程实现角度深入解析 WFC 的核心机制，为开发者提供可落地的参数指南。
算法核心模型：重叠与平铺
WFC 算法包含两种核心模型，分别适用于不同场景。理解这两种模型的差异是正确实现算法的第一步。
重叠模型（Overlapping Model） 是最原始的实现方式，它从输入位图中提取所有 N×N 大小的像素模式，然后在输出中保持这些模式的存在。典型值为 N=3，即考虑 3×3 像素窗口内的模式。该模型的输出与输入具有高度局部相似性，非常适合纹理生成和像素艺术创作。实现时，每个输出位置实际上代表一个可能的 N×N 模式集合，算法需要确保相邻位置的模式在重叠区域保持一致。
平铺模型（Simple Tiled Model） 进一步简化了问题，它将输入定义为有限集合的瓦片，每个瓦片具有预定义的邻接关系。该模型不依赖于从图像中提取模式，而是直接使用人工定义的瓦片及其相邻约束。对于平铺模型，N×N 的概念退化为单个瓦片单元，约束传播简化为纯粹的邻接关系检查。平铺模型的计算开销显著低于重叠模型，适合大规模关卡生成。
两种模型的选择取决于具体需求：若希望从单张图像自动生成内容，应选择重叠模型；若需要精确控制瓦片组合和关卡结构，平铺模型更为合适。
模式提取与数据结构
重叠模型的实现首先需要从输入图像中提取所有唯一的 N×N 模式。这一步骤看似简单，但涉及若干关键技术细节。
模式提取的基本流程如下：遍历输入图像的每一个可能的 N×N 窗口，将窗口内容转换为哈希键并存储在字典中，同时统计每个模式的出现次数。模式的出现频率直接影响后续坍缩时的选择概率 —— 高频模式被选中的可能性更高，这实现了弱约束条件（C2）：输出中模式的分布应与输入相似。
在实现层面，模式数据结构的效率直接影响整体性能。常见的做法是使用整数位掩码或字符串键值作为哈希索引。对于彩色图像，可能需要对颜色进行量化以减少唯一模式的数量。原始实现中采用的 N=3 对于 256 色图像会产生最多 1677 万种理论模式，但实际图像中的唯一模式数量通常远小于此值。
旋转与反射增强 是提升生成多样性的重要手段。在提取模式时，可以将原始模式通过 D4 二面体群（包括 4 次旋转和 4 种镜像变换）进行变换，将所有变体添加到模式集合中。这不仅增加了输出变化，还能确保生成结果在视觉上更加自然。需要注意的是，增强后的模式权重应进行归一化处理，避免因重复计数导致概率偏差。
熵计算与观察步骤
WFC 算法的核心迭代由两个交替步骤组成：观察（Observation）与传播（Propagation）。理解熵的计算方式是实现观察步骤的关键。
香农熵用于量化每个输出位置的不确定程度。对于特定位置，其熵定义为所有可能模式的概率对数的负和。数学表达式为：H = -Σ(p_i × log₂(p_i))，其中 p_i 表示第 i 个可能模式的概率。当某位置只有一个可能的模式时，熵为 0，表示该位置已被确定；当所有模式概率相等时，熵达到最大值。
在实际实现中，算法通常采用简化的熵计算方式。由于系数是布尔值（true 表示允许，false 表示禁止），每个位置的可能模式数量直接决定了熵值。选择熵值最低的非零位置进行坍缩有两重含义：一是优先确定那些约束较多的位置，二是减少传播步骤需要处理的变动。这种最小熵启发式（Lowest Entropy Heuristic）使得算法的中间状态可视化效果极佳，也是其令人着迷的原因之一。
坍缩过程根据当前可能的模式集合按概率随机选择一个模式作为该位置的最终值。概率通常与输入中该模式的出现频率成正比。实现时需要使用加权随机选择算法，例如轮盘赌选择或二分查找法，以确保选择的随机性和正确性。
AC-4 约束传播算法
当一个位置被确定后，其信息需要传播到相邻位置以维持局部一致性。这一过程通过约束传播实现，WFC 采用的是 AC-4 算法（Arc Consistency Algorithm 4），由 Mohr 和 Henderson 于 1986 年提出。
AC-4 算法的核心维护两类数据结构：支持列表（Support List）和逆邻接表（Inverse Adjacency）。支持列表记录每个位置可以匹配哪些相邻位置的可能模式；逆邻接表则记录哪些位置依赖于某个特定位置。这两个数据结构在初始化时构建，后续的传播步骤通过更新它们来快速判断约束冲突。
传播的具体流程如下：当位置 P 被确定为模式 M 后，算法遍历所有与 P 相邻的位置 Q。对于每个相邻位置 Q，检查其所有可能模式是否仍然与 M 兼容。如果某个模式因 P 的确定而变得不兼容，需要从 Q 的可能集合中移除该模式。若 Q 的可能集合发生变化，则将 Q 加入待处理队列，递归地传播这一变化。
AC-4 算法的关键优势在于其增量式更新特性。每次坍缩只影响局部区域，不需要重新计算整个网格的状态。实际测试表明，相对于原始的信念传播（Belief Propagation）方法，AC-4 在 CPU 上的运行速度提升了一个数量级，同时生成质量并无显著差异。
工程实现关键参数
将 WFC 应用于实际项目时，以下参数需要根据具体场景进行调整。
窗口大小 N 是最核心的参数。N=2 时生成的图像与输入高度相似，但可能产生重复感；N=3 是大多数场景的最佳选择，在相似度和多样性之间取得平衡；N=4 或更大值会显著增加计算开销和内存消耗，同时更容易遇到矛盾导致生成失败。对于平铺模型，N 实际上固定为 1，邻接关系由瓦片定义决定。
输出尺寸直接影响生成时间和内存占用。初始实现中，算法在遇到矛盾时会直接放弃本次生成并返回空结果。改进版本引入了回溯机制，在检测到矛盾时返回上一步重新选择。实际部署时，建议设置最大重试次数（如 10-100 次），在多次失败后考虑调整参数或使用更宽松的约束。
** 周期性边界（Periodic Boundary）** 是另一个重要选项。启用后，输出图像的边缘会与对边相连，形成环面结构。这有助于消除边界伪影，但需要输入图像本身支持周期性模式。对于地形生成等开放场景，通常关闭周期性边界。
对称性增强参数控制是否对模式进行旋转和反射增强。启用后，生成结果会更加多样，但会降低与输入的相似度。建议在首次迭代时关闭对称性增强以验证算法基本正确性，后续再开启以提升生成质量。
矛盾检测与处理
矛盾（Contradiction）是 WFC 算法必须面对的问题。当某个位置的所有可能模式都被排除时，即该位置的系数全部变为 false，算法无法继续进行。原始论文指出，判断某个位图是否允许满足约束的非平凡输出是一个 NP 难问题，因此无法保证快速且总是成功的算法。
矛盾检测发生在每次传播步骤之后。AC-4 算法在移除不兼容模式时，可以同时检查该位置是否还有剩余的可能模式。若某位置的可能集合变为空集，则立即标记为矛盾状态。
工程实践中的矛盾处理有多种策略。第一种是简单重试：检测到矛盾后完全重新开始，重复直到成功或达到最大次数。第二种是记录成功状态：在生成过程中保存所有非矛盾的部分状态，从最近的保存点重新开始。第三种是使用 DeBroglie 等库提供的回溯支持，该库实现了更完善的冲突解决机制。
对于游戏关卡生成等需要高成功率的场景，建议结合其他约束处理方法。例如，可以先使用 ConvChain 算法生成一个近似解，再用 WFC 进行局部修正；或者在 WFC 生成后人工干预部分位置，将这些位置作为固定约束重新运行算法。
性能优化实践
WFC 的主要性能瓶颈在于约束传播步骤，特别是支持列表的维护。以下是几项有效的优化策略。
批量传播可以减少函数调用开销。不是每次模式移除后立即处理受影响的位置，而是将所有待处理位置收集到队列中，统一处理。这在 JavaScript 等解释型语言中效果尤为显著。
空间换时间是另一种常见策略。预先计算所有模式之间的兼容性关系，存储在二维数组中。传播时只需查表即可判断两个模式是否兼容，避免重复的像素级比较。对于 N=3 的重叠模型，预计算兼容性可以将每次检查的时间从 O (N²) 降低到 O (1)。
稀疏表示适用于可能模式数量远小于理论值的情况。不使用完整的布尔数组表示每个位置的可能模式，而是只存储实际允许的模式 ID 列表。这可以显著减少内存占用，特别是在大尺寸输出和高色彩深度的情况下。
多线程加速在现代硬件上效果有限，因为 WFC 的核心迭代存在数据依赖，难以并行化。但可以在模式提取、预计算兼容性等独立步骤中使用并行处理。
与其他算法的结合
WFC 的一个重要优势是可以与其他生成算法结合，形成更强大的管线。
** 约束合成（Constrained Synthesis）** 允许在生成过程中施加额外约束。WFC 原生支持固定部分输出内容，算法会在满足用户指定约束的前提下完成剩余部分。这使得人机协作成为可能：开发者可以预设关键路径或重要元素，WFC 负责填充细节。
ConvChain + WFC 组合是官方推荐的管线。ConvChain 算法满足强版本的约束条件（C2），即输出的模式分布与输入完全相同，但可能产生明显缺陷。先运行 ConvChain 得到近似解，再用 WFC 进行局部修正，可以获得兼具分布一致性和局部正确性的结果。
在游戏开发中，WFC 常常与程序化生成的其他方法配合使用。例如，在《Caves of Qud》中，开发者采用多轮 WFC 逐步构建关卡：首先生成地形轮廓，然后在各区域内部署特色内容，最后进行连接性修正。这种分层生成策略比单一 WFC 更加可控。
总结
Wave Function Collapse 算法通过将程序化生成问题转化为约束满足问题，实现了从单示例生成高质量内容的能力。其核心在于：模式提取与概率计算、最小熵启发式观察策略、AC-4 约束传播机制。工程实现时，开发者需要重点关注窗口大小 N 的选择、周期性边界设置、对称性增强以及矛盾处理策略。对于大多数应用场景，N=3、关闭周期性边界、启用对称性增强、设置 10-50 次重试是一个合理的起始配置。随着对算法理解的深入，可以根据具体需求进一步调整参数和优化管线。
资料来源：GitHub mxgmn/WaveFunctionCollapse（https://github.com/mxgmn/WaveFunctionCollapse）