Tutorials/Coding Life simulators

This is an incomplete collection of links to articles on 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

LifeWiki articles contributed by DroneBetter:

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