Show HN: Rust Implementation of Conway's Game of Life
github.com
github.com
The current state of the art is Golly: https://en.wikipedia.org/wiki/Golly_(program)
Possibly https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa...? Or https://www.semanticscholar.org/paper/Exploiting-regularitie...?
https://rustwasm.github.io/docs/book/game-of-life/introducti...
- At any given time each alive cell has a probability to go into the dead state, at 0.01 or lower per iteration - equivalent of "entropy")
- There are localized sources of "energy" (areas where a dead cell will spontanously come alive with high probability, 0.1-0.9 or so)
- some interesting results are immediately noticeable. Like blinkers will die quickly, but blocks can regenerate from entropy damage.
My hypothesis is that large enough simulation of this kind might yield a true A-life pattern.
P.S. I also want to learn Rust a bit more, so this looks like a good project to fork.
Rust makes this both fun and a challenge - immutable variables and trait objects make simulation programming a bit trickier. In the end the project fell off a cliff when I got grumpy that I couldn't create a single templatized breeding function that could apply to both types of brains - because of those trait objects. It started to look like I'd have to unwind a lot of my design to rework it (a common experience in Rust!) and then I got a new job, and you know the story.
In every other respect Rust made this project a real pleasure - the tooling is great, particularly the compiler. It's been a couple of years, perhaps I'll dust it off again!
"The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge" https://www.amazon.com/gp/product/0809252023/ref=as_li_ss_il...
(Strip the affiliate code off if you like!)
I took a stab at it a few years ago. My strategy was to start with a very basic Turing Machine, and then write a compiler that compiled a more sophisticated Turing Machine out of a simpler Turing Machine.
For example, when I wanted cells to have a value and a tag, I wrote a compiler that translated every possible combination of symbol and tag into a single flat space of symbols.
I stacked compiler on top of compiler until I had a Langdon's Ant with various programming conveniences, and I wrote a 9-cell GoL using my Langdon's Ant.
The whole thing compiled to a very simple TM with millions of states, but it worked. I did not make it practical enough to ever manage a GoL big enough to emulate a Turing machine, but I feel that I did enough to get some practical experience with something that is straightforward in theory.
---
Turing Machine in GoL: https://www.youtube.com/watch?v=My8AsV7bA94
If you mean "applications" in the practical sense, there are basically none, but that's part of the fun. GoL is fascinating in part because it's pretty much useless, yet has been studied extensively by bored computer scientists over the decades.
> Ideally the board is "infinite"; the "creatures" can progress infinitely in any direction, so it's best if they don't hit a wall
> The most obvious data structure for Life is a 2D array. But that will have walls, and while it could be re-allocated as necessary to grow indefinitely, this would get extremely memory-inefficient for, say, a glider that shoots off in one direction and leaves nothing behind.
> What I landed on was using a HashMap whose keys are locations (row/column) and whose values are booleans, indicating aliveness state. This allows the structure to be incredibly "sparse"; i.e., memory usage is tied to how many cells are alive, not where they are or where they've been before. It only needs to actually record the ones that are alive right now, and the ones that might become alive next cycle (direct neighbors of the currently-alive). These keys of the current HashMap are then iterated over as the only candidates for being "possibly alive" in the next cycle.
Given that they later state that they maintain two "worlds" ("today" and "tomorrow" - current and next), shouldn't it be enough to record coordinates/location of live cells?
I suppose that'd require a pass to lookup candidates from live cells (complicating the work of creating "tomorrow" from "today" a little). But it seems the boolean/list of neighbors is redundant?
It sounds like you're recommending a list (or Vec) of Locs instead of a HashMap from Locs to booleans. Yes, this would also work, but it would be quite a bit slower because whenever it needed to check the liveness state of a given Loc (which it does very frequently), that would be a O(N) search instead of a O(1) lookup.
Edit: it did just occur to me that a HashSet could be used, which would save a small amount of memory without introducing the performance issue. Though it would also prevent (or at least complicate) the strategy below where I pre-mark the dead neighbors of alive cells.
> But it seems the boolean/list of neighbors is redundant?
Technically including the dead neighbors in the HashMap is also redundant, but it's also a (less important) optimization. By recording the dead neighbors while setting the live cells, a little bit of work is saved on the next phase because otherwise I would have to iterate over all 8 neighbors for each live cell, when determining their next state. This would mean many cells would get iterated over several times, as they might have several alive neighbors. Doing it the way I did also just simplifies the logic a bit.
I was indeed thinking of keeping the "occupied" coordinates in a set-like structure. Not sure how a boolean is stored - is it 8 bits, or a single bit? Either way, just storing two (eg) 64 bit coordinates should trivially align (ish)?
The trick would be to quickly be able to go over all occupied cells and their neighbors in order to build "tomorrow's" board. I suppose the new board might serve as a cache/state helper of sorts, but I think the logic would have to be a bit more complicated.
Maybe it's possible to go from a 1d algorithm to a 2d one by making sure there's a list of occupied cells sorted by their place on a Hilbert curve?
My intuition tells me it's simpler to go center out, than row-by-row (if we store only occupied cells, we need to deal with the empty row "above" our first occurrence somehow - it might be easier to "push" out).
I'd probably have to try and sketch this out on paper though :)
At any rate, I just immediately though storing sn extra dead/alive bit seemed a bit redundant and possibly alignment unfriendly if only "really" needed a list/set of occupied cells.
But perhaps the most pragmatic way of changing just the data structure (and more or less keep the algorithm (with the caveat that I haven't actually looked at the code!))- would be to split each generation in two - a list of live and list of dead cells - each accessible via their coordinates in a quick manner.
But ever since implementing a naive (backed by 2d array) game of life, I from time to time play with the idea of trying for something much higher performance. I'm not sure if this one scales to 30fps at 4k for example (maybe it surpasses that on modern hw!). That's the kind of target that'd be fun to aim for. Quite possibly using the frame buffer for state is more efficient anyway.
Dynamically sized arrays have been in the standard library since day 1.
I am indeed a beginner in rust, and i was surprised by the completely different syntax & types for arrays and Vec... I read about it afterward and get the reason for it, but that's the first time i encountered that peculiarity in a language..
> funny how rust doesn't seem to let you easily work with dynamically sized array
Could instead have been
> why did the author choose a hashmap?