A conventional Game of Life implementation advances a grid one tick at a time. HashLife changes the representation instead: it stores regions in an immutable quadtree, then reuses the computed futures of regions that recur. The payoff can be enormous when large patterns repeat. section 4.0 section 4.4
An n-quad with n greater than 1 contains enough information to compute the future of its center (n−1)-quad. Taking the center matters: cells at the outer edge would need neighbors beyond the quad. To handle a growing pattern, the grid can be enlarged by placing its current quad inside a larger, otherwise-empty one. Cells outside the stored grid are treated as dead. section 4.4 section 4.3.7
public static IQuad Center(this IQuad quad) =>
Quad.Make(quad.NW.SE, quad.NE.SW, quad.SE.NW, quad.SW.NE);
public static IQuad North(this IQuad quad) =>
Quad.Make(quad.NW.NE, quad.NE.NW, quad.NE.SW, quad.NW.SE);
public static IQuad East(this IQuad quad) =>
Quad.Make(quad.NE.SW, quad.NE.SE, quad.SE.NE, quad.SE.NW);
public static IQuad South(this IQuad quad) =>
Quad.Make(quad.SW.NE, quad.SE.NW, quad.SE.SW, quad.SW.SE);
public static IQuad West(this IQuad quad) =>
Quad.Make(quad.NW.SW, quad.NW.SE, quad.SW.NE, quad.SW.NW);
The Center, North, East, South, and West helpers construct overlapping subquads from existing children. They make the geometry needed for recursive stepping explicit. section 4.3.7
The recursive step has a small base case; empty quads can return an empty result without descending further. Its larger advantage comes from memoizing Step, a pure computation: when an identical quad and stepping request recur, the saved result can be returned instead of recomputed. Memoizing Make also deduplicates identical regions, compressing the grid. The fast-stepping version uses these reusable futures to advance large quads many generations at once. section 4.4 section 4.4.4 section 4.4.6
When the cache helps—and when it hurts
In measurements over 5,000 ticks of small Life configurations, just 20 cached argument sets accounted for 40% of calls. Yet 97% of cache entries were hit fewer than 20 times, and half were never hit again. Keeping every result wastes memory; periodically discarding cached state offers a simple speed–memory compromise. section 4.4.4 section 4.4.6
This is not a promise of constant-time simulation for every pattern. HashLife performs poorly during an initial period of chaotic change. Once large regions settle into still lifes, oscillators, or spaceships and their futures have been cached, performance can approach O(1) regardless of grid size. The broader trick is to exploit recurring structure rather than merely optimize a cell-by-cell loop. section 4.4.6 section 4.5
