diffusion limited aggregation

some algorithms have an attraction. beyond the straightforward utility of providing a measurable solution to a highly defined problem, some of them are satisfying analogs of natural processes, or seem promising windows on the mechanics of reality. I’m not sure how to categorize them, but there’s also a class of algorithms that have a particularly visual satisfaction, that explain some process and provide an intuition, that intuition being not a new thing, but the alignment of something previously recognized, falling into place.

the original diffusion limited aggregation algorithm was described in Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon by T. A. Witten, Jr 1. in it, witten describes his approach:

Our model is a variant of the eden model whose initial state is a seed particle at the origin of a lattice. A second particle is added at some random site at large distance from the origin. This particle walks randomly until it visits a site adjacent to the seed. Then the walking particle becomes part of the cluster. Another particle is now introduced at a random distant point, and it walks randomly until it joins the cluster, and so forth. If a particle touches the boundaries of the lattice in its random walk it is removed and another introduced. A similar process was studied by Rosenstock and Marquardt. The exposed ends of our clusters tend to grow more rapidly than other perimeter sites because perimeter sites near the center are “shadowed”; our aggregates should be less compact than the Eden clusters.

Fig. 1 from Witten ‘80

Fig. 1 from Witten ‘80

given the original author’s verbal description of the algorithm and his illustration, I’ll show what I did.

first, the code and some example images can be found at the github repo here. I wrote this code about seven years ago. if I were doing it again, I’d make some different decisions. specifically I’d use go instead of python and work out some parallelization, and allow for animated gifs to show the development of the output over time. much like the 100 books concept, I often return to algorithm implementations over time and redo them in new languages, in new paradigms.

DLA output 1

DLA output 1

experimenting with the program, adding mutliple initial seeds results in multiple structures that grow together over time.

DLA with 5 seeds

DLA with 5 seeds

and if you start with a line of seeds at the bottom, you get this highly directional growth.

line of seeds across the bottom

line of seeds across the bottom

I was aware of the diffusion limited aggregation algorithm for a while, but was ultimately motivated to implement it and tinker with it when after a winter road trip, I noticed these patterns of precipitated salt on the side of my car. the “DLA with 5 seeds” is what ultimately explains the connection. I believe a similar process to that of the DLA was at work as salty water splashed onto the side of my car and dried out due to air rushing by at highway speeds. as the water dried, the salt precipitated out in the DLA pattern.

dried salt on the side of my car

dried salt on the side of my car

this is one of most enjoyable parts of computing, complexity, and nature. when they all overlap in some meaningful way, it feels like the jolt of enjoyment at learning something new, or having realization that two previously unrelated things are in fact related.


  1. Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon by T. A. Witten, Jr ↩︎