8 ms·
Ask HN: What's the best implementation of Conway's Game of Life?
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 https://chakazul.github.io/Lenia/JavaScript/Lenia.html.
- zabzonk 2y agoI've always liked Golly - covers all sorts of CAs. https://golly.sourceforge.io/ https://golly.sourceforge.io/
- jakemanger 2y agooooh the 3d implementation looks very cool
- jakemanger 2y agohttps://chakazul.github.io/Lenia/JavaScript/Lenia.html https://chakazul.github.io/Lenia/JavaScript/Lenia.html
- mikequinlan 2y agohttps://ericlippert.com/2020/04/13/life-part-1/ https://ericlippert.com/2020/04/13/life-part-1/
- dang 2y ago(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 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 2y agoThank 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 2y agoNot an implementation, but Bill Gosper's hashlife algorithm blew my mind when I first encountered it. https://en.wikipedia.org/wiki/Hashlife 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 2y agoFWIW, 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/ https://golly.sourceforge.io/
- js2 2y agoNot sure if it's the best implementation, but Norvig's may be the best explanation: https://colab.research.google.com/github/norvig/pytudes/blob/main/ipynb/Life.ipynb https://colab.research.google.com/github/norvig/pytudes/blob...
- jakemanger 2y agoThat is a great resource. I also love seeing it with ascii characters
- account-5 2y agoHas 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 https://aplwiki.com/wiki/Conway%27s_Game_of_Life
- zeroq 2y agoEven thought I know it has been developed in 1960 I always felt like it was specifically designed for making "twitter implementations" of things. ;)
- DuncanCoffee 2y agoYou may like https://www.dwitter.net/ https://www.dwitter.net/
- dang 2y agoAn HN classic! Conway's Game Of Life in APL (2009) [video] - https://news.ycombinator.com/item?id=22845249 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 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 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 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 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 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 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 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 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 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 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 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 https://news.ycombinator.com/item?id=31537648 - May 2022 (25 comments)
- thesuperbigfrog 2y agoBest by what criteria? Best looking? Lowest resource utilization? Smallest code size? Fastest? Largest playing field? etc.
- scubbo 2y agoThe choice of criteria is left up to the answerer. Pick your favourite(s)!
- jakemanger 2y agoWhatever you think is best, yes. It's up to personal interpretation
- nneonneo 2y agoThis infinitely recursive Game of Life by saharan is pretty dang cool: https://oimo.io/works/life/ https://oimo.io/works/life/
- selcuka 2y agoThis one is quite interesting: https://oimo.io/works/life/ https://oimo.io/works/life/ It was also featured on HN: https://news.ycombinator.com/item?id=39799755 https://news.ycombinator.com/item?id=39799755
- jakemanger 2y agoZooming out on that one is an absolutely amazing experience
- cancerhacker 2y agoI 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]
- planckscnst 2y agoYou can also zoom in
- tombh 2y agoI 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.
- randomcatuser 2y agoNow that you say it like that... What are other Great Wonders of software?
- randomcatuser 2y ago1. 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. ?
- daemonologist 2y agoDepends on your metric, but this recursive one is pretty good: https://oimo.io/works/life/ https://oimo.io/works/life/ Previously: https://news.ycombinator.com/item?id=39799755 https://news.ycombinator.com/item?id=39799755 (Ope, ninja'd)
- jakemanger 2y agoSeems like that's a favourite of almost everyone!
- nonrandomstring 2y agoThere 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 2y agoGame 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/core.clj https://github.com/twpayne/life/blob/master/clojure/src/life...
- drpossum 2y agoWhy is this the best one? Or is it just an implementation you like?
- nickcw 2y agoI 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 2y agoRudy Rucker has Capow, which is pretty great continuous CAs: https://www.rudyrucker.com/capow/ https://www.rudyrucker.com/capow/
- jakemanger 2y agoThat 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 2y agoI 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 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 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 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 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/ https://www.fourmilab.ch/cellab/classic/ https://www.fourmilab.ch/cellab/classic/ https://www.fourmilab.ch/homeplanet/ https://www.fourmilab.ch/homeplanet/ https://www.rudyrucker.com/oldhomepage/cellab.htm 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 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 https://donhopkins.com/home/cam-book.pdf >CAM6 Simulator Demo: https://www.youtube.com/watch?v=LyLMHxRNuck 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-cam-forth-scr.txt https://donhopkins.com/home/code/tomt-users-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 Space Inventory Cellular Automata Chill Resolve 1 https://www.youtube.com/watch?v=319i7slXcbI https://www.youtube.com/watch?v=319i7slXcbI I performed it in real time in response to the music (see the demo below to try it yourself), and there's a particularly vivid excursion that starts here: https://youtu.be/319i7slXcbI?t=314 https://youtu.be/319i7slXcbI?t=314 The following longer demo starts out with an homage to "Powers of 10", and is focused on SimCity, but shows how you can switch between simulators with different rules and parameters, like setting rings of fire with the heat diffusion cellular automata, then switching to the city simulator to watch it all burn as the fires spread out and leave ashes behind, then switching back to another CA rule to zap it back into another totally different pattern (you can see a trail of destruction left by not-Godzilla at 0:50 while the city simulator is running). I had to fix some bugs in the original SimCity code so it didn't crash when presented with the arbitrarily scrambled tile arrangements that the CA handed it -- think of it as fuzz testing; due to the sequential groups of 9 tiles for 3x3 zones, and the consecutive arrangements of different zone type and growth states, the smoothing heat diffusion creates all these smeared out concentric rings of zones for the city simulator to animate and simulate, like rings of water, looping animations of fire, permutations of roads and traffic density, rippling smokestacks, spinning radars, burbling fountains, an explosion animation that ends in ash, etc. Chaim Gingold's "SimCity Reverse Diagrams" visually describes the SimCity tiles, simulator, data models, etc: https://smalltalkzoo.thechm.org/users/Dan/uploads/SimCityReverseDiagrams.pdf https://smalltalkzoo.thechm.org/users/Dan/uploads/SimCityRev... Micropolis Web Space Inventory Cellular Automata Music 1: https://www.youtube.com/watch?v=BBVyCpmVQew https://www.youtube.com/watch?v=BBVyCpmVQew You can play with it here. Click the "X" in the upper left corner to get rid of the about box, use the space bar to toggle between SimCity and Cellular Automata mode, the letters to switch between cities, + and - switch between tile sets (the original SimCity monochrome tiles are especially nice for cleansing the palette between blasts of psychedelic skittles rainbows, and the medieval theme includes an animated retro lores 8 bit pixel art knight on a horse), the digits to control the speed, and 0 toggles pause. (It's nice to slow down and watch close up, actually!): https://micropolisweb.com/ https://micropolisweb.com/ As you can see it's really fun to play with to music and cannabis, but if you're going to use any harder stuff I recommend you get used to it first and have a baby sitter with you. Actually the whole point of my working on this for decades is so that you don't need the harder stuff, and you can put it on pause when you mom calls in the middle of your trip and you have to snap back to coherency, and close the tab when you've had enough. DonHopkins 20 days ago [–] There's so much about it that I love, but my favorite part of Rudy's CALab demo is the "Office of the Future" and 1-800 number at the end: https://youtu.be/lyZUzakG3bE?t=2067 https://youtu.be/lyZUzakG3bE?t=2067
- ahuth 2y agoObviously this TypeScript one: https://huth.me/conway4/ https://huth.me/conway4/
- mintycrisp 2y agoGoL 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/ https://mintycrisp-a-frame-game-of-life.glitch.me/
- deadfoxygrandpa 2y agothis 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 https://x.com/deadfoxygrandpa/status/1819204922271060440 screenshot of it here: https://i.imgur.com/Iq9XXi4.jpeg https://i.imgur.com/Iq9XXi4.jpeg
- drpossum 2y agoWhy is this the best one? Do you believe there no possible improvement to it to make it better?
- davidst 2y agoI 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 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 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.
- pthyme 2y agoGame of life in many languages, benchmarked, by my brilliant former co-worker Eric: https://github.com/ericnewton/many-lives/tree/master https://github.com/ericnewton/many-lives/tree/master
- drpossum 2y agoBut which one is best, like the post asks for?
- AndrewOMartin 2y agoThe one written in Rust, obv.
- zabzonk 2y agoUnrelated 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-computer/ https://latedev.wordpress.com/2011/06/25/a-poker-chip-comput...
- guinn8 2y agoI thought this implementation chatgpt O1 wrote for was visually appealing and fun in its simplicity. https://guinn8.ca/conway.html https://guinn8.ca/conway.html I like control-shift-r to refresh the page.
- marshughes 2y agoOh 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 2y agoHave 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 2y agoIs it possible to implement a “glider gun” in 3D? (With reasonable rules) That was an open question a while ago
- vax425 2y agoI made this one to brighten up any office: https://digitalhorology.etsy.com/listing/1644589175 https://digitalhorology.etsy.com/listing/1644589175
- kfogel 2y agoXlife I believe it implements Bill Gosper's hashlife quadtree algorithm (already mentioned elsewhere in the comments here). Xlife is unbelievably fast.
- DonHopkins 2y agoIn 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/CAM6.js#L263 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. You can play with the SimCity/Micropolis CA by disobeying the important safety warning about not opening up the Space Inventory, by pressing the space bar a few times: https://micropolisweb.com 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 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/ 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 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/MicropolisEngine/src/micropolis.cpp#L776 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 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/CAM6.js#L3025 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/CAM6.js#L5484 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); } } There's some other rule compiler code that calls that function repeatedly over all possible permutations of neighbor states in ruleDict, to generate the lookup table, that's used by the Moore neighborhood (which itself also has some fancy optional features): https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L3511 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... Moore neighborhood explained: https://en.wikipedia.org/wiki/Moore_neighborhood 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 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]; Here's the explanation of the edge condition gutter optimizations that I posted recently: https://news.ycombinator.com/item?id=40701784 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/CAM6.js#L13795 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... [...see Optimization Techniques comments above...] You can either wrap the cells into the gutter from the opposite edge like a torus, which makes nice seamlessly tileable patterns, or in the case of something like SimCity pollution diffusion, you can just clamp the pixels into the gutter along the same edge. Shaders have a way of wrapping and clamping and mirroring automatically (wrapping modes): https://webglfundamentals.org/webgl/webgl-3d-textures-repeat-clamp.html 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.
- JoeDaDude 2y agoThe 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.
- OnionBlender 2y agoHow 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?
- kmoser 2y agoI 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.
- mometsi 2y agoMost 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:Belarus_flag_pattern.svg 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?
- wowthateasy 2y agoYour edit just saved a couple of hours and a lot of disappointment. I was just starting to enter the pattern when I saw it. Still a little bit curious what it does look like though...
- pmc00 2y agoCode-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/ https://shorterlife.github.io/challenge/
- rasulkireev 2y agoi stared at this with more intensity and interest than any movie in the recent times
- oneeyedpigeon 2y agoThis is such a good way of presenting code-golf — well done!
- jimmaswell 2y agoNot 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.
- carabiner 2y agoPure SQL implementation: https://github.com/keithgabryelski/game-of-life-sql https://github.com/keithgabryelski/game-of-life-sql
- petabyt 2y agoSurprised nobody has mentioned https://copy.sh/life/ https://copy.sh/life/
- o1nder 2y agoMade 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/67a71a9f57bc819185cade8f5995b3c7 https://chatgpt.com/canvas/shared/67a71a9f57bc819185cade8f59...
- zamalek 2y agoIt 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 https://youtu.be/xP5-iIeKXE8?si=7NslTsVlW0USjQFw - that one uses Golly.
- vintermann 2y agoI 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?
- spasibanan 2y ago[dead]
- dvh 2y agoThe best game of life is reverse game of life: https://youtube.com/watch?v=g8pjrVbdafY https://youtube.com/watch?v=g8pjrVbdafY (may include SAT solvers and traces of black magic)
- bryukh 2y agoMy favorite for anyone interested in cellular automata optimization is Golly (http://golly.sourceforge.net/ 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.
- kalleboo 2y agoI 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!
- cowboy_henk 2y agoHere's a nice continuous version that has multiple colors and parameters you can tweak. And it works in webgl: https://smooth-life.netlify.app/ https://smooth-life.netlify.app/
- c0nstantine 2y agoI have a minimalistic one (7 lines in Python) using convolutions: https://c0stya.github.io/articles/game_of_life.html 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
- jononor 2y agoThat is fabulous! As a DSP/ML guy, this is a contender for my favorite so far.
- lscharen 2y agoI 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 https://github.com/duckythescientist/SmoothLife
- quuxplusone 2y agoCirca 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.
- spcebar 2y agoI 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/ https://benergize.com/games/conways-game-of-life/
- joeld42 2y agoThe 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#Heading1 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.
- topologie 2y agoI'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 https://en.wikipedia.org/wiki/Quantum_cellular_automaton. :) (In case it's not super clear, I'm kinda jokin' here...)
- kaustav1996 2y ago[dead]
- kaustav1996 2y ago[dead]