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
| |||||||||||||||||