5 ms·

If you want more performance, falling sand simulators can further be made parallel by implementing them using Margolus Neighbourhoods, as in Falling Turnip: htt

by Athas 4y ago

If you want more performance, falling sand simulators can further be made parallel by implementing them using Margolus Neighbourhoods, as in Falling Turnip: https://github.com/tranma/falling-turnip https://github.com/tranma/falling-turnip The idea is that a single iteration divides the world into 2x2 squares and then applies effects sequentially within each square, but not between the squares. This means each square can be processed independently. In the next iteration, the division into squares shifts right and down by one cell each direction. This does mean you need more steps than in a sequential implementation, but I found it to be quite a principled approach to parallelizing cellular automata when I first read about it. One interesting side effect of this design is that falling particles end up being separated by blank space, as shown here: https://futhark-lang.org/static/falling-sand-2016.12.04.webm https://futhark-lang.org/static/falling-sand-2016.12.04.webm I wonder if that is fixable. (Although at larger scale it's not particularly visible: https://sigkill.dk/junk/diving-beet.webm https://sigkill.dk/junk/diving-beet.webm)

slabity 4y ago
If the 2x2 cell is moving horizontally and vertically by 1 block, then wouldn't that mean you miss the 2 corners you don't pass over for the cell you're currently calculating? Unfortunately the demo video in the link you posted seems to be private, so I might be misunderstanding.
- Athas 4y ago
  Yes, but the next iteration will take care of those interactions. You're not really "moving" anything; that was poor imagery on my part. The illustration on the Wikipedia article shows it well: https://en.wikipedia.org/wiki/Block_cellular_automaton https://en.wikipedia.org/wiki/Block_cellular_automaton There are some diagonal interactions that are not directly expressible in this way, but they can propagate through the non-diagonal neighbours instead.
  - Kiro 4y ago
    Do you know if this is a technique they're using in Noita? I've implemented falling sand simulators but I'm baffled how you can make a game like that performant.
    - andybak 4y ago
      I've been meaning to try Noita and it happens to be 50% off on Steam at the moment: https://store.steampowered.com/app/881100/Noita/ https://store.steampowered.com/app/881100/Noita/ Thanks for reminding me.
    - bo0tzz 4y ago
      Here's a talk from the creator of Noita about the underlying tech. From 9:20 he talks about their multithreading implementation. https://www.youtube.com/watch?v=prXuyMCgbTc https://www.youtube.com/watch?v=prXuyMCgbTc
