Fractals from random walkers


The song in my mind while doing this was:


You promised fractals! take me to the fractals! a.k.a. assignment answers

The one on Flake’s 6.5


Cool fractals


This was an assingment from my Modeling Complex Systems course but as I got such a beautiful plots I decided to go for a blog post showing the results from there.

The first thing that I want to talk about is that my main result from that class is going to be a julia julia package (which is hosted right here github), it’s in very early stages so it’ll be changing rapidly (stay tuned); PR, issues and feedback are welcomed and encouraged.


So the first part of the assignment was to fix a L-systems code written in Matlab, but is well known that in order to fix a Matlab code the first thing you have to do is to write in another language (free and open source), so that’s where I decided to build my implementation in Julia from scratch. I didn’t like the object oriented direction that was taken in the original one and decided to go for a dictionary way.

First of all, for those who don’t already know what an L-system (which stands for Lindenmayer system) is an iterative rewriting system which consist in certain rules. These rules are pattern matching ones, so in every iteration you have to look for a certain pattern and replace it with a given rule.


We have the following string: FGFGFFF

And a rule F -> FG


Iteration Resulting String

And so on.

So the first problem was to reproduce a figure from Flake’s book The Computational Beauty of Nature with our shiny new software. But first we want to see if we get the same result from the Matlab’s example code (which I think was hosted here).

The set of rules was:

F -> FF

G -> F[+G][-G]F[+G][-G]FG

We have to know that [ ] means that the rules given inside the brakets are only good inside them, so when we hit ] we’ll return the parameters to the ones that we had before entering them, and the + - signs mean a change in the angle of movement. So, we need a starting point a starting angle and a change rate $\Delta$ for that angle. The starting position is called axiom and its a string seed. In this case we have axiom = G and $\Delta$ = 27.5°.

The resulting figure after 2 iterations is example

Now we want to reproduce the figure that we’ve been told to do. It has the following parameters:

Weed 1

Rules $\Delta$ Axiom
F -> F[-F]F[+F]F 25 F


I don’t have the original image right here, but I can tell you that it is the same 😜

Building your fractal

Sometimes we need to change the angle more than once, so we can add a number preceding the + - signs to tell the (as it’s known) turtle, to change direction multiple times, i.e. if we have $\Delta$ = 10°, then 4+ will change the angle 40° counterclockwise (the same way we normaly measure angles). So that leaves us with the second question of the assignment which was to implement that and try to reproduce a cool figure we came up with.

As I’m a romantic I will try to do a fractal or pseudo-fractal version of this


And I’ll be doing it with the following set of parameters

Rules $\Delta$ Axiom
F -> FF[+F][-F] 45° F
+ -> +F[+2F][-2F]    
- -> -F[-3F][+3F]    

It is a very basic set of rules, but what I wanted to do was avoiding branches to touch (at least the small ones).

The final result


This was achieved by 1-4 iterations of those rules, but we can also see how it grows (on a 3 iteration process)


Here are another cool examples of what can be done

Cool stuff

sierpinski penrose spikes

Diffusion-Limited Aggregation


So for this I did use a some kind of object oriented algorithm, but it is very simple. To speed up things I took advantege of Julia’s speed and try to make the code as modular as possible to get the must out of the JIT compiler. And as it turned out, it runs pretty fast actually.

I used 1000 random walkers in a 10x10 box and make them stop moving if they touched a non-moving walker, and I put a first one of those in the middle of the box. What I got was this cool looking thing


Box-counting algorithm

The last question was to measure Minkowski’s dimension in the figure we got. The algorithm is very simple, you need to grid the space with boxes of the same size and count how many are needed to cover all of the figure. Then such dimension will be

where a is the box size and N the number of boxes needed.

To make this possible I use the power of GEOS which is the sotfware that powers PostGIS and GeoPandas. I build a grid of boxes with filled properties and check wether those are empty or not.

A figure of the dimension as function of box size


The smallest a I used was 0.01 and got a dimension of 1.437

From that we could say that it has fractal structure. But we should test for smaller box sizes.