Simulating 2D diffusion-limited aggregation (DLA) with JavaScript

Jason Webb
17 min readApr 14, 2019

Nature uses all sorts of interesting, often simple processes to generate amazing shapes, patterns, and forms across every scale that never cease to surprise and inspire the keen observer. From the microscopic to the cosmic, matter is arranged, augmented, and transformed using a variety of logical, observable processes, often superimposed upon each other in complex ways.

In this article we will deal with one such process known as diffusion-limited aggregation, or DLA, that produces fractal branching structures using random motion and “sticky” particles (more on that later). Evidence of this process can be found at multiple scales in nature in both organic and inorganic systems, for example:

Left: “A DLA cluster grown from a copper sulfate solution in an electrodeposition cell” via Wikipedia; Right: “Fumed silica with surface area of 130 m2/g” via Wikipedia article on fumed silica.
Left — buildup of metal dust from chop saw via Reddit; Right — “Lichtenberg figure in block of Plexiglas” by Bert Hickman via Wikipedia.
Left — example of window frost via Guide to Frost on Dr. Kenneth Libbrecht’s SnowCrystals.com; Right — sample of manganese oxide dendrites on a limestone bedding plane from Solnhofen, Germany by Mark Wilson via Wikipedia

What is diffusion-limited aggregation?

First described by Thomas Witten and Leonard Sander in their seminal 1981 article Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon, diffusion-limited aggregation is a process in which particles of matter stick together (aggregate) as they chaotically move (diffuse) through a medium that provides some sort of resistive (limiting) force. As these particles clump together over time they form characteristic fractal branching structures known as Brownian trees.

As an illustration, imagine that you have a number of tennis balls covered in a special, magical glue that will only bond to itself such that these tennis balls will get rigidly stuck together when they come in contact with each other, but not when they touch the ground, walls, or other objects. Place a single tennis ball on the floor of a small room (like a closet) and begin randomly tossing other tennis balls in, not aiming at anything in particular.

Eventually some of these tennis balls will come into contact with either the initial ball or other the balls that have thrown in and begin to form rigid clusters. As more balls are thrown in these clusters grow and grow to create complex, bush-like structures.

Now imagine repeating this experiment in a much larger building, like an industrial warehouse, and tossing in thousands upon thousands of sticky tennis balls everywhere. Over time you would see large clusters of tennis balls take shape, not unlike the images shown above!

Dan Shiffman also has a great, more visual explanation of the process here:

In nature these sticky tennis balls / random walkers could be ionized atoms, polarized molecules, charged particulates, or any number of other bits of matter that have a tendency to stick together. So long as these particles move in chaotic (or semi-chaotic) ways and have an affinity for sticking together, recognizable fractal branching structures will emerge due to the diffusion-limited aggregation process!

Technical implementation notes

To implement this process with code we need to first identify the key objects and forces that we want to model. Based on the description above it would be logical to have some sort of data structure that represents a particle (tennis ball) in such a way makes it easy for us to move it around the screen and to detect when it has collided with other particles so they can be “stuck” together. And since we’re going to be dealing with lots of particles, we’re going to need a good way to keep track of all of them efficiently.

When particles are moving around freely, they are called walkers. When they get stuck together, they are collectively called clusters.

Particle systems, spatial indexing, and collision detection

The most brute-force way to do this would be with an simple array of “particle” objects that we constantly loop through, apply forces to, and check against every other particle for collisions. However, this method comes with some major performance hits as the scale of the simulation grows because of the increasing cost of unnecessary calculations as the size of clusters grows.

It would be better to use some sort of data structure or package that can keep track of all the particles for us and enable us to efficiently locate nearby particles and check for collisions. There are a bunch of “kitchen sink” packages out there that could help us do some or all of these things (D3.js, Matter.js, Toxiclibs.js, and more) but I felt like they were all much more complicated than what was really needed here.

In doing a little searching I came across a very nice, robust, and lightweight package simply called collisions that keeps track of particles using an internal spatial index and provides super efficient collision detection based on the shape of the particles.

Motion

To breathe some life into the system we also need to think about the motion of these particles and the forces at play to produce those motions. The classical approach that most people go with involves moving each “non-stuck” particle by a small random amount each cycle to produce what is formally known as Brownian motion. Something as simple as particle.x|y += Math.random(-1,1) could do the trick.

At the molecular scale this is similar to thermal vibrations related to the temperature of the system — the higher the temperature, the faster the particles jiggle. At different scales this motion might be the result of many superimposed forces interacting with each other — wind, pressure, surface tension, gravity, electromagnetism, and so on.

