Simulating Infinity in Conway’s Game of Life with Modern C++

Conway’s Game of Life, simulating Conway’s Game of Life.GOLDE is an editor and simulator for cellular automata capable of simulating trillions of generations instantly. I started building it eight months ago with no C++ experience.I had heard the rumors that C++ was a scary language filled with footguns and segmentation faults, but I had never given it a fair chance myself. This project started as a way for me to learn the basics of OpenGL and C++ by making an app for rendering the Game of Life. What followed was a feedback loop of going deeper into both modern C++ and cellular automata until GOLDE became what it is today.Though there’s a lot to talk about in GOLDE, I want to walk through the aspect of this journey that I found the most technically challenging: implementing the beautiful HashLife algorithm discovered by Bill Gosper which makes near-infinite evolution possible. I’ll discuss how using modern C++23 features made this process safer, cleaner, and more performant.HashLifeHashLife represents the Game of Life universe as a memoized quadtree, where each node caches its state many generations into the future. Each node in HashLife is canonical, meaning identical subpatterns are never computed twice. Larger nodes represent larger areas of the universe and are able to cache more generations into the future. Specifically, a node that is $2^n \times 2^n$ cells large can compute itself $2^{n-2}$ generations in the future. This means a $2048 \times 2048$ universe can jump $512$ generations near-instantly. If we want to go further, GOLDE automatically makes the universe larger by padding the edges with empty cells.For patterns like the Breeder, which expands endlessly, HashLife can jump billions of generations in the time it would take a naive simulation to progress a few hundred. If you’re looking for a more detailed explanation of the algorithm, I recommend this article by Tomas Rokicki. What I want to focus on is the parts that weren’t in any article I could find.

Representing the universeThe actual node-level representation of HashLife looks like this:1 2 3 4 5 6 7 8 9 10 11 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); }; The four pointers on LifeNode form the quadtree structure of HashLife. We precompute the hash of the node so node lookups are almost free, and also cache IsEmpty so we can skip over large areas of the universe that are entirely empty. For a glider traveling through an otherwise empty universe, this means HashLife descends only into the handful of nodes that actually contain live cells, skipping vast empty regions in a single pointer check.To represent the base cases, we use two globally-defined nodes:1 2 3 4 constexpr inline LifeNode StaticTrueNode{nullptr, nullptr, nullptr, nullptr};

constexpr inline const LifeNode* FalseNode = nullptr; constexpr inline const LifeNode* TrueNode = &StaticTrueNode; FalseNode simply represents a dead cell and TrueNode represents a live cell. A nice benefit of this approach is that this will make it easier to expand GOLDE to support multi-state rules in the future, since we just have to add additional base-case nodes.You might be slightly uncomfortable with the use of raw pointers here, but notice that every LifeNode only stores const pointers. Since the entire quadtree data structure is canonical, it is also immutable. But how do we make it canonical? Enter LifeNodeArena, a bump-pointer allocator that hands out nodes in contiguous blocks:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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; }; This is a simple arena implementation with the key advantage that it maintains pointer stability. It’s similar to std::deque, but stores much larger blocks for better cache locality. The custom deleter paired with std::unique_ptr makes memory management trivial here. The emplace function itself is also fairly simple:1 2 3 4 5 6 7 8 9 10 11 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 is particularly useful here to avoid the naked call to a placement new. In fact, the ::operator new in this code snippet is the only occurrence of a raw new in the entire codebase!Since LifeNodeArena has no built-in way to look up cached nodes, I turned to ankerl::unordered_dense for an open-addressing hash table fit for the job and used an ankerl::unordered_dense::map<const LifeNode*, const LifeNode*>.The base case: 65,536 precomputed universesWe represent the universe using an $8 \times 8$ base case. Recall that HashLife will advance by $2^{n-2}$ generations, and since $n = 3$ for the $8 \times 8$ base case, we will advance $2^{3-2}=2$ generations.

The goal of the base case is therefore to compute what the center $4 \times 4$ grid of the $8 \times 8$ region looks like $2$ generations from now.A $4 \times 4$ grid contains $16$ cells, and can therefore be squeezed inside a uint16_t like so:1 2 3 4 bit 15 14 13 12 bit 11 10 9 8 bit 7 6 5 4 bit 3 2 1 0 Bit $0$ is the bottom-right cell, and bit $15$ is the top-left cell. The entire $8 \times 8$ grid is then four uint16_ts: nw, ne, sw, se.Since there are $16$ bits that each have two states, there are a total of $2^{16}=65,536$ possible combinations. For a computer, this is a relatively small number, so we pre-compute all $65,536$ patterns at startup using the Game of Life rules.Crucially, each result in the lookup table is stored in a uint16_t as well, with the four center bits going in bits $0$, $1$, $4$, and $5$, which are the bottom-right quadrant of the bit layout shown above. This decision will pay off later when we’re assembling the final result.This approach allows for easy integration with rules other than Conway’s Game of Life, since all we need to change is the lookup table for different rules, and the rest of the HashLife algorithm still works. The entire BuildRuleTable function is also constexpr, but in practice compilers find it a bit tricky to fill in such a big table at compile-time. For now, GOLDE simply computes this table when starting up the app (or after changing a rule).For advancing this $8 \times 8$ base case, we essentially apply the HashLife algorithm at the bit-level rather than the node-level. Nine overlapping $4 \times 4$ windows are formed in the $8 \times 8$ grid. Each window is extracted from the $8 \times 8$ grid purely using bitwise operations.

Here is how the center is extracted, for example:1 2 3 4 5 6 7 8 9 10 // Bitmasks for extracting 2x2 quadrants from a 16-bit 4x4 grid. 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); } Each of the nine windows is looked up in the precomputed table, returning the next-generation state of that window’s center $2 \times 2$ cells. The results from this first step are combined like so:1 2 3 4 5 6 7 8 9 10 11 12 13 14 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] }; } These nine $2 \times 2$ results are then recombined into four overlapping $4 \times 4$ windows and looked up a second time, producing the final centered $4 \times 4$ output.

Two generations, thirteen table lookups, and zero branching.Supporting bounded topologies through abstractionGOLDE supports finite toroidal grids, where the universe wraps around like a donut:HashLife has no concept of this. It assumes the universe extends infinitely in all directions, and that everything outside the quadtree is dead.The solution is to lie to HashLife. Before each simulation step, GOLDE copies live cells from each edge of the bounded region to just outside the opposite edge. This means a cell at the rightmost column will get a ghost copy one cell past the left boundary, and vice versa.HashLife then runs normally and sees the correct neighbors for each cell. Afterwards, the ghost cells are discarded and the simulation is rendered to the screen. All of this happens without HashLife ever even knowing there were bounds to the universe.Though GOLDE only supports the torus right now, there are several other possible topologies, such as klein bottles, cross-surface topologies, and spheres. The extension point is made readily available through the three-way abstraction central to GOLDE’s algorithm layer: LifeDataStructure, LifeAlgorithm, and Topology. When it’s time to add another topology, all it takes is extending the Topology interface:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 is the complementary side of this contract. At minimum it exposes Get and Set methods, but our Torus can deny any data structures that don’t have additional features it needs, like Extract, using the CompatibleWith method. HashLife itself only ever sees the abstract interfaces, so swapping in a new topology requires no changes to the algorithm. PrepareBorderCells and CleanupBorderCells handle the pre- and post-processing of the bounded grid we discussed earlier.