From HashLife to WebGPU: Simulating the Game of Life at Planetary Scale

The rules of Conway's Game of Life fit in a tweet, and a working simulator is a beginner programming exercise. Yet some of the most celebrated patterns ever built—metapixel arrays, in-Life computers, self-replicating machines—contain millions of cells and require trillions of generations to do anything interesting. A naive simulator would need centuries.

That gap, between trivial rules and astronomical scale, has driven fifty years of algorithmic ingenuity. Here is how we got from checking eight neighbors in a loop to simulating universes in your browser tab.

The Naive Approach and Its Limits

The textbook simulator stores a 2D array and, each generation, counts every cell's live neighbors. For an N×N grid, that's O(N²) work per generation, forever. It's perfectly fine for watching a Pulsar blink or an R-pentomino bloom.

But consider the Breeder 1, which grows quadratically without bound, or the OTCA Metapixel—a 2048×2048 construction that simulates a single Life cell using tens of thousands of real ones. An array of metapixels emulating even a modest pattern pushes cell counts into the billions. The naive approach collapses immediately.

Early optimizations helped: storing only live cells in sparse sets, skipping regions that haven't changed, packing cells into machine words and updating 64 at a time with bit tricks. These deliver order-of-magnitude gains. What came next delivered exponential ones.

HashLife: Trading Memory for Time Travel

In 1984, Bill Gosper—already famous for discovering the Gosper Glider Gun—published an algorithm so counterintuitive it still feels like cheating. HashLife represents the universe as a quadtree: the grid splits into four quadrants, each quadrant into four more, down to individual cells. Every subtree is stored once in a hash table, no matter how many times it appears.

This exploits Life's deepest regularity: patterns repeat, in space and in time. Empty regions, blocks, blinkers, glider streams—the same tiles recur endlessly, and HashLife stores each exactly once.

The masterstroke is memoization in time. For each node, HashLife computes and caches the node's future—and thanks to a recursive doubling scheme, a node of size 2^k can be advanced 2^(k-2) generations in a single cached lookup. Encounter a familiar region, and you don't simulate it; you simply recall its future.

The results defy intuition. HashLife can run patterns for 2^60 generations in seconds—not by being fast, but by recognizing that it has, in effect, already been there. Regular, machine-like patterns—guns, puffers, metapixel arrays, the Universal Turing Machine—collapse into compact, largely pre-computed structures. It is the algorithm that made the modern era of monumental Life engineering possible, and it remains the beating heart of Golly, the community's standard simulator.

HashLife has limits: chaotic, never-repeating soups defeat its caching, and its appetite for memory is fearsome. But for engineered patterns, nothing else comes close.

The GPU Era

Where HashLife exploits repetition, graphics hardware exploits raw parallelism. Life's update rule is embarrassingly parallel—every cell computes independently from its neighbors—which makes it a perfect match for GPUs whose thousands of cores were built to update millions of pixels at once.

A GPU implementation stores the grid as a texture and applies the rules in a fragment or compute shader: every cell, every generation, all at once. Even a mid-range laptop GPU can update grids of hundreds of millions of cells at 60 frames per second—brute force at a scale Conway's first players, pushing counters across a Go board in 1970, could not have imagined.

The newest chapter is WebGPU, the modern successor to WebGL that began shipping in Chrome in 2023 and has since arrived across all major browsers. Unlike WebGL, WebGPU exposes true compute shaders to web pages, meaning full-strength, GPU-accelerated Life simulation now runs in an ordinary browser tab—no installation, no plugins. The barrier between "toy web demo" and "research-grade simulator" has effectively vanished.

Two Philosophies, One Universe

Modern Life computing rests on these two complementary pillars:

Approach	Superpower	Weakness	Best for
HashLife	Skips redundant time and space entirely	Chaotic patterns, memory usage	Engineered machines, deep time
GPU brute force	Massive real-time throughput	Every generation still costs work	Random soups, interactive play, visualization

The division mirrors something real about Life itself. Engineered patterns like Gemini are crystalline and compressible—HashLife territory. Random soups are incompressible chaos—GPU territory. That the same four rules produce both is precisely what makes this universe inexhaustible.

Why Scale Matters

Faster simulation isn't just convenience; it changes what can be discovered and built. Soup searches that catalog the fates of trillions of random starting configurations—the source of many recent pattern discoveries—are only feasible because each soup resolves in microseconds. Monumental constructions like in-Life computers playing Tetris, or metapixel arrays running Life inside Life, are only verifiable because HashLife can fast-forward through quadrillions of cell updates.

Every leap in simulation power has expanded the horizon of what the community dares to attempt. Conway gave us an infinite universe; Gosper, and now the GPU in your pocket, gave us the means to actually explore it.