This motion need not be completely chaotic; in fact, combining Brownian motion with either directional and rotational forces can produce some really interesting effects, which we will explore later in this article.

Grids — to use or not to use?

The original implementation of DLA described by T. A. Witten and L. M. Sander in 1981 involved associating particles with individual pixels on the screen, which means the whole process would take place on a uniform grid of squares. At the time this was perfectly logical because it built upon prior research in the fields of mathematics and physics, particularly the Eden growth model introduced by Murray Eden in 1961. Other relevant topics include cellular automata, the lattice model, crystallography / crystal structure / crystal growth, and matrix theory.

Interestingly, this grid-based approach greatly simplified collision detection and eliminated the need for a spatial index or particle system altogether because every pixel / particle could be checked for collisions simply by examining the state of it’s 8 immediate neighbor pixels. In fact, this approach is so efficient that even today it is among the fastest techniques available!

While one could certainly replicate this implementation today and realize the same performance benefits, it does involve some trade-offs. Firstly, although our screens today are significantly higher in pixel density than they were in 1981, they do still have a finite number of pixels to work with, so the simulation will be limited to a certain scale. Secondly, this approach would always produce images with that characteristic, inherently raster (blocky) aesthetic because of the uniform grid-aligned pixels it is based on.

The first of these trade-offs may be compensated for by moving to a virtual grid rather than using literal screen pixels. One could make a grid of arbitrary, even dynamic, size that can panned, zoomed, and rotated independently of the screen dimensions, not unlike Google Maps. I’d love to see someone give that a go and share their results!

The second trade-off is harder to get around though. I wanted to see what the DLA process could produce with non-uniform and non-square particle shapes, so it seemed to me that no matter what, I would need to decouple the particles from the grid structure in order to open up more possibilities for experimentation. Doing so, however, would necessitate the use of tools like spatial indexing and more complex collision detection that would come with unavoidable impacts to performance. For me this trade-off between performance and aesthetic flexibility was worth it though, at least for this series of exploratory experiments. Besides, if I find a particular effect that I like I can always refactor my code to optimize for that effect later!

Project setup

Enough with the theory — let’s build something!

At the heart of my implementation I am using p5.js for it’s helpful <canvas>-based drawing functions along with ES6-flavored JavaScript transpiled to ES5 for current-gen browsers using Webpack and NPM scripts. See the webpack.config.js and package.json files for more.

Over the course of building out my implementation I ended up using the following packages, all available via NPM:

  • collisions for robust, lightweight collision detection without the use of a full physics package. Includes an internal bounding volume hierarchy (BVH) for spatial indexing.
  • svg-pathdata for parsing path information from SVG files in order to create custom shapes.
  • svg-points for generating the d attribute of SVG <path> elements for exporting vector drawings.
  • file-saver for initiating a download of exported SVG fles to the user’s machine.

Since I knew I wanted to build out multiple experiments on this topic, I chose to decouple my DLA-related code from each of the individual p5.js sketches so that each sketch only really has to manage the configuration and flow of the DLA process as though it were a third-party package. I did this by creating a ./core folder with the following modules:

  • DLA.js — manages and runs the simulation itself. Call the iterate() function to move forward one cycle, and draw() to draw all the particles to the screen. A whole bunch of other functions are also exposed to allow for all sorts of fun configurations!
  • Defaults.js — an object containing configuration parameters that can be overridden by individual sketches.

JSDoc-based technical documentation of these modules and their functions can be found here.

I wonder if this might be a cool thing to turn into an NPM package 🤔. Let me know if this is something you would be interested in!

All of the source code for my experiments can be found on Github here:

And you can play with all of these experiments in your browser here:

Global key commands

The following key commands are available in every sketch — use them anytime you want!

  • Space — pause/unpause the simulation
  • w — toggle visibility of walker particles
  • c — toggle visibility of clustered particles
  • r — reset simulation with current settings
  • f — toggle the use of the “frame”
  • l — toggle line rendering effect
  • e — export an SVG file of what is currently on the screen
  • 19 — cycle through variations, if available

Experiment 01 — basic DLA

Right off the bat, let’s build out a sketch using the simplest possible configuration — a set of randomly-arranged “seed” particles and a set of randomly-arranged, randomly-moving walker particles, all with uniform size and shape.

In my implementation we only need to use the out-of-the-box default functionality of the DLA.js module along with the default walker and cluster creation functions (createDefaultWalkers() and createDefaultClusters() respectively).

