Hacker News new | past | comments | ask | show | jobs | submit login
Recursive Game of Life (oimo.io)
1072 points by alden5 on Dec 14, 2022 | hide | past | favorite | 117 comments



The author says: (https://twitter.com/shr_id/status/1602691898162184192)

  In the beginning I didn't think it was possible without cheating something but finally found a way to "build everything perfectly"
  Due to the inifinite recursion, each level is aperiodic for both space and time, and you'll never see the same pattern no matter how much you scroll


At a certain draw distance (probably/hopefully depending on framerate and other specs), the platform replaces the individual cells with the OTCA metapixel, effectively giving the illusion that it is GoL all the way down.

Neat, even when you know the trick.

https://conwaylife.com/wiki/OTCA_metapixel


The other trick is that the simulation speed scales with draw distance, such that once you've zoomed out a full cycle the simulation has gotten exactly 35328x faster, which is the period of the OTCA metapixel.

There's some lovely "engineering diagrams" of the OTCA metapixel on this (sparse) blog: http://otcametapixel.blogspot.com/2006/05/how-does-it-work.h.... It's fun to zoom in on the posted site and identify all the features, like the rule table near the bottom left.

For context, the OTCA metapixel is a large pattern (2048x2048) which is capable of simulating Conway's Game of Life rules (or, indeed, any rule set consisting of neighbour-counting birth/death conditions); it does this by having adjacent pixels coordinate sharing of state (whether they're on or off) and then looking up what to do via a (programmable) lookup table. Based on the current state (on or off), a series of "glider guns" will be conditionally activated, which creates the appearance of a filled center (filled with moving gliders).


It also appears to retain the current state of arbitrarily higher recursive instances, not that they move much when you're zoomed in. Makes me wonder, how do you code for the current 'position' in the whole stack in a way that remains consistent? Conceptually the space is very big. If you zoom/recurse in to a random metapixel 13 times in a row, you're almost certainly looking at a pixel that no other human has or ever will see, and you have scaled from the width of the observable universe to the width of a proton.


Yeah, this part is very clever and quite well-done IMHO. I suspect the trick is to only store the state for any levels you've actually seen.

As you go higher, they can just arbitrarily select a location in the simulation a few levels up from where you are that is consistent with the metapixels you've seen; once you go up a few levels, there's no chance of you having seen beyond a very small window of the simulation, so it's a matter of just finding a matching pattern.

As you go lower, the time step cannot be set be zero, so they can simply initialize the simulation a few levels down to an arbitrary state since the lower levels will tick exponentially faster.

The only problem is that you do have to store state for levels between the highest level you've seen and the current level as you zoom in. I suppose this means that if you zoom out a lot (just spam the scroll) and then zoom in a lot, there might be substantial memory usage. I've tested it and they do seem to consistently remember the exact state of the simulation at least a few levels up - it's easy to check by looking at the length of the clock train on the left of the metapixel in each level.


Need they do any simulation? I would need paper and some time, but can’t you store 16 animations of a cell and then just have the state as a zoom level, position in x y space (wrapping) and a time (in a loop). The rest should be calculatable assuming this is a true fractal which I think it is. 0 zoom is probably the starting position. Zooming in actually switches to maximally zoomed out with each cell following the prerecorded animation from a layer up based on the x y position. What state are you imaging?


Yes, you’re right on the state: the state for each level can just be OTCA timestep and x,y within the parent level. However, I think you need to store somewhat more than 2^4 animations: there are 35328 cycles per OTCA tick, and a cell’s animation depends on all of its neighbors, for something like 2^9 * 35328 distinct states. The vast majority of cells are quite predictable (and have short animation periods) but some of the logic elements will change in somewhat unpredictable ways. There is likely to be some fancy compression that can be done if the states need to be computed ahead-of-time.

Some of the more subtle bits do depend on the neighbor cells in the parent level, so I think there still does need to be some simulation done to ensure that these subtle bits are correct when viewing lower levels. But that only needs it be done in a small neighborhood.


Interesting, I guess I forgot that the game of life includes edge neighbors and had no idea of the cycle time. Why isn’t it 2^8 neighbors though?. Maybe just running 2^8 simulations is the way to go? Or that’s 9 megabytes * frame size per so maybe that ends up being small enough with compression

