1. Fractals and L-Systems

Worth: 10%
DUE: February 7th, 2023; submitted on MOODLE.

Learning objectives:

Write some code
Solving a question
Thinking abstractly
Work with existing code
Understand existing code
Variables
Using functions
Boolean operators
Conditionals
Comments
Using your code to answer questions

Warning

The assignment is individual. You should not expect to be able to sit down and just start coding a solution. Computer science does not work this way. Expect this assignment to take hours. Expect to get things wrong, then, expect to get things wrong more.

In this assignment you will draw fractals using the Lindenmayer System (or L-System).

Download the asn1.ipynb notebook and upload it to Colab to get started. See below image. WARNING: You should be sure to save a copy of this to your Google drive and then work with that one. You don’t have to, but you will have to re-upload the project every time you want to work on it.

1.1. Lindenmayer System

The Lindenmayer System is a formal language created by the biologist Aristid Lindenmayer to represent how plant cells grow.

The L-System is a recursive system that is very powerful to create fractals and in particular realistic plant fractals.

L-Systems works by using a formal language to form a recursive set of instructions.

In programming recursive functions means a function calling itself.

Example

One example could be a function countdown(n) that count from n to 0:

def countdown(n):
  print(n)
  if n > 0:
    countdown(n-1)

The idea is to combine recursive function in Python and the recursive formal language of the L-System.

Consider the L-System rule \(F \rightarrow F+F-\) for the python Turtle:

\(F\): means moving forward or call the function again.
\(+\): means turning right
\(-\): means turning left

Similarly to our countdown function the rule needs to stop. When it is the last iteration \(F\) means forward.

If it’s not the last iteration it means using the rule again.

Example

If we execute the rule only once, we call it iteration \(0\), then the rule is \(F\).

Now if we increase the iterations, we take the previous iteration and we replace each \(F\) by \(F+F-\):

Iteration \(1\), the rule becomes: \(F+F-\).
Iteration \(2\), the rules becomes: \(F+F-+F+F--\)
Iteration \(3\), the rules becomes: \(F+F-+F+F--+F+F-+F+F---\)

And we can continue forever.

Now it needs to be transformed in Python.

Example

We want to create the python function of the L-System rule \(F \rightarrow F+F-\).

This rule is called Levy C Curve, we obtain the following code:

def levy_c(iterations, length, angle):
        """
        :param iteration: The number of iterations or the depth of the recursion.
        :param length: the length of one forward.
        :param angle: the angle to turn right or left.
        """

        if iterations == 0:
                # If iteration is equal to 0 then we apply F as one forward.
                forward(length)
        else:
                # Otherwise we apply the rule F+F-

                # First we remove one iteration to ensure that it stops!
                iterations = iterations - 1

                # As it is not iteration == 0, this "F" calls the function again
                # replacing "F" by "F+F-".
                levy_c(iterations, length, angle)
                # This is our "+" meaning turning right
                right(angle)
                # This is the other "F" that we replace by "F+F-"
                levy_c(iterations, length, angle)
                # This is "-" meaning turning left
                left(angle)

Concretely if we use this for iteration 0, we obtain only forward (\(F\)):

levy_c(0, 50, 90)

If we apply for iteration 1, we obtain \(F+F-\).

levy_c(1, 50, 90)

We see that it draws forward then turn right, and finally draw forward again. Turning is not drawing anything, so we don’t see it.

If we apply for iteration 2, we obtain \(F+F-+F+F--\).

levy_c(2, 50, 90)

We see that it draws forward,turn right, draw forward again, turn left then right, so it doesn’t change the direction.

Then draw forward again, turn right and draw a final line.

If we apply for iteration 3, we obtain \(F+F-+F+F--+F+F-+F+F---\).

levy_c(3, 50, 90)

Convince yourself that it actually draw the following figure.

Note

Use a piece of paper and do it manually if you’re not sure.

Now you know all you need for the actual assignment!

1.2. Complete the following functions

You need to implement the following function to draw the L-System rule provided.

If the function is implemented correctly, it must draw the same thing.

1.2.1. Blobs

This fractal follows the rule \(F \rightarrow F-F++F\).

Complete the following function:

