HN Explorer

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

107 points by jakemanger ↗ HN
Anyone else, like me, at one point try to implement Conway's Game of Life? If you have, what is the best implementation you've found?

Mine has to be this continuous version that makes pretty crazy looking creatures: https://chakazul.github.io/Lenia/JavaScript/Lenia.html.

98 comments

[ 3.0 ms ] story [ 158 ms ] thread
dang
(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!)
jakemanger
Thank you again Dang! I pressed submit, accidentally made a typo, then edited, then realised I messed it up again. I’m glad you’re here
mordechai9000
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.

teraflop
FWIW, Golly (mentioned elsewhere in this thread) implements Hashlife as one of its core algorithms. So you can use it to simulate enormous patterns at enormous speeds, as long as they are sparse and/or regular enough that the hash hit rate is high.

https://golly.sourceforge.io/

account-5
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 ⌽¨ ⊂⍵}
The video runs you through it, even if it doesn't make it any clearer for non-apl'ers.

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

zeroq
Even thought I know it has been developed in 1960 I always felt like it was specifically designed for making "twitter implementations" of things. ;)
dang
An HN classic!

Conway's Game Of Life in APL (2009) [video] - https://news.ycombinator.com/item?id=22845249 - April 2020 (13 comments)

Conway's Game of Life in One Line of APL (2007) - https://news.ycombinator.com/item?id=10366441 - Oct 2015 (12 comments)

Conway's Game Of Life in APL - https://news.ycombinator.com/item?id=7492585 - March 2014 (2 comments)

Conway's Game Of Life written in one line of APL - https://news.ycombinator.com/item?id=4642628 - Oct 2012 (2 comments)

Conway's Game of Life in APL - https://news.ycombinator.com/item?id=4611015 - Oct 2012 (1 comment)

Conway's Game Of Life in one line of APL - https://news.ycombinator.com/item?id=3840273 - April 2012 (2 comments)

Conway's Game of Life in one line of APL - https://news.ycombinator.com/item?id=2547655 - May 2011 (22 comments)

Conway's Game of Life in one line of APL - https://news.ycombinator.com/item?id=1499630 - July 2010 (1 comment)

Conway's Game Of Life in one line of APL - https://news.ycombinator.com/item?id=1041500 - Jan 2010 (31 comments)

Game of Life implemented in 5 minutes using APL (amazing video) - https://news.ycombinator.com/item?id=451951 - Jan 2009 (1 comment)

Conway's Game of Life in one line of APL - https://news.ycombinator.com/item?id=451923 - Jan 2009 (1 comment)

Conway's Game of Life in one line of APL - https://news.ycombinator.com/item?id=204042 - May 2008 (4 comments)

---

Honorable mention:

Conway's Game of Life in APL in Forth - https://news.ycombinator.com/item?id=31537648 - May 2022 (25 comments)

yiyus
Alternatively,

    life←{≢⍸⍵}⌺3 3∊¨3+0,¨⊢
thesuperbigfrog
Best by what criteria?

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

scubbo
The choice of criteria is left up to the answerer. Pick your favourite(s)!
jakemanger
Whatever you think is best, yes. It's up to personal interpretation
selcuka
This one is quite interesting:

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

It was also featured on HN:

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

jakemanger
Zooming out on that one is an absolutely amazing experience
cancerhacker
I made that a slowly panning and enlarging Mac OS screensaver from that site - 10 lines of source I’ve long since lost to load a web view. [edit to make sense]
tombh
I think "quite interesting" is an understatement. This is the Game Of Life simulating the Game Of Life. I personally consider it to be one of the Great Wonders of software.
orblivion
You know one of the hard questions here must be, what configuration exactly is it simulating? It has to be a configuration that simulates the same Game of Life at a higher scale. Any change you make to the configuration must also change the higher level configuration that it simulates.

And it occurs to me, a blank sheet of paper qualifies as the Game Of Life simulating the Game Of Life.

zamadatix
What makes GoL in GoL somewhat magical feeling is less "there are layers of logic being executed" and more "GoL rules and conditions are extremely restrictive yet still just complex enough to simulate nested execution of the ruleset itself". When you move up the complexity chain to "person with a sheet of paper" you lose some of that wonder to just end up with "extremely complex system can throw away most of the complexity to also simulate execution of a simple system" which feels a lot less surprising.
thatguysaguy
If you think about it, that's basically what's going on if someone does a quantum mechanics simulation.
[deleted]
(comment deleted)
randomcatuser
Now that you say it like that...

What are other Great Wonders of software?

randomcatuser
1. Game of life simulating itself 2. Lisp interpreter (in C? or in Lisp) 3. a game engine?? 4. Bitcoin 5. Other distributed systems?? (Spanner?) 6. AI/deep learning representative. GPT4? AlphaGo? Pikadditions? 7. ?
FLT8
- Error correcting codes (viterbi, reed/Solomon, ...)

- cryptography in general

- data compression

