1. 项目概述当算法遇见地牢如果你玩过《Noita》或者《Bad North》又或者对独立游戏开发感兴趣那你大概率听说过“Wave Function Collapse”波函数坍缩简称WFC这个名字。它听起来像是从量子物理课本里蹦出来的术语但在程序生成领域它指的是一种基于局部约束的、优雅而强大的内容生成算法。简单来说WFC算法通过观察一个“样本”比如一张已经设计好的地牢局部图学习其中各个“模块”比如一块地板、一堵墙、一扇门相邻时的规则然后在一个空白画布上通过“可能性坍缩”的方式生成一个全新的、但遵循同样局部规则的整体结构。这个项目就是用C#语言从零开始完整实现WFC算法并将其核心应用于“随机地牢生成”这个经典的游戏开发场景。为什么是C#因为它在游戏开发领域尤其是Unity引擎生态中占据着半壁江山拥有庞大的开发者社区。用C#实现WFC意味着你可以直接将这套逻辑无缝集成到你的Unity项目中或者任何.NET应用里去生成关卡、地形、甚至像素艺术。那么为什么不用更简单的随机房间摆放或者BSP二叉空间分割树传统的随机地牢生成算法往往在“局部合理性”上有所欠缺。你可能生成两个完全无法连通的房间或者出现一堵孤零零的墙悬浮在半空中。WFC的魅力在于它生成的每一个结果在微观局部上都是“合理”的。如果你在样本中定义了“墙的右侧必须是墙或者门而不能是空地”那么生成的结果就绝不会违反这条规则。这种对“约束”的精确控制是创造具有可信度游戏世界的关键。2. 核心思路拆解从量子叠加态到像素地图理解WFC我们可以暂时忘掉那些复杂的数学公式用一个更生活化的例子来类比拼图。想象你有一盒拼图碎片我们称之为“模块”以及一张完整的参考图“样本”。你的任务是在一个空白板“画布”上只用这盒碎片拼出一张全新的、但看起来和参考图风格一致的图画。WFC算法就是一位不知疲倦的、概率驱动的“拼图大师”它的工作流程可以拆解为以下几个核心阶段2.1 模块提取与邻接关系分析这是算法的“学习”阶段。我们不是直接处理像素而是将样本图像切割成一个个小的、有重叠的“瓦片”Tile。例如将一个32x32像素的地牢样本切割成无数个3x3像素的重叠小块。每一个这样的小块就是一个独特的“模块”。接下来算法会扫描整个样本记录下每一个模块在所有四个方向上、下、左、右上曾经和哪些其他模块相邻过。例如模块A一块平地的右侧在样本中只出现过模块B一堵墙和模块C一扇门。那么我们就为模块A建立一条约束规则“A的右侧允许的邻居集合是 {B, C}”。同理我们为样本中出现的每一个模块都建立这样一套完整的“邻接规则字典”。这个字典就是整个生成过程的“宪法”它定义了什么样的局部连接是合法的。注意模块的大小NxN是一个关键超参数。N越大捕捉的上下文信息越多生成的结果与样本的相似度越高但计算量也呈指数级增长且可能限制创造性。对于像素级的地牢N2或3通常是甜点区。2.2 初始化叠加的“可能性波”在生成开始时我们面对的是一个空白的、由网格组成的画布。画布上的每一个格子最初都处于一种“量子叠加态”——它可能成为我们模块库中的任何一个模块。也就是说每个格子的“可能性集合”包含了所有已知的模块。整个画布就是一个巨大的、未观测的“波函数”。2.3 观察与坍缩做出第一个决定算法需要打破这个全叠加状态。它会在所有未确定的格子中选择一个“熵”最低的格子。“熵”在这里是一个借用概念可以简单理解为该格子剩余可能性的多少。如果一个格子只剩下一种可能熵为0那它就已经确定了如果它还有10种可能熵较高那它就很不确定。通常算法会选择当前熵最小的格子如果多个格子熵相同则随机选一个。选中之后我们就“观察”这个格子根据它当前可能性集合中各个模块的权重权重可以在样本分析阶段根据出现频率计算随机但按权重概率为其选定一个具体的模块。这个过程就是“坍缩”。一旦坍缩这个格子的状态就从“多种可能”变为“唯一确定”。2.4 传播连锁反应的约束求解这是WFC算法的灵魂也是最耗计算资源的部分。当一个格子的状态确定后它的邻居们原来宽泛的可能性集合就必须根据我们之前学到的“邻接规则字典”进行收缩。例如刚刚坍缩的格子X被确定为模块A。我们查看规则“A的右侧允许的邻居集合是 {B, C, D}”。那么它右侧的邻居格子Y其原有的可能性集合就必须与 {B, C, D} 取交集。如果交集比Y原来的集合小说明Y的可能性被限制了熵减少了。这个“限制”事件本身又会将Y标记为“已变更”。接下来算法会处理所有“已变更”的格子对它们的邻居再次进行同样的可能性收缩检查。这个过程像波浪一样在整个画布上传播开来因此得名“Wave Function Collapse”。传播会持续进行直到没有任何格子的可能性集合再发生变化为止。此时画布上所有格子的可能性都根据当前已确定的信息达到了一个局部一致的状态。2.5 迭代循环完成一轮“观察-坍缩-传播”后画布上会有一些格子被确定更多格子的可能性被缩小。算法然后回到第3步再次在所有未确定的格子中寻找熵最小的进行坍缩并引发新一轮的传播。如此循环直到发生以下两种情况之一成功所有格子都坍缩为唯一确定的状态。一个全新的、符合样本约束的地牢生成了。矛盾在传播过程中某个格子的可能性集合在与邻居约束取交集时变成了空集。这意味着根据当前已做的决定出现了无法满足约束的情况生成失败。如果发生矛盾常见的处理策略是“回溯”记录关键决策点在失败时回退或者更简单的“完全重启”。对于地牢生成这种规模可控的场景重启往往是更简单高效的选择。3. 核心数据结构与C#实现要点理解了算法流程我们来看看在C#中如何用代码构建这个世界。整个项目的骨架依赖于几个核心类和数据结构。3.1 模块Tile与规则Rule的建模首先我们需要定义什么是“模块”。对于地牢生成一个模块可以是一个简单的枚举也可以是一个包含更多信息的类。public class Tile { public int Id { get; set; } // 唯一标识符 public string Name { get; set; } // 如 “Floor”, “Wall_N”, “Door_Closed” public float Weight { get; set; } 1.0f; // 在样本中出现的频率权重 // 可以扩展例如指向一个Prefab用于Unity或者具体的纹理坐标 } // 或者对于简单情况直接用枚举 public enum DungeonTile { Empty, // 空地或虚空 Floor, Wall, Door, // ... 其他类型 }接下来是最关键的邻接规则。我们可以用一个嵌套的数据结构来存储DictionaryTile, DictionaryDirection, HashSetTile rules;这个字典的含义是对于任何一个给定的模块键我们知道它在某个方向内层字典的键上允许哪些邻居模块内层字典的值一个集合。在样本分析阶段我们会遍历样本网格为每一对相邻的单元格组合向这个规则字典中添加记录。3.2 生成画布叠加态网格画布本身是一个二维网格但每个格子不再是一个简单的值而是一个包含当前所有可能模块的集合以及一个计算出的熵值。public class Cell { public Vector2Int Position { get; set; } public bool IsCollapsed { get; set; } false; public Tile CollapsedTile { get; set; } // 坍缩后的确定模块 public HashSetTile Superposition { get; set; } // 叠加态的可能性集合 public float Entropy { get { if (IsCollapsed) return 0; // 熵的计算可以简单为可能性数量的对数并考虑权重 float sumWeight 0f; float sumWeightLog 0f; foreach (var tile in Superposition) { sumWeight tile.Weight; sumWeightLog tile.Weight * Mathf.Log(tile.Weight); } return Mathf.Log(sumWeight) - (sumWeightLog / sumWeight); } } } public class WfcGrid { public Cell[,] Cells; public int Width; public int Height; // ... 初始化方法将所有Cell的Superposition设为所有Tile }初始化时Cells中每个Cell的Superposition都包含模块库中的所有Tile。3.3 熵的计算与最小熵格子的选择熵的计算方式直接影响生成结果的风格。最简单的熵是剩余可能性的数量。但更常用的、效果更好的是“香农熵”它考虑了不同模块的权重。权重高的模块在样本中出现频繁对熵的贡献更大。上面Cell.Entropy属性展示了一种基于权重的香农熵计算方式这里用了Unity的Mathf在纯.NET中可使用Math.Log。选择最小熵格子的函数需要高效因为每轮都要执行。一个简单的方法是遍历所有未坍缩的格子找到熵最小的。对于较大的网格可以考虑使用优先队列如PriorityQueue来优化。private Cell FindMinEntropyCell() { Cell minCell null; float minEntropy float.MaxValue; for (int y 0; y Height; y) { for (int x 0; x Width; x) { var cell Cells[x, y]; if (cell.IsCollapsed) continue; float entropy cell.Entropy; // 引入微小随机扰动避免完全确定性选择 entropy 0.0001f * Random.value; if (entropy minEntropy) { minEntropy entropy; minCell cell; } } } return minCell; }3.4 坍缩基于权重的随机选择选中格子后需要根据其可能性集合中各个模块的权重随机选择一个进行坍缩。private void CollapseCell(Cell cell) { var candidates cell.Superposition.ToList(); float totalWeight candidates.Sum(t t.Weight); float randomPoint Random.Range(0f, totalWeight); float cumulativeWeight 0f; foreach (var tile in candidates) { cumulativeWeight tile.Weight; if (cumulativeWeight randomPoint) { cell.CollapseTo(tile); // 这个方法将IsCollapsed设为trueSuperposition清空CollapsedTile赋值 return; } } // 理论上不会走到这里 cell.CollapseTo(candidates[0]); }3.5 传播约束求解的核心传播算法通常使用一个队列Queue或栈Stack来实现遵循“先进先出”或“深度优先”的策略。这里使用队列。private void Propagate(Cell startCell) { QueueCell cellsToProcess new QueueCell(); cellsToProcess.Enqueue(startCell); while (cellsToProcess.Count 0) { var cell cellsToProcess.Dequeue(); // 检查cell的四个邻居 foreach (var dir in Enum.GetValues(typeof(Direction))) { var neighborPos cell.Position GetDirectionVector(dir); if (!IsPositionValid(neighborPos)) continue; var neighborCell Cells[neighborPos.x, neighborPos.y]; if (neighborCell.IsCollapsed) continue; // 关键步骤根据cell已确定的模块限制邻居的可能性 HashSetTile allowedNeighbors GetAllowedNeighbors(cell.CollapsedTile, dir); // 与邻居当前的可能性取交集 bool wasChanged neighborCell.Superposition.IntersectWith(allowedNeighbors); // 如果邻居的可能性集合因此缩小了且不为空则将其加入待处理队列 if (wasChanged) { if (neighborCell.Superposition.Count 0) { // 矛盾生成失败 throw new ContradictionException($矛盾发生在位置 {neighborPos}); } cellsToProcess.Enqueue(neighborCell); } } } }GetAllowedNeighbors方法就是从之前构建的rules字典中查找cell.CollapsedTile在dir方向上允许的所有模块。4. 约束设计从通用算法到特色地牢基础的WFC可以生成纹理但要让其生成可玩性高的地牢我们需要在“约束”上做文章。基础的邻接约束保证了墙壁挨着地板、门连接房间等物理合理性但这还不够。我们需要引入更高级的、全局性或语义层面的约束。4.1 基础邻接约束这是通过样本学习自动获得的也是最核心的约束。它确保了生成的局部图案与样本一致。例如一个“墙角”模块它的上方和左方必然允许“墙壁”模块而右下方则允许“地板”模块。4.2 手动增强约束边界与强制放置边界约束我们通常希望地牢被墙壁包围。这可以在初始化时强制将画布四周边界格子的可能性集合设置为只包含“墙”模块。// 初始化网格后 for (int x 0; x Width; x) { Cells[x, 0].Superposition.IntersectWith(wallTilesOnly); // 上边界 Cells[x, Height-1].Superposition.IntersectWith(wallTilesOnly); // 下边界 } for (int y 0; y Height; y) { Cells[0, y].Superposition.IntersectWith(wallTilesOnly); // 左边界 Cells[Width-1, y].Superposition.IntersectWith(wallTilesOnly); // 右边界 }强制放置你可能想确保地牢中一定有一个“入口”和一个“宝藏房”。你可以在生成开始前在特定坐标或随机选择后固定的格子上直接将其坍缩为“入口”或“特殊地板”模块然后再开始通用算法流程。这相当于为算法提供了“锚点”。4.3 高级语义约束通过“模块属性”实现这是让地牢变得有趣的关键。我们为Tile类增加属性标签。public class Tile { public int Id { get; set; } public string Name { get; set; } public float Weight { get; set; } public HashSetstring Tags { get; set; } new HashSetstring(); // 例如{“Walkable”, “BlocksMovement”, “Interactable”} }然后我们可以定义基于标签的约束这些约束在传播阶段被额外检查连通性约束确保所有标有“Walkable”地板、门的格子是连通的。这不能在局部传播中实现需要在生成完成后或生成过程中定期进行全局检查如使用洪水填充算法。如果发现不连通可以视为一种“软矛盾”触发回溯或局部修复。房间大小约束不希望房间过大或过小。我们可以定义“房间”地板模块并约束其扩展。一种方法是在模块中增加“房间ID”属性在传播时如果一个地板模块试图与另一个房间ID不同的地板模块相邻则禁止此连接从而将房间隔开。同时可以统计每个房间ID的模块数量在超过阈值时禁止该房间ID的地板模块再与空位叠加态连接。敌人/物品密度约束为“敌人生成点”或“宝箱”模块添加标签。在坍缩选择时动态调整其权重。例如已放置的敌人越多后续“敌人生成点”模块的权重就越低从而控制密度。实现这些高级约束需要更精巧的设计。一种通用的方法是创建“约束处理器”IConstraint接口在算法主循环的关键节点如初始化后、坍缩后、传播后被调用由它们来检查和修改网格状态。public interface IWfcConstraint { void Initialize(WfcGrid grid); bool OnCellCollapsed(Cell cell, WfcGrid grid); // 返回false表示违反约束 void OnPropagationFinished(WfcGrid grid); } public class ConnectivityConstraint : IWfcConstraint { private string _requiredTag; public ConnectivityConstraint(string walkableTag) { _requiredTag walkableTag; } public bool OnCellCollapsed(Cell cell, WfcGrid grid) { // 定期如每坍缩10次检查连通性 if (grid.CollapsedCount % 10 0) { return CheckAllTaggedCellsAreConnected(grid, _requiredTag); } return true; } // ... 实现洪水填充检查逻辑 }将约束模块化使得我们可以像搭积木一样组合不同的规则创造出具有不同风格的地牢如迷宫型、房间型、开放型。5. 性能优化与实用技巧纯朴素的WFC实现在网格变大时可能会很慢主要瓶颈在于熵的计算和传播的广度。以下是一些实战中的优化技巧熵的缓存与更新不要每次调用Cell.Entropy的getter时都重新计算。在Cell内部缓存熵值只有当该格子的Superposition集合发生变化时在传播阶段才重新计算并更新缓存。在选择最小熵格子时直接读取缓存值。使用优先队列选择最小熵格子如前所述维护一个按熵排序的优先队列可以避免每轮遍历整个网格。当某个格子的熵在传播中发生变化时需要更新它在优先队列中的位置。提前排除矛盾在传播阶段当一个格子的可能性集合被缩小后立即检查其大小。如果为1可以立即将其“坍缩”并加入传播队列。这相当于将“观察”步骤提前能更早地触发连锁反应有时能更快地发现矛盾。模块对称性与旋转地牢元素通常具有旋转对称性。与其为每个旋转角度的墙都创建一个独立模块不如定义一个“基础墙”模块并在规则中声明它支持90度旋转。在样本分析时如果发现基础墙模块自动生成其旋转后的版本并推导出相应的旋转后规则。这能极大减少模块库的大小提高规则匹配和传播效率。分块生成对于超大地图可以将其分割成多个区块Chunk依次或并行生成每个区块区块之间预留重叠边界并施加边界约束。这类似于Minecraft的地形生成能有效控制内存和计算负载。控制随机种子使用确定的随机种子Random.State或System.Random的种子可以让生成过程完全可复现。这对于调试和生成稳定的游戏内容至关重要。6. 常见问题与调试实录即使理解了原理实现WFC时还是会踩不少坑。下面是我在项目中遇到的一些典型问题及解决思路。6.1 矛盾频发生成成功率低这是新手最常见的问题。原因1样本过小或过于复杂。样本提供的信息不足导致推导出的邻接规则过于严苛或存在隐藏矛盾。解决使用更大型、更“典型”的样本。确保样本自身是局部一致的没有无法解释的局部图案。可以手动绘制一个小的、完美的“元地牢”作为样本。原因2模块尺寸N过大。N太大时模块过于独特导致每个模块的允许邻居集合非常小极易在传播中产生矛盾。解决从N2开始尝试。对于地牢N2或3通常足够。原因3边界或强制放置的约束与学习到的规则冲突。比如强制在中间放一个“水”模块但样本中“水”从不与“地板”相邻而你的边界又都是地板导致传播时矛盾。解决检查手动约束的合理性。或者在算法开始时先应用手动约束再进行一轮初始传播如果立即矛盾则说明约束无效。6.2 生成结果过于杂乱或过于重复过于杂乱感觉像是随机噪声没有形成大的结构如房间。原因模块权重设置不合理或者样本本身就是杂乱的。熵计算中的随机扰动因子太大。解决检查样本。增大模块尺寸N让算法能捕捉更大的结构模式。减小熵选择时的随机扰动。过于重复生成的地牢像是样本的简单拼接缺乏新意。原因样本模式单一且模块尺寸N可能偏大限制了组合空间。解决提供更多样化的样本。尝试减小N值给予算法更多自由组合的空间。在熵计算中可以尝试对低权重模块给予一点点偏好鼓励探索非主流组合。6.3 性能瓶颈定位使用性能分析工具如Unity的Profiler或.NET的Stopwatch来定位。热点在熵计算实现熵的缓存机制。热点在查找最小熵格子引入优先队列。热点在传播时的集合交集运算确保HashSetT的大小合理。如果模块总数成百上千但每个格子的可能性集合通常只有几十个那么交集运算很快。如果可能性集合非常大则需要审视模块设计。6.4 高级约束导致死锁例如连通性约束要求所有地板连通但局部规则又可能生成隔离的区域。解决不要追求一次生成就完美。采用“生成-检查-修复”的循环。先生成一个基础版本然后运行一个后处理脚本寻找孤立的地板区域要么用通道将其连接起来要么将其移除替换为墙壁。更高级的做法是将连通性作为“软约束”在坍缩选择时倾向于选择能保持或提高连通性的模块。6.5 在Unity中的集成在Unity中Tile类可以关联一个GameObject预制体或一个Tilemap中的Sprite。生成算法运行在逻辑层一个二维的TileID数组生成完成后再根据这个数组在场景中实例化对应的预制体或绘制Tilemap。切记将耗时的WFC计算放在协程Coroutine中分帧进行避免主线程卡顿。你可以每帧执行一次“观察-坍缩-传播”循环并在编辑器下可视化当前叠加态例如用颜色深浅表示熵这将是一个非常强大的调试视图。实现一个可用的WFC地牢生成器是一个迭代的过程。从最简单的2x2模块、无额外约束开始先让算法能跑通生成一些虽然简单但合理的走廊。然后逐步增加模块类型墙角、门、不同地板、引入边界约束、尝试更大的N值、最后再加入房间检测、连通性保证等高级特性。每步都进行测试观察生成结果的变化你就能越来越深刻地体会到约束设计如何像雕刻刀一样从混沌的可能性中塑造出你想要的游戏世界。