Simulating Infinity in Conway’s Game of Life with Modern C++ | Ryan Keane<br>Post<br>Cancel<br>Simulating Infinity in Conway’s Game of Life with Modern C++<br>Contents Simulating Infinity in Conway’s Game of Life with Modern C++
Conway’s Game of Life, simulating Conway’s Game of Life.<br>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.<br>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.<br>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.<br>HashLife<br>HashLife 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.<br>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.<br>Representing the universe<br>The actual node-level representation of HashLife looks like this:
10<br>11<br>struct LifeNode {<br>const LifeNode* NorthWest;<br>const LifeNode* NorthEast;<br>const LifeNode* SouthWest;<br>const LifeNode* SouthEast;
uint64_t Hash;<br>bool IsEmpty;
constexpr LifeNode(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se);<br>};
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.<br>To represent the base cases, we use two globally-defined nodes:
constexpr inline LifeNode StaticTrueNode{nullptr, nullptr, nullptr, nullptr};
constexpr inline const LifeNode* FalseNode = nullptr;<br>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.<br>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:
10<br>11<br>12<br>13<br>14<br>15<br>16<br>class LifeNodeArena {<br>public:<br>const LifeNode* emplace(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se);
void clear();
private:<br>constexpr static auto BlockCapacity = 65536UZ / sizeof(LifeNode);
struct BlockDeleter {<br>void operator()(LifeNode* p) const;<br>};
std::vectorstd::unique_ptrLifeNode, BlockDeleter>> m_Blocks;<br>size_t m_Current = BlockCapacity;<br>};
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:
10<br>11<br>const LifeNode* LifeNodeArena::emplace(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se) {<br>if (m_Current == BlockCapacity) {<br>auto* raw = static_castLifeNode*>(<br>::operator new(BlockCapacity * sizeof(LifeNode)));<br>m_Blocks.emplace_back(raw);<br>m_Current = 0;<br>auto* node = m_Blocks.back().get() + m_Current++;<br>std::construct_at(node, nw, ne, sw, se);<br>return...