- DonHopkins 4y ago
  Typically a cellular automata simulation will have some edge condition like wrapping or mirroring an adjacent cell. A nice optimization trick is to make the cell buffers 2 cells wider and taller (or two times whatever the neighborhood radius is), and then before each generation you update the "gutter" by copying just the wrapped (or mirrored) pixels. Then your run the rule on the inset rectangle, and the code (in the inner loop) doesn't have to do bounds checking, and can assume there's a valid cell to read in all directions. That saves a hell of a lot of tests and branches in the inner loop. Also, you you can define the Margolus neighborhood in terms of the Moore neighborhood + horizontal phase (even/odd column x) + vertical phase (even/odd row y) + time phase (even/odd time). With that information the rule can tell if it's at an even or odd step, and which of the four squares of the grid it's in. That's how the CAM6 worked in hardware: it used the x/y/time phases as additional bits to determine the Margolus neighborhood lookup table index. https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L4303 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... Here's how my CAM6 emulator computes the CAM6-hardware-compatible Margolus lookup table index, based on the 9 Moore neighbors + phaseTime, phaseX, and phaseY: function getTableIndexUnrotated( nw, n, ne, w, c, e, sw, s, se, phaseTime, phaseX, phaseY) { // 0 1 2 3 4 5 6 7 8 9 // c0 c1 cw0 ccw0 opp0 cw1 ccw1 opp1 pha0 pha1 // 0x1 0x2 0x4 0x8 0x10 0x20 0x40 0x80 0x100 0x200 var cw, ccw, opp; if (phaseTime) { return ( // c c' (c & 0x03) | // cw cw' (cw = (phaseX ? (phaseY ? (e & 0x03) : (n & 0x03)) : (phaseY ? (s & 0x03) : (w & 0x03))), (((cw & 0x01) << 2) | ((cw & 0x02) << 4))) | // ccw ccw' (ccw = (phaseX ? (phaseY ? (s & 0x03) : (e & 0x03)) : (phaseY ? (w & 0x03) : (n & 0x03))), (((ccw & 0x01) << 3) | ((ccw & 0x02) << 5))) | // opp opp' (opp = (phaseX ? (phaseY ? (se & 0x03) : (ne & 0x03)) : (phaseY ? (sw & 0x03) : (nw & 0x03))), (((opp & 0x01) << 4) | ((opp & 0x02) << 6))) | // pha pha' 0x200); } else { return ( // c c' (c & 0x03) | // cw cw' (cw = (phaseX ? (phaseY ? (w & 0x03) : (s & 0x03)) : (phaseY ? (n & 0x03) : (e & 0x03))), (((cw & 0x01) << 2) | ((cw & 0x02) << 4))) | // ccw ccw' (ccw = (phaseX ? (phaseY ? (n & 0x03) : (w & 0x03)) : (phaseY ? (e & 0x03) : (s & 0x03))), (((ccw & 0x01) << 3) | ((ccw & 0x02) << 5))) | // opp opp' (opp = (phaseX ? (phaseY ? (nw & 0x03) : (sw & 0x03)) : (phaseY ? (ne & 0x03) : (se & 0x03))), (((opp & 0x01) << 4) | ((opp & 0x02) << 6))) | // pha pha' 0x100); } };
ericleong 4y ago
Another way to do this (albeit without simple support for fluids) is to use the Moore neighborhood and use a left and right "bias" to decide which direction a grain should fall towards if it can't fall straight down. This works pretty well as a shader, and has the same side effect with the horizontal lines. https://github.com/ericleong/sand.js https://github.com/ericleong/sand.js
howaboutnope 4y ago
When I made it with WebGL (with no clue what I was embarking on, I just wanted to try it), I ended up with 8 substeps. Looking at it now it confuses the hell out of me, but IIRC it had to do with with checking each cardinal direction both ways ("both ways" meaning both "do I want to swap positions with this other pixel", and "does this other pixel want to swap position with me"). edit: I don't have a good video of this atm, but just to demonstrate it: https://www.youtube.com/watch?v=rItnlDmGALU https://www.youtube.com/watch?v=rItnlDmGALU it's not visualized in the video, but the pixels also have temperature, and materials a sort of stickyness (basically sand that takes longer to form into a pyramid), that's about it.
DonHopkins 4y ago
The Moveable Feast Machine is kind of like a cellular automata, but it has a larger neighborhood extending out in a radius of several cells, it has read/write access to every cell in that neighborhood (not just the center), and it's non-deterministic in the order the rules are applied to the cells. It's embarrassingly parallel because it executes randomly chosen non-overlapping neighborhood regions in parallel. >the division into squares shifts right and down by one cell each direction. The MFM non-deterministic equivalent of the Margolus neighborhood's alternating x,y offset is to randomly execute non-overlapping neighborhoods in parallel. That has the same effect of incrementally diffusing information evenly in all directions over time, just not perfectly, synchronously, symmetrically, and deterministically like the Margolus neighborhood does. Moveable Feast Machine rules make it much easy to implement particle based simulations than with traditional cellular automata rules, which compute just the center cell. Instead, the MFM rules can simply "pick up and move" any number of particles within the wider neighborhood. They can implement all kinds of interesting chemical and biological behaviors between locally interacting particles, like holding molecules of different particles together with atomic bonds, and constructing membranes like cell walls that separate and contain and transport other particles, and implementing magical computational "force fields" and "tractor beams" and "traffic lights" that route other particles around. They're even good for simulating computational DNA-like behaviors: https://www.youtube.com/watch?v=DauJ51CTIq8 https://www.youtube.com/watch?v=DauJ51CTIq8 >Programming the Movable Feast Machine with λ-Codons >λ-Codons provide a mechanism for describing arbitrary computations in the Movable Feast Machine (MFM). A collection of λ-Codon molecules describe the computation by a series of primitive functions. Evaluator particles carry along a stack of memory (which initially contains the input to the program) and visit the λ-Codons, which they interpret as functions and apply to their stacks. When the program completes, they transmute into output particles and carry the answer to the output terminals (left). The Moveable Feast Machine is similar to cellular automata, but different in some important ways, that make it extremely robust and fault tolerant: It's a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. Robust programs running on massively parallel unreliable hardware can actually tolerate hardware failure and repair themselves. The Demon Hoard Sort algorithm is an inherently robust sorting algorithm for the Moveable Feast Machine. http://movablefeastmachine.org/ http://movablefeastmachine.org/ The "Distributed City Generation" video demonstrates a Movable Feast Machine rule that builds a self-healing city that fills all available space with urban sprawl, with cars that drive between buildings, and city streets that adaptively learn how to route the cars to their nearest destinations, and the city even repairs itself after disasters! https://www.youtube.com/watch?v=XkSXERxucPc https://www.youtube.com/watch?v=XkSXERxucPc Here's some more info: https://news.ycombinator.com/item?id=14236973 https://news.ycombinator.com/item?id=14236973 JavaScript implementation: https://mfm.rocks/ https://mfm.rocks/ https://github.com/walpolea/MFM-JS https://github.com/walpolea/MFM-JS Robust First Wiki: http://robust.cs.unm.edu/doku.php http://robust.cs.unm.edu/doku.php
Adverblessly 4y ago
I think the ultimate in performance and parallelism would be to run it on a GPU. As long as you are able to define your algorithm in such a way that the new value of each pixel can be calculated just from itself and its neighbours it will work very quickly. For fun, I've written a Game Of Life implementation in GLSL and even though it is naively implemented it will run at thousands of iterations per second at 4K resolution on a 6 year old desktop gpu.
- Someone 4y ago
  A GPU more likely would give performance that’s independent of the pattern and that has constant stepping time, but given the existence of Hashlife (https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife), I don’t think it’s a given that a GPU would provide the ultimate in performance.

by Athas 4y ago

slabity 4y ago

If the 2x2 cell is moving horizontally and vertically by 1 block, then wouldn't that mean you miss the 2 corners you don't pass over for the cell you're currently calculating? Unfortunately the demo video in the link you posted seems to be private, so I might be misunderstanding.

Athas 4y ago
Yes, but the next iteration will take care of those interactions. You're not really "moving" anything; that was poor imagery on my part. The illustration on the Wikipedia article shows it well: https://en.wikipedia.org/wiki/Block_cellular_automaton https://en.wikipedia.org/wiki/Block_cellular_automaton There are some diagonal interactions that are not directly expressible in this way, but they can propagate through the non-diagonal neighbours instead.
- Kiro 4y ago
  Do you know if this is a technique they're using in Noita? I've implemented falling sand simulators but I'm baffled how you can make a game like that performant.
  - andybak 4y ago
    I've been meaning to try Noita and it happens to be 50% off on Steam at the moment: https://store.steampowered.com/app/881100/Noita/ https://store.steampowered.com/app/881100/Noita/ Thanks for reminding me.
  - bo0tzz 4y ago
    Here's a talk from the creator of Noita about the underlying tech. From 9:20 he talks about their multithreading implementation. https://www.youtube.com/watch?v=prXuyMCgbTc https://www.youtube.com/watch?v=prXuyMCgbTc
DonHopkins 4y ago
Typically a cellular automata simulation will have some edge condition like wrapping or mirroring an adjacent cell. A nice optimization trick is to make the cell buffers 2 cells wider and taller (or two times whatever the neighborhood radius is), and then before each generation you update the "gutter" by copying just the wrapped (or mirrored) pixels. Then your run the rule on the inset rectangle, and the code (in the inner loop) doesn't have to do bounds checking, and can assume there's a valid cell to read in all directions. That saves a hell of a lot of tests and branches in the inner loop. Also, you you can define the Margolus neighborhood in terms of the Moore neighborhood + horizontal phase (even/odd column x) + vertical phase (even/odd row y) + time phase (even/odd time). With that information the rule can tell if it's at an even or odd step, and which of the four squares of the grid it's in. That's how the CAM6 worked in hardware: it used the x/y/time phases as additional bits to determine the Margolus neighborhood lookup table index. https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L4303 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... Here's how my CAM6 emulator computes the CAM6-hardware-compatible Margolus lookup table index, based on the 9 Moore neighbors + phaseTime, phaseX, and phaseY: function getTableIndexUnrotated( nw, n, ne, w, c, e, sw, s, se, phaseTime, phaseX, phaseY) { // 0 1 2 3 4 5 6 7 8 9 // c0 c1 cw0 ccw0 opp0 cw1 ccw1 opp1 pha0 pha1 // 0x1 0x2 0x4 0x8 0x10 0x20 0x40 0x80 0x100 0x200 var cw, ccw, opp; if (phaseTime) { return ( // c c' (c & 0x03) | // cw cw' (cw = (phaseX ? (phaseY ? (e & 0x03) : (n & 0x03)) : (phaseY ? (s & 0x03) : (w & 0x03))), (((cw & 0x01) << 2) | ((cw & 0x02) << 4))) | // ccw ccw' (ccw = (phaseX ? (phaseY ? (s & 0x03) : (e & 0x03)) : (phaseY ? (w & 0x03) : (n & 0x03))), (((ccw & 0x01) << 3) | ((ccw & 0x02) << 5))) | // opp opp' (opp = (phaseX ? (phaseY ? (se & 0x03) : (ne & 0x03)) : (phaseY ? (sw & 0x03) : (nw & 0x03))), (((opp & 0x01) << 4) | ((opp & 0x02) << 6))) | // pha pha' 0x200); } else { return ( // c c' (c & 0x03) | // cw cw' (cw = (phaseX ? (phaseY ? (w & 0x03) : (s & 0x03)) : (phaseY ? (n & 0x03) : (e & 0x03))), (((cw & 0x01) << 2) | ((cw & 0x02) << 4))) | // ccw ccw' (ccw = (phaseX ? (phaseY ? (n & 0x03) : (w & 0x03)) : (phaseY ? (e & 0x03) : (s & 0x03))), (((ccw & 0x01) << 3) | ((ccw & 0x02) << 5))) | // opp opp' (opp = (phaseX ? (phaseY ? (nw & 0x03) : (sw & 0x03)) : (phaseY ? (ne & 0x03) : (se & 0x03))), (((opp & 0x01) << 4) | ((opp & 0x02) << 6))) | // pha pha' 0x100); } };

ericleong 4y ago

Another way to do this (albeit without simple support for fluids) is to use the Moore neighborhood and use a left and right "bias" to decide which direction a grain should fall towards if it can't fall straight down. This works pretty well as a shader, and has the same side effect with the horizontal lines. https://github.com/ericleong/sand.js https://github.com/ericleong/sand.js

howaboutnope 4y ago

When I made it with WebGL (with no clue what I was embarking on, I just wanted to try it), I ended up with 8 substeps. Looking at it now it confuses the hell out of me, but IIRC it had to do with with checking each cardinal direction both ways ("both ways" meaning both "do I want to swap positions with this other pixel", and "does this other pixel want to swap position with me"). edit: I don't have a good video of this atm, but just to demonstrate it: https://www.youtube.com/watch?v=rItnlDmGALU https://www.youtube.com/watch?v=rItnlDmGALU it's not visualized in the video, but the pixels also have temperature, and materials a sort of stickyness (basically sand that takes longer to form into a pyramid), that's about it.

DonHopkins 4y ago

The Moveable Feast Machine is kind of like a cellular automata, but it has a larger neighborhood extending out in a radius of several cells, it has read/write access to every cell in that neighborhood (not just the center), and it's non-deterministic in the order the rules are applied to the cells. It's embarrassingly parallel because it executes randomly chosen non-overlapping neighborhood regions in parallel. >the division into squares shifts right and down by one cell each direction. The MFM non-deterministic equivalent of the Margolus neighborhood's alternating x,y offset is to randomly execute non-overlapping neighborhoods in parallel. That has the same effect of incrementally diffusing information evenly in all directions over time, just not perfectly, synchronously, symmetrically, and deterministically like the Margolus neighborhood does. Moveable Feast Machine rules make it much easy to implement particle based simulations than with traditional cellular automata rules, which compute just the center cell. Instead, the MFM rules can simply "pick up and move" any number of particles within the wider neighborhood. They can implement all kinds of interesting chemical and biological behaviors between locally interacting particles, like holding molecules of different particles together with atomic bonds, and constructing membranes like cell walls that separate and contain and transport other particles, and implementing magical computational "force fields" and "tractor beams" and "traffic lights" that route other particles around. They're even good for simulating computational DNA-like behaviors: https://www.youtube.com/watch?v=DauJ51CTIq8 https://www.youtube.com/watch?v=DauJ51CTIq8 >Programming the Movable Feast Machine with λ-Codons >λ-Codons provide a mechanism for describing arbitrary computations in the Movable Feast Machine (MFM). A collection of λ-Codon molecules describe the computation by a series of primitive functions. Evaluator particles carry along a stack of memory (which initially contains the input to the program) and visit the λ-Codons, which they interpret as functions and apply to their stacks. When the program completes, they transmute into output particles and carry the answer to the output terminals (left). The Moveable Feast Machine is similar to cellular automata, but different in some important ways, that make it extremely robust and fault tolerant: It's a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. Robust programs running on massively parallel unreliable hardware can actually tolerate hardware failure and repair themselves. The Demon Hoard Sort algorithm is an inherently robust sorting algorithm for the Moveable Feast Machine. http://movablefeastmachine.org/ http://movablefeastmachine.org/ The "Distributed City Generation" video demonstrates a Movable Feast Machine rule that builds a self-healing city that fills all available space with urban sprawl, with cars that drive between buildings, and city streets that adaptively learn how to route the cars to their nearest destinations, and the city even repairs itself after disasters! https://www.youtube.com/watch?v=XkSXERxucPc https://www.youtube.com/watch?v=XkSXERxucPc Here's some more info: https://news.ycombinator.com/item?id=14236973 https://news.ycombinator.com/item?id=14236973 JavaScript implementation: https://mfm.rocks/ https://mfm.rocks/ https://github.com/walpolea/MFM-JS https://github.com/walpolea/MFM-JS Robust First Wiki: http://robust.cs.unm.edu/doku.php http://robust.cs.unm.edu/doku.php

Adverblessly 4y ago

I think the ultimate in performance and parallelism would be to run it on a GPU. As long as you are able to define your algorithm in such a way that the new value of each pixel can be calculated just from itself and its neighbours it will work very quickly. For fun, I've written a Game Of Life implementation in GLSL and even though it is naively implemented it will run at thousands of iterations per second at 4K resolution on a 6 year old desktop gpu.

Someone 4y ago
A GPU more likely would give performance that’s independent of the pattern and that has constant stepping time, but given the existence of Hashlife (https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife), I don’t think it’s a given that a GPU would provide the ultimate in performance.