2
\$\begingroup\$

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
        self._position = np.add(pos, dirn)
    def rotate(self, theta):
        """ 
        Rotate turtle direction by angle theta in degrees. 
        """
        (x, y) = self._direction
        current_angle = atan2(y, x)
        new_angle = current_angle + radians(theta)

        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:

enter image description here

Other examples include the Sierpinski Arrowhead curve:

axiom = 'FX'

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

n_iterations = 8

theta = 60

enter image description here

The Hilbert curve:

axiom = 'X'

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

n_iterations = 5

theta = 90

enter image description here

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

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there another way to call these functions without using exec() ? \$\endgroup\$ – Vermillion Oct 25 '16 at 16:55
  • 1
    \$\begingroup\$ @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...). \$\endgroup\$ – Graipher Oct 25 '16 at 17:38
  • \$\begingroup\$ Is this the best way to move the turtle then? \$\endgroup\$ – Vermillion Oct 25 '16 at 18:36
  • \$\begingroup\$ @Vermillion I don't think so, but I need some more time to think of a better one. \$\endgroup\$ – Graipher Oct 25 '16 at 18:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – LarsH Dec 14 '16 at 20:26
2
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.