Ask HN: What's the best implementation of Conway's Game of Life?

This one is quite interesting:

https://oimo.io/works/life/

It was also featured on HN:

https://news.ycombinator.com/item?id=39799755

Has to be the APL implementation [0] purely due to how small and arcane it is:

    life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

[0] https://aplwiki.com/wiki/Conway%27s_Game_of_Life

Not an implementation, but Bill Gosper's hashlife algorithm blew my mind when I first encountered it.

https://en.wikipedia.org/wiki/Hashlife

My personal favorite has to be the one I made in x86 assembly ~30 years ago. I didn't know about hash life at the time, but still, it ran pretty fast. I seem to remember I used page flipping and moved the start of video memory each iteration. Or something like that.

Code-golfed Game of Life in Javascript we wrote a while back with some friends. Always surprising how much abuse Javascript can take: https://shorterlife.github.io/challenge/

Game of life implemented as sets in Clojure:

(defn neighbors [[x y]] #{[(dec x) (dec y)] [(dec x) y] [(dec x) (inc y)] [ x (dec y)] [ x (inc y)] [(inc x) (dec y)] [(inc x) y] [(inc x) (inc y)]})

(defn count-neighbors [world cell] (count (set/intersection (neighbors cell) world)))

(def rules #{[true 2] [true 3] [false 3]})

(defn live [world cell] (contains? rules [(contains? world cell) (count-neighbors world cell)]))

(defn evolve [world] (into #{} (filter #(live world %) (reduce set/union (map neighbors world)))))

Full source: https://github.com/twpayne/life/blob/master/clojure/src/life...

Not sure if it's the best implementation, but Norvig's may be the best explanation:

https://colab.research.google.com/github/norvig/pytudes/blob...

I wrote Qlife, a game of life "compiler" that generated X86 asm code, for one of Michael Abrash's optimization challenges in the early 90s.

Description: https://www.phatcode.net/res/224/files/html/ch18/18-01.html

Code: https://www.phatcode.net/res/224/files/html/ch18/18-03.html

Hashlife is far superior so while Qlife was interesting it wasn't the best implementation.

My favorite for anyone interested in cellular automata optimization is Golly (http://golly.sourceforge.net/). It uses the Hashlife algorithm, which can simulate enormous patterns by caching repeated blocks. While other implementations might be prettier, Golly's ability to run complex patterns at incredible speeds makes it the go-to for serious exploration.

Depends on your metric, but this recursive one is pretty good: https://oimo.io/works/life/

Previously: https://news.ycombinator.com/item?id=39799755

(Ope, ninja'd)

I've always liked Golly - covers all sorts of CAs.

https://golly.sourceforge.io/

The best one is the one you make yourself. I made my first one using a BASIC compiler for the Timex Sinclair 2068. The compiler only supported 1-dimensional arrays and I used special characters so I could get 4 pixels in each alpha numeric character position. That required a lot of (for my age) clever programming but it worked so well, I would let it run for hours and just watch the patterns it produced.

Oh my god, I've been meaning to give Conway's Game of Life a shot for ages! Your post just gave me the final push. What makes the continuous version stand out? Are there any unique features in the rules that lead to those crazy - looking creatures? I'm all ears!

Circa 25 years ago, I spent a lot of time with my (Borland Turbo C, Mode 13h) implementation that was just a vanilla Game of Life, but depicted as a red-to-blue heatmap. Every time a cell changed state, it'd become R gradations redder; every time it didn't change state, it'd become B gradations bluer. This produces a visualization where the background "space" is a uniform blue, blinkers are hot red hollow diamonds, and the actually interesting chaotic parts are appealingly fuzzy shades of reddish purple. Because it takes a while for a cell to "heat up," a glider can be almost invisible, depending on how you choose the constants R and B.

I'm not saying this is mechanically interesting (it's just a simple filter) or will change your life or anything, but I do remember spending a lot of time tinkering with and watching that particular implementation.

Rudy Rucker has Capow, which is pretty great continuous CAs: https://www.rudyrucker.com/capow/

https://ericlippert.com/2020/04/13/life-part-1/

Best by what criteria?

Best looking? Lowest resource utilization? Smallest code size? Fastest? Largest playing field? etc.

Game of life in many languages, benchmarked, by my brilliant former co-worker Eric: https://github.com/ericnewton/many-lives/tree/master

I have a minimalistic one (7 lines in Python) using convolutions:

https://c0stya.github.io/articles/game_of_life.html

### The code ###

  import numpy as np
  from scipy.signal import convolve2d

  field = np.random.randint(0, 2, size=(100, 100)) # 100x100 field size
  kernel = np.ones((3, 3))
  
  for i in range(1000): # 1000 steps
      new_field = convolve2d(field, kernel, mode="same")
      field = (new_field == 3) + (new_field == 4) * field

This infinitely recursive Game of Life by saharan is pretty dang cool: https://oimo.io/works/life/

https://chakazul.github.io/Lenia/JavaScript/Lenia.html

I remember there was an old C programming textbook which used game of life as an introduction to basic data structures and algorithms, going from lists of live cells to hashmaps etc. It was more focused on teaching basic programming than the game of life itself, so it stopped short of HashLife, but I think it had at least three increasingly sophisticated implementations.

Maybe someone on HN remembers it and can tell me its name?

GoL is always so interesting and a lot of cool implementations here I haven't seen before. I made a 3D on a 2D board version a while back in Web XR with A-Frame that turned out pretty neat if anyone wants to check it out --> https://mintycrisp-a-frame-game-of-life.glitch.me/

There was this one that ran on networked SGI Indigos, tiling an X Display for screensaver on each workstation so the whole lab came alive as this insane petri-dish of things flying around the room.

The one that had the most personal influence on me was the chapter from Michael Abrash's Graphics Programming Black Book: https://www.phatcode.net/res/224/files/html/ch17/17-01.html#...

CPU are very different these days, but the process he goes through is essentially unchanged.

I'm fond of this one, since a friend of mine, Carlos Pérez Delgado, worked on it: https://en.wikipedia.org/wiki/Quantum_cellular_automaton. :)

(In case it's not super clear, I'm kinda jokin' here...)

It might be argued that one of the dynamic programming (caching) ones would be the best by a reasonable standard. These can be used to simulate absolutely monstrous grids, and is where we see simulated CPUs and whatnot.

Here's the game of life running in the game of life: https://youtu.be/xP5-iIeKXE8?si=7NslTsVlW0USjQFw - that one uses Golly.

Surprised nobody has mentioned https://copy.sh/life/

I certainly can't claim it's the best, but I combined Conway's Game of Life and the falling sand game and I think it's neat. https://benergize.com/games/conways-game-of-life/

Made this last week with the help of o1, it's hexagonal cells and you can adjust the rules for birth and survival.

https://chatgpt.com/canvas/shared/67a71a9f57bc819185cade8f59...

I thought that SmoothLife was fascinating when I found it.

At the time I was doing a lot of simulation work, so methods for bridging discrete and continuous domains were interesting.

https://github.com/duckythescientist/SmoothLife

Unrelated to my other comment here - how to do life without an actual computer, an old blog of mine:

https://latedev.wordpress.com/2011/06/25/a-poker-chip-comput...

I wrote one in 6502 (ok, 6510) assembler for the C-64 several decades ago, which included the ability to edit and save playing fields. I also wrote one in Excel using only formulas (no VBA). Neither of them were the "best" but they were great learning experiments.

Here's a nice continuous version that has multiple colors and parameters you can tweak. And it works in webgl: https://smooth-life.netlify.app/

I wrote one in 68000 assembly on my Atari ST which implemented the life rules using bitwise logic. That meant I could do 32 cells in parallel in a kind of primitive SIMD!

The most mind blowing algorithm has to be hashlife though. Well worth studying for those aha moments.

The best game of life is reverse game of life: https://youtube.com/watch?v=g8pjrVbdafY

(may include SAT solvers and traces of black magic)

I thought this implementation chatgpt O1 wrote for was visually appealing and fun in its simplicity.

https://guinn8.ca/conway.html

I like control-shift-r to refresh the page.

I made this one to brighten up any office:

https://digitalhorology.etsy.com/listing/1644589175

Pure SQL implementation: https://github.com/keithgabryelski/game-of-life-sql

Not strictly an answer, but I just started learning low-level CUDA and this gives me the idea to implement it there as an exercise. Certainly lends itself to parallelization.

I wrote one complete with a GUI in yBasic on my Palm Vx when I was bored during lectures, to me that makes it the one that has given me the most value!

this one is my own implementation in blender geometry nodes. i did it in only 10 nodes and i think it's interesting:

https://x.com/deadfoxygrandpa/status/1819204922271060440

screenshot of it here: https://i.imgur.com/Iq9XXi4.jpeg

Obviously this TypeScript one: https://huth.me/conway4/

How do people update the grid? Do people use two grids and alternate them? Like double buffering in a game? Or is a grid a wrong representation?

Xlife

I believe it implements Bill Gosper's hashlife quadtree algorithm (already mentioned elsewhere in the comments here).

Xlife is unbelievably fast.

Most clever has to be the encoding on the left side of the flag of Belarus, which reveals a special pattern after 1991 iterations!

https://en.wikipedia.org/wiki/Flag_of_Belarus#/media/File:Be...

Edit: not really. But what a wasted opportunity. Come on, State Committee for Standardization of the Republic of Belarus, what are you doing all day?

In this recent discussion of "SimCity in the web browser using WebAssembly and OpenGL (micropolisweb.com)", I posted a description of a couple of general purpose cellular automata optimization techniques for CPUs (which don't apply to GPU cores working in parallel, but optimize the edge condition branching and memory bandwidth of a serial scanning CPU implementation). I used both techniques in my CAM6 simulator, and the SimCity/Micropolis code, to run CA in SimCity's tiles.

The edge condition optimization eliminates the eight conditional branches in the inner loop checking for edge conditions, and the memory optimization eliminates six out of nine loads per cell in the inner loop.

Here are the comments about optimization from the CAM6 code:

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

  // Optimization Techniques
  //
  //   Extra copying is eliminated by swapping between two cell buffers,
  //   one for the past and the other for the future. After applying the
  //   rule, the past cell buffer becomes the future, and the future
  //   becomes the past.  It's necessary to have two buffers, because
  //   you can't apply cellular automata in-place in one buffer, since
  //   you would stomp on your past neighbors whose future you just
  //   computed, since the neighbors above and to the left would be
  //   from the future instead of the past.
  //
  //   Edge conditions eliminated from inner loop by making cell buffers
  //   two cells wider and taller, and wrapping edges around to the
  //   extra edge cells before applying rule, so the inner loop does not
  //   have to check for edge conditions to wrap the cells, and other
  //   edge treatments can be applied besides wrapping, like clamping or
  //   reflecting.
  //
  //   Index table lookup based rules, that allow you to define rules in
  //   JavaScript in terms of their neighbors, which are then applied to
  //   every possible combination of neighbor states, to generate a
  //   lookup table that is used by the neighborhood to evaluate the
  //   rule without running a lot of JavaScript code. This is how the
  //   CAM6 hardware works, and the rule tables are compatible with its
  //   rule tables. The hardware concatenates the bits of the neighbors
  //   into an index that is used to look up the next cell value in the
  //   lookup table. It's not clear if this is actually any faster in
  //   software, because it's a software emulation of a hardware
  //   optimization, and depends a lot on the rule and the code that
  //   implements it, but at least it lets you write your rule
  //   definitions clearly without worrying about efficiency, and also
  //   translate the Forth rules defined in the Cellular Automata
  //   Machine to JavaScript (or use old rule tables generated by Forth
  //   if you can find them), and run them in the simulator.
  //
  //   JavaScript code templates for neighborhood functions, rules,
  //   tools, colormap generators, etc, with slots that let rules inject
  //   custom code into the inner loop, disable unnecessary code,
  //   calculate parameters, inline constants, etc. This enables
  //   neighborhoods to be much more general purpose, and not only
  //   deeply parametrizable but also arbitrarily extensible,
  //   supporting complex rule definition, as well as real time analysis
  //   and event reporting (like the cell value histogram). And it also
  //   enabled users to play around with writing their own rules and
  //   modifying and extending existing ones, and they will still run
  //   efficiently.

https://micropolisweb.com

Here's a video I recoded of playing around with that to music:

SimCity Micropolis Tile Sets Space Inventory Cellular Automata To Jerry Martin's Chill Resolve:

https://www.youtube.com/watch?v=319i7slXcbI

The musical style of "Chill Resolve" may ring a bell, because Jerry Martin is the musician who composed the music for The Sims and SimCity 2000 and many other Maxis games, and he has some more great free music on his web site:

https://boombamboom.com/

And here is a longer demo that explores some of the more subtle effects, starting out with an homage to "Powers of 10", with some more great music by Juho Hietala, Blamstrain:

Micropolis Web Space Inventory Cellular Automata Music 1:

https://www.youtube.com/watch?v=BBVyCpmVQew

The space bar randomly toggles between two CA rules (one heat diffusion with randomized parameters, and one combination of Anneal, Life, and Brain's Brain).

Here's the code that implements the cellular automata running in SimCity's 16 bit tile memory. I originally wrote it a long time ago in C on a 68k Sun 3 Workstation, so it uses some terribly ugly C macrology. This code is written in C++ and compiled to WebAssembly, and is adapted to deal with SimCity's in-memory tile layout that doesn't have an gutter around it, so it performs an extra copy, so isn't optimal. But if you were implementing a pure optimized cellular automata not duct-taped and bailing-wired into an existing game, you could just use two buffers of the same size with gutters around them, and swap their pointers each iteration, to eliminate the extra copy of all the cells, of course:

https://github.com/SimHacker/MicropolisCore/blob/main/Microp...

The heatWrap parameter switches between different edge condition wrapping/clamping modes applied to the gutters, defaulting to 4, which wraps the edges around like a torus.

You can play with the CAM6 emulator here, which is written in JavaScript. Click the square in the upper right corner to show the controls, and switch the rule to Life, but it has many other rules too:

https://donhopkins.com/home/CAM6

Here's the source code of a hard-coded Life rule (with some bonus features like running a heat diffusion in parallel in the upper bits, and rotating the scanning order to cancel out the heat diffusion dithering artifacts):

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

There is another lookup-table based implementation of Life that is compatible with the way the CAM6 hardware works. It uses a Moore neighborhood. This code snippet is not run in the inner loop, it's run over all possible input configurations to generate a lookup table that is used by the generic Moore neighborhood code. So it doesn't need to be optimized because it runs outside of the inner loop:

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

    // ruleFunction_Moore_life computes the life rule Moore
    // neighborhood lookup table.
    function ruleFunction_Moore_life(ruleDict, state) {
        var sum8 =
            ruleUtil_Moore_sum8_0(state);
        if (state.c0) {
            return (((sum8 == 2) ||
                     (sum8 == 3))
                ? 1 : 0);
        } else {
            return ((sum8 == 3)
                ? 1 : 0);
        }
    }

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

Moore neighborhood explained:

https://en.wikipedia.org/wiki/Moore_neighborhood

Here's an in-depth technical demo that I recorded for Norman Margolus explaining how it was inspired by his book and how it works:

https://www.youtube.com/watch?v=LyLMHxRNuck

Here's the technique for reducing the number of memory loads per cell in the inner loop from 9 to 3. For each row you "prime the pump" by loading the right two columns of a 3x3 window, and then for each cell you scroll the window to the left and load the three incoming cells.

    for (var cellY = 0;
         cellY < height;
         cellY++) {

        // Load the right two columns of the 3x3 window.
        n  = cells[cellIndex - nextCol - nextRow];  ne = cells[cellIndex - nextRow];
        c  = cells[cellIndex - nextCol          ];  e  = cells[cellIndex          ];
        s  = cells[cellIndex - nextCol + nextRow];  se = cells[cellIndex + nextRow];

        for (var cellX = 0;
             cellX < width;
             cellX++) {

            // Scroll the 3x3 window to the right, scrolling the middle and right
            // columns to the left, then scooping up three new cells from the right
            // leading edge.
            nw = n;  n = ne;  ne = cells[cellIndex + nextCol - nextRow];
            w  = c;  c =  e;  e  = cells[cellIndex + nextCol          ];
            sw = s;  s = se;  se = cells[cellIndex + nextCol + nextRow];

https://news.ycombinator.com/item?id=40701784

DonHopkins 8 months ago | parent | next [–]

Amazing!

Decades ago, Will Wright suggested to me a nice optimization for cellular automata and convolution filters that lets you eliminate the bounds checks in the inner loop, which I implemented in my CAM6 cellular automata machine simulator:

Eliminate the edge conditions (and conditionals in the inner loop) by making a "gutter" of one extra pixel (or however many pixels your neighborhood extents out) around all the edges of the bitmap (i.e. increase the width and height by 2, then inset x and y by 1), then before processing each frame, copy the appropriate edges into the corresponding gutters (wrapping or clamping), then iterate over the pixels just inside the gutters, so you don't have to perform any bounds checks.

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

    [...see Optimization Techniques comments above...]

https://webglfundamentals.org/webgl/webgl-3d-textures-repeat...

But on old school consoles you have have to use software tricks like that instead of relying on the hardware.

And of course if you're using power of two sized bitmaps you can just mask the coordinates, which is practically free.

You could fix SimCity to use that trick, but it would make the code more complex, and it's probably not worth it on anything but really old hardware like the C64 or Sega Dreamcast.

(I did a bit of surgery on this post - I moved your text to the top and moved the link to the text so that the submission would show up on /ask. Then I put it in the second-chance pool (see https://news.ycombinator.com/item?id=26998308) so it will get a random placement on HN's front page. I hope this is all ok!)