现代C++实现无限网格生命游戏：HashLife算法与内存优化实战

Conway 生命游戏看似简单，却蕴含着复杂的涌现行为。当模拟规模扩展到无限网格、代数跃升至万亿级别时，传统二维数组方案会迅速崩溃。GOLDE 项目通过现代 C++23 实现 HashLife 算法，展示了如何用稀疏存储结构和内存优化策略攻克这一经典难题。

HashLife 的核心思想

HashLife 由 Bill Gosper 于 1980 年代提出，其核心洞察在于：重复模式只需计算一次。算法将宇宙表示为规范化的四叉树，每个节点缓存未来多代的状态。一个大小为 $2^n \times 2^n$ 的节点可以一次性计算 $2^{n-2}$ 代后的结果。这意味着 2048×2048 的宇宙能瞬间跳转 512 代，而像 Breeder 这类无限扩张的模式，HashLife 能在传统模拟完成几百代的时间内跳跃数十亿代。

这种记忆化策略的代价是空间换时间，但现代硬件的内存容量让这一权衡极具价值。

四叉树节点设计

GOLDE 的节点结构体现了现代 C++ 的安全理念：

struct LifeNode {
    const LifeNode* NorthWest;
    const LifeNode* NorthEast;
    const LifeNode* SouthWest;
    const LifeNode* SouthEast;
    uint64_t Hash;
    bool IsEmpty;
};

所有指针均为const，配合规范化的节点存储，整个四叉树成为不可变数据结构。这一设计消除了数据竞争风险，使多线程读取无需加锁。IsEmpty标记允许算法跳过大片空白区域 —— 对于在空旷宇宙中穿行的滑翔机，HashLife 只需下探到包含活细胞的少数节点。

基础单元用两个全局节点表示：FalseNode（死细胞）和TrueNode（活细胞）。这种设计为未来支持多状态规则预留了扩展空间。

Arena 分配器与指针稳定性

节点规范化要求稳定的内存地址作为唯一标识。GOLDE 采用 bump-pointer 风格的 Arena 分配器：

class LifeNodeArena {
    constexpr static auto BlockCapacity = 65536UZ / sizeof(LifeNode);
    std::vector<std::unique_ptr<LifeNode, BlockDeleter>> m_Blocks;
    size_t m_Current = BlockCapacity;
};

每个块 64KB，大块存储提升缓存局部性。std::construct_at替代裸 placement new，这是代码库中唯一的::operator new调用点。自定义BlockDeleter配合std::unique_ptr使内存管理几乎零成本。

节点查找使用ankerl::unordered_dense的开放寻址哈希表，键为const LifeNode*。哈希值预存在节点内，查找开销接近免费。

8×8 基础用例与位运算优化

HashLife 的递归需要基础用例终止。GOLDE 选择 8×8 网格作为叶子节点，可计算 2 代后的中心 4×4 区域。关键优化在于：预计算所有 65536 种可能的 8×8 模式。

4×4 区域压缩为 16 位uint16_t，8×8 则由四个 16 位值（nw/ne/sw/se）表示。预计算表在启动时生成，也可改为constexpr编译期计算。运行时只需查表，无需分支判断。

两代推进通过位运算完成：9 个重叠的 4×4 窗口提取自 8×8 网格，每个查表得到中心 2×2 结果，再组合为 4 个新的 4×4 窗口进行二次查表。整个过程仅需 13 次表查找，零条件分支。

任意代数的精确跳转

标准 HashLife 只能按 2 的幂次推进。GOLDE 的创新在于支持精确跳到任意代数。算法找到不超过目标的最大 2 的幂，执行跳转后从剩余步数中扣除，循环直至完成。

例如 1000 代分解为 512+256+128+64+32+8，仅需 6 次跳转而非 125 次。代价是缓存键需同时包含节点大小和代数计数，牺牲了部分缓存复用效率。这种折中在交互式编辑器场景下值得 —— 用户输入任意数字都能立即响应。

环形拓扑的优雅抽象

HashLife 假设无限平面，但 GOLDE 支持有限环形拓扑（torus）。解决方案是欺骗算法：每步模拟前，将边界活细胞复制到对侧边界外形成 "幽灵细胞"。HashLife 正常运行后丢弃这些幽灵细胞。渲染层无需感知边界存在。

三层抽象支撑这一设计：LifeDataStructure定义数据访问接口，Topology处理边界逻辑，LifeAlgorithm执行核心算法。新增拓扑只需实现PrepareBorderCells和CleanupBorderCells方法，HashLife 代码零改动。

多线程与优雅停止

C++20 的std::jthread和std::stop_token解决了长时间模拟的取消问题。模拟线程携带 stop token，每次递归检查stop_requested()。用户点击停止时，安全退出并清理不完整缓存。std::jthread的析构函数自动请求停止并等待 join，杜绝了线程泄漏风险。

多编辑器并发使用静态缓存数组std::array<HashLifeCache, 256>，每个线程通过thread_local size_t CacheIndex选择独立槽位。编辑操作仅在模拟暂停时执行，天然避免数据竞争。

可落地的工程要点

若要在项目中实现类似系统，建议关注以下参数与决策点：

• 块大小：64KB 平衡了分配频率与内存碎片，可根据目标平台缓存行大小调整
• 基础用例尺寸：8×8 是内存与计算量的折中，4×4 会减少预计算表但增加递归深度
• 哈希表选择：开放寻址在密集键场景下显著优于链式结构
• 不可变设计：const 指针和规范化存储是并发安全的基础，值得早期引入
• 停止策略：stop token 比原子标志更规范，与 C++ 标准库线程工具无缝集成

GOLDE 证明现代 C++ 已摆脱 "充满陷阱" 的旧印象。C++23 的std::construct_at、结构化绑定、以及标准库对并发的原生支持，使复杂系统开发既能保持性能，又能写出清晰安全的代码。

资料来源

• Ryan Keane, "Simulating Infinity in Conway's Game of Life with Modern C++", 2026-05-14
• Tomas Rokicki, Dr. Dobbs Journal article on HashLife (2006)

systems