def blobs(iterations, length, angle):
        """
        This function draw the blobs fractal.

        :param iterations: Number of iterations left
        :param length: Length of the forward line
        :param angle: Turn angle
        """

        # Write your code there.
        # Don't forget the case for iteration 0!

If used as:

blobs(6, 25, 90)

You should obtain:

1.2.2. Tiling

This fractal follows the rule \(F \rightarrow FFF-F\).

Complete the following function:

def tiling(iterations, length, angle):
        """
        This function draw the tiling fractal.

        :param iterations: Number of iterations left
        :param length: Length of the forward line
        :param angle: Turn angle

        """

        # Write your code there.
        # Don't forget the case for iteration 0!

If used as:

tiling(5, 10, 90)

You should obtain:

1.2.3. Koch curve

The Koch curve is one of the best known fractal and follow the simple rule \(F \rightarrow F+F--F+F\).

Complete the following function:

def koch_curve(iterations, length, angle):
        """
        This function draw the Koch curve.

        :param iterations: Number of iterations left
        :param length: Length of the forward line
        :param angle: Turn angle

        """

        # Write your code there.
        # Don't forget the case for iteration 0!

If used as:

koch_curve(4,7,60)

You should obtain:

1.3. Two rules

It is possible to use two different rules at the same time.

The rules call each other to create more complicated fractal.

The following one is based on Sierpinski triangles and the rules are:

\(X \rightarrow FYY\)
\(Y \rightarrow X-X\)

The starting rule is \(X\) and as you can see only \(X\) as a move forward \(F\). So \(Y\) doesn’t use forward, it only calls \(X\), turn left, then call \(X\) again.

You need to implement the following functions:

def sierpinski_X(iterations, length, angle):
        """
        This function draw the sierpinski fractal.

        :param iterations: Number of iterations left
        :param length: Length of the forward line
        :param angle: Turn angle
        """

        # Write your code there.
        # Don't forget the case for iteration 0!

def sierpinski_Y(iterations, length, angle):
        """
        This function is part of the sierpinski fractal.
        If iterations is equal to 0 nothing happens.

        :param iterations: Number of iterations left
        :param length: Length of the forward line
        :param angle: Turn angle
        """

        # Write your code there.
        # For iteration 0 you do nothing. You only do something if iterations > 0.

If used as:

sierpinski_X(10, 10, 90)

You should obtain:

1.4. Now try it!

Try your code. Do not hesitate different parameters if you want.

Be careful to not increase iterations too much otherwise it will run for a very very long time.

Important

Once you’re done put back the default parameter for each functions.

1.5. What to submit to Moodle

Submit your work on Moodle.

Your version of asn1.py. Do not submit the .ipynb file. To get the asn1.py file from Colab, see the image below.
- Make sure your NAME and STUDENT NUMBER appear in a comment at the top of the program.

VERIFY THAT YOUR SUBMISSION TO MOODLE WORKED! IF YOU SUBMIT INCORRECTLY, YOU WILL GET A 0

1.6. Some hints

Work on one function at a time.
Get each function working perfectly before you go on to the next one.
Test each function as you write it.
- This is a really nice thing about programming: you can call your functions and see what result gets returned. Does it seem correct?
If you need help, ask! Drop by my office hours.

1.7. Some marking details

Warning

Just because your program produces the correct output, that does not necessarily mean that you will get perfect, or even that your program is correct.

Below is a list of both quantitative and qualitative things we will look for:

Correctness?
Did you follow instructions?
Comments?
Variable Names?
Style?
Did you do just weird things that make no sense?

1.8. General FAQ:

I don’t know how to do X.
- OK, go to google.ca and type in X.
It’s not working, therefore Python is broken!
- Probably not; you’re very likely doing something wrong
Do I have enough comments?
- I don’t know, maybe? If you’re looking at code and have to ask if you should comment it… just comment it. That said, don’t write me a book.
Can I work with my friend?
- No.
I know I cheated, but I’m really sorry. Can we just ignore it this time?
- No
If I submit it at 11:56pm, you’ll still mark it?
- No. 11:55pm and earlier is on time. Anything after 11:55pm is late. Anything late is not marked. It’s rather simple really.
I accidentally submitted the wrong code. Here is the right code, but it’s late.
- No.