Fallen Sand: A World Where Every Pixel Is Simulated

I have been building a game called Fallen Sand. It is a post-apocalyptic shooter where the world is a falling-sand simulation: every pixel on screen is a cell with a material, and every cell follows rules. Sand piles. Water spreads. Methane pools under a ceiling until a spark finds it. Shoot a wall and the bullet carves what it can get through and chips what stops it. Blow out the floor under a building and the part that lost its support comes down.

This post is about the simulation itself: how the world is stored, how it updates fast enough, and the decisions that made the whole thing tractable for one person.

A cell is 64 bits

The world is a flat grid of cells. Each one packs into a single 64-bit value:

material:  u16   // index into the material table
flags:     u8    // updated-this-tick parity, part of a rigid body, burning, wet
color_var: u8    // per-pixel shade variation, baked when the cell is created
temp:      i8    // coarse temperature
life:      u8    // lifetime, health or charge, depending on the material
extra:     u16   // velocity bucket or rigid body id

Keeping cells as plain integers matters more than it looks. There is no object per grain, no allocation in the inner loop, and the rules could move to a compute shader later without being rewritten. Materials are data too. A table says whether something is a powder, a liquid, a gas or a solid, how dense it is, how far it spreads, whether it burns and what it burns into. Reactions between materials are rows in the same file.

Material(
  name: "gasoline", class: Liquid, density: 0.75, dispersion: 6,
  flammable: 0.9, burn_into: "fire", ignite_temp: 40,
)
Reaction(a: "methane", b: "spark", chance: 1.0, explode: 6)
Reaction(a: "water", b: "live_wire", chance: 1.0, a_into: "electrified_water")

Chunks, dirty rects and sleep

The grid is split into 64 by 64 chunks. Each chunk keeps a dirty rectangle, and only the cells inside it (plus a one-cell border) are visited on a tick. A chunk where nothing has moved for a while goes to sleep and costs nothing until a neighbour wakes it. In practice most of the world is asleep most of the time. A street with a fire on it is a few busy chunks and a lot of quiet ones.

Updating in parallel without racing

A falling grain writes into the cell below it, and that cell may belong to the next chunk down. If two threads update neighbouring chunks at the same time, they fight over it. The fix is a checkerboard. Chunks are split into four groups by whether their x and y are even or odd, and each group is updated as its own pass. No two chunks in the same pass are neighbours, so a chunk can write into its neighbours freely. Four passes a tick, each spread across all the cores.

Within a chunk the sweep goes bottom-up, so a grain lands before the one above it moves, and the left-to-right order alternates every tick so nothing drifts sideways over time. A parity bit on each cell stops it from moving twice in one tick.

Determinism on purpose

Every random decision in the simulation comes from a generator seeded on the tick and the chunk, never from a global one. A seeded world therefore steps the same on any machine. The tests lean on this: run a seed for a few hundred ticks and hash the grid. If the hash moves, something changed, and that catches more regressions than I expected. It is also what makes co-op possible at all, because two machines can run the same world and compare notes.

Why the simulation is on the CPU

I looked hard at putting the simulation on the GPU and decided against it for this game. The gameplay needs the world on the CPU. Collision, bullet hits, pathfinding and pulling collapsed structures out as rigid bodies all read cells, and reading the grid back from the GPU every frame adds latency. GPU cellular automata also have to stop two particles from racing into the same empty cell, which pushes you toward block-based update schemes that limit what the rules can express.

At a 480 by 270 internal resolution the CPU handles the sim with room to spare, so the GPU does what it is good at: drawing the grid, lighting, cosmetic particles, and the post-processing pass that gives the game its look (a palette LUT, grain, dither, a vignette). Fallen Sand 3D, the companion project, makes the opposite call, because 256 cubed cells is a different problem. That is a post of its own.

When concrete loses its support

Static solids need holding up. Anchored material like bedrock and a building's frame holds. A column stands on it. A slab is held by its walls, and a cantilever only so far. When a blast or a tunnel cuts a piece off from everything anchored, its cells are lifted out of the grid, turned into a rigid body in Box2D, allowed to fall and tumble, and stamped back into the grid when they settle.

That mechanic is the one that makes the others matter. There is no point carving a wall if the building above it does not notice.

Where it stands

The game runs on Windows at a fixed 60 Hz, with story, survival, creative and endless-wave modes, a daily challenge, and co-op over a hosted lobby. It is not released, and whether it goes to Steam is a decision for later. The product page has screenshots and the current feature list.