Let Sleeping Atoms Lie | Slow Rush Studios

This week, liquids of different densities separate properly - so oil tends to float on water, rather than stay as globs floating in water.

The trick was in rewriting the atom sleep logic, which led to a bit of a performance optimization rollercoaster.

Also, you can cast three spells now, so let's have at it!

Mixing liquids

Before, if you threw oil and water together, you'd get a clump of oil:

Mixing oil and water would form a clump of oil.

It was caused by atoms "going to sleep". To allow the game to run fast enough, each time the game runs its atom simulation logic, each atom makes a "sleep decision" - one of:

wake its neighbors (if it moved next to new neighbors, set neighbors on fire, etc)
just stay awake itself (if it moved a tiny bit, it knows it didn't impact its neighbors, etc)
go to sleep (if it can't move, etc)

Sleeping atoms don't get simulated anymore, until they are woken again.

Now, density is implemented as the heavier atoms checking to see if they can displace lighter atoms when they move, so our heavier water atoms (who should be displacing the oil atoms) were surrounded by other atoms, and would go to sleep:

Here, awake atoms are painted red. You can see that some water atoms do displace oil, but they sleep too soon.

I might have been able to tune the sleep decision making, but it's very finicky already.

So instead I took a sledgehammer to the current approach of keeping track of which atoms are awake, and reimplemented it using "bounding rectangles":

Red rectangles illustrate which atoms are awake. Oil now floats on top properly!

This approach is - like 97% of the "game" so far - blatantly stolen from Noita:

Divide the world into 64x64 atom chunks.
Each chunk has a "woke rectangle" associated with it.
Simulate the atoms chunk by chunk.
If an atom decides that it (and/or its neighbors) needs to stay awake, you extend the bounding box to include it (and/or its neighbors).
An atom that moves into a new position always wakes neighbors around its old position (because the neighbors may want to move into that position).

The net effect is that when a water atom displaces an oil atom several atoms away, all the atoms between the old and new positions also get woken. That combats the "blobbing" effect.

Patching Performance

One way to implement the above would be to implement the 64x64 awake-tracking as a layer on top of the existing atom storage abstraction, so that it is only relevant for awake-tracking. That would have been smart.¹

Instead I rewrote everything to operate on a grid backed by 64x64 chunks of atoms, and that made the game run 3-10x slower²; there were 2 big culprits...

Repairing the (Now-Slow) Physics Bridge

The physics bridge was slowing things down because it was accessing every atom in the whole level each frame. it creates the colliders for the terrain, so moving bodies (and the player) wouldn't fall through the world (see Bridging Physics Worlds).

I applied the same optimization that Noita did: moving bodies aren't everywhere, so only generate colliders for 64x64 chunks³ where moving bodies currently are (or will be moving to).

Red squares aren't getting collider updates, green squares are. You can see the presence of a moving body (including a player) causes the colliders to be updated.

Blurring Grounding

Grounding is the process of calculating which atoms are "supported enough" to form part of the terrain. I came up with it for calculating colliders for the physics bridge (see Playing Nice with Moving Bodies for explanatory diagrams), but also for controlling when steam condenses (see Boil and Toil), and maybe other things in future.

Unfortunately, an atom was defined as grounded if the atoms directly-below and diagonally-below it are also grounded - which meant I couldn't (easily⁴) divide the world into chunks (or look at woke regions) for recalculating grounding, as the calculation would cross such boundaries.

So I changed the rules.

Now an atom is pseudo-grounded as soon as it goes to sleep (which is good enough for steam to condense), but an atom is only included in terrain collider generation by the physics bridge if enough atoms around it are also pseudo-grounded.

Even if the falling orange-circled atom can't move and gets marked asleep, it still won't be turned into a collider because (at least) the atoms below it won't be asleep. Whereas the red-circled atom is surrounded by sleeping atoms so it will form part of the collider.

Effectively, it's like running a blur filter over all the atoms based on how grounded they are, and feeding the output into the Marching Squares calculation (see Bridging Physics Worlds again) to find the polygons which end up being terrain colliders.

Marching squares output is thick red and pink. Colliders are thin red lines. You can see bodies collide with piles of atoms, can push atoms away and don't get crushed by atoms.

It's fast⁵ and works well in the three most important test cases - which I'll write down here for the next time I have to touch this fiddly area:

Atoms in a pile on the floor form colliders (except for the outermost ones⁶).
Atoms in the air falling down don't form colliders (so they can be knocked away by moving bodies)
Atoms stacking on⁷ moving bodies create colliders that don't intersect with colliders of moving bodies (so they don't crush the moving bodies or otherwise cause them to flip out)

The only thing that doesn't work well is that a moving body covered in atoms can't be dislodged easily. Clever suggestions to tackle that are welcome, but I'm still calling it a win. ⁸

Spellcasting

My plan is for spells to be based on the atom physics, so I added 3 spells to see if atom-based spells are actually any fun:

Acid Lob. Does what it says on the tin!

And Flamethrower:

Or at least, a liquid-spark-thrower. (It's a liquid with fire behavior attached.. a clever suggestion from my manager, aka wife.)

And Water Wave:

A little light on the 'wave' aspect perhaps, but a moving wall of atoms seems to work.

Let me know what you think! (in Discord or via email)

Playable web build‎

Cast yourself some spells:

Click to focus, then play with keyboard and mouse. No mobile support! Give feedback.

Keyboard spell-casting controls are:

Left-Shift for Flamethrower
E for Water Wave
Q for Acid Lob

Or if you've got a gamepad, just press some buttons - you'll figure it out.

You can also turn on the "Show collider chunk updates" and "Rigid Body Colliders" debug options to see the colliders being created as you move around or spawn moving bodies (though you'll see they're currently 32x32 rather than 64x64.. there's some web-build-specific memory issue that I haven't gotten to the bottom of yet, and it causes the game to crash instantly with 64x64 chunk sizes.)

I actually broke the atom storage up into 64x64 chunks because cloning the game world's state each simulation step (necessary for time traveling backwards for debugging... and maybe for online multiplayer in future) was taking a really long time on large levels (like, 100ms or more in debug mode). I hoped that by tracking which chunks hadn't changed, I could avoid cloning them. So I had a reason, but it wasn't a particularly good one. And no, I haven't checked yet whether that idea works.

Exactly why was performance ruined by adding the 64x64 atom chunks? For the programmers among you:

the old implementation indexed directly into an array of atoms (a multiplication and an addition - both fast operations).
The new implementation indexed into an array of chunks (so 2 divisions, which are slow, plus a multiplication and an addition) and indexed into an array of atoms (stored in the chunk, so another multiplication + addition).
I improved that a bit by indexing with unsigned integers and using Rust's const generics to tell the compiler that the chunks are always 64 by 64 (those two changes makes the first 2 divisions into left-shifts, which are faster) but it was still slower.

Why did I use 64x64 chunks again for rigid body collider generation? Mainly because I figured that I could use them to avoid more work: if we know that a chunk of atoms hasn't changed, then we can skip generating colliders for them. But I haven't implemented that yet because it's complicated by the bridge itself: the atoms that make up moving bodies themselves each cause chunks to be considered changed each simulation step. That makes such an optimization moot, unless I can think of a clever (& performant) way to ignore those atom placements.

⁴

Well, it's possible to make the grounding work with the 64x64 chunking, but you can't do it at the same time as simulating the atoms (the outcome relies on the simulation end-state of atoms you haven't simulated yet), so it's a headache. Specifically, the grounding calculation relies on looking left-down, middle-down and right-down, so you have to loop from bottom upwards. The woken rectangle for each chunk tells you what atoms to look at, but the rectangle won't start at the same height in each chunk. So it'd be doable, but fiddly.

⁶

The outermost atoms don't form colliders unless they're "always grounded", like Stone is. It looks a bit janky today but at some point I'll make the bodies and players get rendered after the atoms, and then it should look like the player/body just sunk into the sand a little.

⁵

I thought the blurring would be kinda slow, but blurring + Marching Squares is actually faster than the original already-fairly-optimized Marching Squares implementation so that was a win! I had optimized the Marching Squares implementation a bit, but it inherently needs to look at every atom four times - so the blur is sort of precomputing some values: it's saving some expensive atom lookups. Or in short, it's faster to read a bunch of booleans from a 64x64 fixed-size array than to read a boolean from a biggish data structure (the atom's state) from two levels of array-based indirection. Obvious in hindsight!

⁸

The new blur-based grounding is a bit less accurate, but it's also more straightforward, less surprising in gameplay because it's "local", it doesn't have to be done for all awake regions (only those where moving bodies exist), and (in future) easily parallelizable. So yeah, a win, I think.

⁷

And likewise it reasonably handles atoms sneaking into the middle of moving bodies. This happens because there are inherent inaccuracies associated with rotating pixelated sprites, and those cause moving bodies to have single-atom-sized holes in the atom grid. They're painful.