Tutorials/Coding Life simulators
Jump to navigation
Jump to search
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
| |||||||||||||||||