4 ms·

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 current

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

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