使用现代C++在康威生命游戏中模拟无限性

# 用现代 C++ 模拟康威生命游戏中的无限迭代 来源：https://ryanjk5.github.io/posts/GOLDE/ 康威生命游戏在 GOLDE 中自我渲染。 （https://ryanjk5.github.io/assets/2026-05-14-GOLDE/life_in_life.gif） *康威生命游戏，模拟康威生命游戏。* GOLDE（https://github.com/RyanJK5/GOLDE）是一个元胞自动机编辑器和模拟器，能够瞬间模拟数万亿代演化。我八个月前开始构建它，当时完全没有 C++ 经验。我曾听说过 C++ 是门可怕的语言，充满了陷阱和段错误，但从未认真尝试过。这个项目最初只是我学习 OpenGL 和 C++ 基础的一个途径——做一个渲染生命游戏的应用程序。结果却进入了一个反馈循环：我不断深入现代 C++ 和元胞自动机，最终 GOLDE 变成了今天的样子。 虽然 GOLDE 有很多可聊的话题，但我想重点谈谈这段旅程中技术上最具挑战性的部分：实现由 Bill Gosper 发现的、能够实现近乎无限进化的优雅算法——HashLife（https://en.wikipedia.org/wiki/Hashlife）。我将讨论如何使用现代 C++23 特性让这一过程更安全、更简洁、性能更高。 ## HashLife https://ryanjk5.github.io/posts/GOLDE/#hashlife HashLife 将生命游戏的宇宙表示为一个带记忆的四叉树，其中每个节点会缓存自己未来多代的状态。在 HashLife 中，每个节点都是规范化的（canonical），意味着相同的子模式永远不会被计算两次。更大的节点代表宇宙中更大的区域，并且能够缓存更多未来世代的状态。具体来说，一个面积为 \(2^n \times 2^n\) 个细胞的节点可以计算未来 \(2^{n-2}\) 代的状态。这意味着一个 \(2048 \times 2048\) 的宇宙可以在接近瞬间内跳转 512 代。 如果我们想走得更远，GOLDE 会自动通过用空细胞填充边缘来扩大宇宙。对于像 Breeder（繁殖者）这样无限扩展的模式，HashLife 可以在朴素模拟器只运行几百代的时间内跳转数十亿代。如果你需要更详细的算法解释，我推荐 Tomas Rokicki 的这篇文章（https://jacobfilipp.com/DrDobbs/articles/DDJ/2006/0604/0604b/0604b.html#rf4）。我想聚焦的是那些我在任何文章中都找不到的部分。 ### 表示宇宙 https://ryanjk5.github.io/posts/GOLDE/#representing-the-universe HashLife 的实际节点级表示如下： ```cpp struct LifeNode { const LifeNode* NorthWest; const LifeNode* NorthEast; const LifeNode* SouthWest; const LifeNode* SouthEast; uint64_t Hash; bool IsEmpty; constexpr LifeNode(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se); }; ``` `LifeNode` 上的四个指针构成了 HashLife 的四叉树结构。我们预先计算节点的哈希值，这样节点查找几乎零成本；同时缓存 `IsEmpty`，这样我们可以跳过宇宙中完全为空的大片区域。对于在空宇宙中飞行的滑翔机来说，这意味着 HashLife 只会下降到那些实际包含活细胞的少数节点中，通过一次指针检查就能跳过广阔的空区域。 为了表示基例（base cases），我们使用两个全局定义的节点： ```cpp constexpr inline LifeNode StaticTrueNode{nullptr, nullptr, nullptr, nullptr}; constexpr inline const LifeNode* FalseNode = nullptr; constexpr inline const LifeNode* TrueNode = &StaticTrueNode; ``` `FalseNode` 简单地表示一个死细胞，`TrueNode` 表示一个活细胞。这种方法的一个好处是，将来扩展 GOLDE 以支持多状态规则会更容易，因为我们只需添加额外的基例节点即可。 你可能会对使用原始指针感到些许不适，但请注意每个 `LifeNode` 只存储 `const` 指针。由于整个四叉树数据结构是规范化的，因此它也是**不可变的**。那么如何使其规范化呢？请看 `LifeNodeArena`，一个 bump-pointer 分配器，它在连续的内存块中发放节点： ```cpp class LifeNodeArena { public: const LifeNode* emplace(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se); void clear(); private: constexpr static auto BlockCapacity = 65536UZ / sizeof(LifeNode); struct BlockDeleter { void operator()(LifeNode* p) const; }; std::vector<std::unique_ptr<LifeNode, BlockDeleter>> m_Blocks; size_t m_Current = BlockCapacity; }; ``` 这是一个简单的 arena 实现，其关键优势在于保持指针稳定性。它类似于 `std::deque`，但存储更大的块以获得更好的缓存局部性。配合 `std::unique_ptr` 的自定义删除器使得内存管理变得简单。`emplace` 函数本身也相当简单： ```cpp const LifeNode* LifeNodeArena::emplace(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se) { if (m_Current == BlockCapacity) { auto* raw = static_cast<LifeNode*>( ::operator new(BlockCapacity * sizeof(LifeNode))); m_Blocks.emplace_back(raw); m_Current = 0; } auto* node = m_Blocks.back().get() + m_Current++; std::construct_at(node, nw, ne, sw, se); return node; } ``` `std::construct_at` 在这里特别有用，避免了直接调用 placement `new`。实际上，这段代码中的 `::operator new` 是整个代码库中唯一一次使用原始 `new`！由于 `LifeNodeArena` 没有内置的方式查找缓存节点，我使用了 `ankerl::unordered_dense`（https://github.com/martinus/unordered_dense）这个开源寻址哈希表，并搭配 `ankerl::unordered_dense::map`。 ### 基例：65,536 个预计算宇宙 https://ryanjk5.github.io/posts/GOLDE/#the-base-case-65536-precomputed-universes 我们使用 \(8 \times 8\) 的基例来表示宇宙。回顾一下：HashLife 会前进 \(2^{n-2}\) 代，而对于 \(8 \times 8\) 基例，\(n=3\)，因此会前进 \(2^{3-2}=2\) 代。因此基例的目标是计算出 \(8 \times 8\) 区域中心 \(4 \times 4\) 网格在 2 代后的样子。一个 \(4 \times 4\) 网格包含 16 个细胞，因此可以塞进一个 `uint16_t` 中，如下所示： ``` bit 15 14 13 12 bit 11 10 9 8 bit 7 6 5 4 bit 3 2 1 0 ``` 位 0 是右下角的细胞，位 15 是左上角的细胞。整个 \(8 \times 8\) 网格由四个 `uint16_t` 组成：`nw`、`ne`、`sw`、`se`。由于有 16 位，每位两个状态，总共有 \(2^{16} = 65,536\) 种可能的组合。对于计算机来说，这个数字相对较小，因此我们在启动时根据生命游戏规则预先计算所有 65,536 种模式。关键的一点是，每个结果也存储在 `uint16_t` 中，其中四个中心位放在位 0、1、4 和 5——也就是上面位布局中右下象限的位置。这个决定在之后组装最终结果时会带来好处。 这种方法使得很容易集成其他规则，而不仅仅是康威生命游戏——我们只需要改变不同规则的查找表，HashLife 算法的其余部分仍然有效。整个 `BuildRuleTable` 函数也是 `constexpr` 的，但实际上编译器在编译时填充如此大的表会有些困难。目前 GOLDE 只是在启动应用时（或改变规则后）计算这个表。 对于推进这个 \(8 \times 8\) 基例，我们本质上是在位级别而非节点级别应用 HashLife 算法。在 \(8 \times 8\) 网格中形成九个重叠的 \(4 \times 4\) 窗口。每个窗口完全通过位运算从 \(8 \times 8\) 网格中提取。例如，中心窗口的提取方式如下： ```cpp // 用于从 16 位 4x4 网格中提取 2x2 象限的位掩码。 constexpr uint16_t MaskNW = 0xCC00; constexpr uint16_t MaskNE = 0x3300; constexpr uint16_t MaskSW = 0x00CC; constexpr uint16_t MaskSE = 0x0033; uint16_t WindowCenter(uint16_t nw, uint16_t ne, uint16_t sw, uint16_t se) { return ((nw << 10) & MaskNW) | ((ne << 6) & MaskNE) | ((sw >> 6) & MaskSW) | ((se >> 10) & MaskSE); } ``` 每个窗口都在预计算表中查找，返回该窗口中心 \(2 \times 2\) 细胞的下一代状态。第一步的结果组合如下： ```cpp HashLife::FirstGenResults HashLife::ComputeFirstGeneration( const LeafQuadrants& q) const { const auto& table = s_Rule.Table(); return { .nw = table[q.nw], .n = table[WindowN(q.nw, q.ne)], .ne = table[q.ne], .w = table[WindowW(q.nw, q.sw)], .center = table[WindowCenter(q.nw, q.ne, q.sw, q.se)], .e = table[WindowE(q.ne, q.se)], .sw = table[q.sw], .s = table[WindowS(q.sw, q.se)], .se = table[q.se] }; } ``` 这九个 \(2 \times 2\) 结果随后被重新组合成四个重叠的 \(4 \times 4\) 窗口，并进行第二次查找，得到最终居中的 \(4 \times 4\) 输出。两次世代、十三次表查找、零分支。 ### 通过抽象支持有界拓扑 https://ryanjk5.github.io/posts/GOLDE/#supporting-bounded-topologies-through-abstraction GOLDE 支持有限环面网格（toroidal grids），其中宇宙像甜甜圈一样环面化： GOLDE 中的环面带状图。 （https://ryanjk5.github.io/assets/2026-05-14-GOLDE/torus.gif） HashLife 本身没有这个概念。它假设宇宙在所有方向上无限延伸，四叉树之外的所有东西都是死的。解决办法是“欺骗”HashLife。在每个模拟步骤之前，GOLDE 将有界区域每个边缘的活细胞复制到相对边缘的外侧。这意味着最右列的细胞会在左边界外一个细胞处得到一个幽灵副本，反之亦然。然后 HashLife 正常运行，看到每个细胞的正确邻居。之后，丢弃幽灵细胞，并将模拟结果渲染到屏幕上。整个过程 HashLife 甚至从未知道宇宙存在边界。 虽然 GOLDE 目前只支持环面，但还有其他可能的拓扑结构，例如克莱因瓶、交叉表面拓扑和球面。扩展点通过 GOLDE 算法层的三个核心抽象暴露出来：`LifeDataStructure`、`LifeAlgorithm` 和 `Topology`。当需要添加新的拓扑结构时，只需要扩展 `Topology` 接口： ```cpp class Topology { public: Topology(Rect bounds = {}); virtual ~Topology() = default; // ... virtual bool CompatibleWith(const LifeDataStructure& data) const = 0; virtual int32_t Log2MaxIncrement(const BigInt& requestedStep) const = 0; virtual void PrepareBorderCells(LifeDataStructure& data) = 0; virtual void CleanupBorderCells(LifeDataStructure& data) = 0; }; ``` `LifeDataStructure` 是该契约的互补部分。它至少暴露 `Get` 和 `Set` 方法，但我们的 Torus 拓扑可以使用 `CompatibleWith` 方法来拒绝那些不具备其所需额外特性（如 `Extract`）的数据结构。HashLife 本身只看到抽象接口，因此切换新的拓扑结构不需要对算法进行任何修改。`PrepareBorderCells` 和 `CleanupBorderCells` 处理我们之前讨论过的有界网格的预处理和后处理。 然后这个拓扑被传递给 `LifeAlgorithm`，`HashLife` 继承自它： ```cpp class LifeAlgorithm { public: virtual ~LifeAlgorithm() = default; // ... virtual BigInt Step(LifeDataStructure& data, const BigInt& numSteps, /* ... */) = 0; virtual void SetTopology(std::unique_ptr<Topology> topology) = 0; virtual void SetRule(const LifeRule& rule) = 0; virtual bool CompatibleWith(const LifeDataStructure& data) const = 0; }; ``` 这些接口共同使得将来扩展 GOLDE 以支持 QuickLife 等算法、独特规则等功能变得简单。 回顾 `Topology` 接口，虚方法 `Log2MaxIncrement` 控制算法单步可前进的最大世代数。在无限平面上，这个数值可以非常大，但在有界网格上通常限制为 1，因为幽灵细胞技巧只能逐代进行。这引出了 GOLDE 的 HashLife 实现中最有趣的一个方面：我们是如何支持任意步长的？ ### 精确跳转 \(n\) 代 https://ryanjk5.github.io/posts/GOLDE/#jumping-exactly-n-generations 如前所述，HashLife 自然以 2 的幂次进行跳转。对于一个交互式编辑器，用户可以在步数输入框中输入任意数字，这是一个问题。如果有人想要精确的 1000 代，朴素的 HashLife 实现无法做到。我在开发早期遇到了这个障碍，并且在网上找不到任何关于解决方案的资料。不确定该如何继续，我直接给 Tomas Rokicki（前面链接的 Dr. Dobbs 文章作者，也是 Golly（https://golly.sourceforge.io/）的核心开发者之一）发了一封冷邮件询问。 Golly 的方法简洁而优雅。它找到一个等于步长最大 2 的幂因子的 `maxadvance`。对于步长 1000，最大 2 的幂因子是 \(2^3=8\) 代，因此 Golly 会进行 125 步，每步 8 代。如果被推进的节点通过常规 HashLife 已经能够预测 `maxadvance` 代（或更少），那么我们可以直接使用上述方法。但对于慢路径，我们需要不同的算法。 与标准的 9 窗口方法不同，慢路径将每个节点划分为 \(8 \times 8\) 网格并构建 16 个重叠窗口。我们每次只递归下降一层（而不是常规 HashLife 在组装每个节点时将其推进两次），并将 `maxadvance` 约束贯穿调用栈。我们还需要一个替代的基例，它只跳转一代而不是两代。这就是 Rokicki 在回复中描述的技术，它使得每次跳转都能精确落在正确的世代上，不会过冲。 在回复的结尾，Rokicki 补充道：“这不是唯一的实现方式……这可能是一个有趣的可玩之处！”这个随口的建议成为了 GOLDE 模拟循环的基础。GOLDE 不是寻找能**整除** \(n\) 的最大 2 的幂，而是寻找小于等于 \(n\) 的最大 2 的幂，跳转该数量，从剩余步数中减去，然后重复。在代码中是这样的： ```cpp BigInt generation{}; while (generation < numSteps) { const auto advanceLevel = m_Topology->Log2MaxIncrement(numSteps - generation); const auto gens = BigPow2(DoOneJump(hashQuadtree, advanceLevel, stopToken)); generation += gens; } ``` 因此步长 1000 被分解为 \(512 + 256 + 128 + 64 + 32 + 8\)：共 6 步，而不是 Golly 的 125 步。 这种方法并非严格优于 Golly 的。因为 `maxadvance` 随着循环的每次迭代而变化，一次跳转的记忆化结果不能总是被下一次重用。为了保持效率，我们必须将哈希表键同时包含节点大小和世代数。Golly 的固定 `maxadvance` 意味着整个步骤中缓存保持热状态，而 GOLDE 则用部分缓存效率换取在至多 \(\log_2{n}\) 次跳转内到达任意代数的能力。 在与 Rokicki 的进一步交流中，我们讨论了算法的改进，结合了 Golly 和 GOLDE 两种方法的优点，我将在 GOLDE 的持续开发中对此进行研究。