Edit: the author has said that it’s non periodic apparently which seems like it would make this whole thing a lot harder and probably require more state


Eight neighbors plus the cell itself. With a period of 35,328 and a size of 2048 x 2048 cells for the OTCA metapixel you end up with ‭75,866,302,316,544‬ bit without any compression.


That's purely an optimization, though. Meaning, it would look just like this if it really was "GoL all the way down".


Thank you, I came here to ask for an explanation for how this was optimized.


Wow! At the speed of around 0.15 you can see all the relevant computations: Every few seconds three glider triples get sent out, obviously directly representing the 9 neighboring cells. These interact with some lane shifting and 90 degree reflections. In the process these "byte" may lose a glider or two, representing the result of the game of life computation. Then you can see a fuse burn down, then a single glider makes a round and suddenly the whole cell switches state by an army of gliders gently touching the producing border.


Did you zoom yet?


Whoa!


Who else had this experience.

Cool - Game Of Life on my phone. Some pretty cool patterns. Recursion? Don't see it. But look - I can zoom out. Wow, that's a pretty large pattern. Oh shit!

I've not delved into the code. But I am assuming that this is a static model and not actually doing the GOL calculations. Is that correct?


FYI it looks fine on my laptop (a Mac running Chrome). But it looked messed up on my phone (a Pixel 2), kind of like random static.


First off, this is one of the coolest things I've ever seen.

Second, judging from the author's github [0], I'm guessing this was made in Haxe [1], which is a language often used to make games. I'd looked at Haxe before, but I hadn't realized that it has a lot of Ocaml-like features. I think I need to give it a try on my next prototype project!

[0] https://github.com/saharan

[1] https://haxe.org/


*OCaml


I LOVE how you can set it to scroll forever by itself. This website is a true work of art.


How do you do that? I only see the speed slider, and it doesn't seem to respond to keystrokes.


Scroll quickly out, it will just keep on going. Maybe it’s a desktop only thing?


I love that too, only wish auto-scrolling speed could be adjusted (would like it to be slower).


For me there's a horizontal slider in bottom middle of the screen which controls the auto-scrolling speed.


I did not realize that. If you are not auto-zooming it seems to just control the simulation speed but while auto-zooming it effects the speed of the zoom. That probably makes sense at a deep level because as you zoom in and out the simulation speed has to be adjusted to make the new level run at the same speed as the old one.


I can wrap my head around zooming in - conceptually you run any life simulation you want, i.e. a base level game of life, and then recursively decompose each cell into the 2²² cells of a OTCA metapixel.

Zooming out I find much harder to make sense of. What does it look like if you zoom out infinitely often? Is there some limit? If you take an empty universe with all cells dead there seems to be nothing at first, but at closer inspection there is of course still a lot of stuff going on in all the dead metapixels making up the empty universe. After zooming in a couple of times it would be hard to tell that zooming out a bit would leave you with an empty universe. And it would not have to be an empty universe, it could be anything.


> What does it look like if you zoom out infinitely often?

Make a sharp backwards roll of your mouse wheel and see for yourself - it'll turn on the autopilot mode.


I am really enjoying this full screen with auto-zoom-out at the slowest speed setting. If the controls faded like media player controls do in full screen, I would be perfectly satisfied.

This inspired a bit of awe in me, especially after I learned from another comment here that each game is unique.

edit: Oh wow, of course it's last month's Bubbles creator.

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


Already tried that, does not zoom quickly enough to reach infinity before I have to go to bed.


I don't think you need to reach infinity to realize it's OTCA metapixels all the way down and OTCA metapixels all the way up. In a way, it just loops forever.


That is the question I am asking. Zooming out finitely often gives you metapixels but what happens in the limit at infinity? Just like increasing x by any finite amount will always leave you with a small positive number for 1/x but in the limit you get 0.


But how long do you have to wait to know it's infinite? ;-)


Rarely do I look at a website in amazement and ask "How?". This is awesome.


there's an open source tool/toy called "Golly" which can show you.

https://golly.sourceforge.net/


And if you want to explore continuous-state automata ('reaction diffusion') there's Golly's cousin-app Ready, too! (Next version of Ready's Houdini plugin (py3/H19.5) hopefully coming soon!)


I tried searching around to find out what this is, and I think it's https://github.com/gollygang/ready


I'm never going to stare at TV static and see deeper meaning in random noise, and while this is almost the opposite of that, I'm surprised by how I felt watching this.

Awe and mild discomfort aren't the usual feelings I get watching information being processed.


Very smooth. Wonder if there are any optimizations like Hashlife going on? There’s a lot of spatial redundancy to exploit.

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


It need not do any simulation at all. Representing this as an animation should be very doable. Probably 2^4 animations (1 for each potential state of a cell) then you just need to tile the animations and replace sub pixels as needed. So you start out showing a zoomed in view of the animation. As you zoom out you tile based on the animation shown one layer up. The exact tiling is probably tough, but easier than actually simulating and keeping tons of state


I've also heard that Game of Life can be implemented as a pixel shader, so your browser gets to use all that dank GPU available.

But a looping animation makes sense too.


The OTCA metapixel has 2048x2048 cells and a period of 35328. That's a total of 18.5 GB. And that's not counting the different states depending on neighbors and on-off-transitioning state.

Even with compression that's a lot of data.


While an interesting effect, this recursive nature of this game can not be seen unless one has a mouse scroll wheel. I think it would be good to allow zoom in/zoom out to be done a different way (such as page up/page down or +/-). Not everyone has a mouse scroll wheel.


While this may not work for tablets (?), the vast majority of laptops have a setting called two-finger scrolling that lets you use two fingers on a trackpad to give scroll wheel inputs.


It works perfectly fine on mobile and it feels really smooth :)


What kind of mouse doesn't have a scroll wheel?


This is amazing! I've seen "life in life" as a video from ages ago[0], but this is just suck a slick implementation of it!

[0] https://www.youtube.com/watch?v=xP5-iIeKXE8


It isn’t often I verbally exclaim on opening an HN link. Wow.


It looks quite different on mobile here (both Chrome and Firefox) than on desktop. It's way better on desktop, on mobile quite chaotic and doesn't seem to follow the actual Game of Life rules.

Really cool on desktop here!


Yeah, on mobile even if I turn the speed way down, it skips over many steps making everything unrecognizable. It lowers the FPS but still skips just as much between rendered frames. Seems like a programming error.


Doesn't work in Firefox

