A quadtree represents a two-dimensional grid as a recursive full tree: each node has four children, and each level describes a larger square region. This replaces a flat mutable array with a structure that can share repeated regions. section 4.0 section 4.4
The representation becomes especially powerful for Conway’s Game of Life. An immutable quadtree can deduplicate identical subtrees, while memoization reuses results for patterns that recur during evolution. section 4.0 section 4.3.3
A practical quadtree implementation develops around these behaviors:
- Represent a square region by four smaller quads, recursively reaching cell-sized 0-quads. section 4.4 section 4.3.3
- Treat cells outside the current tree as dead, and embiggen the tree when a write falls beyond its boundary. section 4.4
- Reuse equal nodes instead of constructing duplicate objects; repeated empty or stable regions then consume less memory. section 4.3.3
- Use each sufficiently large quad’s center to compute future states for larger jumps through HashLife. section 4.4
HashLife grid access
A Life grid can start with an empty 9-quad, representing 512 cells per side. Reading outside it returns dead; setting an outside cell repeatedly embiggens the tree until the coordinate fits, then updates the corresponding quad. section 4.4
Listing 4.7 A class for the HashLife algorithm
using static Quad;
sealed class HashLife : ILife
{
private IQuad cells = Empty(9);
private int stepCallCount = 0;
public HashLife(){}
public void Clear() => cells = Empty(9);
public bool this[long x, long y]
{
get => cells.Contains((x, y)) && cells.Get((x, y)) != Dead;
set
{
while (!cells.Contains((x, y)))
cells = cells.Embiggen();
cells = cells.Set((x, y), value ? Alive : Dead);
}
}
Inspect the C# HashLife shell that stores cells as an IQuad, clears to an empty quad, handles outside reads, and expands before writes. section 4.4
