大概花了几个月的时间，我才让我的WFC实现能处理4倍于原来大小的格子，而我想跟您分享我学习的东西。
数据
我使用了三个不同图块集，以便看图块复杂性的约束对生成时间的影响。使用相同的求解器、相同的硬件和相同的格子大小：
| 格子大小 | 点数 | 25 个图块（Simple） | 41 个图块（Medium） | 331 个图块（Complex） |
|---|---|---|---|---|
| 100×100 | 10K | 0.19s | 0.47s | 1 - 3秒 |
| 250×250 | 62.5K | 0.50s | 0.94s | 4 - 10秒 |
| 500×500 | 250K | 1.60s | 2.49s | 30 - 40秒 |
| 1000×1000 | 1M | 5.46秒 | 7.74秒 | 50秒 - 1分钟15秒 |
| 2000×2000 | 4M | 22.22秒 | 29.97秒 | 4分钟23秒 |
"The “Simple”的调色板有25个图块具有清晰的，预测性的边缘连接。"Complex"是我的实际手工雕刻的Isometric调色板，有331个图块，具有多种栖息地类型、生态过渡和紧密的方向约束。
几个事情很显眼。首先，25和331图块调色板在使用相同的求解器和相同的优化时运行速度大约是10倍。有更多图块意味着有更多约束检查的步数、更多潜在的矛盾次数和更多错误复位。
你的图块设计是性能对变量。
其次，求解器变得越来越高效，因为格子变得越来越大：
| 格子 | 点数 | 时间 | 比例 |
|---|---|---|---|
| 100×100 | 10,000 | 0.19秒 | 基准值 |
| 250×250 | 62,500 | 0.50秒 | 6.25x cells，2.6x时间 |
| 500×500 | 250,000 | 1.60秒 | 25x cells，8.4x时间 |
| 1000×1000 | 1,000,000 | 5.46秒 | 100x cells，28.7x时间 |
| 2000×2000 | 4,000,000 | 22.22秒 | 400x cells，117x时间 |
在2000×2000，如果是线性时，预期是400倍时长。但实际是117倍。较大的格子可以并行运行更多的代码块（CPU利用率越好），而最初的固定支出（构建临界数规则、初始化缓冲区等）则被分散在更多的细胞上。
41 个图块（Medium）：从此链接获取完整分辨率
331 个图块（Complex）：从此链接获取完整分辨率
我碰到的障碍（和能让它变好的关键）
有很多快的WFC实现（fast-wfc在C++中非常适合中等大小的网格，Tessera使用了一种良好的AC-4求解器等）。问题不是WFC在小尺寸上慢，它的问题在于大尺寸时，它会垮掉，因为一些细节不在那里，只在较大的尺寸下出现。以下是我的问题：
壁障#1：“每个细胞一步步前进”
标准WFC的工作流程如下：
- 找到最低熵的细胞
- 衰减它
- 传播约束
- 回到主线程
- 重复
对于一个1,000,000个细胞的格子，这意味着会进行100万次返回主线程。每一次都有附加的开销：调度、内存同步、状态拷贝。
什么解决了它：多步执行。 不需要返回主线程，我就可以在内置编译 Burst-worker 中处理50个细胞。关键是，需要实现内务负责的倒退：如果在倒退时遇到一个错误，在这个职位之前不应该离开它。我们可以使用环形缓冲区快照系统来达成这一点：在每一个倒退步骤之前保存一个轻量级快照，并在出现错误时返回到它。
壁障#2：“整个网格是一个大问题”
WFC看起来似乎是有序的：一下子就衰减一个细胞，然后传播一波。但不一定这么做：
什么解决了它：大块级并行。 我把网格分成块并在每个块上独立的CPU核心上使用Unity的Job系统（IJobFor.ScheduleParallel）并行处理。假设有6个CPU核心，我们可以同时处理6个块。横跨块的冲突在边界发生时会出现，有时会被协同处理：取消冲突的边缘细胞、重新打开这个块，让它重新解决这个边界部分。
壁障#3：“错误的复位杀死了东西”
当WFC遇到矛盾（一个细胞没有经过有效图块），通常会通过重新初始化整个网格或退回一个栈来解决问题。但是在大尺寸下，这都是有害的：
- 重新启动：丢弃100,000已衰变的细胞，因为一个错误的选择
- 单步向后：可能要花费几百步来逃脱真正的死胡同
什么解决了它：深度积累加快传播。 当出现矛盾时：
1. 在内务负责的职位上：尝试向后退最近的1、3、7或15步（递增的深度根据重复错误判断）全部在内置编译的 Burst-worker 中。
2. 如果失败：在下一帧的下一个工作职位上标记它。主线程只是在共享数组中写一个整数，而Burst-worker则在下一帧处理更昂贵的恢复。
3. 当倒退栈完全耗尽时：只重新启动这个单一块，而不是整个网格。
我在此之前及之后 profil了这个函数。在之前，错误复位耗费了473ms/帧在大型网格中（主要来自主要线程 AC-3 + 再传播）。在将错误复位延迟到并行 Burst-worker 时，主线程的成本基本为零。
壁障#4：“传播查找开销”
当你衰减一个细胞时，你会向外推行并问每一个邻居：“我刚刚放入一个新细胞后，你还能接受多少个合乎道德的邻居？”这需要查找兼容性规则。
大多数实现使用了字典或散列表：rules[(tileID, 方向)]返回一组兼容的图块。对于小尺寸来说是OK的。但是传播是WFC中的最高循环。在一个一百万细胞的网格中，你将在单个生成过程中执行这条指令数百万次。
什么解决了它：预计算的平面数组。 在启动时，我将字典扁平化到一个由平面数组索引的32位整数： [moduleIdx << 8 | 方向] 。一个数组索引是一个缓冲指针偏移；而散列表则涉及对值进行哈希、二级桶、寻址和潜在冲突解决。虽然我没有计算每个查找指令的精确开销，但在改变这条指令后，传播阶段变得更快了。对于WFC这样的指令执行数百万次的数据集来说，即便很小的查找吞吐率也会导致实际分钟。
壁障#5：“在第一时间出现了太多矛盾”
即使有了出色的错误复位，矛盾也很昂贵。最好的解决方案是降低矛盾的发生频率。
什么解决了它：预测性选择。 在衰减一个图块之前，我检查： “放置这个图块会让我的四个邻居中的任何一个都没有有效的选项吗？” 如果是的话，我就跳跃它并尝试下一个候选项。它是一个简单的1步预测（不是深度搜索），并预防了大量的矛盾。
看一下上面的benchmark表格：25个图块的调色板和331个图块的调色板使用同样的求解器和同样的优化，速度差异为10倍。10 倍的速度差异几乎完全是因为矛盾发生的频率不同。更简单清晰的边缘规则=较少的枯死=预测性跳过几乎所有的矛盾。复杂的图块交互=更多的情况，其中即使预测性跳过也无法预防矛盾 2-3 步之外的位置。
这些技术工作如何在一起
没一个这样的优化在单独情况下都是有效的。 在大尺寸下，如果没有多步执行，甚至不能使用内置编译 Burst-worker 将会出现慢速管理的C#代码。但是如果没有大块并行，会在每次遇到块矛盾时将所有时间花费在阻塞。但是，如果没有预测性选择，他们也会在大多数时间里花费在错误的复位中。它们彼此都是力学加速度，因此这些组合才能达到如此之巨大的增益才是。
我学到的东西
- 优化之前先 profil。 我的第一个直觉是“传播比率慢了”，优化了传播。我先 profil显示后，在大型网格中错误复位占据了主要线程的6倍时间。结果，我花了一个星期时间优化了错误复位错误地方。
- 你的图块集是一个性能大杠杆。看一下数据表。25个图块和331个图块在使用相同的求解器和相同的优化时，复杂的调色板被预测性图标放慢了10倍。如果你的WFCC变慢，首先看你的图块集。
- Unity的原生数组不是可选的。如果你的数据在管理的C#数组上，虽然没多大影响，但我发现在预生成的 Unity 6 中使用 Native Array 已经减少了我的生成时间。因为内置编译的 Burst_worker 没法优化管理堆缓冲区。如果你使用内置编译，所有热点位置就需要在非托管内存中。
- 看看你的编码限制。我用如下方式编码邻域规则：
( moduleIdx << 8 ) | 方向。这个使用下8位为方向而上8位为模块索引 (实际为 2 位，因为这只是 North/South /East/West 需要的，然而我预留了空白 ) 。此类编码具有关键作用：它被以32位整数形式储存在调色盘中的规则表中（实际上与 4 个参数有关，对于 my 这个案例 Isometric Sprite 表 ) 。在 hashmap 版本，编码此表时只有问题：对于大于 256 的图块数量才无法很好地工作。这意味着要更窄的关键字（比如 64 位的整数）或更大的条目。这是一家编码选择。
那么，让我们通过此分析来看看最重要的障碍有哪些，以及如何解决它们。
评论 (0)