Lichen Pattern Simulation

Introduction

One of my programming inspirations is the youtube channel The Coding Train, which frequently features breakdowns and implementations of scholarly articles that can be used for generative art. While I started watching as a beginner, I’ve recently found some success looking into their source material for more information.

I’ve also been trying to learn the processing-adjacent library OpenFrameworks, which isn’t covered by the Coding Train channel, so I decided to go searching out my own source to re-implement.

This project is an implementation of the lichen pattern generation algorithm described by Robert Sumner in his thesis, Pattern Formation in Lichen. It’s written in C++ using the OpenFrameworks library, and I did it without any external resources beyond the OpenFrameworks documentation.

The Algorithm

The system essentially works by using random walkers to emulate the two forces that drive a lichen’s shape; there is the growth force that causes branches to expand quickly the less competition they have from other lobes, but also the limiting force that causes growth to slow the further away the branch is from the centre body of the mass.

While randomly moving particles sticking to each other don't reflect the real biological mechanics of lichens, by creating rules about how they stick we can create visually similar patterns.

The rule in this case is that a particle is more likely to stick if there are more stuck particles around it. This mixes with the typical rule that the outer fringes of the mass will be more likely to be hit to create those two opposing forces mentioned above.

Implementation

A black and white image of a lichen-like shape made out of small circles.

My first low resolution simulations went well, but when I started to make the cell size smaller and the cell count larger, that’s when things started to get interesting.

A dense lichen-like shape with several arms, one that stretches up in a long, thin, golden ratio-like spiral.

As you can see here, it developed into a single large, spiralling arm, not a rounded lichen at all. I think this is because I’m spawning all of my particles at the same time, not one at a time as the paper does.

I didn’t think it would make a difference, but the paper mentions that they should be spawned far enough away their behaviour is the same as if they originated infinitely far away. Maybe the little bits of interaction that happen when multiple particles stick at the same time is enough to throw off the mathematical equilibrium and create a single long arm like this? It happened every time with these small particles and large spawning radius, and it cleared up when I switched to sending them one at a time.

A dense lichen-like shape made out of many branching arms. The arms all curve slightly in a clockwise direction.

Even then, there’s still a visible clockwise spiral. I think that one's because of one of the ‘sticking’ steps.

A digram from a scientific paper, subtitled Figure 6-5: Before a walker is added to the cluster, it is moved backward to the point of intersection and then rotated until it touches another element.

The paper doesn’t mention how this rotation is calculated, and my initial improvised approach was always rotating them clockwise, which creates these spirals. Instead, I used this line of code float clockwise_Adjust = ceil(ofRandom(2)) == 1? 0.1 : -0.1; to randomise which direction the random walker rotates in. This reduces the obvious spiralling pattern, although I still feel like there’s some bias.

A dense lichen-like shape made out of many branching arms. The arms might be curving in one direction above others.

Maybe it’s just my imagination, but do you notice how the anticlockwise faces seem to be a bit smoother?

I did some measurements of generation speed, and I found that one of the major delays was when a particle would get stuck moving at the slowest speed in an area without any settled clusters.

One of the optimisations the paper suggests is to make the particles take larger steps when they are outside of the settled cluster’s range, which speeds up the random walks immensely, but it only tests the range with a radius, assuming it’s a perfect circle. In extremely not-round cases, this slows the particles down drastically without any chance of them meeting the settled cluster.

A diagram of a large, dense lichen-like shape. There's a circle drawn around it in red that has a lot of empty space. There is also a blue rectangle drawn around it that fits the shape much closer.

Instead, by using a rectangular bounding box, we can speed up the steps without adding much more computational load. There’s still cases where the particle is wandering around in the middle of nowhere, but the worst-case scenarios are limited. This optimisation becomes less useful the more exactly circular the lichen becomes, but my generations seem to generally end up with an off-centre profile.

Conclusion

In its current state, my simulation's a bit slow, especially compared to the paper's speeds of 100,000 elements in 15 minutes. It's not putting any strain on my computer, so I think I need to more fully understand how to make use of the full computing power available to me. I've added a few visualisation options in the code file, but it's a bit of a hassle to change the variables manually.

If I was to come back to this, I'd like to speed it up and add a Ui that could expose those options and let other people experiment with it. OpenFramworks and C++ aren't quite as easy to embed in a webpage as P5.js, but I've seen that there are ways, and it would be nice to add the tool to this website.