Visualising diffusion-limited aggregation in pure JS

What is diffusion-limited aggregation?

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.

DLA

Above we can see a DLA cluster grown from a copper sulfate solution in an electrodeposition cell.

DLA

Above we can see cluster grown by our algorithm.

Model

To visualise DLA in browser we need to agree to some model. Let’s assume that:

Each particle performs a random walk in our system.
When particle is next to a cluster it sticks to it.
We start with a simple seed cluster consisting of one particle in the center of the visualisation.

Model is dead simple. Let’s see how we can implement it and generate some pretty pictures.

Code

First we need to to create initial parameters and fill the input with them. We need to do it after the DOM is loaded:

window.onload = function () {
	var initialParameters = { width : 800, height:800, particle_density:0.25, stopping_fraction:0.5};
	document.getElementById("parameters").value = JSON.stringify(initialParameters);
};

We have four parameters:

width and height of our simulation
particle_density indicating how many particles will we used ( particle_density x width x height )
stopping_fraction as we need to specify some stopping condition for our simulation, we will stop when specified fraction of all particles will be part of the cluster

First we need to create some default colors we will use:

var background_color = [50,50,50]; // dark gray
var particle_color = [52,152,219]; // ligh blue

// colormap which converts value from the 0..1 range into a color
// it looks like a heatmap
function colormap(v) {
	return [
		255 * ((v <= 0.5) ? v * 2.0 : 1.0), // red
		255 * ((v > 0.25) ? ((v < 0.75) ? (v - 0.25) * 2.0 : 1.0) : 0.0), // green
		255 * ((v > 0.5) ? (v - 0.5) * 2.0 : 0.0) // blue
	];
}

Next we need to create field where particles will be moving:

var CLUSTER_SIZE = 0;

function createField(width, height) {
	var field = { width:width, height:height, field: new Uint32Array(width * height) };
	field.field[Math.floor(width / 2) + Math.floor(height / 2) * width] = 1;
	return field;
}

We will use a lot of typed arrays in our project. Elements that are part of the cluster will be have CLUSTER value.

Next we need to create particles and initialize their positions.

function resetParticle(particles, field, i) {
	var x = Math.floor(Math.random() * field.width);
	var y = Math.floor(Math.random() * field.height);

	while(field[y*field.width+x]) {
		x = Math.floor(Math.random() * field.width);
		y = Math.floor(Math.random() * field.height);
	}

	particles.x[i] = x;
	particles.y[i] = y;
}

function createParticles(field, count) {
	var particles = {
		count: count,
		stuck: new Uint32Array(count),
		x: new Uint16Array(count),
		y: new Uint16Array(count),
	};

	var i = count;
	while (i--)
		resetParticle(particles, field, i);

	return particles;
}

Reset function generates new position for the particle until it’s a position that is not occupied by any cluster. We create three arrays, one for storing x coordinates of the particles, one for storing y coordinates of the particles and storing for the flag indicating whether the particle is stuck in a cluster.

Then we need a function that will perform random walk:

function updateParticle(particles,field, i) {
	var xmove = Math.random();
	var ymove = Math.random();
	var x = particles.x[i] + (xmove > 2/3 ? 1 : xmove > 1/3 ? 0 : -1);
	var y = particles.y[i] + (ymove > 2/3 ? 1 : ymove > 1/3 ? 0 : -1);

	if ( (x < 0) || (y < 0) || (x >= field.width) || (y >= field.height)) {
		resetParticle(particles, field, i);
	}

    particles.x[i] = x;
    particles.y[i] = y;

	if (isNextToCluster(particles, field, i)) {
		particles.stuck[i] = ++CLUSTER_SIZE;
		field.field[y*field.width + x] = CLUSTER_SIZE;
	}
}

In first two lines we find new place for the particle by randomly moving it in any of 8 direction or not moving it all (with equal probability = 1/9). Then if particle ventured out of our field we reset its position.

If new position is a valid one we check if particle is next to a cluster:

function isNextToCluster(particles, field, i) {
	var cx = particles.x[i], cy = particles.y[i];
	var lx = cx - 1, rx = cx + 1;
	var ty = cy - 1, by = cy + 1;

    // if we are at boundary
	if (lx < 0 || rx >= field.width ||  ty < 0 || by >= field.height) {
		return false;
	}

	cy *= field.width;
	by *= field.width;
	ty *= field.width;

	// the check if we have neighour
	return field.field[cx + ty] || field.field[lx + cy] || field.field[rx + cy] || field.field[cx + by] ||
		field.field[lx + ty] || field.field[lx + by] ||  field.field[rx + ty] || field.field[rx + by];
}

This is pretty much all the logic we need. The rendering function looks like this:

function render(field, canvas, particles, stopping_fraction) {
	var i = particles.count;
	while (i--) {
    	var index = (particles.y[i] * field.width + particles.x[i]) * 4;

    	var v = Math.sqrt(particles.stuck[i] / (stopping_fraction * particles.count));
    	var color = v > 0 ? colormap(v) : particle_color;
    	canvas[index] = color[0]; // red
        canvas[++index] = color[1]; // green
        canvas[++index] = color[2] ; // blue
        canvas[++index] = 255; // alpha
	}
}

The start function glues together functions above and triggers render function every frame.

Result

Rest of the code and markup for the sample can be viewed & downloaded here: You can download finished visualisation code here.

Below you can specify parameters and start simulation: