Step by Step Fractals with Python
Fractals are awesome, they are built with very complex pattern and they allow you to zoom in forever! In this post we will see how easily it is to plot several kinds of fractals using a tool called L-Systems and the Python Turtle module for the step to step plotting.
In this post I'm not going to dive into too many technical details but instead I'll present a little introduction, a lot of animated examples and at the end, the code to generate your own. If you want skip the theory and see the animations, jump directly to the animated examples, if you want to see the code instead, jump directly to that section. Additionally, there will be some resources for both code and math background if you want to explore at the end.
What's a Fractal?
First lets give a "non-strict" definition of what a fractal is, it is basically a geometric figure which shows the same characteristics no matter how much you zoom in.
It isn't quite correct but for those who wanted to know the exact definition here it is:
A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales. A plot of the quantity on a log-log graph versus scale then gives a straight line, whose slope is said to be the fractal dimension. - Math World
How can we draw Fractals with Python?
Fractals are typically hard to draw, because there is a concept which is deeply tight in them, recursion. When we talk about graphics and plotting we usually talk about pixels or vectors, but there is always a limit, fractals by definition are infinitely recursive. So when we want to plot one we should stop at some point, that's why we talk about "iterations". At each iteration the fractal becomes more and more complex, but at some point it is impossible to distinguish between to successive iterations (this happens when changes occur at individual pixel levels), so it is quite reasonable to stop there, sometimes it is quite clear what the shape is and we can stop even earlier.
A two examples for this are the Quadratic Koch Island, which with 3 iterations has a clear structure and in the other hand the Dragon Curve which has a clear structure with 8 iterations. How many iterations are needed depends highly on the specific fractal we are working with.
Certainly there are lots of plotting libraries in Python, being Matplotlib the most popular but they are usually design to plot statistical data and well known plots. Matplotlib in particular has some low level constructs that allow us to build fractals but this time we will be focusing in a usually forget module in the standard library, the Turtle Module.
Turtle Module
According to Python docs: "Turtle graphics is a popular way for introducing programming to kids. It was part of the original Logo programming language developed by Wally Feurzig and Seymour Papert in 1966."
The key here is that turtle recognizes basically 3 commands:
- Move Forwards
- Turn Left by angle
- Turn Right by angle
Note: THe standard library provided other commands but here we are going to just those 3.
Additionally we have the option to:
- Disable writing
- Enable writing
This characteristics seems too simple for plotting such complex graphics as fractals but we will use another tool that uses just this little set of instructions, I'm talking about L-Systems.
L-Systems
An L-System is a way of representing recursive structures (such as fractals) as a string of characters, this is done by rewriting the string over and over. Again, the formal definition is the following:
A Lindenmayer system, also known as an L-system, is a string rewriting system that can be used to generate fractals with dimension between 1 and 2. - Math World
Once we understand what an L-System is we can produce recursive structures, but before we are able to do that we need to understand what are the pieces we need. Every L-System has:
- An alphabet: The set of symbols the L-System is going to use.
- An axiom: The initial string for the generation.
- A set of production rules: These rules tells how each symbol should be replaced in the following iteration.
Note for computer science fans: If you ever dived into Computer Science this might sound familiar, it is actually since this is very similar to the definition of a Formal Grammar, the key difference is that in each iteration, as opposed to grammars, as many rules as possible are applied instead of just one. So L-Systems are a subset of Context-Free Grammars.
Since we are going to use Turtle to plot and L-Systems to represent what we want to plot we need to create a relationship between them.
Since the only commands we have in Turtle are the mentioned above we will assign each a symbol which will represent the alphabet
- F: Move Forwards
- +: Turn Right
- -: Turn Left
In order to make this work, each fractal should also provide an angle, which will be the angle the turtle will turn either right or left, for simplicity reasons only one angle should be provided and the L-System should be written taking that into consideration.
The axiom and the production rules will depend on the fractal only, but the fractal should be written in a way that can be represented by these only three symbols. This introduces a limitation, we will be able to produce only one-line fractals, so some such as the Cantor Set won't be able to be produced this way, this is only a simplification, since we can introduce two other commands to move forwards without writing and analogously for the backwards movement, but to keep things simple we will keep that simplification.
Now let's move to some examples!
Animated Examples
The following examples were compiled from several places publicly available on internet. I decided to port them to Python with the help of the Turtle module, center them, adding colors and provide a way to export them in vectorial format.
Because the browser execute Python via Skulpt and Colorsys isn't supported yet, the animations will be Black & White but images with colors and the corresponding code to generate them will be provided. Each animation has a code associated which you can open and fork in Repl.it
WARNING: The animations you are about to see are quite large in size, it is recommended to see them only with a good connection. The Repl snippet may not work since it uses your resources so mobile users might not be able to see it properly.
Note: Skulpt uses YOUR BROWSER to render and to make the animation so if in any case you experience delays, lags or strange behaviour it may be a problem with the browser, replaying the animation or reloading the page should fix most issues. It may not work properly on mobile.
The examples are ordered by their complexity (my own judgement though), so the best ones are at the end.
Koch-Snowflake"
axiom = "F--F--F"
rules = {"F":"F+F--F+F"}
iterations = 4 # TOP: 7
angle = 60
Quadratic-Koch-Island
axiom = "F+F+F+F"
rules = {"F":"F-F+F+FFF-F-F+F"}
iterations = 2 # TOP: 4
angle = 90
Crystal
axiom = "F+F+F+F"
rules = {"F":"FF+F++F+F"}
iterations = 3 # TOP: 6
angle = 90
Quadratic-Snowflake
axiom = "F--F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90
Box-Fractal
axiom = "F-F-F-F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90
Levy-C-Curve
axiom = "F"
rules = {"F":"+F--F+"}
iterations = 10 # TOP: 16
angle = 45
Sierpinski-Arrowhead
axiom = "YF"
rules = {"X":"YF+XF+Y", "Y":"XF-YF-X"}
iterations = 1 # TOP: 10
angle = 60
Siepinski-Sieve
axiom = "FXF--FF--FF"
rules = {"F":"FF", "X":"--FXF++FXF++FXF--"}
iterations = 7 # TOP: 8
angle = 60
Board
axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+FF"}
iterations = 3 # TOP: 5
angle = 90
Tiles
axiom = "F+F+F+F"
rules = {"F":"FF+F-F+F+FF"}
iterations = 3 # TOP: 4
angle = 90
Rings
axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+F+F-F"}
iterations = 2 # TOP: 4
angle = 90
Cross-2
axiom = "F+F+F+F"
rules = {"F":"F+F-F+F+F"}
iterations = 3 # TOP: 6
angle = 90
Pentaplexity
axiom = "F++F++F++F++F"
rules = {"F":"F++F++F+++++F-F++F"}
iterations = 1 # TOP: 5
angle = 36
32-Segment-Curve
axiom = "F+F+F+F"
rules = {"F":"-F+F-F-F+F+FF-F+F+FF+F-F-FF+FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+"}
iterations = 3 # TOP: 3
angle = 90
Peano-Gosper-Curve
axiom = "FX"
rules = {"X":"X+YF++YF-FX--FXFX-YF+", "Y":"-FX+YFYF++YF+FX--FX-Y"}
iterations = 4 # TOP: 6
angle = 60
Sierpinski-Curve
axiom = "F+XF+F+XF"
rules = {"X":"XF-F+F-XF+F+XF-F+F-X"}
iterations = 4 # TOP: 8
angle = 90
Krishna-Anklets
axiom = " -X--X"
rules = {"X":"XFX--XFX"}
iterations = 3 # TOP: 9
angle = 45
Quadratic-Gosper
axiom = "YF"
rules = {"X": "XFX-YF-YF+FX+FX-YF-YFFX+YF+FXFXYF-FX+YF+FXFX+YF-FXYF-YF-FX+FX+YFYF-",
"Y": "+FXFX-YF-YF+FX+FXYF+FX-YFYF-FX-YF+FXYFYF-FX-YFFX+FX+YF-YF-FX+FX+YFY"}
iterations = 2 # TOP: 3
angle = 90
Moore-Curve
axiom = "LFL-F-LFL"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 0 # TOP: 8
angle = 90
Hilberts-Curve
axiom = "L"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 8 # TOP: 9
angle = 90
Hilbert-Curve-II
axiom = "X"
rules = {"X":"XFYFX+F+YFXFY-F-XFYFX", "Y":"YFXFY-F-XFYFX+F+YFXFY"}
iterations = 4 # TOP: 6
angle = 90
Peano-Curve"
axiom = "F"
rules = {"F":"F+F-F-F-F+F+F+F-F"}
iterations = 2 # TOP: 5
angle = 90
Cross
axiom = "F+F+F+F"
rules = {"F":"F+FF++F+F"}
iterations = 3 # TOP: 6
angle = 90
Triangle
axiom = "F+F+F"
rules = {"F":"F-F+F"}
iterations = 2 # TOP: 9
angle = 120
Dragon-Curve
axiom = "FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 8 # TOP: 16
angle = 90
TerDragon-Curve
axiom = "F"
rules = {"F":"F-F+F"}
iterations = 5 # TOP: 10
angle = 120
Twin-Dragon-Curve
axiom = "FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 6 # TOP: 16
angle = 90
ThreeDragon-Curve
axiom = "FX+FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 7 # TOP: 15
angle = 90
Code
All the examples above were produced by the same code and some challenges emerged when working on it, mainly to keep the fractal centered (or at least as much as possible), dealing with colors, inversions and offsets and to export it quickly in a vectorial format. Here I will show you the most basic version, if you want to know how I dealt with those challenges, leave me a comment and I will make a Part 2.
This version plots in black and white and with no export functionalities
import turtle
def create_l_system(iters, axiom, rules):
start_string = axiom
if iters == 0:
return axiom
end_string = ""
for _ in range(iters):
end_string = "".join(rules[i] if i in rules else i for i in start_string)
start_string = end_string
return end_string
def draw_l_system(t, instructions, angle, distance):
for cmd in instructions:
if cmd == 'F':
t.forward(distance)
elif cmd == '+':
t.right(angle)
elif cmd == '-':
t.left(angle)
def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
x_offset=0, offset_angle=0, width=450, height=450):
inst = create_l_system(iterations, axiom, rules)
t = turtle.Turtle()
wn = turtle.Screen()
wn.setup(width, height)
t.up()
t.backward(-x_offset)
t.left(90)
t.backward(-y_offset)
t.left(offset_angle)
t.down()
t.speed(0)
t.pensize(size)
draw_l_system(t, inst, angle, length)
t.hideturtle()
wn.exitonclick()
Code Explanation
import turtle
First we need to import the Turtle Module
def create_l_system(iters, axiom, rules):
start_string = axiom
if iters == 0:
return axiom
end_string = ""
for _ in range(iters):
end_string = "".join(rules[i] if i in rules else i for i in start_string)
start_string = end_string
return end_string
Then we need to generate the L-System which will be the set of instructions for the turtle. We define a function called create_l_system which receives the number of iterations, the axiom and the production rules. It starts with the axiom and uses an auxiliary variable called end_string if iteration is equal to 0 it will return the axiom since some fractals can be plot with iterations equal to 0. Rules here are assumed to be dictionaries, so the key will be unique and represents the symbol and the value represents what should be replaced with. So we join all the replacements for each symbol and we end up with the string for the next iteration.
def draw_l_system(t, instructions, angle, distance):
for cmd in instructions:
if cmd == 'F':
t.forward(distance)
elif cmd == '+':
t.right(angle)
elif cmd == '-':
t.left(angle)
Then we define a draw_l_system which takes the turtle, the set of instructions (the output of the L-System), the angle for the turn right/left and the length of each individual line. It consist of a simple elif structure for each of the previously defined commands.
def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
x_offset=0, offset_angle=0, width=450, height=450):
inst = create_l_system(iterations, axiom, rules)
t = turtle.Turtle()
wn = turtle.Screen()
wn.setup(width, height)
t.up()
t.backward(-x_offset)
t.left(90)
t.backward(-y_offset)
t.left(offset_angle)
t.down()
t.speed(0)
t.pensize(size)
draw_l_system(t, inst, angle, length)
t.hideturtle()
wn.exitonclick()
And finally the main function, it receives all the parameters it need for the generation of the L-Systems and also y_offset, x_offset, offset_angle, width and height. The first three represent the offset of the turtle, this is merely for positioning the plot as we want inside the canvas.
The function first generates a set of instructions and stores it in inst then it initializes the turtle and the screen and it positions the turtle in the defined position, then it plots the instructions and wait for a click to close.
Special Considerations
As I mentioned earlier there are lots of limitations here, first we are not including the possibility of moving the turtle without drawing, this would require another symbol, it isn't either a symbol for going backwards, or remember previous positions. This weren't necessary for all the fractals you've seen but for some other (like fractal trees), these symbols are required.
Additional Resources
There are lots of resources in internet about fractals both from the programming and from the math perspective. I will show you two that I find really interesting: The 3Blue1Brown for math and the CodingTrain for code.
Coding Train
3Blue1Brown
Sources and References
This post was inspired by a Math World post, the Paul Broke Blog and an university assignment for Genetic Algorithms.