An n-quad is a square region with side length 2^n cells. A 0-quad is one live or dead cell; every larger n-quad contains four (n−1)-quads named northwest, northeast, southwest, and southeast. section 4.3
The recursive structure supplies three useful invariants:
- Each nonleaf node has exactly four children. section 4.3
- Every leaf lies exactly n levels below the root of an n-quad. section 4.3
- Larger regions can be assembled from smaller regions without enumerating every cell. section 4.3
In Life simulation, overlapping subregions can be advanced recursively and recombined. Nine present 3-quads produce four future 3-quads, allowing an n-quad to advance its central region by 2^(n−2) ticks rather than stepping one tick at a time. section 4.4.5
Scaling to enormous empty grids
A memoized empty 60-quad represents a square with 2^60 cells per side while requiring only 61 objects. This makes storage depend on pattern irregularity rather than simply on grid dimensions. section 4.3.5
Figure 4.12 Given nine 1-quads, all one tick in the future from the original 3-quad, we can form them into four 2-quads. Instead of simply taking their centers, we step each of those 2-quads forward one tick. That gives us a 1-quad from each 2-quad, and from them, we build a 2-quad that’s the center of the original 3-quad two ticks in the future, not one.
Shows how nine one-tick-ahead 1-quads become four 2-quads, then advance again to form the original 3-quad’s center two ticks ahead. section 4.4.5
