1. 项目背景
发布于 2026 年 5 月 14 日，更新于 2026 年 5 月 16 日，作者使用现代 C++ 在康威生命游戏中模拟无限。[GOLDE] 是一款用于细胞自动机的编辑器和模拟器，能够瞬间模拟数万亿代。八个月前，作者在没有任何 C++ 经验的情况下开始开发它。项目最初是作者学习 OpenGL 和 C++ 基础知识的方式，随后在现代 C++ 和细胞自动机领域不断深入探索，最终 GOLDE 发展成了现在的样子。
2. HashLife 算法介绍
HashLife 将生命游戏的宇宙表示为一个记忆化的四叉树，其中每个节点都会缓存其未来多代的状态。HashLife 中的每个节点都是规范的，相同的子模式永远不会被计算两次。较大的节点代表宇宙中更大的区域，并且能够缓存更远未来的世代。具体来说，一个大小为 $2^n \times 2^n$ 个细胞的节点可以计算自身未来 $2^{n - 2}$ 代的状态。这意味着一个 $2048 \times 2048$ 的宇宙可以近乎瞬间跳跃 512 代。如果想跳得更远，GOLDE 会自动通过在边缘填充空细胞来扩大宇宙。对于像繁殖者（Breeder）这样不断扩展的模式，HashLife 可以在简单模拟前进几百代的时间内跳跃数十亿代。
3. 表示宇宙
HashLife 的实际节点级表示通过 `LifeNode` 结构体实现，其中四个指针构成了 HashLife 的四叉树结构。预先计算节点的哈希值，同时缓存 `IsEmpty` 标志，以便跳过宇宙中完全为空的大片区域。为了表示基本情况，使用两个全局定义的节点：`FalseNode` 表示一个死细胞，`TrueNode` 表示一个活细胞。这种方法使 GOLDE 未来更容易扩展以支持多状态规则。为使四叉树数据结构规范，引入了 `LifeNodeArena`，它是一个块指针分配器，以连续块的形式分配节点，保持指针稳定性。还选择了 [ankerl::unordered_dense] 作为适合工作的开放寻址哈希表。
4. 基本情况：65,536 个预计算的宇宙
使用一个 $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` 中。由于有 16 位，每位有两种状态，总共有 $2^{16} = 65,536$ 种可能的组合，在启动时使用生命游戏规则预先计算所有 65,536 种模式。查找表中的每个结果也存储在一个 `uint16_t` 中，四个中心位位于位 0、1、4 和 5。这种方法允许轻松集成除康威生命游戏之外的其他规则。在推进 $8 \times 8$ 的基本情况时，在位级别应用 HashLife 算法，形成九个重叠的 $4 \times 4$ 窗口，每个窗口纯粹使用位操作从 $8 \times 8$ 网格中提取，九个窗口中的每个窗口都在预计算表中查找，返回该窗口中心 $2 \times 2$ 细胞的下一代状态，然后重新组合成四个重叠的 $4 \times 4$ 窗口，并再次查找，产生最终的中心 $4 \times 4$ 输出。
5. 通过抽象支持有界拓扑
GOLDE 支持有限的环形网格，HashLife 假设宇宙在所有方向上无限延伸，解决方案是对 HashLife 进行“欺骗”，在每次模拟步骤之前，将有界区域每个边缘的活细胞复制到对面边缘之外，然后 HashLife 正常运行，之后幽灵细胞被丢弃，模拟结果被渲染到屏幕上。通过 GOLDE 算法层的三元抽象 `LifeDataStructure`、`LifeAlgorithm` 和 `Topology` 轻松实现扩展点，当需要添加另一种拓扑时，只需要扩展 `Topology` 接口。`LifeDataStructure` 是契约的补充部分，HashLife 本身只看到抽象接口，交换新的拓扑不需要对算法进行任何更改。`PrepareBorderCells` 和 `CleanupBorderCells` 处理有界网格的预处理和后处理。`Log2MaxIncrement` 虚拟方法控制算法在单一步骤中可以推进的最大代数。
6. 精确跳跃 $n$ 代
HashLife 自然地以 2 的幂次推进，对于交互式编辑器，用户输入任意步长成了问题。Golly 的方法是找到能整除步长的最大 2 的幂次，分多步推进。而 GOLDE 是找到小于或等于 $n$ 的最大 2 的幂次，按这个量跳跃，从剩余步数中减去它，然后重复。这种方法并不一定比 Golly 的方法更好，GOLDE 牺牲了一些缓存效率，以换取在最多 $\log_2{n}$ 次跳跃内到达任何一代的能力。作者还与 Tomas Rokicki 讨论了结合 Golly 和 GOLDE 方法优点的算法改进，并将在 GOLDE 的开发过程中继续研究。
7. 优雅停止
为确保 HashLife 能在用户瞬间要求下停止，使用 C++20 的 `std::jthread` 和 `std::stop_token`，并贯穿于 HashLife 算法中。当模拟开始时，`std::jthread` 将停止令牌传递给 HashLife，每次递归调用时，HashLife 会快速检查停止令牌是否请求停止，若请求停止则开始提前退出。请求停止后，清除相关的缓存条目。GOLDE 支持同时运行多个模拟，为解决典型静态哈希表的问题，选择了静态的 `std::array`，每个线程拥有一个 `thread_local size_t CacheIndex`，线程根据唯一 ID 选择缓存，实现了静态缓存的效率和线程之间安全共享缓存的能力。
8. 结论
GOLDE 远不止 HashLife，多线程模拟循环将网格突变任务卸载到后台线程，同时相机继续渲染；OpenGL 渲染器通过将细胞打包到扁平纹理中，将整个宇宙批量处理为单个绘制调用；基于 ImGui 构建的 GUI 库需要在不牺牲双方优势的情况下，将其 C 风格的即时模式 API 与 GOLDE 的所有权模型进行桥接。现代 C++23 让构建这一切比 C++ 的名声所暗示的要更简洁，如果你害怕这门语言，值得再给它一次机会。
