chapter four

4 Memoizing immutable quadtrees to make a better Life

 

This chapter covers

  • The Game of Life is a famously simple two-dimensional grid automaton
  • Quadtrees can represent cellular grids
  • The HashLife algorithm powerfully combines immutability, recursion and memoization
  • Astonishing performance improvements can come from leveraging specific quirks

“The Game of Life” -- or just “Life” for short -- is a cellular automaton created by the mathematician John Conway. What is a cellular automaton? Imagine a grid of “cells”, each of which has some discrete value. 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 cell 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 Gosper’s 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