Diffusion-Limited Aggregation Simulator

Put one particle in the middle of an empty grid. Release a second one far away and let it wander, a step at a time, with no sense of direction at all. When it bumps into the first, it stops for good. Release another.

That is the whole of diffusion-limited aggregation. Nothing in the rule mentions branches, yet after a few thousand arrivals the pile is not a blob. It is a spray of thin arms that fork and fork again, with deep empty bays between them, somewhat like frost on a window pane.

A model from 1981

Thomas Witten and Leonard Sander published the model in Physical Review Letters in 1981. Their abstract describes a computer simulation of random aggregates, applicable to a metal-particle aggregation process whose correlations had already been measured. In the simulated clusters the density correlations fell off with distance as a fractional power law, as they did in the metal aggregates, and the radius of gyration followed a power law too. They added that the model is a limit of a model of dendritic growth.

The idea applies wherever diffusion is the main way material reaches a growing surface. What makes it diffusion-limited is patience. The walkers must be so few that each finishes its journey alone, so that the only thing shaping the cluster is where a random walk happens to land.

The pictures escaped physics quickly. The clusters came to be called Brownian trees, and for a while in the 1990s growing them was a form of computer art, at a time when a home computer needed hours or even days for a small one. Tens of thousands of particles now take seconds.

Why the tips win

The branching comes from a plain unfairness. A walker arriving from outside meets the outermost parts of the cluster first. To reach the bottom of a bay it would have to drift down a narrow channel without once brushing either wall, and a random walk is poor at that. So a wandering particle is more likely to stick to a protrusion than to a depression.

Growth then feeds itself. A bump that catches more walkers becomes a longer bump, which catches more still and soon sprouts bumps of its own.

The bays are never filled in afterwards, because the arms that made them keep screening them. A ring seed shows this bluntly. Start the tool from a ring and every walker, launched from outside, sticks to the outer face. The inside of the ring stays empty however long the run lasts.

The other dials change the texture, not the principle. Contact can count the four cells that share an edge or all eight around a cell. A sticking probability below one lets a walker carry on after touching, so it may settle somewhere else. Change one, keep the seed number, and compare the two clusters side by side.

What a dimension of 1.71 means

The word fractal dimension was brought to the fore by Benoit Mandelbrot, building on a 1967 paper about self-similarity in which he cited Lewis Fry Richardson’s odd finding that the measured length of a coastline depends on the length of the measuring stick. A fractal dimension is the exponent that records how fast detail piles up as the ruler shrinks.

For a cluster, two rulers are in common use. The first sets mass against radius. The radius of gyration is the root mean square distance of the particles from their centre of mass. If a cluster of M particles has radius R, and R grows as M raised to a power beta, then M grows as R raised to the power D, with D equal to one over beta. A filled disc would give 2. A straight line would give 1.

The second ruler is box counting. Lay a grid over the picture and count the boxes that contain any part of it. Make the boxes smaller and count again. The dimension is the rate at which the logarithm of the count rises against the logarithm of one over the box size.

For walkers that move freely in the plane, tied to no grid, simulations put the dimension at about 1.71. Anton Menshutin and Lev Shchur, who grew a hundred clusters of 50 million particles each, quote 1.71 plus or minus 0.01 as the accepted estimate, and they add a warning that matters to anyone with one picture on a screen: the fractal dimension is a weakly self-averaging quantity. A single cluster, however large, does not pin it down.

The grid leaves fingerprints

Put the walkers on a square grid and the story changes slowly. Yen Lee Loh’s summary of the literature records that early papers found much the same exponent on and off the lattice, and that later ones saw square-lattice clusters start roughly circular and turn into diamonds and then crosses. Small round clusters show a radius-of-gyration exponent of 0.585, which is one over 1.71. As the arms lengthen it creeps toward two thirds, a dimension of 3/2. That ceiling is one of the few proved facts in the subject: Harry Kesten showed in 1987 that the arms can grow no faster than the two-thirds power of the mass.

Denis Grebenkov and Dmitry Beliaev grew square-lattice clusters of up to a hundred million particles and watched growth run fastest along the axes. Clusters of ten thousand particles or fewer were still almost round. Their explanation is that a lattice offers very few places where a particle can attach near a tip. Over a hundred clusters they measured a box-counting dimension of 1.666 plus or minus 0.004.

Nobody has watched the drift finish. Menshutin and Shchur estimate that reaching 3/2 would take a cluster of at least a hundred billion particles.

Even the standard recipe has soft spots, and Loh lists them. Walkers are launched from a circle a few cells outside the cluster, at an angle snapped to the nearest grid point, and thrown away if they stray beyond a larger circle. Snapping distorts the launch. Throwing a walker away and starting a fresh one at a random angle ignores the fact that a real stray would more often return on the near side. Loh’s own algorithm pushes both errors below one part in a trillion.

The tool on this page runs the standard recipe and says so. Its one shortcut, a jump to the rim of an empty square, uses the exact rule for where a grid walk first reaches that rim, so it changes the speed and not the odds.

A run you can repeat, and what it cannot tell you

The tool opens on a worked example: a point seed, contact on four sides, sticking at 100 percent, seed number 2026, a grid of 1,024 cells a side, 20,000 particles. To place them it launched 24,592 walkers, and 4,592 of those strayed past the kill circle and were discarded. The cluster reaches 303.4 cells from the centre. A straight line fitted to the logarithm of radius against the logarithm of mass, over 62 points from 101 to 20,001 cells, gives a mass-radius estimate of 1.74.

Now press the button that repeats the run with ten other seed numbers. The ten estimates average 1.70 with a standard deviation of 0.05, and they range from 1.64 to 1.82. That spread is the honest size of the answer, which is why the page prints two decimals and no more. Box counting on the same cluster gives 1.63, and 1.61 plus or minus 0.02 across the ten. It reads lower because the cluster is small. Boxes under 8 cells are left out of the fit, since branches one or two cells wide follow the grid and not the fractal.

Does anything real grow this way? In 1984 Mitsugu Matsushita and colleagues grew flat zinc leaves by electrodeposition, digitised the photographs and measured a dimension of 1.66 plus or minus 0.03, in line with the model. In the same year Brady and Ball reported fractal growth of copper electrodeposits in Nature.

Sparks qualify too. Niemeyer, Pietronero and Wiesmann showed in 1984 that the simplest nontrivial stochastic model of dielectric breakdown leads naturally to fractal discharge patterns, and compared planar discharges with experiment. Their model joins the aggregation rule to an electric field and accounts for the branching Lichtenberg figures left by a discharge. In rock, water rich in manganese and iron seeps along fractures and deposits fern-like dendrites so lifelike that they are often mistaken for fossils. Mineral deposits appear on the usual list of places where the process can be seen.

What can the tool not do? It cannot hand you the dimension of diffusion-limited aggregation. It gives two estimates for one finite cluster, with the fit window drawn on the chart and the spread across seeds beside the number. It works on a square grid in two dimensions, with a cap of 2,048 cells a side, so it sees only the early, nearly round stage of a shape that goes on changing for longer than any computer has followed. And it keeps the standard launch and kill circles, with the two small biases that come with them.

That is a fair picture of the subject itself. The rule fits in a sentence, the pattern appears almost at once, and a number as plain as its dimension still has to be measured with care, hedged with a spread, and reported together with the grid it was grown on.