- a lot of DSP stuff is pretty magical in it's various applications - digital filtering, modulation/demodulation, recovery of weak signals in noisy environments, beam-forming etc

There's a lot of really amazing, largely mathematical, foundation work that we now tend to take for granted and without which we'd be back in the relative dark ages.

ethanjstark
Beautiful. Looks like what I'd see when I would press on my closed eyeballs.

Within 30 seconds, it crashed my 2016 MacBook Pro (maybe overloaded the CPU + the failing battery? It's a feeble machine).

After the Mac's version of the BSD, Mac helpfully restored all of my windows (I have that setting turned off), and there it was again, happily Game Of Lifing in the background. Shut it down just as the fans were spinning up again.

thymine_dimer
Next time I'm discussing the ol' "are we part of a simulation?" dilemma, I'll pull this up
disillusioned
Also the obligatory link to "I Don't Know, Timmy, Being God is a Big Responsibility" by qntm:

https://qntm.org/responsibilit

s-lambert
The Futurama episode "All the Way Down" and the visual novel Anonymous;Code have the same premise, it's a fun one.
teekert
This one is like looking the universe into its soul.

Btw, can the game of life (at least in theory) simulate chaotic systems like a double pendulum?

AndrewOMartin
It's Turing complete, it can simulate anything any other Turing equivalent machine (e.g. a PC) can.
kinderjaje
This is one of the best demos of Game of Life. I guess its just looping, and not all the movements are calculated, since you can zoom out till infinity?

Correct me if I am wrong.

berikv
This should be my new screensaver
nonrandomstring
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.
twp
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...

drpossum
Why is this the best one? Or is it just an implementation you like?
Jaxan
What would “best” even mean? There is no absolute criterium the test for.
drpossum
Agreed. The premise of this topic can't solicit a reasonable response, but you offered one anyways, hence my confusion.
nickcw
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.

failrate
Rudy Rucker has Capow, which is pretty great continuous CAs: https://www.rudyrucker.com/capow/
jakemanger
That one has creatures that look very much alive. I also haven't seen a 3d plane plot view version like that before. Very cool!
DonHopkins
I love Rudy Rucker's ingenious SciFi stories, as well as the cool CALab stuff he did with John Walker at Autodesk!

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

DonHopkins 20 days ago | parent | context | favorite | on: Psychedelic Graphics 0: Introduction

Here's a classic video by Rudy Rucker demonstrating his CALab product that he made with John Walker at Autodesk:

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

At 24:28 he shows a running Belousov–Zhabotinsky reaction mapped onto a 3d model's texture:

https://youtu.be/lyZUzakG3bE?t=1468

I wrote about it in the discussion of John Walker passing away, and Josh Gordon, who worked on Chaos at Autodesk, joined the discussion:

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

>DonHopkins 11 months ago | parent | context | favorite | on: John Walker, founder of Autodesk, has died

>I really love and was deeply inspired by the great work that John Walker did with Rudy Rucker on cellular automata, starting with Autodesk's product CelLab, then James Gleick's CHAOS -- The Software, Rudy's Artificial Life Lab, John's Home Planet, then later the JavaScript version WebCA, and lots of extensive documentation and historical information on his web page. CelLab:

https://www.fourmilab.ch/cellab/

https://www.fourmilab.ch/cellab/classic/

https://www.fourmilab.ch/homeplanet/

https://www.rudyrucker.com/oldhomepage/cellab.htm

[...]

>josh_gordon 11 months ago | prev [–]

>I'm amazed that my beloved CHAOS still runs beautifully on emulators like DOSbox. It was the last programming project where I could completely roll my own interface - and maybe my last really fun one.

Here's some stuff I did that was inspired by Rudy Rucker and John Walker's work, as well as Tommaso Toffoli and Norm Margolus's wonderful book, "Cellular Automata Machines: A New Environment for Modeling":

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

by DonHopkins on Aug 7, 2023 | parent | context | favorite | on: My history with Forth and stack machines (2010)

>"Cellular Automata Machines: A New Environment for Modeling" is one of my favorite books of all time! It shows lots of peculiarly indented Forth code.

https://donhopkins.com/home/cam-book.pdf

>CAM6 Simulator Demo:

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

>Forth source code for CAM-6 hardware:

https://donhopkins.com/home/code/tomt-cam-forth-scr.txt

https://donhopkins.com/home/code/tomt-users-forth-scr.txt

And a couple more recent videos to music using the SimCity/Micropolis tile set and WebGL tile engine to display cells:

SimCity Tile Sets S...

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

marshughes
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!
jakemanger
Have fun with it! The continuous version leads to much more "living" creatures and different looking creatures as the world is more detailed and complex. It's also a bit more complex than the OG grid system implementation. There's so many variants out there to try (3d ones are my other favourite)
petters
Is it possible to implement a “glider gun” in 3D? (With reasonable rules) That was an open question a while ago
kfogel
Xlife

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

Xlife is unbelievably fast.