Making a falling sand simulator | Hacker News Reader

Making a falling sand simulator

jason.today

233 pointsjasonjmcghee65 comments

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

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 I wonder if that is fixable. (Although at larger scale it's not particularly visible: https://sigkill.dk/junk/diving-beet.webm)

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.

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

There are some diagonal interactions that are not directly expressible in this way, but they can propagate through the non-diagonal neighbours instead.

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.

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/

Thanks for reminding me.

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

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

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

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

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.

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

>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/

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

Here's some more info:

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

JavaScript implementation:

https://mfm.rocks/

https://github.com/walpolea/MFM-JS

Robust First Wiki:

http://robust.cs.unm.edu/doku.php

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.

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), I don’t think it’s a given that a GPU would provide the ultimate in performance.

Nice work, Jason. I enjoyed a lot a talk [1] at GDC by Petri Purho (Nolla Games and before that Kloonigames) that explains the "Falling Everything Engine" used in their game Noita (that I would love to play on my mac...). Highly recommended if you want to dive deeper into the topic.

[1]: https://www.youtube.com/watch?v=prXuyMCgbTc "Exploring the Tech and Design of Noita"

Thank you! What an enjoyable talk! Adding solid bodies and Box2D physics into the mix would certainly complicate things. It does sound fun to work on...

That was a wonderful talk. Anyone know of similarly great (gaming focused) talks? (Or a playlist containing them.) They're so hard to find.

That's a really cool article!

One more step: self-organized criticality... At a 'critical angle', any additional grains of sand can trigger an avalanche. (Be careful though, this is a deeply fascinating rabbit hole!)

Here's a nice paper: https://www.researchgate.net/publication/252164461_Self-orga...

And an article: https://www.jstor.org/stable/24936753

I love this. As a visual learner this helps get the ideas across extremely clearly. It’s a lot of fun, too.

As you noted at the bottom to reach out if we want to see more like this - yes please, I think that would be great.

Coincidentally I’ve been curious about writing something like this since playing a game with very primitive materials and physics with my son a few years ago. This made me realize we could actually build something quite easily, so thanks!

Alright! Do you have an area of particular interest? Add new materials? Improve performance? Polish the details? Something else?

Oh wow, great questions and thanks for asking.

In the post you wrote, as some people already mentioned, the sand distributes first to one side and then the other. It would be cool to get something non-deterministic happening instead.

Performance improvements are always very interesting to me, regardless of the context. That’s a definite yes.

Otherwise I suppose other materials would be great. How could you make a vine grow? Or a tree? Far too complex? I’m not sure but I’d enjoy the hell out of learning how.

I love simple browser-based projects like this. I did one years ago that is surprisingly still running: http://busyboxes.org/fizx/

Nice

I see the final result here has a left bias, just press and hold to see it stacking towards left before right. So the next fix could be a random choice.

I also observe this bias, I imagine it is an artifact of > versus >= on the pixel boundary.

It's because the left pixel is checked before the right pixel (the settling behaviour section). This is common in games where you handle movement input (left, right arrow keys) - if you press both of them you'll always go one way, because that way is checked first for movement.

It does indeed! It's a great note. As you say, randomly choosing between left and right if they both exist would fix the bias.

Another issue is that it forms a perfect diagonal, which isn't the most pleasing to look at. It can be addressed by randomly allowing for stacks of two granules and allowing spreading further than just one position to the left or right.

I figured where I left it was appropriate for this post, but I'm happy to write follow-ups for other particle types and the kind of improvement you mentioned!

Also wraps around if the pile gets too big to fit in the frame.

It's true! This has to do with how I wrote the "belowLeft" and "belowRight" variables. I don't ensure they are in the same row. You can do this by taking a pair of indices, dividing by width and flooring and checking for equality.

Choosing between left and right if they're both open fixes the bias when there is only a single pixel falling, but not when a circle is used. This is because the update function runs from right to left across the screen, so the falling pillar of sand behaves like a solid wall as the update has not had the chance to move the other side of the circle yet. The best example of this is dropping a pillar on the right slope of an existing cone, a solid line will form on the right side of the falling segment, but a slope will form against the left side of the pillar. When you try this with the left side of a cone, the behavior is correct.

One fix I found is relatively straightforward:

        class FallingGrid2 extends FallingGrid {
            // Draw from the end of the list to the beginning
            update() {
    +          const direction = Math.random() > 0.5 ? 'ltr' : 'rtl';
               for (let i = this.grid.length - this.width - 1; i > 0; i--) {
    -            this.updatePixel(i);
    +            if (direction === 'rtl') {
    +              this.updatePixel(i);
    +            } else {
    +              const offset = i % this.width;
    +              const flipped = this.width - offset;
    +              this.updatePixel(i - offset + flipped);
    +            }
              }
            }
          }