Experiment 02 — directional bias

Next let’s introduce some sort of additional movement force (called a “bias”) to the walker particles to get them to accumulate in interesting, semi-predictable ways.

This bias force can be added to the particle’s movement on top of the typical Brownian motion so that it still has that characteristic “random” behavior while drifting in some particular direction. The force can be applied along just the horizontal or vertical axis (or both), or even according to a custom-defined formula (skip to experiment 07 to see that in action).

In my implementation, a directional movement bias can be added by setting the value of the global BiasTowards parameter (either in Defaults.js or a local Settings.js file) to a string describing the direction of movement you want particles to move in. Valid string values for BiasTowards are 'Left', 'Right', 'Up', 'Down', 'Center', 'Edges', 'Equator', and 'Meridian'.

To give the particles something to actually hit and accumulate onto I also create “walls” of clustered particles by passing in the string 'Wall' when spawning new clusters using createDefaultClusters(). When that parameter is set, a line of clustered particles will be created on the wall(s) opposite whatever direction is set in BiasTowards. For example, if BiasTowards is 'Left', then createDefaultClusters('Wall') will create a line of cluster particles along the right wall.

Left: particles drift towards bottom; Right: particles drift towards center (X only)
Left — particles spawn in center with movement biased away from center; Right — particles spawn at edges with movement bias towards center

Experiment 03 — different sizes

Next let’s see what happens when we vary the sizes of the walker particles. Would the branching structure look any different, or even form at all?

In this experiment I worked out two interesting ways to vary the walker particle sizes — proportional to the distance from center, and randomly within a range.

To enable these effects in my code, set either VaryDiameterByDistance or VaryDiameterRandomly to true. For both of these effects to work properly you’ll also need to provide the upper and lower limits for particle diameters by providing an array of two values [lower, upper] to the parameter CircleDiameterRange. See the Settings.js file for this sketch to see how.

As it turns out, the characteristic Brownian tree fractal branching structure emerges all on it’s own from these variations too! This is a good illustration of the “self similar” nature of fractals, showing that similar (sometimes identical) structures will emerge at different scales.

Left: increasing particle diameter based on distance to center; Right: randomly varying particle diameters

Experiment 04 — different shapes

Now what would happen if we played around a bit with the shape of the walker particles? Would the branching structure be affected by the geometry of the particles?

In my implementation all particles are circles by default, since I figured that would be the most common configuration. However, the underlying collisions package also allows for the use of single points or arbitrary polygons defined by arrays of points. I was never able to get the “single point” mode working properly, but polygons worked like a charm!

I’m betting that if you were to able to get the simulation working with single points via the collisions package then you’d see some pretty large performance gains. The package uses different collision detection algorithms for different shapes, so I wouldn’t be surprised if it relied on a grid-based “neighbor count” approach not unlike what T. A. Witten and L. M. Sander used back in 1981!

Creating polygonal particle shapes is as simple as passing in arrays of coordinates to the createWalker() function of the DLA module. There aren’t many limitations to what these shapes can be, though the documentation for the collisions package does mention that it doesn’t support convex polygons (polygons with inward “dents”).

In my sketches I chose to implement regular polygons with varying sizes and rotation amounts. Since these polygons are radially symmetrical, all that is needed to change the overall shape is to change the number of vertices. For example, three vertices for triangles, four for squares, and so on.

Interestingly, the same fractal branching structures emerge here as well, again showing the “self similar” nature of fractals. Another observation we could make is that the branching structures tend to be more “dense” as the number of vertices (and therefore overall size) decreases — which make a lot of sense, as simpler polygons tend to leave larger gaps between them as they aggregate.

Top left: triangles; top right: squares; bottom left: pentagons; bottom right: random number of sides between 3 and 6.

Experiment 05 — SVG as input

Up to this point we’ve been using pretty simple initial conditions for the DLA process to build upon — just single points or lines (“walls”) of points. To me the next logical step was to enable arbitrary geometry through the use of external SVG files.

For these experiments I implemented a new module (SVGLoader.js) that reads very simple SVG files and spits out arrays of coordinates for each <path> that can be used to construct polygons directly through the collision detection package. Walker particles then need to be checked for collisions with both clustered particles and these custom shapes.

To make my life easier, the SVGLoader module is very particular about the SVG files it accepts. If you want to use your own SVG files, they’ll need to meet the following criteria:

