Emergent Algorithms

Produce pretty pictures with code.

There’s no grand philosophy in this post, just an appreciation for how complex behaviours can arise from simple rules.

All the algorithms below are surprisingly easy to implement; each can be crafted in a few hundred lines of code (or less!). And they are perfect playground for experimentation (optimize for speed? move into a different dimension? golf it into a single line? avoid if statements?). They’re fun, visual and even when you screw up, the results are often pretty cool!

The Game of Life

Conway’s Game of Life is a set of really simple rules, from which complex behaviours emerge. It’s played on a 2D grid where a cell can either be alive or dead.

There are just four rules:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.

2. Any live cell with two or three live neighbours lives on to the next generation.

3. Any live cell with more than three live neighbours dies, as if by overpopulation.

4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Yet from these simple rules, all sorts of behaviours can emerge from gliders to guns, to self-replication.

The game of life (redder = more state changes)

Boids

The Boids algorithm describes the flocking behaviour of a group of animals. In this case, there are just three simple rules.

To translate this into code, each Boid starts with a random position and velocity. Each iteration we calculate the acceleration vector for each boid and nudge it in the right direction according to these rules.

• Avoidance: The avoidance force pushes a boid away from nearby neighbours. To calculate this for a boid, find all the boids within a radius

• Alignment: The alignment force steers a boid toward the average heading direction of its neighbours by subtracting its current velocity from the average velocity of its neighbours.

• Cohesion: The cohesion force pulls a boid toward the centre of mass of its flock by directing it toward the average position of its neighbours.

And from this, you get beautiful patterns reminiscent of the murmuration patterns you might see from a group of birds¹.

The Lindenmayer system

A Lindenmayer system (L-system) is a string rewriting system that generates complex patterns through recursion and simple rules. The core components of the system are:

1. Axiom - the starting string

2. Production rules - a set of string replacement rules

3. Interpretation mechanism - how to visualize the resulting string.

A “string rewriting system” sound grandiose, but really it’s just something a bit like this, where the “Rules” are just simple replacements.

public class LSystem
{
    public string Axiom { get; }
    public Dictionary<char, string> Rules { get; }
    public string CurrentString { get; private set; }

    public LSystem(string axiom, Dictionary<char, string> rules)
    {
        Axiom = axiom;
        Rules = rules;
        CurrentString = axiom;
    }

    public void Iterate(int n = 1)
    {
        for (int i = 0; i < n; i++)
        {
            StringBuilder nextString = new StringBuilder();
            foreach (char c in CurrentString)
                nextString.Append(Rules.ContainsKey(c) ? Rules[c] : c.ToString());
            CurrentString = nextString.ToString();
        }
    }
}

For an example of some simple rules see Wikipedia!

The interpretation mechanism is usually something Logo based and this is where the magic happens. If you’ve not come across Logo, it’s basically like programming a Roomba! You have a movable pen, you can rotate it, lift it up and put it down, move it forward and turn. But again, from this simplicity complexity can emerge. Your job when implementing an L-system is to write instructions for the robot. Again, it doesn’t have to be complicated.

                case 'F': // Move forward and draw
                    MoveForward(draw: true);
                    break;

                case 'f': // Move forward without drawing
                    MoveForward(draw: false);
                    break;

                case '+': // Turn right
                    Angle += turnAngleRadians;
                    break;

                case '-': // Turn left
                    Angle -= turnAngleRadians;
                    break;

As an example, here’s the dragon curve, produced via a string rewriting system with the axiom F (start state), production rules (F → F+G, G → F-G). The rules for drawing are that F ad G mean move forward and + and - mean turn.

The dragon curve!

Gray Scott Model

The Gray Scott Model is a system that shows how two chemicals can interact. It creates super cool patterns!

Imagine you have two chemicals, U and V, spread across a petri disk. U is the food substance, and V is a predator that eats U (important, not you). These chemicals play by these rules

1. They move around by diffusion (spreading from high to low concentration)

2. They react with each other

3. More food is continuously added from the outside.

And they are modelled using this pair of funky-looking equations:

\(\begin{cases} \frac{\partial U}{\partial t} = D_U \nabla^2 U - UV^2 + F(1-U) \\ \frac{\partial V}{\partial t} = D_V \nabla^2 V + UV^2 - (F+k)V \end{cases}\)

This looks super intimidating, so let’s break it down a big.

• U and V represent the chemicals, let’s imagine they are a 2D grid with co-ordinates i and j (e.g. U[i][j] is the concentration of a chemical at i and j). We’re going to apply these operations to each bit of the array.

• Du and Dv are constants representing diffusion rates (e.g. you pick these numbers!).

• The funky triangle (∇²) is the Laplacian operator. We can approximate that with the five-point stencil method (take the values up, down, left and right and takeaway 4 x the middle number). Or simpler if you prefer code U∇² is u[x+1, y] + u[x-1, y] + u[x, y+1] + u[x, y-1] - 4* u[x, y];

• F is the feed rate of U (e.g. the food added from the outside). k is the removal rate of the V.

Put this all together and twiddle some numbers and you get some super funky patterns emerging!

F = 0.035, K = 0.065

But what’s really cool, is that with just a very slight change of parameters you can get a wildly different visualization.

F=0.06, K=0.062

Conclusion

All the code to generate this is over at https://github.com/fffej/emergent-algorithms (C#).

If you’re after a fun evening project, then I’d encourage you to find an algorithm you like and just experiment to produce cool visualizations. As some ideas:

• Can you colour things in nicely? (learn about different color spaces)

• Can you make it go 100x faster? (learn about performance, garbage collection, ref vs. value, stack vs. heap etc)

• Can you write it in a purely functional style? (learn about fold!).

• Can you write it in a different language? (Clojure, Rust, Haskell, JavaScript)

• Can you write it idiomatically in that language?

• Can you extend it to another dimension?

If you do, I’d love to see so please share! And equally, if there are more emergent algorithms, show me!

1. No idea how to attach big-animated gifs, just turned this into an MP4 with ffmpeg instead.