chapter four

4 Memoizing immutable quadtrees to make a better Life

 

This chapter covers

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

“The Game of Life” -- or just “Life” for short -- is a cellular automaton created by the mathematician John Conway. Imagine a grid of values, where each value is in a “cell”. The grid evolves one step at a time, based only on the arrangement of values in the previous step. It’s not really a game in the traditional sense: though it has rules, there are no players. Rather, you can create a particular arrangement of values and then see if they have interesting behaviors as they evolve.

Building your own Life implementation is a common project in many programmers’ early attempts at learning their craft, and I was certainly no different. I wrote Life implementations for my Commodore 64 and Amiga 500 as a teenager and have re-implemented 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 Change tracking improves the algorithm

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?

4.4.5 Take bigger steps forward

4.4.6 Putting it all together

4.5 Summing up