1. The file format must be as simple as possible. In Inkscape you should save the file as “plain SVG”. You may need to go in to the SVG file and simplify things a bit. Take a look at the contents of the files in the ./svg folder for clues.
2. All coordinates should be absolute.
3. Only straight lines are accepted — no arcs, circles, curves, etc. You can approximate curves by adding lots of additional nodes and converting them all the straight segments.

This time we end up with some really great organic-looking results as the characteristic branching structures seem to grow naturally and randomly on the surface of our shapes. To me this is where things can start to get really interesting!

All of the previous experiments involved very simple, schematic conditions that were helpful in studying the fundamental process itself, but now that we can start working with arbitrary geometry we can really start doing some creative things. Here are just a few basic examples I came up with, but I’d love to see what you all create on your own!

Left: text converted to SVG paths; Right: various polygons that have been boolean unioned together
Growth on a 2D supershape generated using my SuperformulaSVG web app

Experiment 06 — interactivity

Throughout all of these experiments I found myself wishing I had more direct control over the walker particle movements so I could add more growth in specific areas. I ended up exploring a few fun possibilities, including:

  1. A “gravity well” effect that pulls walkers towards the mouse position when you click and hold.
  2. A “mouse trailer” effect that continuously emits walker particles around the mouse that are biased towards the center.
  3. A version of the classic “Asteroids” game where users can use WASD to move and Space to shoot.
  4. A radial version of the classic “Bust-a-Move” game where users can move using A and D, aim using the mouse, and shoot using the left mouse button.

I would love to see what other kinds of interactions you all can think of!

Left: click and hold to create a “black hole” that draws all walkers towards it; Right: “mouse trailer” mode — walkers continuously spawn around the current mouse position and move towards center
Left: “asteroids” mode — move triangle ship with arrow keys, hold space to fire; Right: radial “Bust a Move” mode — use A and D to rotate, hold mouse button to fire walkers towards mouse.

Experiment 07 — flowfields

The last thing I could think of was inspired by Daniel Shiffman’s Coding Challenge #24: Perlin Noise Flow Field, in which he uses an equation to direct the movement of particles on the screen. Specifically he used the ubiquitous Perlin noise() function, though lots of other equations can be used.

In my implementation, all we have to do is define a function that takes a particle reference as input and returns an X and Y velocity (dx and dy) that is then added to the particle’s position during the core walker movement function (iterate in DLA.js). We provide this function to the DLA module by assigning it to the DLA.customMovementFunction variable, then away it goes!

There is a whole lot to explore here, but I have to admit that I’m not very familiar with different flow field equations myself. If you know of some interesting equations, please share them with me!

30,000 walker particles guided by 2D Perlin noise function
30,000 particles guided by equation `sin(x) + sin(y)`

Effects and features

While building out these experiments I stumbled on a couple interesting visual effects that I decided to turn into globally-available features.

Line rendering effect

In this effect we only draw lines between each particle rather than the particles themselves. This creates very organic-looking branching structures that start to look a little bit like veins!

You can toggle this effect in any of the experiments above using the l (lower-case L) key.

Export as SVG

One of the most useful features is the ability to export SVG drawings at any time using the e key. These files are great for digital fabrication workflows and can be useful for pen plotters, laser cutters, vinyl cutters, CNC machines, and more.

Colors

If you know your way around the color wheel (which I sadly don’t), you can fully customize the colors of each element of the simulation for some great effects. Check out the “COLORS” section of Defaults.js to see what you can modify!

Going further

This article is really just an introduction to the topic of diffusion-limited aggregation, and there are a number of ways you can go beyond what I’ve presented here.

  1. Bump up the number of particles to the 1–10+ million range to see interesting macro-structures emerge (see Andy Lomas’ Aggregation series for inspiration). See if you can find a way to go even further and the push the state of the art to a new level!
  2. In order to reach higher particle counts you’ll need to use a more performant language or framework like Processing, openFrameworks, Cinder, vanilla C++, Go, or Python. Professional VFX tools and game engines like Houdini, Unity, and Unreal might also be worth a try!
  3. Implement a more efficient algorithm such as Michael Fogleman’s dlaf.
  4. Play with Softology’s Vision of Chaos.
  5. Extend the simulation into three dimensions using OpenGL
  6. Implement probabilistic “stickiness” factor to vary the density of the branching structures. Paul Bourke’s article on DLA describes this nicely.

Resources

If you’d like to explore this topic further, here are some relevant articles and code repositories I found when doing research for this article:

Articles

Code

--

--

Jason Webb

Creative technologist exploring digital morphogenesis through code, simulation, and digital fabrication.