This one is quite interesting:

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

It was also featured on HN:

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

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.

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.

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.

You might like this puzzle.

https://adventofcode.com/2024/day/21

It really makes you think about this; interaction between levels in a simulation.

If you think about it, that's basically what's going on if someone does a quantum mechanics simulation.

Now that you say it like that...

What are other Great Wonders of software?

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

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

Zooming out on that one is an absolutely amazing experience

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]

You can also zoom in

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.

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?

Cellular automata in general can exhibit chaos

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

It's Turing complete, it can simulate anything any other Turing equivalent machine (e.g. a PC) can.

Next time I'm discussing the ol' "are we part of a simulation?" dilemma, I'll pull this up

Also the obligatory link to "I Don't Know, Timmy, Being God is a Big Responsibility" by qntm:

https://qntm.org/responsibilit

The Futurama episode "All the Way Down" and the visual novel Anonymous;Code have the same premise, it's a fun one.

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.

This should be my new screensaver

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

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

You may like https://www.dwitter.net/

Alternatively,

    life←{≢⍸⍵}⌺3 3∊¨3+0,¨⊢

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)

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.

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/

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/

i stared at this with more intensity and interest than any movie in the recent times

This is such a good way of presenting code-golf — well done!

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

Why is this the best one? Or is it just an implementation you like?

What would “best” even mean? There is no absolute criterium the test for.

Agreed. The premise of this topic can't solicit a reasonable response, but you offered one anyways, hence my confusion.

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

That is a great resource. I also love seeing it with ascii characters

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.

Why is this the best one?

For me, because of the algorithm and implementation, plus they have clients for different platforms with open-source code. Plus you can explore other cellular automatas.

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)

Seems like that's a favourite of almost everyone!

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

https://golly.sourceforge.io/

oooh the 3d implementation looks very cool

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!

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)

Is it possible to implement a “glider gun” in 3D? (With reasonable rules) That was an open question a while ago

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/

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

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!

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 Space Inventory Cellular Automata Chill Resolve 1

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

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/SimCityRev...

Micropolis Web Space Inventory Cellular Automata Music 1:

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/

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

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.

Best by what criteria?

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

The choice of criteria is left up to the answerer. Pick your favourite(s)!

Whatever you think is best, yes. It's up to personal interpretation

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

But which one is best, like the post asks for?

The one written in Rust, obv.

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

That is fabulous! As a DSP/ML guy, this is a contender for my favorite so far.

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

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?

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.

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.

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

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.

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.

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

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

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

Why is this the best one? Do you believe there no possible improvement to it to make it better?

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!

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?

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

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.

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

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);
        }
    }

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/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];

Here's the explanation of the edge condition gutter optimizations that I posted recently:

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

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

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

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