I wanted water that runs into a basin and lies down flat, without computing any flow. Falling sand is the smallest solution I know: a grid where every cell holds sand, water, stone or nothing, and every cell only looks at its neighbours.
A tap is already running at the top left when the demo starts. The water hits a shelf, drops off its right end into a basin, and sand that fell onto the island in the basin now sits as a pile in the water. Hold the mouse to paint water, sand or stone, the eraser removes. The brush size is 1, 3 or 6, also on the mouse wheel. "Tap" turns the tap off, "Pause" freezes everything, "Clear" empties the grid, "Basin" rebuilds the start scene, and "Flow" sets how far water may slide sideways per step. Below the grid: cell counts and time per step.
Grid and texture
The grid is 240 by 104 cells, each 4 by 4 pixels. Every cell is one pixel of a single texture (SDL_PIXELFORMAT_RGBA32, SDL_UpdateTexture) that SDL scales up 4x with the nearest filter. Empty cells have alpha 0, so the page's grid shows through.
The simulation runs in fixed steps, 60 per second, with an accumulator. How that works is in Delta time and Fixed timestep, it is the same loop here.
One step and the order
Every particle may move exactly once per step. That is the easiest place to get lost:
++tick_;
for (int y = h_ - 1; y >= 0; --y) {
const bool leftToRight = ((tick_ + static_cast<std::uint32_t>(y)) & 1U) == 0;
for (int i = 0; i < w_; ++i) {
const int x = leftToRight ? i : w_ - 1 - i;
const Cell& c = cells_[index(x, y)];
if (c.movedAt == tick_) continue;
if (c.kind == Kind::Sand) {
stepSand(x, y);
} else if (c.kind == Kind::Water) {
stepWater(x, y);
}
}
}
The rows run from the bottom to the top. If you start at the top, you move a drop from row 5 to row 6, reach row 6 and move it on. By the end of the step it lies on the floor. Going bottom to top, a falling particle lands in a row that is already done. I reversed the loop and removed the stamp as an experiment: fallsOneRowPerStep fails right away.
The movedAt stamp covers sideways moves. There the particle stays in the row that is being scanned and could come up again further ahead. Whatever has moved carries the current tick and is skipped. The empty cell left behind gets no stamp. Otherwise it would block the particle directly above it, and a falling column could no longer follow in single file. aFallingColumnMovesAsOneTrain checks that with three water cells on top of each other.
Left and right
When sand falls diagonally, someone has to decide whether left or right is tried first. Always left first means every pile leans left. I flip a coin per cell and step, derived from a hash of position and tick:
int coin(int x, int y) const { return (detail::hash(x, y, tick_) & 1U) != 0 ? 1 : -1; }
On top of that the scan direction flips every row and every step. There is no random generator with state, so the world stays deterministic: two worlds with the same start are identical cell by cell after 500 steps (sameStartSameResult). The drift test drops 200 sand cells as a column at x = 49 to 52. Afterwards the pile has its centre of mass at 50.48 and spans columns 36 to 65.
Water runs further than one cell
Water falls, otherwise it falls diagonally, and when both are blocked it runs sideways. With one cell per step a heap of water takes painfully long to lie down. So a particle looks up to spread cells ahead:
int probe(int x, int y, int dir, bool& drop) const {
int target = x;
drop = false;
for (int i = 1; i <= spread; ++i) {
const int nx = x + dir * i;
if (!isEmpty(nx, y)) break;
target = nx;
if (isEmpty(nx, y + 1)) {
drop = true;
break;
}
}
return target;
}
It goes to the farthest free cell but stops where there is air below, so water runs over an edge instead of shooting past it. The test builds a basin 12 cells wide and stacks 24 water cells on the left. With range 4 the level is two cells high everywhere after 15 steps, with range 1 after 169. The "Flow" chip switches between 1, 4 and 8. At 8 the stream at the edge of the shelf looks ragged, 4 is my compromise.
If the cell count does not fill whole rows, the surplus wanders along the surface as single cells, a faint twitching in a pond.
Sand sinks
Sand swaps places with water, straight down and diagonally, so that a pile under water gets its slope:
bool sandCanEnter(int x, int y) const {
const Kind k = kind(x, y);
return k == Kind::Empty || (k == Kind::Water && cell(x, y).movedAt != tick_);
}
Water that has already moved in this step stays off limits, otherwise it would get its turn twice. The test puts a block of sand above a pond and checks after 400 steps that in every column all the water lies above the sand.
Nothing gets lost
The test that gives me the most peace of mind: a scattered world of stone, 400 water and 300 sand cells, 1000 steps, counted every 25.
const Counts before = w.counts();
for (int round = 0; round < 40; ++round) {
steps(w, 25); // 1000 steps in total
const Counts now = w.counts();
assert(now.water == before.water);
assert(now.sand == before.sand);
assert(now.wall == before.wall);
assert(now.empty == before.empty);
}
Everything moves by std::swap, so a particle can neither appear nor disappear. There is also an edge test: outside the grid every cell counts as stone (kind() returns Kind::Wall there), so the logic never checks bounds.
Colours
The colour variation belongs to the particle. Every cell gets a fixed random value (tint) when it is created, and it travels along when cells swap. If the variation depended on the position, flowing water would flicker. Water also gets darker with depth and the topmost cell under air gets lighter.
The step time is shown at the bottom right, in headless Chromium it was 180 to 250 microseconds with 4000 to 5400 water cells.
The code is in the repo under pixel-water. The project Game Dev Snippets collects all demos of the series.