Turtle Graphics 2:  Fractals

Comp 110 Course Module 11b

Our goal in this module is to build turtle fractals, weird shapes that are exactly the same at every level of detail.  We begin by reintroducing some of the turtle programs we created in Module 11a.  Then we shall go on to study techniques for writing recursive turtle programs to generate fractal curves.

Turtle Global Variables:  Position, Direction, and Turtlepath

init:=Module[{},position ={0,0};direction={1,0}; turtlepath={}]

Turtle Commands:  Forward, Move, Turn, and Resize

forward[dist_]:=Module[{oldposition=position},position=oldposition + dist(direction);AppendTo[turtlepath,Line[{oldposition,position}]]];



move[dist_]:=position=position + dist(direction)


turn[angle_]:=direction=N[ direction .(({{Cos[angle Degree], Sin[angle Degree]}, {-Sin[angle Degree], Cos[angle Degree]}}))]


resize[scalefactor_]:=direction=N[ direction .(({{scalefactor, 0}, {0, scalefactor}}))]

Turtle Display

displayturtlepath[r_,g_,b_, t_]:=Graphics[{RGBColor[r,g,b],Thickness[t],turtlepath},AspectRatio->Automatic,PlotRange->All,ImageSize->200]

Polygons

poly[numsides_]:=Do[forward[1];turn[360/numsides],{numsides}];

Shift, Spin, and Scale

shift[program_,parameterList_,n_,dist_]:=Do[Apply[program,parameterList];move[dist],{n}];

spin[program_,parameterList_,n_,angle_]:=Do[Apply[program,parameterList];turn[angle],{n}];

scale[program_,parameterList_,n_,scalefactor_]:=Do[Apply[program,parameterList];resize[scalefactor],{n}];

Fractals -- Recursion Made Visible

What are fractals?  We have seen fractals before:  Julia sets, the Mandelbrot set, and fractals generated from Newton interation.  We shall now use LOGO to generate some new fractals.  What are fractals?  From the turtle's point of view, fractals are simply recursion made visible.   Here we shall write simple recursive turtle programs to generate several interesting kinds of fractals, including gaskets, snowflakes, quilts, and trees.

Sierpinski Gasket

The first type of fractal we shall investigate is called a gasket.  Below is a picture of the Sierpinski gasket.
			
How do you write a turtle program to generate the Sierpinski gasket?  Don't panic.  You don't have to give the turtle thousands of forward and turn commands to generate this figure.  A simple recursive program will do the job.
The key observation is that the big gasket is made up of three identical smaller gaskets.  A Sierpinski gasket is just three smaller Sierpinski gaskets joined together.  This definition of the Sierpinski gasket would be circular, if we did not have a base case at which to stop.  So we shall say that a very small Sierpinski gasket is just a small triangle.
The structure of the sierpinski program must be something like the following:
	To make a large gasket, 
		Make a smaller gasket at one of the corners.
		Then move to another corner and make another small gasket.
		Then move to the third corner and make another small gasket.
		Then return to the turtle to her original state (location and heading).
The moves can be made with move and turn commands;  the rescaling is achieved with resize commands.  To make the smaller gaskets requires three recursive calls to the sierpinski program.  Form follows function!   By the way, why do you think you have to return to the turtle to the state in which she started?
Below is the Mathematica program sierp for generating the Sierpinski gasket.  It's short and simple.  There is only one variable, the variable level which is the number of levels of recursion.  Six levels will usually suffice.  We use Manipulate to illustrate the Sierpinski gasket for different levels of recursion.  (Note:  The use of TrackedSymbols speeds up the Manipulate procedure.)

Clear[sierp];

sierp[level_]:=If[level==0,poly[3],Do[resize[1/2];sierp[level-1];resize[2];move[1];turn[120],{3}]]

Manipulate[Module[{},init;sierp[level];displayturtlepath[0,0,0,.0025]],{level,Table[k,{k,0,6}]},TrackedSymbols:>{level}]

Exercises

1.  Use the buttons above to see what the sierpinski gasket looks like after different levels of recursion.
2.  Apply the spin and scale procedures to the sierp program to generate some interesting new fractals.
3.  The base case for the sierp program is a triangle.  Experiment with different base cases.  Replace poly[3] in the base case with poly[numsides] and add numsides as a parameter to sierp[level, numsides], but do not make any other changes to the sierp program.  Use Manipulate to build buttons to control the number of sides of the polygon in the base case in the same way that Manipulate controls the number of levels.  What do you observe now when you run this new version of the sierp program for several levels of recursion?

Square Gaskets

We can generalize the program for the Sierpinski gasket to generate gaskets for arbitrary polygons.  Here we will look at square gaskets.  The structure of the program squaregasket[level, scalefactor] is almost identical to the structure of the sierp program, except that there is a gasket (a recursive call surrounded by resize commands) in each corner of the square.

Exercises

1.  Write the code for the program squaregasket[level, scalefactor].

2.  Use Manipulate to create a slider to control the size of the scalefactor, and build some fractal square gaskets with different values of the scalefactor.  What happens if you choose scalefactor = 1/2?

Snowflakes

Snowflakes make interesting fractals.  Below is the fractal known as the Koch snowflake.  Notice its sixfold symmetry.  This curve has an amazing property:  it is continuous everywhere, but differentiable nowhere.  That is, the Koch snowflake is pointy at every point on the curve.  You are going to generate the Koch snowflake using your turtle.

There is a simple trick for generating the Koch snowflake and other snowflakes as well.  Consider the following simple triangular pulse:  

To generate one part of the Koch snowflake, replace every line in this figure by this triangular pulse, scaled to 1/3 the size of the line.  Now you have:

Repeat this process again and again until the bumps are very small --  that is, replace each line by a triangular pulse 1/3 the size of the line.  This procedure builds 1/3 of the Koch snowflake.


How do you generate the code koch for this part of the Koch snowflake.  Easy.  There are four recursive calls.
	To make a large koch curve, 
		Make a smaller koch curve along one of the edges of the original triangular pulse.
		Then move to the next edge and make another small koch curve.
		Then move to the next edge and make another small koch curve.
		Then move to the last edge and make another small koch curve.
Below is the Mathematica program for koch.  Notice that the base case is simply a straight line.  (To begin the recursion, we replace the straight line with a triangular pulse.)

Clear[koch];

koch[level_]:=If[level==0,forward[1],resize[1/3];
koch[level-1];turn[60];koch[level-1];turn[-120];koch[level-1];turn[60];koch[level-1];resize[3]]

Manipulate[Module[{},init;koch[level];displayturtlepath[0,0,0,.0025]],{level,Table[k,{k,0,6}]},TrackedSymbols:>{level}]

Exercises

1.  Use the buttons above to see what the koch curve looks like after different levels of recursion.
2.  Apply the spin program to rotate the koch curve three times through -120 degrees.  You should get the Koch snowflake.
3.  The base case for the koch program is can be either a straight line or a triangular pulse.  Experiment with a square pulse (see below) in the base case.  Write a helper function sqpulse and replace the forward command in the base case with the program sqpulse, but do not make any other changes to the koch program.  What do you observe now when you run this new version of the koch program for several levels of recursion?

A square pulse.

Quilts

Next we introduce a recursive turtle program sqkoch that generates fractals based on the square pulse pictured below.  To generate this fractal curve, you are going to replace every line in this figure by this square pulse, scaled to 1/3 its size.  Then you will repeat this process again and again until the bumps are very small.

Afterwards, you will write another program quilt that uses the sqkoch program to generate the closed quilt like curve pictured below.

Exercises

1.  Write the code for the program sqkoch[level].  (Hint:  The easiest way to write the code for sqkoch is to start with your sqpulse procedure and replace every forward command with a recursive call to sqkoch.  Remember to add a base case and to restore the turtle to her initial size at the end of the program -- compare to the program for the koch curve.)

2.  Use Manipulate to build buttons to control the level of recursion in sqkoch.

3.  Use the buttons above to see what the sqkoch curve looks like after different levels of recursion.
4.  Apply the spin program to rotate the sqkoch curve to generate the square quilt depicted above. 
5.  Apply the spin program to rotate the sqkoch curve to generate the fractal star depicted below.

A fractal star.

Turtle Fractals

Every recursive turtle program generates a fractal curve.  When writing turtle programs to generate specific fractals, you should always be able to answer the following questions.
1.  Where does the turtle start?
2.  Where does the turtle finish?
3.  How many recursive calls must the turtle make?
4.  What are the scale factors?
5.  What are the turtle transitions (move and turn commands) between recursive calls?
Notice, by the way, that when you write a turtle program to generate a fractal, you do not need to worry too much about the base case.  Why?

The most common mistake students make in writing recursive turtle programs to generate specific fractal curves is failing to return the turtle to her original state.  Not all fractals require that the turtle must return to her original state, but if the curve resulting from your recursive turtle program does not produce the desired result, the first thing you should check is whether you have restored your turtle to the proper state at the end of your recursive procedure.

More Fractals

Below are some exercises to help you hone your ability to build recursive turtle programs to generate specific fractals.

Another Square Gasket

Exercises

1.  Write the code for the program to generate the square gasket depicted above.  (Hint:  How many recursive calls should appear in your program?  Be sure to bring your turtle back to where she started.)

2.  Use Manipulate to build buttons to control the level of recursion.  (Warning:  This program takes a long time to run because there so are many recursive calls.  Therefore to save time, you should test only the first four levels of recursion.)

C-Curve

The simplest pulse fractal is the C-curve shown below.  

The C-curve looks complicated, but it is simply the pulse fractal generated by starting with a straight line and recursively replacing each straight line with the right angle depicted below.

Exercises

1.  Write the code for the program to generate the C-curve illustrated above.  (Hint:  How many recursive calls should appear in your program?  What is the scale factor?)

2.  Use Manipulate to build buttons to control the level of recursion.  You may need at least a dozen levels of recursion to get a good picture of the C-curve.

Fractal Hangman

Exercises

1.  Write the code for the program to generate the fractal hangman depicted above.  (Hint:  How many recursive calls should appear in your program?  Be sure to bring your turtle back to where she started.)

2.  Use Manipulate to build buttons to control the level of recursion.

Fractal Trees

We can also generate somewhat realistic looking trees using recursive turtle programs.   To make the following tree, first make the tree trunk, then make the left subtree, then make the right subtree, and return the turtle to her initial state.

Exercises

1.  Write the code for the program to generate the fractal tree depicted above.  (Hint:  How many recursive calls should appear in your program?  Be sure to bring your turtle back to where she started.)

2.  Use Manipulate to build buttons to control the level of recursion and the angle between the branches of the tree.