Cheers for making the source so easily hackable :)

Ah! I see now! Yes, we should alternate the direction of the rowwise pass, or pick randomly, as you demonstrate. This would be a great step to start a next post with.

Interesting, I solved it differently, by just randomly selecting the order in which belowLeft and belowRight are checked, inside the updatePixel function:

    updatePixel(i) {
        const below = i + this.width;
        const belowLeft = below - 1;
        const belowRight = below + 1;
        // flag to indicate if we checked the left side already
        let checkedLeft = false;

        if (this.isEmpty(below)) {
            swap(i, below);
        // check the left side first with 50 % prob (ltr)
        } else if (Math.random() <= 0.5 && this.isEmpty(belowLeft)) {
            swap(i, belowLeft);
            // indicate we checked the left side already
            checkedLeft = true;
        // check the right side first with 50 % prob
        } else if (this.isEmpty(belowRight)) {
            swap(i, belowRight);
        // if we haven't checked the left side earlier, check it now (rtl)
        } else if (!checkedLeft && window.sandgrid[belowLeft] == 1)
            swap(i, belowLeft);
    }

I may be testing wrong, but I believe that approach causes dropping a steady stream of sand on the right side of a cone to produce very strange falling behaviour as compared to the left, because the stream is more than one pixel wide. Looks like you changed some other bits around so you may have addressed this some other way.

Whoops I just noticed a copy-paste error I did, which might be the reason for what you describe in case you copied my code above

3rd last line the "window.sandgrid[belowLeft] == 1" needs to be "this.isEmpty(belowLeft)" instead

Other than that I'm not sure what would be causing the weird behaviour. I use this and it seems to work just fine.

Enjoyable demo, but Chrome is suddenly taking high CPU when dropping sand and my laptop is sounding like a plane about to take off. Why are canvas demos always so inefficient in the browser?

These are usually iterating over a screen-sized buffer every frame. There's no nice way to slice that, just a bunch of work for the machine to constantly do.

EDIT: I'm out of quota. For games like this it's pretty hard. You can move it into a fragment shader or maybe mark certain rectangles in the canvas as "empty" (there's a very fast algorithm for cellular automata which pretty much has the same issue.) There are no "easy" solutions though.

Is there a better way to build cute little canvas or browser games?

One simple improvement would have been to pause simulations as soon as system comes to rest.

I was thinking - maybe JS is not the way to do this? Maybe to write similar things one should do it in WebAssembly. Thoughts? I mean, even with paused simulations, I don't see why an i7 CPU should be working at 100% just to draw something on a tiny window in a browser. It seems like a flaw in canvas and JS to me.

This is supportive more than constructive but this is a really great article. Your code is clear and instructions are really nice to follow. Bravo!

Thank you!

Anyone else remembers the Blastersound BBS intro from 1994, by Iguana? :-)

https://www.youtube.com/watch?v=qPOoU44GU50

I didn't, but this made me think of the game Cataclysm, which came out on the Acorn Archimedes in 1991.

https://youtu.be/3Byyz1Vlv8w

Just saw a familiar word there that feels like a hundred years old: Fidonet. A 1984 BBS network, it seems. I only got to experience the final years of BBSes but it feels very nostalgic still.

P5 is such a fun library. I'm constantly impressed at how quickly you can get an idea from paper to screen with it. I can't speak to it's viability in production but for research, prototype and just fun there are few alternatives out now.

It reminds me a bit of old basic on Amiga/commodore systems where getting something drawn on the screen and making a beep was trivial and built into the environment.

The large Bootstrapping procedures has become a huge problem in most modern developer tools. Libraries like p5.js are fresh breeze of air.

In 1990s we were writing a virus at school which applied this algorithm to all characters on the DOS screen after some period of inactivity. Destroying Norton Commander on a computer used by a teacher or sysadmin was quite fun (the virus had to be manually installed, did not survive reboot and screen was restored on keypress event, so it was quite harmless). Nobody punished us for this kind of jokes.

That isn't a virus. It is a terminate and stay resident (TSR) DOS program. What you wrote was basically a screen saver.

well, as kids we certainly called it "virus", but you are of course right :)

You should make the <code> tags scrollable. The right half of your snippets are cut off on mobile and I can't scroll to see them.

