8 ms·
Making a falling sand simulator
- jacquesm 5y agoVery neat! Would it be an idea to make the humidity of the sand variable?
- kzrdude 5y agoNice 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.
- techbio 5y agoI also observe this bias, I imagine it is an artifact of > versus >= on the pixel boundary.
- tpxl 5y agoIt'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.
- jasonjmcghee 5y agoIt 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!
- UncleEntity 5y agoAlso wraps around if the pile gets too big to fit in the frame.
- jasonjmcghee 5y agoIt'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.
- jakear 5y agoChoosing 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 :)
- jdthedisciple 4y agoInteresting, 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); }
- dannyking 5y agoThis is supportive more than constructive but this is a really great article. Your code is clear and instructions are really nice to follow. Bravo!
- jasonjmcghee 5y agoThank you!
- steve_adams_86 5y agoI 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!
- jasonjmcghee 5y agoAlright! Do you have an area of particular interest? Add new materials? Improve performance? Polish the details? Something else?
- steve_adams_86 5y agoOh 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.
- panzerboiler 5y agoNice 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 https://www.youtube.com/watch?v=prXuyMCgbTc "Exploring the Tech and Design of Noita"
- jasonjmcghee 5y agoThank 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...
- natly 5y agoThat was a wonderful talk. Anyone know of similarly great (gaming focused) talks? (Or a playlist containing them.) They're so hard to find.
- Athas 5y agoIf 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 5y agoIf 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 5y agoYes, 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 5y agoDo 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.
- danbmil99 5y agoI love simple browser-based projects like this. I did one years ago that is surprisingly still running: http://busyboxes.org/fizx/ http://busyboxes.org/fizx/
- fractallyte 5y agoThat'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-organized_criticality_An_experiment_with_sandpiles https://www.researchgate.net/publication/252164461_Self-orga... And an article: https://www.jstor.org/stable/24936753 https://www.jstor.org/stable/24936753
- sh4rks 5y agoNice. 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.
- Kiro 5y ago> 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?
- jasonjmcghee 5y agoThe 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.
- Kiro 5y agoI 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?
- 7373737373 5y agoYeah, 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-cellular-automata-and-graph-based-game-systems-part-1.html https://blog.macuyiko.com/post/2017/an-exploration-of-cellul... https://blog.macuyiko.com/post/2017/an-exploration-of-cellular-automata-and-graph-based-game-systems-part-2.html https://blog.macuyiko.com/post/2017/an-exploration-of-cellul... https://blog.macuyiko.com/post/2018/an-exploration-of-cellular-automata-and-graph-based-game-systems-part-3.html https://blog.macuyiko.com/post/2018/an-exploration-of-cellul...
- Macuyiko 5y agoActually 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-cellular-automata-and-graph-based-game-systems-part-4.html 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.
- Rodeoclash 5y agoI'm aware of Powder Toy and Noita, both of which are excellent, any other developments in this space?
- natly 5y agoI found this the other day: https://store.steampowered.com/app/1196080/Space_Simulation_Toolkit/ 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 https://www.youtube.com/watch?v=3HygqknsmjY
- luismedel 5y agoAnyone else remembers the Blastersound BBS intro from 1994, by Iguana? :-) https://www.youtube.com/watch?v=qPOoU44GU50 https://www.youtube.com/watch?v=qPOoU44GU50
- petepete 5y agoI didn't, but this made me think of the game Cataclysm, which came out on the Acorn Archimedes in 1991. https://youtu.be/3Byyz1Vlv8w https://youtu.be/3Byyz1Vlv8w
- swah 5y agoJust 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.
- Dorothy014 5y ago[dead]
- osandov 5y agoThis 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...
- bioemerl 5y agoI 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.
- sgt 5y agoEnjoyable 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?
- usrn 5y agoThese 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.
- sgt 5y agoIs there a better way to build cute little canvas or browser games?
- 5560675260 4y agoOne simple improvement would have been to pause simulations as soon as system comes to rest.
- sgt 4y agoI 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.
- GrumpyNl 5y agoI must drink coffee first. I kept reading, failing, and was wondering, where, it works great. Nice job.
- deleted 5y ago[deleted]
- davidkunz 5y agoBack 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 https://en.wikipedia.org/wiki/Clonk
- is0tope 5y agoLove 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!
- DonHopkins 5y agoThere'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 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 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 https://www.youtube.com/watch?v=diGjw5tghYU >Coding Challenge #107: Sandpiles >In this coding challenge, inspired by Numberphile I visualize "sandpiles" with Processing (Java).
- Evidlo 5y agoYou 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.
- jasonjmcghee 5y agoThanks for the feedback! Can I trouble you for your browser / platform? For the browsers I have tested, scrolling has worked.
- cosmiccatnap 5y agoP5 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.
- mrtksn 4y agoThe large Bootstrapping procedures has become a huge problem in most modern developer tools. Libraries like p5.js are fresh breeze of air.
- ivan_gammel 5y agoIn 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.
- compressedgas 5y agoThat isn't a virus. It is a terminate and stay resident (TSR) DOS program. What you wrote was basically a screen saver.
- ivan_gammel 5y agowell, as kids we certainly called it "virus", but you are of course right :)
- mbrodersen 5y agoWhat a great article. Short and to the point with excellent interactive segments demonstrating everything. Bravo!