1. 16

  2. 6

    Author here. This is the 4th in a series of Conway’s Game of Life implementations I’ve done over the years. See the live demo here.

    This one uses some ideas from Michael Abrash’s Graphics Programming Black Book. Specifically:

    • Maintains a count of “on” neighbors for each cell. Updating this count is cheaper than brute-force counting them for each cell whenever computing the next generation.
    • Representing the state (on/off and the neighbor count) with bits in a byte. Not sure how much of a performance impact there is in this case. But it was interesting using bit operations like that for the first time.

    Haven’t done any of the other optimizations from the book, yet.

    1. 3

      Let me take this opportunity to reference the amazing HashLife algorithm ( https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 is a good introduction, reposted at https://github.com/mafm/HashLife due to site issues ), which at the cost of silly amounts of memory manages to achieve exponential speedup on certain Game of Life problems. (You read that right - it runs exponentially faster the longer you run it!)

      tl;dr: HashLife conceptualizes the Game of Life board as a canonized quadtree, and builds a giant hashtable of update steps transforming an order-n quad node into an order-n-1 node. Since this is achieved by applying the HashLife update step twice per recursion, each nodestep up leads to a doubling of step size.

      I strongly recommend any Game of Life fan to try their hand at implementing Hashlife. The way the update step breaks the problem up into subparts and puts them back together is sublime; to me, at first glance it felt like it shouldn’t work, like it was geometric cheating.

      I recall reading a different article on HashLife, where the author mentions an amusing bug where their program exited after a few seconds because the step counter overflowed…