Tutorials/Coding Life simulators

This is an index of several insights into the art of coding Life simulators.

Articles by Eric Lippert

In 2020-21, Eric Lippert wrote a 38-part coding tutorial discussing a series of algorithms for simulating Conway's Life (and/or other cellular automata), in his blog called Fabulous adventures in coding.

Part 1: Purpose and plan for Fabulous Adventures in Coding series

Part 2: Intro to Life rules, plus intro to client and computation engine used in these articles

Part 3: Naïve implementation of Life algorithm -- fixed board vs. wrap-around vs. embiggen as needed

Part 4: Asymptotic performance of naïve Life algorithm -- a series of useful digressions about big-O notation

Part 5: Naïve algo is proportional to number of cells in grid -- more salubrious and nourishing exercises with big-O notation

Part 6: Naïve algo, concluded -- speed bottlenecks and how to find them

Part 7: Scholes' Life algorithm in one line of APL -- life grid as array as mathematical value

Part 8: Scholes' Life algo, concluded -- performance metrics, and two ways to improve

Part 9: Parallelizing computation of Life grids -- SIMD (Single Instruction on Multiple Data)

Part 10: Hardware acceleration and image processing -- GPUs and their limitations re: Life

Part 11: Optimization guru Michael Abrash's algorithm from the 1990's -- performance, optimizations, and tradeoffs

Part 12: Turning Abrash's algo into Stafford's algo -- how to know when a cell might need to change?

Part 13: Turning Abrash's algo into Stafford's algo, continued -- performance as grid size increases

Part 14: Uses of a bigger grid -- puffers, rare ash, and the Wall of Death

Part 15: Abrash's algo to Stafford's algo, continued -- 18 pounds in a 15-pound sack

Part 16: Stafford's algo, continued -- updating neighbor counts

Part 17: UI optimizations

Part 18: Stafford's algo, continued -- optimizations

Part 19: Stafford's algo implementation completed -- a lookup of functions

Part 20: Stafford's algo concluded (almost) -- verification of big-O predictions

Part 21: Stafford's algo addendum -- optimization suggestions from David Stafford, Michael Abrash, Terje Mathisen

Part 22: Life with sparse arrays -- see also Python version on Madelyn Eriksen's blog

Part 23: Putting together a prototype of Hensel's QuickLife algo -- data structure first intro

Part 24: Prototype of Hensel's QuickLife algo, continued -- stepping forward the center of a quad

Part 25: Prototype of Hensel's QuickLife algo, continued -- 12x12 (9 Quad2s) -> 8x8, 1 tick later

Part 26: Prototype of Hensel's QuickLife algo, continued -- Quad3s and Quad4s

Part 27: Prototype of Hensel's QuickLife algo, continued -- stepping algorithm

Part 28: Proto-QuickLife analysis -- speed not too bad, memory use pretty good

Part 29: Optimization of Hensel's QuickLife algo -- miscellaneous bit-twiddling

Part 30: Adding change tracking for quads in Hensel's QuickLife algo -- a big optimization win

Part 31: Implementation of Hensel's QuickLife algo, concluded

Part 32: Core data structure of HashLife -- introducing quadtrees, quads, and memoization of quads

Part 33: Finding specific coordinates in a quadtree, drawing subsets of a quadtree

Part 34: A first attempt at Gosper's HashLife algorithm -- how do we step a quad forward one tick?

Part 35: Deriving HashLife for real -- a missed algorithmic optimization

Part 36: Digging into debugging -- a bug from part 32 tracked down, analyzed, and mercilessly exterminated

Part 37: Are there any Life patterns that have unbounded quadratic growth? Yes!

Part 38: A 1970's BASIC implementation of one of the simplest possible Life algorithms

Articles by DroneBetter

Independent to above, LifeWiki user DroneBetter has contributed the following articles.

• Tutorials/Coding Life simulators/bitwise SWAR Life
• Tutorials/Coding Life simulators/eightfold reducer