How my sand sim works

After playing Noita, it reminded me of messing around with similar online sand toys when I was younger. They were so simple but complex at the same time. The Powder Toy is probably the most well known one. It made me want to try and build my own.

For those that don't know what they are, these sand simulations are a form of cellular automata. A grid of cells, updating each tick according to a set of rules based on whatever material it contains, and what the surrounding cells contain.

A grain of sand does the first of these that it can:

1. Move straight down.
2. Move diagonally down. It picks left or right at random and tries that side first.
3. Stay where it is.

Sand moves into empty cells first. If there are none, it can swap places with water, allowing it to sink.

Water follows the same rules but it can also move sideways. If it can't move down, it checks up to 7 cells to one side and moves to the furthest empty one. If that side is blocked, it tries the other.

The emergent behaviours from these rules allow for pools of water and piles of sand to form. Right now, there are 16 materials, most with variations of these rules.

Starting in Typescript

The first version of this was written in Typescript, with just sand, water and oil. It ran in a web worker, drew to an OffscreenCanvas and kept two copies of the grid, one for the current tick and one for the next. It worked, and performance was fine on a 200×150 grid, but it wasn’t going to scale with the materials and ideas I had in mind, I needed something else.

I explored other options, and came across WASM, compiled from Rust. It gave me a chance to learn a new language, and offered better performance as things got bigger, so I went for it.

The grid

The grid is one flat array. The default size is 480x270, but sliders in the UI can change that. Each cell is 6 bytes:

#[repr(C)]
pub struct Cell {
    pub material: Material,
    pub ra: u8,      // random value, set at creation, used for colour variation
    pub rb: u8,      // spare register, e.g. how long fire has burned
    pub clock: u8,   // tick stamp, used to skip cells
    pub vx: i8,      // sideways velocity
    pub vy: i8,      // vertical velocity
}

ra and rb are used for a few different things. ra is a random value set when the cell is created, and never changes. It shift's the colour of the cell a bit for some variation, and can also affect how long smoke, steam and embers last. rb starts at 0 and the rules can modify it. Fire, smoke, steam and embers use it to count their age.

The first Rust version kept two copies of the grid, like the Typescript one. Cells read from one and wrote to the other, so every cell had to be written each tick, even if it didn't move. Each move also had to check the second copy, in case another cell had already taken that spot. With one copy, a cell only writes when something changes, and every rule sees the grid as it is right now. clock marks the cells that were just written, so the loop can skip them.

The order cells are visited in also matters, because each cell sees the moves made before it. My first version scanned in one fixed direction and always tried down-left first, which caused ugly artefacts with falling sand.

Alternating the scan direction and the side it tried first fixed that, but with one grid copy, sand still leaned to one side and could leave a sheer wall. Cells are now visited in a random order, using a Fisher-Yates shuffle.

Velocity

Cells used to have no inherent speed, so nothing could accelerate. The addition of vx and vy changed that, and took the cell from 4 bytes to 6.

Each tick, apply_gravity adds the material's gravity to vy, up to a limit (10 for sand, 8 for water and 4 for lava). resolve_velocity then moves the cell along its velocity, one cell at a time, until it runs out of velocity or hits something. If it's blocked on an axis, its velocity on that axis goes to 0. Sideways velocity fades with drag in the air and friction on a surface.

Lava and acid are thick, so they build up speed every tick but only move on about 1 tick in 3.

The extra 2 bytes don't really impact performance. The extra work was the expensive part. Every sand cell ran both functions each tick, even in a settled pile.

On a full grid a step went from about 13ms to about 22ms, which is past the 16.7ms a step has at 60 steps a second, and the frame rate dropped to 4fps. Adding chunks fixed that, I'm working on another article discussing that further.

Materials

Each material’s values live in one array, PROPS, with its colour, colour variation, glow and physics values. There are 17 entries: the 16 materials plus "empty". This is sand:

// sand
MaterialProps {
    group: Group::Powder,
    colour: [210, 185, 110, 255],
    colour_variation: [5, 7, 12],
    glow: [0, 0, 0, 0],
    gravity: 1,
    terminal_velocity: 10,
    slide_acceleration: 1,
    air_drag: 0.95,
    base_friction: 0.85,
    surface_slipperiness: 0.82,
},

These values used to be separate match blocks on the material: one for colour, one for colour variation and one for glow. The array keeps a material's look and physics in one place, and it's what the velocity code reads.

Behaviour lives in update functions. Most materials have one, and a single match picks which to run:

pub fn update_cell(cell: Cell, api: SimAPI) {
    match cell.material {
        Material::Sand | Material::Ash => powders::update_sand(cell, api),
        Material::Water => liquids::update_water(cell, api),
        Material::Lava => liquids::update_lava(cell, api),
        Material::Acid => liquids::update_acid(cell, api),
        // ...
        _ => {} // Wall, Wood, Obsidian, Empty: nothing to do
    }
}