Uncaught Object { message: "assertion error", stack: "C@https://oimo.io/works/life/main.js:31:459\nze@https://oimo.i..., g: {…}, value: "assertion error" } main.js:37:66


I use firefox 108, worked for me just fine


Works with 107.0.1 as well


Firefox 108 on macOS Monterey, works.


It just says "Loading" for me with FF 106.


I got that error in Brave until I turned off the blockers


Perhaps disable some extensions?


Firefox Android, ok.


But hours later, Firefox Ubuntu crash with "assertion error". I disabled uBO, Decentraleyes, Privacy Badger, it doesn't go away.


I guessed almost immediately how this is implemented, but I'm still amazed by how fast it is.


I guessed too. Do you think I was right?


This is awesome. How would one describe this formal system? There are no cells essentially


That's what's really awesome about it. In essence there's nothing but the rules of the game of life.

I wonder if it's the same for reality. Everytime we've been looking at some particles we deemed fundamental they appear to be made of even smaller ones.


> Everytime we've been looking at some particles we deemed fundamental they appear to be made of even smaller ones.

Not everytime. There is a list of particles that we currently deem fundamental, because no one has found any structure in them. But maybe we haven't looked closely enough yet. Some entertain the idea that they consist of vibrating strings instead of structurless, pointlike particles, but then those would be fundamental.


Well, electrons are sort-of fundamental.

But they can also be seen as quantized excitations of some underlying quantum field.


There are cells, but they are not atomic but decomposeable.

Each cell in level N is the stable pattern of gliders arranged into a square shape in the lower level N-1. If you think about it, this is how "objects" in the real world exist - not as an essence of the object, but as a pattern of simpler elements arranged in space-time that we recognize as an object.


You can't fool me! It's Life all the way down!


Life is life - nana na nana


That is so cool! This person really is a freak, in good way. They also created their own physics engine, which was featured here a while ago: https://github.com/saharan/OimoPhysics

But it would be cool if we could change the GoL parameters and see how that affects the infinite fractal recursion!


Wow, this is something I never considered... go down the rabbit hole on this site ("guns", "glider guns", etc). I had no idea people actually tried to "game" or discover useful patterns in game of life:

https://conwaylife.com/wiki/OTCA_metapixel


“It was the right day to micro dose”, Christopher Robin said to himself.


If you zoom in, you get lower and lower level OTCA metapixels forever, very straightforward.

But if you zoom out, at any time it could be possible for them to compute a different pattern. But it's OTCA metapixel all the way up. What is being computed, other than more OTCA metapixels? What is being computed after infinite zoom out steps?

Makes me question the meaning of existence!


OK, this is mind-blowing


haha getting the speed right at the different levels and everything, nice


My God, it's full of pixels!


Super well done! The transition between levels is beautiful.


I am enjoying this. Is there a way to pause? I have to verify each cell just to boggle my mind at the fact that everything is adhering to GOL rules.


It is interesting to observe that the perception of time changes with zooming in/out. I know the actual speed of the gliders remains the same, but it seems to my eye that they speed up if you zoom out and slow down if you zoom in.

I wonder if this perception has an analogue in the physical world that has relativity as a consequence.


They really slow down it's not just perception. Try to time it.


The distance metric also changes.


This is really great. I would like to use it as a visual backdrop on a big screen when playing DJ sets. I see that it enters a permanently zooming out mode when I zoom out fast, would be awesome if the zoom control disappears when it enters that mode so that it just displays the game of life itself and no UI elements.


Make a greasemonkey script and Bob's yer uncle! :)


Unfortunately the controls UI elements seem to be rendered in the canvas, so it's not as simple as just hiding something. I can't even inspect it.


Nice zoom out, it feels like the Universe is constructed a bit like this


i can't possibly be the only one who didn't get what this is


It's a game of life simulation that is -itself- running a game of life simulation that is running a game of life simulation that is ...

https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Game of Life is Turing-complete, and has all sorts of other weird and interesting implications in chaos theory and philosophy of maths.

You can write a game of life implementation on a rainy sunday afternoon, and be stuck playing with it for weeks.

This guy took it to another level though.


Hint: zoom out.


Mesmerizing, I am interested for the code and how is this built. When I said build the entire fractal concept is it emergent or deliberate? Who did author envisioned this>


I wonder what the smallest molecules/things are that could be used to make a real game of life? Could you do it with bacteria? Surely not viruses or amino acids?


The longest-running evolution experiment uses bacteria and it has been running for more than 30 years. There's a Veritasium video about it: https://www.youtube.com/watch?v=w4sLAQvEH-M


The difficulty is keeping it error-free. The best way we know is what we're using for CPUs.


This is the coolest thing I've seen in a long time!


Mesmerising! And so fast!

@JWZ, can we have a xscreensaver for this please!


Incredible. There's more here: https://oimo.io/works


This person's entire website is beautiful.


No matter what speed/zoom I set it to, it skips steps like crazy and no simulation can be seen.


well this guy makes me feel stupid, tbh.


also duplicated at: https://news.ycombinator.com/item?id=33971341

There must be a trick to it, but some of it has to be real... and it's so smoothly done I can't easily see the transition.


It wasn't immediately obvious to me: you need to scroll to see the recursive aspect.

(This is really amazing)


I had a sudden dawning zooming out that really felt like a psychedelic "insight".


How is this even possible?


As you zoom out, the simulation of the underlying cells is swapped for a higher level simulation of the cells at the next higher level. Watch how the simulation of the cells from the level down speeds up as you transition to the next level.


Life in Life is a real thing.

https://golly.sourceforge.net/ is a tool/toy that will help you explore this stuff if you're interested.


Amazingly performant. Runs on old hardware very smoothly.


This should be an option for a screensaver. Well made!


amazing, both visually and conceptually.


Has anyone tried this in a 3D cell distribution instead of 2D arrangement of cells with similar rules?

Does it simulate life or universe at any scale?


OOOohhh, you have to scroll!


Neat


Loading...


It should be oiomo.io


That is beautiful


this is what the internet is all about thx :)


Beautiful


How?


WOW


Trippy.


beautiful


neat




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: