Samuel Skottenborg

- Personal website



Implementing on-and off-lattice diffusion-limited aggregation algorithms in Processing

Keywords

  • DLA algorithms
  • Processing (Java)
  • Optimization techniques

Tumor growth, copper sulfate crystals, snow crystals, and Lichtenberg figures are among a number of naturally occurring fractal structures caused by a phenomenon known as diffusion-limited aggregation (DLA). This project explores both on- and off-lattice techniques, two distinct takes on simulating the phenomenon.

Click here to jump to the gallery

What is diffusion-limited aggregation?

Diffusion-limited aggregation (DLA) is a naturally occurring process under certain circumstances where particles form a fractal structure. Particles diffuse around in a limited space due to Brownian motion which makes them wander randomly. Somewhere in the space, usually in the center, the first particle is placed. This “seed” is simply a static particle able to collide with wandering particles. Whenever a randomly diffusing particle collides with the seed or other particles which have become part of the aggregate, the wandering particle will become a part of the aggregate itself. Becoming a part of the aggregate simply entails being static and able to collide with wandering particles. This, of course, means the structure will undergo exponential growth.

Common examples of DLA include tumor growth, copper sulfate crystals, snow crystals, and Lichtenberg figures. The latter is most commonly known as the result of connecting the anode and cathode of a high-voltage power supply to a piece of damp wood. Interestingly enough, the same figure appears on persons having been struck by lightning.

This photo of an ice crystal I took looks eerily similar to some of the generated DLA clusters later in this post.
I took this picture of some trees in a sort of orthographic way. I definitely think it looks like DLA clusters, but I’ve never seen trees mentioned in the context of DLA.

Two methods of implementing DLA

Strictly speaking, there are two main ways to go about implementing DLA, off- and on-lattice.  Both methods have their merits depending on what you are going for.

Off-lattice simply means there is no organized grid the particles can move in, instead you have a list or array of the particles. The downsides to this method are that there is no fast way to calculate the nearest neighbor, which in addition means collision detection becomes quite expensive in computing power. Because of the necessary collision detection against the static aggregation of particles, this method becomes exponentially slower as the number of aggregated particles increase. One of the advantages of this method, however, is the possibility of varying the particles’ size as you have to iterate through every particle in order to check for collisions.

On-lattice, on the other hand, means all the particles are organized in a 2-dimensional array. This method makes it awfully easy to calculate the neighbor, as it would just be adding or subtracting from the array index. Knowing the nearest neighbor would be possible on off-lattice but would require further computing power to an already slow method.  With the neighbor known, it is now possible to implement interesting coloring options since it is possible to retrieve the color of the neighbor. I chose to mutate the color of the neighbor by an adjustable parameter which resulted in some of the most beautiful DLA clusters. But the biggest advantage of this method is speed. It is mind-bogglingly fast compared to on-lattice! Now real-time simulations are suddenly possible. The reason it is so much faster is that there is no longer a necessity to iterate through every aggregated particle for collision detection for each wandering particle. The only requirement is checking the neighbors.  This means on-lattice keeps a linear speed throughout the simulation in opposition to the exponentially slower off-lattice. There are some downsides though, one of them being scalability. Because everything is stored in a two-dimensional array, there is going to be a lot of wasted memory space on empty cells. Furthermore, if the particle radius is not smaller than a few pixels the produced image will be chunky and pixelated due to the particles being restrained to a grid. For any practical purposes, the particle radius has to be less than 3-4 pixels, and even then, it takes some hacks to get it looking nice.

#1 implementation: simulating off-lattice

My first attempt was off-lattice, meaning I had to have a 1-dimensional list of all particles. Actually, I used two arrays instead of a single; one for wandering particles, one for aggregated particles. A single array could easily have been used instead by writing a particle class with a boolean variable determining if it is aggregated yet. I opted for arrays of PVectors instead of ArrayLists as it presumably would be faster, and optimization is key for a problem known to be notoriously slow to compute. This also means the number of particles is fixed, which is neither good nor bad.

The particles’ movement is determined by a simple solution equivalent to Brownian motion. For each simulation tick, every wandering particle’s x- and y-position are either increased or decreased by “minWalk+random(maxWalk)”. Collision detection was at first equally primitive, so every wandering particle was iterated and checked against each aggregated particle. This was, of course, exponentially slower until it practically halted. To circumvent this problem, I added a function that for each simulation tick calculates a circle encompassing all aggregated particles. Now collision detection could be significantly sped up by only checking wandering particles within the radius of the encompassing circle. It ended up 50% faster!  Not only that, now knowing the radius of the aggregation it was possible to spawn particles just outside the circle and furthermore force wandering particles outside of the circle towards the aggregation, which, of course, did wonders for the speed as well. From the first working implementation of off-lattice to the last I increased the benchmark speed from 130 seconds to 2.5 seconds.

Screenshot showing an early implementation of the circle-technique which discriminates the particles outside.
Primitive coloring algorithm for the off-lattice implementation

#2 implementation: simulating on-lattice

I wasn’t satisfied with the speed of my solution and I was curious as to how much an on-lattice implementation would actually speed it up. Naturally, I couldn’t help myself but port the code to on-lattice as well. I wrote it in a couple of hours so there’s minimal optimization, yet it turns out to be blazingly fast.

Even though I ported the circle-technique, spawn method, Brownian motion, etc., the underlying principles changed quite a bit by going on-lattice instead. All particles were now contained within a 2-dimensional array of the class “particle” with the size windowSize/atomRadius. In principle, booleans would have been just fine as well, but having a class allows for individual colors, which means it is possible to mutate the neighbor’s color. Finding the neighbor is as earlier explained extremely simple by doing it this way, which means speed!

Conclusion

For a weekend worth of coding, optimizing and porting, I’m quite happy with the results as the focus wasn’t on speed, but rather getting results. I might revisit the project in the future with speed in mind, but not anytime soon.
I had chosen some benchmark parameters for testing speed increase. The very first working implementation took an average of ≈ 130 s, whereas the final version took ≈ 1 s. For now, it is only single-threaded with a CPU usage of ≈15% on my laptop, so there is probably quite a speed increase to be had by going multithreaded.

Gallery