I rewrote most of the atom movement and made it about 40% faster on my big test level.
Yeah, I know, I've written a lot of updates about performance-tuning lately.
So instead, let's talk about how I made fluids behave a lot more, well, fluidly.
Fluid Simulation ABCs
How to simulate fluid mechanics in 5 easy steps:
- Decide whether to model compressible fluids (tip: don't).
- Decide whether grid-based (Eulerian) or particle-based (Lagrangian) or a hybrid computational method is most appropriate.
- Select one of the matching algorithm(s) for your method, such as PIC, SPH, FLIP, MPM, APIC, etc. 1
- Lock yourself in a dark room for 3-30 days to read computational physics papers and implement your chosen algorithm.
- Rewrite your algorithm to run on a graphics card, so it isn't dog slow.
There's even a specific subfield of fluid simulation for simulating fluids with cellular automata (which is what underlies my atom simulation).
But, I forgot my differential calculus ~15 years ago,2 3 so I'll walk you through my more expedient approach:
Fiddling With Atom Movement Until Fluids Look Good.
Powder Atom Movement
Fluid movement is based on powder movement, so here's Baby's First powder simulation: 4
You can add in some biased randomness to make it look more natural: 5
Now, how can we make this more liquid-y?
Fluid Atom Movement
The common advice is to allow fluid atoms to move sideways:
This works, but you can see fluid levels equalize very slowly.
The best trick I've found mostly stolen6 is to allow fluids to move many spaces horizontally: 7
This "spreading" behaviour allows fluid atoms to get out of each others' way faster, but we can do better!
Fundamentally, atoms have to be updated one at a time8, and because the world is broken into chunks of size 64 by 64 that are simulated individually,9 we tend to get atoms being blocked by atoms in chunks that haven't been simulated yet. That causes some pile-up behavior.
The key is realizing that fluid atoms moving through each other is totally unnoticeable:
Fluid levels now equalize in a second or two, yay!
Here's a slowed down visualization showing the moves that atoms are making:
Anyway, this works great, right up until you try to cast a water spray spell:
Spraying Fluids
Fixing fluid dribbling gets complicated quickly. 10
Up until now, each atom checks a few directions randomly and moves along them if it can - and next time, it might pick a different direction.
But to spray, atoms need to have a consistent velocity, which is altered by gravity and hitting obstacles:
This drastically improves the dribbling, but it isn't entirely fixed - how come?
The remaining dribbling happens when an atom A is blocked by enough other water atoms (which haven't yet moved) so that it can't actually find a free spot to move to. So atom A reverts back to the old movement rules and falls down. Now atom A ends up blocking other atoms and the problem compounds.
My dirty hack approach is to temporarily defer atom A's movement:
- Take atom A out of the world.
- Move all other atoms, which hopefully frees up atom A's preferred destination.
- Try to put Atom A back at its preferred destination. 11
That way, atom A can move, and it also doesn't block other atoms, so we can finally spray water properly:
For comparison, here's what spraying water looked like up to last week:
Test the new fluid simulation
I've also applied these techniques to pseudo-fluids, so now you can more reliably spray fire or steam too - try it out below.
Tell me: can you break the new fluid (or powder or gas) simulation? Please 
let me know!
Tip: you can press F4 to enter edit mode, and choose from different atoms (like bouncy rubber) or set the velocity of atoms you draw using the sidebar on the left.
Some issues I'm aware of:
- Spraying fire works a little too well - it looks a bit too uniform?
- Dropping moving bodies like barrels into liquids sometimes makes some of the liquid disappear.
- Dropping moving bodies into liquids should make nice splashing happen, but it doesn't yet.
- Some powders are way too slippery, so they take a long time to (or never) slide to a stop. 12
Ideally based on a thorough understanding of the tradeoffs of each as discussed in the relevant papers, rather than which Youtube videos seem most entertaining or shortest.
On an entirely unrelated note, I highly recommend Sebastian Lague's Fluids video and Matthius Mueller's Ten Minute Physics videos.
Or, approximately 15 minutes after my last mathematics exam.
Well, I did implement the basic CPU-based Eulerian fluid simulation shown above a couple months back, with the goal of working up to full FLIP fluid sim. But even at this small scale, it this simulation was way too slow (25ms per simulation tick, when my time budget is about 1ms).
Perhaps SPH would be fast enough (I doubt it), or I could get something fast enough if I ported it to graphics-card-based compute, but I am not sure if that will break determinism, or if reading back data from the GPU can be done fast enough to rely on it for more than cosmetic purposes. Experimenting with that is still on the TODO list!
Well, you also need to update the simulation from bottom-to-top row-wise, otherwise an atom will be blocked by atoms below it that haven't moved.
Up until this week, my falling sand simulation mostly didn't use any randomness, which made it easier to understand and debug. But I eventually gave up on that because randomness makes it a lot easier to get results that look good: we aren't used to seeing uniformity. You can also adjust a lot of behavior by tweaking the randomness thresholds - for example, increased odds to move diagonally makes atoms spread out more and seem gaseous.
From Powder Toy's source code. Did I say stolen? Because I meant to say "unearthed with great difficulty": Powder Toy is super cool but I find its source code quite tricky to unravel (e.g. this thousand line function).
There's a few more details I'm eliding: for example you should also make fluid atoms try to move down after moving across, otherwise they end up floating in air sometimes. And you need to remember which direction fluid atoms spread in last time & continue that - otherwise a bunch of fluid atoms can flip-flop between two positions and stay in a pile, instead of eventually finding a lower point to move to.
Well, strictly speaking you could update atoms in parallel, but it becomes quite tricky to maintain determinism without sacrificing a lot of performance; for example, atoms must be able to resolve conflicts such as two atoms trying to move into the same position.
I'm simplifying here.
Atoms are in 64x64 chunks for performance reasons, but in each chunk there's a rectangle covering all "active" atoms, and within that rectangle each row of atoms is updated left to right in one row, then right to left in the next row, then left to right, etc. And the next time, the orders are flipped.
Those two levels of alternation help reduce some visible artifacts.
There is actually a simple-ish approach which is to transfer the atom into a separate "particle simulation" until it approaches some other atom; this is what Noita does. But then the particle-atom can't interact with the atom simulation, so e.g. spraying fire (also a liquid, sort of) would prevent the fire atoms from changing color or turning into smoke after a while.
What if its destination is still occupied?
Well, there's no good answer, because the position the atom moved from is probably also occupied, so we likely can't put it back. So I search up and around using the raycast tree and just plonk the atom into the first available position.
It's not accurate, but it seems to work well enough.
This is actually an interesting side-effect of storing the velocity of atoms as two fixed-point 8-bit numbers! Fixed point numbers have a fixed increment between representable numbers and so at low speeds the drag (friction) applied from collisions (sliding) is too low to actually change the velocity of atoms.
Increasing the drag is the easy fix - I just haven't done it yet.