chapter four

4 Memoizing immutable quadtrees to make a better Life

This chapter covers

Following the rules of Life, a two-dimensional grid automation
Using quadtrees to represent grids of bits
Implementing the HashLife algorithm
Finding astonishing performance improvements

The Game of Life—Life, for short—is a cellular automaton created by mathematician John Conway. Imagine a grid of values in which each value is inside a cell. The grid evolves one step at a time, based only on the arrangement of values in the preceding step. Life isn’t really a game in the traditional sense: although it has rules, it has no players. Instead, you create a particular arrangement of values and see whether it displays interesting behaviors as it evolves.

Building your own Life implementation is a common project in many programmers’ early attempts to learn their craft, and I was certainly no different. I wrote Life implementations for my Commodore 64 and Amiga 500 as a teenager and have reimplemented it many times since just for fun.

4.1 The rules of Life

4.2 A typical first attempt

4.2.1 Performance of the naïve implementation

4.2.2 Same algorithm, better constant factor

4.2.3 Improving the algorithm with change tracking

4.3 An immutable quadtree

4.3.1 The IQuad interface

4.3.2 Implementing the 0-quad leaf cells

4.3.3 A strategy for compressing space

4.3.4 A general-purpose memoizer

4.3.5 A memoized quadtree implementation

4.3.6 Indexing an immutable quadtree like an array

4.3.7 A few more helpful extension methods

4.4 The HashLife algorithm

4.4.1 The base case: Stepping a 2-quad produces a 1-quad

4.4.2 A first attempt at a recursive algorithm

4.4.3 The grid always shrinks

4.4.4 Is this algorithm inefficient?

Summary