# Diffusion-limited aggregation (DLA)

Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by Witten and Sander in 1981, is applicable to aggregation in any system where diffusion is the primary means of transport in the system. DLA can be observed in many systems such as electrodeposition, Hele-Shaw flow, mineral deposits, and dielectric breakdown. (Wikipedia)

This JavaScript application is a computer simulation of DLA. Try it now.

## basic idea

We always start with a seed in the center of a grid. New particles start diffusing at a random position on a circle with fixed radius which is part of the grid. This circle is simulating the infinity. There is only one particle at a time diffusing. If this particle leaves the grid a new one starts at another random position. The particle attaches to the existing particles if it reaches a position with at least one particle in the Von Neumann neighborhood. This way a DLA cluster growths starting at the initial seed. Once a diffusing particle sticks to another particle at a position on the circle no new particles gets created. If the cluster has reached the circle the approximation of the circle to simulate infinity does no more hold at all.

A particle diffuses by drawing two random numbers δx and δy out of {−1, 0, 1} and adding the vector (δx, δy) to the current position (x, y). This way the particle moves into one of the eight possible directions up, up right, right, down right, down, down left, left, up left or stays at its position with equal probability.

### Variants

In this one-grain version you can set the probability that a new particle sticks to an existing particle. If at least one particle exists in the Von Neumann neighborhood the current particle sticks to them with this probability. If it does not stick it continues diffusing but avoids positions which already contains any particle.

In the two-grain version there are two different types of particles, named 2 and 3, which are generated alternating. We always start with a particle 2 in the center of the grid. Two particles have (depending on whom to attach) a sticking probability given by the following matrix. • Two particles of type 2 stick together with probability 1.
• If a diffusing particle of type 2 hits a particle of type 3 it gets attached with probability a.
• If a diffusing particle of type 3 hits a particle of type 2 it gets attached with probability b.
• Two particles of type 3 stick together with probability 1 − c.

As sticking probability the sum of all these probabilities for the particles in the Von Neumann neighborhood of the diffusing particle is used.

## rendered images

All images are generated with dimension 600×600 and a circle with radius 240.

### one-grain version

With a sticking probability of 1 we get the following cluster. With a sticking probability of 0.5 we get the following cluster. With a sticking probability of 0.1 we get the following cluster. One can observe that the branches of the cluster consists of more particles the lower the sticking probability is. This can be explained by watching the movement of one particle: It starts on the circle and hits one of the outer particles of the cluster first. With high sticking probability it attaches to one of the outer particles of the cluster. With a lower sticking probability the diffusing particle does not attach to the first particle it hits and thus can diffuse deeper into the cluster.

### two-grain with a = b

With sticking probabilities of a = 0.1, b = 0.1 and c = 0.1 we get the following cluster. With sticking probabilities of a = 0.1, b = 0.1 and c = 0.5 we get the following cluster. With sticking probabilities of a = 0.1, b = 0.1 and c = 0.9 we get the following cluster. With increasing c one can observe the same behaviour as with decreasing sticking probability in the one-grain-version. Additionally one can observe that with increasing c more type 3 particles—the blue ones—gets attaches to the type 2 particles—the lime ones. The type 2 particles form long branches whereas the type 3 particles gets attaches to any other particles and from random dot clouds.

### two-grain version with a ≠ b

With sticking probabilities of a = 0.9, b = 0.1 and c = 0.1 we get the following cluster. In this picture type 2 particles—the lime ones—gets attached to any existing particle with high probability.

With sticking probabilities of a = 0.1, b = 0.9 and c = 0.1 we get the following cluster. In this picture type 3 particles—the blue ones—gets attached to any existing particle with high probability. Therefore the type 3 particles should form longer branches, but I am not able to see that difference.

## technical details

The function `readOptions` gets called every time the start button is pressed. It uses jQuery to read the options edited in the HTML input fields and sets variables declared at the beginning of the script.

As drawing surface the HTML5 canvas element is used. The function `clearCanvas` gets called every time the start button is pressed. First it sets the dimension of the canvas according to the given width, height and zoom factor. The zoom is achieved simply by the difference of the width and height attributes of the canvas element and the width and height set to the canvas element via CSS. Once the canvas has the correct size it gets cleared using clearRect and the circle is drawn using arc.

The function `drawPoint` draws a particle with type of the given value at the given position in the canvas. The type value gets transformed into the corresponding color and the pixel gets painted on the canvas using fillRect.

The current state of the grid is internally stored in the variable `grid`. This variable is a JavaScript object and is indexed via x + y · width. A JavaScript objects works roughly like a hash map, so storing spare matrices like this grid is more efficient than using real arrays. (JavaScript does not have real arrays anyway.)

The function `addPoint` takes the coordinates of a point and a value and adds this point to `grid`, calls `drawPoint` and adds the point to the list `oldPoints`. In this list a fixed number of last points is kept. These are the highlighted points and the list is used to remove the highlighting from the canvas for every point that leaves the queue.

The function `computeStartPoint` returns a random start point somewhere on the circle. This point gets computed using a random number α out of the range [0, 2π) and evaluating x = radius · cos(α) and y = radius · sin(α).

The function `computePoint` computes a start point with the above function and lets it diffuse. If the particle moves out of the grid, the inner loop ends and the outer loop starts another run with a new start point. If a position with particles in the neighborhood is reached the function returns the current position if a random number out of [0,1) is lower than the specified stickiness.

The function `computePointTwo` works analogue to `computePoint` but using `computeProp` to get the sticking probability. The function `computeProp` takes the value of the diffusing particle and the value of the neighbor particle and returns the stickiness probability. The returned value for all neighbor particles get added together and if a random number out of [0,1) is lower than the stickiness computed this way the function returns the current position.

The functions `step` and `stepTwo` are calling `computePoint` or `computePointTwo` and `addPoint` to perform one step. This function is not called in a loop but calling itself using window.setTimeout. This way the browsers gets back control after every particle added to the clister and the user can see the cluster growing while it gets computed.

Finally the function `start` calls the setup functions to initialize the canvas and the `grid` and places the initial seed. Then it starts the first `step`.