About The Turtle

The file TurtlePanel.java defines a panel that represents the turtle habitat. The habitat has x-coordinates that range from -10 on the left to 10 on the right, and it has y-coordinates that range from -10 on the bottom to 10 at the top. The turtle starts out in the center, at (0,0), facing to the right. The turtle has a "pen" that can be raised or lowered. If the pen is down when the turtle moves, it leaves a trail: The pen draws a line from the starting point to the point to which the turtle moves.

If turtle is a variable of type TurtlePanel, you give commands to the turtle by calling instance methods of turtle such as turtle.forward(5), turtle.turn(45), and turtle.penUp(). To learn about all the available methods, read the source code file, TurtlePanel.java.

The file TurteGraphics.java contains the main() routine. Currently, it doesn't draw anything. You will add code to this file to make it draw several recursive images. (SierpinskiTurtle.java is a version of TurtleGraphics.java, with code added for drawing a Sierpinski triangle. We looked at this example in class last Friday. You will not work on SierpinskiTurtle.java, but you can use it as an example.

TurtleGraphics.java includes a method delay(t) that causes the program to pause for t milliseconds when it is called. You can use this method to insert a delay into your program, to give the user a better chance to see what is going on. There is also a method turtle.setAutoDelay(t) that tells the turtle to delay for t milliseconds after every action. Both of these methods are used in SierpinskiTriangle.java.

Before you start working on the lab exercises, you might want to try some non-recursive turtle graphics to get more familiar with the concept. For example, try adding the following code at the end of main():

turtle.setTurtleIsVisible(false);
turtle.setAutoDelay(10);
for (int i = 0; i < 360; i++) {
    turtle.randomColor();
    double dist = 10*Math.random();
    turtle.forward(dist);
    turtle.back(dist);
    turtle.turn(1);
}

Or, you could simply draw a square with

for (int i = 0; i < 4; i++ ) {
    turtle.forward(5);
    turtle.turn(90);
}

Recursive Drawing

For your exercises in recursive drawing, you will work entirely in the file TurtleGraphics.java. You will be writing at least four recursive methods. To show your work to the user, I suggest that you program a kind of slide show that shows the user all of your drawings, one after the other. If you want to be fancy, you could show different "levels" of the recursive drawing, as I did for the Sierpinski triangle. The drawing code in the main program might look something like this:

runExercise1();   // (but use better names!!!)
delay(4000);
runExercise2();
delay(4000);
runExercise3();
delay(4000);
runExercise4();

For the first exercise, you should implement the Koch curve, which we looked at in class as an example. You should write a method

   private static void koch( double size, int level )

to draw a Koch curve with a given size and level of recursion. Recall that a true Koch curve is a "fractal" which is made up of 4 smaller sized copies of itself. You can't draw a true Koch curve, but you can draw an approximation. For the approximation, a Koch curve of level 0 is just a line segment. For N > 0, a Koch curve of level N is made up of 4 smaller-sized level (N-1) curves. To draw it with turtle graphics, you need to be careful about the sizes and the angles between the pieces. (Hint: The angles inside an equilateral triangle are 60 degrees.) This picture shows Koch curves of various recursion levels. The last one is a pretty good approximation of the real Koch curve:

The main program should place the turtle at the desired starting point for the curve and then call your koch() method with a reasonable value for the recursion level. Alternatively, you can do something like what I did with the Sierpinski triangle, where I showed a series of triangles with increasing recursion levels.

For the remaining turtle graphics exercises, you should choose at least three of the following recursive drawings, and write recursive methods to draw them:

Recursive "I-bar." An I-bar of level 0 is just a line segment. An I-bar of level N consists of a line segment with a smaller-sized, rotated I-bar of level (N-1) on each end. (Hint: The turtle should start at the center of the bar and should return to that position after drawing the bar.)

Sierpinski carpet. A Sierpinski carpet of level 0 is just a square. A Sierpinski carpet of level N consists of 8 1/3-sized Sierpinski carpets of level (N-1). The picture shows a level-5 carpet. It takes a long time to draw a carpet with level greater than 5, but there is a bigger picture of a level-6 carpet at this link.

Improved tree. This is a version of the tree example that we covered in class, in which I have varied the color and line width while drawing the tree. (Level-0 trees are drawn in green.) A level-4 tree and a level-7 tree are shown.

Square Koch. This is a version of the Koch curve that uses squares instead of triangles. Square Koch curves of level 1, 2, and 8 are shown.

C Curve. A rather pretty thing, composed of two copies of itself at a 90 degree angle. A level-0 curve is a line segment. To get a level-N curve, start by turning 45 degrees, draw the two level-(N-1) curves, then turn 45 degrees again so you are facing in the original direction. If size is the size of the level-N curve, the size of each smaller curve is size/Math.sqrt(2). The pictures were drawn by ccurve(8,1), ccurve(8,3), and ccurve(8,12).

Random Factors. It's interesting to add some randomness to recursive drawing. The pictures were drawn by two different versions of the tree algorithm with some randomness added. The one on the right has a chance of having side branches on each stem. You could try to do something similar, or you could think up your own random recursion.

Maze Solver

The final exercise uses the files MazePanel.java and MazeSolver.java. You will only work on MazeSolver.java, which contains the main() routine for the program. If you run MazeSolver without making any changes, it will open a window showing a randomly created maze. (It doesn't do anything else -- you can just close the window.)

The MazePanel class defines the panel that creates and displays the random maze. The maze is made up of a grid of small colored squares. Black squares represent "walls" and white squares represent "corridors." Note that there is a border of black squares all around the edge of the maze. (There is no exit from the maze!)

MazeSolver.java has a global variable named maze of type MazePanel. This variable has the following methods, which you can use in the program:

• maze.getColor(r,c) -- Returns the color of the square in row r, column c. When the maze is first created, all the squares are either or white.
• maze.setColor(r,c,color) -- Set the color of the square in row r, column c to color. The color should be non-null.
• maze.getRows() -- Returns the number of rows in the maze.
• maze.getColumns() -- Returns the number of columns in the maze.

Your job is to add a method to MazeSolver.java that will solve the maze. The maze is considered solved if you find a path from location (1,1) to location (maze.getRows()-2,maze.getColumns()-2). These points are the upper left and lower right white squares in the original maze. You should mark the path by setting its color to something other than black or white. You might also want to color squares that your method visits while it is searching for the solution. Here is a picture of a maze that shows the solution in red; other squares that were visited during the search are colored yellow:

The essential idea of the recursion is: "to solve the maze from (x,y), move one square from that position and try to solve it from there." It's possible that you might try all four directions from (x,y) without finding a solution. One interesting point is how to end the process once you find a solution, since at that point you will be deep in the recursion. One nice way to do it is to return a boolean value from the method. If you find a solution, you can immediately return true; if you try all four directions without finding a solution, you can return false. (Another way to get out of a deep recursion is to throw an exception.)

Your program can simply call the solver method at the end of the main() routine. You might need to call maze.repaint() at the end of main() to get the solved maze to show up.

If you want to do something fancier than simply showing the final solution, copy the delay() method from TurtleGraphics.java. In the main program, add a delay of a few seconds after the call to window.setVisible. This will give the user a chance to see the unsolved maze. Then, in your solver method, insert short delays in the process, and follow each delay by maze.repaint() to refresh what is shown on the screen. This will let the user see the process of solving the maze. To get even more fancy, make an infinite loop in which you repeatedly make new random mazes -- by calling maze.create() -- and solve them. The program will end when the user closes the window.

You might also want to make a bigger maze, say "new MazePanel(150,200,5)"