针对非完全可解问题的Wave Function Collapse算法改进

1. 增量式状态快照优化 #

原始回溯每次坍缩都存储完整网格快照，内存开销极大。可改为仅记录坍缩操作的逆过程：

• 每次坍缩单元格时，只保存该单元格坍缩前的候选状态集合，以及受此次坍缩影响的相邻单元格的候选状态变更记录（如哪些候选被剔除）。
• 回溯时直接基于这些逆操作恢复状态，无需复制整个网格。这能将内存占用从O(NMK)（N、M为网格尺寸，K为候选状态数）降至O(L*K)，L为坍缩操作步数。

2. 分支剪枝策略 #

在回溯过程中提前剪掉不可能优于当前最优解的分支：

• 维护全局当前最优合规性分数（如破坏约束的单元格数量）。
• 当某个分支的当前已破坏约束数 + 剩余未坍缩单元格的最小可能破坏数 ≥ 当前最优分数时，直接终止该分支探索。
  • 剩余未坍缩单元格的最小可能破坏数可通过统计每个未坍缩单元格的候选状态中，能满足所有相邻已坍缩单元格约束的状态数量：若单元格无任何候选状态能满足相邻约束，则必然破坏约束，计数+1；否则计数为0。

3. 基于约束传播的提前评估 #

每次坍缩前，通过WFC约束传播机制预演该坍缩选择的后果：

• 对当前单元格的每个候选状态，临时应用坍缩后执行一轮约束传播，统计传播后出现的“无法满足约束的单元格”数量。
• 优先探索预演后破坏约束数更少的分支，这并非启发式（基于精确计算的优先级，而非经验规则），但能减少无效分支探索次数，同时保证遍历所有可能找到最优解。

4. 并行化分支探索 #

利用多核CPU并行处理不同坍缩分支：

• 将当前网格的可选坍缩分支分配给不同线程，每个线程独立探索分支内所有可能，记录分支内最优解。
• 主线程定期收集各线程结果，更新全局最优分数，并通知其他线程剪掉已不可能超越当前最优的分支。
• 该方式不改变算法正确性（仍遍历所有可能），仅通过并行计算缩短总耗时。

5. 状态哈希与缓存 #

对已探索过的网格状态（所有单元格的候选状态集合）进行哈希缓存：

• 若后续遇到相同网格状态，直接使用之前记录的该状态下的最优合规性分数，无需重复探索。
• 注意：此处状态指所有单元格的候选集合，而非已坍缩单元格状态——相同已坍缩状态可能对应不同候选集合，会影响后续探索。

内容的提问来源于stack exchange，提问作者Ombrezz