Diffusion-Limited Aggregation

April 2021

Diffusion-Limited Aggregation (DLA) is one of the first algorithms I ever implemented following Daniel Shiffman's 34th Coding Challenge. It's one of the first digital morphogenesis algorithm that became well known and toyed with by geeky fractal digital artists in the 90's as computers then had just enough power to start simulating Brownian Motion.

Though DLA is characteristic to chemistry, describing the diffusion and aggregation of zinc ions (Zn2+) onto electrodes in an electrolytic solution, it is also the basis of the Brownian Tree structure, a pattern omnipresent in nature, formed by clusters of randomly moving particles aggregating in one place. You've probably seen it before, in the way that lightning strikes tear through the sky, or in the ways that some corals grow in the reefs.

the diffusion-limited aggregation algorithm

A key element to this algorithm is the random walker, or walker for short, which, aside from being the word used to designate zombies in a terrible tv show adapted from a great comic is also the name given to randomly moving particles.

The system is initiated with Step 1 : Setup Walkers & Aggregation in a setup function. Step 2 : Random Walk and Step 3 : Stick are then repeated at every frame of the simulation (typically in a draw function). Here is an example where you can see the random walkers avidely aggregating towards the center in their lust for blood.

Waiting for the aggregation to form can be pretty uneventful sometimes. In the 90s it could take entire days for computers to generate large Brownian Trees, but today, using the right optimisations it's possible to get the intricate patterns formed by thousands if not millions of particles in real-time on an average computer. I sometimes use a custom Quad Tree data structure for this purpose exactly, though recently I have become very passionate about GPU coding as a means to parallelize large amounts of similar operations. In fact, all my blog post simulations involving particles use a GPU accelerated particle system made from scratch. Though if you want to avoid being as environmentally unconcerned as a bitcoin miner, a massive optimisation and power saver is to add a tiny towards aggregation force. To slightly encourage the particles to move towards the aggregation center. By choosing a low force coefficient you shouldn't loose to much of the original pattern.

That's it for today ! If at some point I finally crack GPU QuadTrees I'll make sure to upload a version with a million particles as the patterns start to get really interesting at that point. Ttyl :)