Thanks for the feedback! Can I trouble you for your browser / platform? For the browsers I have tested, scrolling has worked.

Love this. I also was wondering how to do this cleanly, and in my mind it seemed to make sense to apply the rules to the sand, but onto a blank canvas so as not to have the sand interfere with the sand below.

Doing it from the bottom up solves this problem, however I think in a general sense (eg. with different sources of gravity it would become more tricky!

> Can we always iterate from back to front? (What if our particle was smoke?)

What's the answer to this? How do you mix smoke and sand?

The question I intended to prompt the reader with was, if a particle had a rule to rise instead of fall, which direction should we iterate?

You can try this yourself by using dev tools to modify the code and check the position above instead of below.

I presume the answer is that we need to iterate the other direction but what I'm wondering is how we can mix these. Do we need to iterate the grid twice?

Yeah, I'm wondering how The Powder Toy does it (especially since it also has electronics/wires and changeable gravity)...

Edit: I found a great intro to the cellular automata approach:

https://blog.macuyiko.com/post/2017/an-exploration-of-cellul...

https://blog.macuyiko.com/post/2018/an-exploration-of-cellul...

Actually part 4 should be most interesting if you're interested to know how different materials can be mixed. It also looks at Noita:

https://blog.macuyiko.com/post/2020/an-exploration-of-cellul...

Kudos to the OP article. Although it doesn't go very far the presentation style is very clean and appealing.

I'm guessing here, but I assume a double buffer would solve this for many cases.

I'm aware of Powder Toy and Noita, both of which are excellent, any other developments in this space?

I found this the other day: https://store.steampowered.com/app/1196080/Space_Simulation_... which seems to be a GPU implementation of typical powder toy sims https://www.youtube.com/watch?v=3HygqknsmjY

This was great. Before Powder Game, there were several games in this genre, and a very active Falling Sand Game BBS forum. I got my start in programming by writing mods for one of those games, Burning Sand. I wonder if anyone from those forums is around here...

I was, and my story was very very similar to yours!

I remember fighting burning sand 2 triggers to make a little cursor that would follow your mouse and totally failing at it.

And writing my own little planetary simulator- not one of the popular ones but I gave it my best shot.

I'd love to see a new "game engine" like BS2, but modernized and cleaned up and easier to code on. Powder toy is awesome but not nearly as hackable and isn't super performant.

Back in the day, I really enjoyed playing the game Clonk[1]. I like how water/sand was simulated, great times!

[1]: https://en.wikipedia.org/wiki/Clonk

Nice. I used to play powder game a lot as a kid, and Noita is currently one of my favourite games ever.

Would love to see this made into a series. Maybe implement different elements or optimisations to existing mechanics.

What a great article. Short and to the point with excellent interactive segments demonstrating everything. Bravo!

I must drink coffee first. I kept reading, failing, and was wondering, where, it works great. Nice job.

Very neat! Would it be an idea to make the humidity of the sand variable?

There's some interesting research from 1987 about simulating falling sand!

Don't let the ideas from the past slip through your fingers like sand through an hourglass. ;)

Abelian sandpile model

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

>The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

>Three years later Deepak Dhar invented that the BTW sandpile model indeed follows the abelian dynamics and therefore referred to this model as the Abelian sandpile model.

>The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.

>Dhar has shown that the final stable sandpile configuration after the avalanche is terminated, is independent of the precise sequence of topplings that is followed during the avalanche. As a direct consequence of this fact, it is shown that if two sand grains are added to the stable configuration in two different orders, e.g., first at site A and then at site B, and first at B and then at A, the final stable configuration of sand grains turns out to be exactly the same. When a sand grain is added to a stable sandpile configuration, it results in an avalanche which finally stops leading to another stable configuration. Dhar proposed that the addition of a sand grain can be looked upon as an operator, when it acts on one stable configuration, it produces another stable configuration. Dhar showed that all such addition operators form an abelian group, hence the name Abelian sandpile model.

>The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs). It is closely related to the dollar game, a variant of the chip-firing game introduced by Biggs.

https://www.youtube.com/watch?v=1MtEUErz7Gg

>Sandpiles - Numberphile

>Luis David Garcia-Puente discusses sandpiles, and how they produce amazing "fractal zeroes". Dr Garcia-Puente is an associate professor at Sam Houston State University and was interviewed while attending an MSRI-UP summer program.

https://www.youtube.com/watch?v=diGjw5tghYU

>Coding Challenge #107: Sandpiles

>In this coding challenge, inspired by Numberphile I visualize "sandpiles" with Processing (Java).

Reply on news.ycombinator.com