现代 C++ 助力 GOLDE：康威生命游戏模拟无限的技术突破！

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 能在用户瞬间要求下停止使用 C20 的 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 的所有权模型进行桥接。现代 C23 让构建这一切比 C 的名声所暗示的要更简洁如果你害怕这门语言值得再给它一次机会。