The update functions don't touch the grid directly. They get a small API that works in relative positions. api.get(0, 1) is the cell below. api.try_move(1, 1, cell) tries to move diagonally down-right if the spot is empty. Anything outside the grid reads as wall, so the rules don't need bounds checks. This keeps the rules short. Here's lava meeting water:

for (dx, dy) in [(0, -1), (-1, 0), (1, 0), (0, 1)] {
    if api.get(dx, dy).material == Material::Water {
        let ra = api.rand_u32() as u8;
        api.set(dx, dy, Cell { material: Material::Steam, ra, rb: 0, clock: 0, vx: 0, vy: 0 });
        // ...more steam in the empty cells around it
        let ra2 = api.rand_u32() as u8;
        api.set(0, 0, Cell { material: Material::Obsidian, ra: ra2, rb: 0, clock: 0, vx: 0, vy: 0 });
        return;
    }
}

Most reactions are a few lines like this:

• Acid has a list of what it can eat and how quickly.
• Fire has a lifespan and a chance to leave ash behind.
• Ice slowly freezes water next to it.
• Steam condenses into water after a while.
• Lava is more viscous than other liquids so it has a chance to not move each tick.
• etc..

Heat

Heat isn't stored in the cells. It has its own grid, with one byte per cell, so heat runs from 0 to 255. Every tick, lava sets its cell to 254, fire to 230 and embers to 180. Then each cell's heat becomes the average of itself and its four direct neighbours, so heat spreads outward and drops quickly. This step does use a second buffer, because each new value has to be worked out from the old ones.

Materials read the heat at their own position. Water above 45 has a chance each tick to boil into steam. Ice above 30 can melt into water. Stone above 55 can, very rarely, melt into lava. This lets a reaction happen at a distance: water can boil near lava without touching it.

Skipping settled cells

Every cell used to be visited every tick, even in a settled pile. Now the grid is split into 16×16 chunks, which is 510 at 480×270, and only awake chunks get updated. When a cell is written, it wakes its own chunk, and the chunk next to it if the cell is on an edge. A chunk where nothing is written goes to sleep.

Every write now does a bit more work, but the real cost is that rules have to be careful. A cell can be busy without writing anything, and if nothing is written, its chunk sleeps with the cell stuck inside. Acid waiting on a random chance to dissolve its neighbour writes nothing until it hits, so it has to call keep_awake. The loop also wakes the chunk whenever it skips a cell. My first attempt missed both, which left sand frozen in mid-air and acid frozen inside a sand pile.

Displaying the grid

Rust writes RGBA values into a pixel buffer, and fills a second buffer for glow. The heat grid is a third buffer. All three live inside the WASM module's memory. Every pixel used to be rewritten after every step. Now only the chunks that changed are rewritten, at the cost of one more set of flags to keep.

wasm-bindgen connects the two sides. Marking Simulation with #[wasm_bindgen] makes wasm-pack generate a JavaScript wrapper, so you can call sim.step(4). That's fine for function calls, but going through it for every pixel would be slow, so the pixels skip it.

JavaScript can see WASM memory directly. Rust provides a pointer and a length, and JavaScript wraps them in a typed array, so nothing has to be copied out of WASM first:

const pixels = new Uint8Array(buffer, sim.pixels_ptr(), sim.pixels_len());

In the browser

Drawing the grid used to use Canvas2D, put the pixels on an offscreen canvas, scale it up, and draw the glow over the top with a blur filter. That was much less code but was limited. It's now WebGL2, in a renderer of about 340 lines, with its own shaders and textures to set up.

In exchange, the scaling, blur and heat colours all run on the GPU. The glow is blurred in two passes, across and then down, and added on top. Tool previews have their own canvas over the top.

There are five tools for drawing: brush, line, rectangle, fill and replace.

The brush passes the pointer position to paint_circle in Rust, and repeats every 16ms while the pointer is held down.

React draws the controls. It mounts the canvas and leaves drawing to the animation loop, which uses a requestAnimationFrame callback inside a hook. Anything the loop needs, such as pause state and speed, goes through refs so changes don't trigger re-renders. Material counts and frame rate update React state every 30 frames, which is about twice a second on a 60Hz screen.

The simulation steps at a fixed rate of 60 times a second. Each frame works out how much real time has passed and runs as many steps as it owes, up to 200ms worth, which is 12 steps. That keeps the speed consistent whether you're on a 60Hz screen or a 144Hz one. Each step runs a number of ticks set by the speed slider, 4 by default.

Final thoughts

This was a really fun project to work on, and there are still many things that could be added. Similar projects like The Powder Toy and Sandspiel offer some cool features, like saving, sharing scenarios, uploading images to be displayed as materials, and a huge range of new material ideas. It's a project I can chip away at every now and then, and offers a lot of learning opportunities. Those are often the best kind of projects.

If you haven't already, be sure to check it out at sandsim.jamesmddoyle.com.

Thanks for taking the time to read!