Diffusion-Limited Aggregation

DEFINITION

release a random walker; when it touches
the cluster, it sticks there permanently

NOTES

Particles wander at random until they bump into a growing cluster, then freeze. Because the outer tips intercept walkers before they can reach the interior, the result is always branched and never solid. This is the shape of electrodeposition, dielectric breakdown, mineral dendrites and lightning.

PROVENANCE

Origin

T. A. Witten & L. M. Sander, Phys. Rev. Lett. 47, 1981

Standing

Public domain — a growth process

Constants

Sticking probability below 1 thickens the branches

Source

doi:10.1103/PhysRevLett.47.1400

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 27 · DIFFUSION-LIMITED AGGREGATION — Thomas Witten & Leonard Sander, 1981
//   release a random walker; when it touches
//   the cluster, it sticks there permanently
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=dla

float p_grid  = 170 + chf('grid_tweak');      // grid resolution · live 80 .. 260
float p_stick = 1 + chf('stick_tweak');       // sticking probability · live 0.05 .. 1

// The plate's own colour: FORMA's AUTOMATA accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.3301 + 0.3588 * cos(6.28318530718 * (t + 0)),
    0.2255 + 0.2451 * cos(6.28318530718 * (t + 0.05)),
    0.46 + 0.5 * cos(6.28318530718 * (t + 0.1)));
}

// Witten & Sander's cluster, grown to saturation in one cook. Walkers are
// released one at a time from a ring just outside the cluster's radius,
// random-step until they touch an occupied neighbourhood, and stick there
// with the published probability — the plate's own spawn ring, escape test
// and sticking draw, run to the same finish line: 7.5% of the lattice, or
// the wall. The plate grows 130 walkers a frame and holds the saturated
// cluster before dissolving it; the cook is that held cluster. One point
// per stuck particle, coloured by arrival order through the plate's own
// mapping. The live plate paints its newest sixty in HILITE — a growth
// cursor, not part of the finished cluster, so it is not ported.
// Deterministic: every draw is random(counted seed) on the plate's own
// first-era seed, so every cook is the same cluster.
int n = int(rint(p_grid));
int half = n / 2;
int full = int(n * n * 0.075);
int rc = 8;                      // seeded(7 + era) at era 1 — the plate's opening cluster

int g[];
resize(g, n * n);
g[half * n + half] = 1;
int count = 1;
float r = 3.0;

// Walkers until the cluster is grown; hard-bounded so no tweak can hang the
// cook. The bound is never the finish line — measured at the defaults the
// loop ends on the plate's own conditions after ~3,000 walkers, and it is
// the wall that ends it, not the count: the spawn ring rides at r + 2, so
// the early cluster sticks nearly every walker and r ratchets outward
// ~2 cells per record stick, reaching half − 3 long before 7.5% of the
// lattice is filled. The plate finishes the same way — verified against
// its own draw() run headless: count 878, r 84.8, on the wall — so the
// ~1,100-point cluster this cook emits is the cluster the plate holds.
int guard = full * 40;
for (int w = 0; w < guard; w++){
    if (count >= full || r >= half - 3) break;
    float a = random(rc) * M_PI * 2.0;  rc++;
    float spawnR = min(r + 2.0, half - 2.0);   // the ring has to be inside the grid
    int x = int(rint(half + cos(a) * spawnR));
    int y = int(rint(half + sin(a) * spawnR));
    for (int step = 0; step < 2200; step++){
        x += int(random(rc) * 3) - 1;  rc++;
        y += int(random(rc) * 3) - 1;  rc++;
        float d = sqrt(float((x - half) * (x - half) + (y - half) * (y - half)));
        // too far out, or off the lattice: this walker is spent
        if (d > r * 2.0 + 6.0 || x < 1 || y < 1 || x >= n - 1 || y >= n - 1) break;
        int hit = 0;
        for (int dy = -1; dy <= 1 && !hit; dy++)
            for (int dx = -1; dx <= 1; dx++)
                if (g[(y + dy) * n + (x + dx)]){ hit = 1;  break; }
        if (hit){
            float sd = random(rc);  rc++;
            // a refused stick keeps walking, exactly as the plate's does
            if (sd < p_stick){
                g[y * n + x] = count;          // arrival order, before the increment
                count++;
                r = max(r, d + 2.0);
                break;
            }
        }
    }
}

// the cluster as points: canvas y runs down, so it is negated about centre
for (int y = 0; y < n; y++){
    for (int x = 0; x < n; x++){
        int v = g[y * n + x];
        if (!v) continue;
        int pt = addpoint(0, set(float(x - half), float(half - y), 0.0));
        setpointattrib(0, "Cd", pt, forma_ramp(float(v) / count * 0.55 + 0.1));
    }
}