5 ms·
Show HN: Rust Implementation of Conway's Game of Life
- jfoutz 7y agoI wish I could find the original article I read about hashlife[1]. So many dirty tricks to just reach as deep as possible into the evolution of the system. The hash approach is a good trick. you can abuse it quite a bit more than just row/col. Anyway, you might poke around for a hashlife writeup if you're into that kinda thing. [1] https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife
- brundolf 7y agoThat's pretty neat! One of the cool implications of Life being a wholly deterministic and discrete system, even though it's spatial.
- JoshTriplett 7y agoHashlife is also incredibly good at being able to accelerate large-scale computational structures, such as Unit Life cells, which simulate the game of life (or arbitrary other cellular automata) within the game of life: https://www.conwaylife.com/wiki/Unit_cell https://www.conwaylife.com/wiki/Unit_cell The current state of the art is Golly: https://en.wikipedia.org/wiki/Golly_(program) https://en.wikipedia.org/wiki/Golly_(program)
- Someone 7y ago”I wish I could find the original article I read about hashlife” Possibly https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa...? Or https://www.semanticscholar.org/paper/Exploiting-regularities-in-large-cellular-spaces-Gosper/50f1d10032d94c87b421cc410f7ff23325cebc98 https://www.semanticscholar.org/paper/Exploiting-regularitie...?
- braythwayt 7y agoHere's a HashLife implementation that runs in the browser, with an infinitely scrolling universe: https://github.com/raganwald/hashlife https://github.com/raganwald/hashlife
- jacquesm 7y agohttps://jennyhasahat.github.io/hashlife.html https://jennyhasahat.github.io/hashlife.html
- ShorsHammer 7y agoIf you are interested in compiling down to wasm. https://rustwasm.github.io/docs/book/game-of-life/introduction.html https://rustwasm.github.io/docs/book/game-of-life/introducti...
- d_silin 7y agoThere is an intriguing variety of Conway's Life I want to find some time to work on: - 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.
- brundolf 7y agoIs this an established variation or something you invented?
- d_silin 7y agoThis is something I invented many years ago, I even wrote a basic implementation in C#, but it was not suitable for large-scale simulations.
- fastball 7y agoAt that point I think you have gone above Conway's Game of Life and are now just in the superset of "Cellular Automata".
- rsiqueira 7y agoLet's think about more simple properties that could be added to create a more interesting dynamical system. Some ideas are: each cell could be a small neural network that learn properties of its surrounding environment; each generation could produce variation of neural network parameters so it could use evolutionary algorithm to evolve; the cells (or group of cells) could be able to move (e g. the evolutionary algorithm will select the ones that move towards the energy source); the cells could have sensors (e.g. sensing proximity of the energy source); cells or group of cells could compete for resources.
- 7y ago
- mauricedenassau 7y agoFor even more memory efficiency there's Transpose Jagged Diagonal Storage format (TJDS) https://www.sciencedirect.com/science/article/abs/pii/S0020019004000249 https://www.sciencedirect.com/science/article/abs/pii/S00200...
- bsaul 7y agofunny how rust doesn't seem to let you easily work with dynamically sized array. Why pick a hashmap to represent the world instead of a vec ?
- quietbritishjim 7y agoFrom the readme: > 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.
- bsaul 7y agoThanks, indeed i missed that !
- e12e 7y ago> What I landed on was using a HashMap whose keys are locations (row/column) and whose values are booleans, indicating aliveness state. 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?
- brundolf 7y ago> shouldn't it be enough to record coordinates/location of live cells? 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.
- braythwayt 7y agoA must-read for fans of Conway's Game of Life and laypersons looking for an approachable read. It covers both the history of GoL, and its implications for understanding the nature of Life itself: "The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge" https://www.amazon.com/gp/product/0809252023/ref=as_li_ss_il?ie=UTF8&tag=raganwald001-20 https://www.amazon.com/gp/product/0809252023/ref=as_li_ss_il... (Strip the affiliate code off if you like!)
- tasuki 7y agoHere's John Scholes coding up the Game of Life in an APL one liner: https://www.youtube.com/watch?v=a9xAKttWgP4 https://www.youtube.com/watch?v=a9xAKttWgP4
- spanxx 7y agoI'm interested as well in implementing Conway's Game of Life but I wonder, what are the applications of this system in computation? Can a Turing Machine be constructed with this system?
- Der_Einzige 7y agoYes
- braythwayt 7y agoNot only is the answer "Yes, a Turing machine can be constructed out of GoL, demonstrating that GoF is universal," but given that GoL is itself a computation, the reverse is true: You can build GoL out of a Turing machine. 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 https://www.youtube.com/watch?v=My8AsV7bA94
- empath75 7y agoYou can not only build a turning machine with GoL, but you can build GoL in GoL https://youtu.be/xP5-iIeKXE8 https://youtu.be/xP5-iIeKXE8
- brundolf 7y ago> what are the applications of this system in computation? 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.
- rsiqueira 7y agoThere are JavaScript implementations of Conway's Game of Life in just 140 characters, here are some of them: https://www.dwitter.net/h/gameoflife https://www.dwitter.net/h/gameoflife Some have changed the rules to produce other population dynamics.