Generating fractals and space filling curves, using a general function for L-systems

An L-system is a rewriting system that can be used to generate fractals and space filling curves, because of its recursive nature.

Some L-systems for mathematical curves can be found here.

An example L-system:

Axiom:

$$FX+FX+$$

Production rules:

$$X → X+YF$$ $$Y → FX-Y$$

Angle: $$\theta = 90$$

In this example, F means "move forward", "+" means "turn right by angle theta, and "-" means "turn left by angle theta". These are simple commands that are followed by a "turtle", which moves around and creates a path. The letters X and Y are not commands, they are only used for the substitution process.

The axiom states "move forward, turn right, move forwards, turn right". After applying the production rules, the command string becomes

$$FX+YF+FX+YF+$$

Performing many iterations produces long, complicated chains of commands. As the turtle follows the commands, very interesting shapes can be produced.

import matplotlib.pyplot as plt
import numpy as np
from math import sin, cos, atan2, radians

class turtle:
"""
A turtle is a simple object with a direction and a position.
It can follow two basic commands: move forward and turn by an angle
"""
def __init__(self):
self._direction = np.array([1, 0]) # 2D direction vector
self._position = np.array([0, 0]) # 2D position vector
def forward(self):
"""
Move turtle forward by one unit.
"""
pos = self._position
dirn = self._direction
def rotate(self, theta):
"""
Rotate turtle direction by angle theta in degrees.
"""
(x, y) = self._direction
current_angle = atan2(y, x)

self._direction = [cos(new_angle), sin(new_angle)]

def L_system(commands, axiom, production_rules, theta, n_iterations):
"""
Executes the commands of an L-system on a turtle object,
and returns the resulting positions.

Beginning with a string of simple commands, this string is made longer by
replacing single characters with longer strings, in a recursive manner.

By completing a number of iterations of this process, a long command string
is generated. A 'turtle' object then follows these commands in order.
It can only move forward or change its direction. The positions of the turtle are
returned in a matrix.

Parameters
----------
commands : dict
Maps single characters to function calls written as strings
The functions are performed on a turtle object
e.g. {'+': 't.rotate(-theta)', '-': 't.rotate(theta)', 'F': 't.forward()'}

axiom : str
The initial string of command characters.
The associated function calls of these characters are found in param commands
e.g. 'FX+FX+'

production_rules : dict
Maps single character strings to more complicated strings of characters
The value strings replace the key strings on each new iteration
e.g. {'X': 'X+YF', 'Y': 'FX-Y'}

theta : int
Angle of rotation, in degrees
e.g. 90

n_iterations : int
Number of iterations for the L system
e.g. 5

Returns
-------
positions : numpy matrix
The positions of the turtle, while following commands in the final command string

"""
command_string = axiom # Begin commands with only the axiom
for iteration in range(n_iterations):
new_command_string = str()
for char in command_string:
if char in production_rules:
new_command_string += production_rules[char]
else:
new_command_string += char
command_string = new_command_string

n_commands = len(command_string) # Total number of commands for the turtle

t = turtle() # Initialize a turtle at position [0, 0]

positions = np.zeros((n_commands, 2))

for i, command in enumerate(command_string):
if command in commands:
exec(commands[command]) # Perform command on turtle
positions[i, :] = t._position

return positions

commands = {
'F': 't.forward()',
'+': 't.rotate(-theta)',
'-': 't.rotate(theta)',
}

axiom = 'FX+FX+'

production_rules = {
'X': 'X+YF',
'Y': 'FX-Y'
}

n_iterations = 11

theta = 90

positions = L_system(commands, axiom, production_rules, theta, n_iterations)

positions = L_system(commands, axiom, production_rules, theta, n_iterations)
plt.plot(positions[:, 0], positions[:, 1])

The output of this code is the Twin Dragon fractal: Other examples include the Sierpinski Arrowhead curve:

axiom = 'FX'

production_rules = {
'X': 'YF+XF+Y',
'Y': 'XF-YF-X'
}

n_iterations = 8

theta = 60 The Hilbert curve:

axiom = 'X'

production_rules = {
'X': '+YF-XFX-FY+',
'Y': '-XF+YFY+FX-'
}

n_iterations = 5

theta = 90 And the Gosper Curve:

commands = {
'A': 't.forward()',
'B': 't.forward()',
'+': 't.rotate(-theta)',
'-': 't.rotate(theta)',
}

axiom = 'A'

production_rules = {
'A': 'A-B--B+A++AA+B-',
'B': '+A-BB--B-A++A+B'
}

n_iterations = 4

theta = 60 Your substituting part should be put into its own function as well. It can also be greatly simplified using dict.get:

rules = {"X": "X+YF", "Y": "FX-Y"}

def apply_rules(text, rules):
return "".join(rules.get(c, c) for c in text)

>>> apply_rules("FX+FX+", rules)
'FX+YF+FX+YF+'

Which you can embed in your code like this:

command_string = axiom # Begin commands with only the axiom
for _ in range(n_iterations):
command_string = apply_rules(command_string, production_rules)

I would put your example code at the end into a if __name__ == '__main__': guard to allow your module to be imported without this code being run.

The variable n_commands is used exactly once, so it is not necessary to declare it.

Your function is potentially very dangerous, because I could put any command in commands, even system calls.

• Is there another way to call these functions without using exec() ? Oct 25 '16 at 16:55
• @Vermillion I was trying to find a better way, but they all suffered the same problem (one would be writing a class deriving from your turtle class with a method handling the translation. But then this class can have arbitrary code in it, too...). Oct 25 '16 at 17:38
• Is this the best way to move the turtle then? Oct 25 '16 at 18:36
• @Vermillion I don't think so, but I need some more time to think of a better one. Oct 25 '16 at 18:51
• @Vermillion: Why not replace exec(commands[command]) with t.exec(commands[command]), where turtle.exec(cmd) is a method that uses the equivalent of a switch statement to dispatch the command? The switch would embody what is now the commands dictionary. That way, the turtle class strictly controls which commands it will accept (and ignores all others). If you want flexibility on which variables (A, B, X, Y, F, but not L, R) get interpreted as forward(), allow the caller to pass in a list of such symbols. Dec 14 '16 at 20:26

L_system performs two unrelated actions:

• It computes the final string containing only terminals, and
• It commands the turtle to draw the string.

I strongly recommend to split it into two methods, e.g.

def L_system(axioms, productions, iterations):

and

def draw_path(L_string, theta, step):

Do you see how these two methods are crying to belong to two different classes?