← All SNES demos

Marching Squares

Cellular Automata

How do you draw the outline of a blob that has no outline — just a field of values? You march: marching squares walks a grid over the field, and in each cell reads the four corners as a 4-bit case, looks up which edges the contour crosses, and interpolates where. The result is a clean iso-line traced around merging, splitting metaballs — here on a Super Nintendo, all integer, so it's bit-exact. Runs on its own; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

Self-running demo — blobs merge and split under a traced contour.

Source msquares.cmsquares.h in wbniv/llvm-mos-65816

What it is

For each cell of the grid, the four corners are thresholded against the iso value into a 4-bit case, a 16-entry table gives the edges the contour crosses, and each crossing is interpolated:

case = (tl>=iso)<<3 | (tr>=iso)<<2       // 4 corner signs
     | (br>=iso)<<1 | (bl>=iso);        // -> a 4-bit index
edges = MS_SEG[case];                   // which edges cross (16-case LUT)
t = (iso - va) / (vb - va);             // crossing point on each edge

Stitch those little segments together across the whole grid and you get the smooth iso-contour of the field — the yellow outline around the blobs. It's a case-table lookup plus a divide per crossing, identical across every codegen mode.

Compiler stress-test

ItemWhat it exercises
the 4-bit caseEach grid cell has four corners; each is either inside the shape or outside. Those four yes/no bits make a number 0..15 — the case. A 16-entry table then says, for that case, which of the cell's edges the contour line crosses.
edge interpolationA crossing is not snapped to the edge midpoint — it is placed by linear interpolation, t = (iso - a) / (b - a), so the contour is smooth. That divide, per crossing, is the heart of the inner loop.
contour extractionThe scalar field here is a sum of moving blobs; marching squares pulls out the single iso-line where the field equals a threshold. It is how contour maps, medical isosurfaces and metaball outlines are drawn.
integer, bit-exactCoordinates are 16-bit and the field and interpolation are 32-bit integers, so the extracted contour is identical on the host and the 65816 — the build gate folds the case indices and crossing points and asserts a match.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x86A7 — a fold of the marching-squares case indices and crossing points over two frames) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg.