CIS 3020 Project 4

From In The Wings
Jump to navigation Jump to search

Introduction

In this exercise, you will use a simple string language to define shapes that will be drawn using the Turtle and Island classes. The shapes that you draw will be fractal shapes defined with a generator and interpreter that you implement.

Notes

  • One of the problems with this code is that it is a major memory hog. Beyond about five generations, the memory usage by the program gets so big that it crashes due to out-of-memory errors. A rewrite would be necessary in how it handles the iterations in order to make it be able to handle more than a limited number of generations.
    • To do this, we would have to move the drawing stage out from the end to where the end of each branch of a tree iteration would occur.

Background

To talk about figures (or shapes), we need to define a language describing the shape we wish to draw. This language uses a string of characters to represent the actions required to draw some specific shape. One simple language definition is:

  • “F” represents moving forward some distance (the face)
  • “-” represents turning Right some angle (the face angle)
  • “+” represents turning Left some angle (the face angle)

Assume that the face length is 10 units and that the face angle we are turning (either left or right) is 60 degrees. The string “F++F++F” defines an equilateral triangle:

  1. “F” – move forward 10 units,
  2. “+” – turn left 60 degrees,
  3. “+” – turn left 60 degrees,
  4. “F” – move forward 10 units,
  5. “+” – turn left 60 degrees,
  6. “+” – turn left 60 degrees, and
  7. “F” – move forward 10 units.

Fractals consist of a starting shape, called the Initiator, and a pattern, called the Generator. Replacing every side of an Initiator with the Generator creates a new shape, the next generation Initiator. For example, suppose our Initiator is the equilateral triangle defined above (“F++F++F”) and our Generator is the string “F-F++F-F”:

Initiator 0: F++F++F Generator: F-F++F-F

Replacing every “F” in Initiator 0 with the Generator creates Initiator 1 shown below. Note the use of color in Initiator 1 and the fact that Initiator 1 is scaled so its overall size is 10 units on a side (the original side length). Each group of red characters is a Generator that has replaced one “F” in Initiator 0. The black “+”s correspond to the two groups of two “+”s in Initiator 0.

Initiator 1: F-F++F-F++F-F++F-F++F-F++F-F

Subsequent generations (Initiator 2, Initiator 3, etc.) are generated in a similar manner: replacing each “F” with the Generator string.

To simplify the process of specifying and drawing a snowflake, we will use two classes, a Generator class and an InterpreterTurtle class. The Generator class will be used to create a string representing one side of the polygon that we will draw. The side will be constructed so the direction that we are facing is the same when we start and end the drawing of the side. This only occurs when the string representing a side contains an identical number of left and right turns and is reversible (it looks the same going forwards or backwards through the string) A string having these characteristics is defined to be balanced. As a result, Generator strings must be balanced. For example, the string “F-F+F+F-F” is balanced and could represent a side or Generator, while “F- F+F+F” is not and could not be used.

The InterpreterTurtle class will use the string created by the Generator class to draw the actual polygon. A method in the class (drawPolygon) will cause each side of the polygon to be drawn, turning the appropriate angle between each side.

UML Diagram

Project4.png

Code

Generator.java

public class Generator {

  // We want initiator to be null initially.
  // Should it be private as well?
  private String initiator = "";

  // This method allows us to reinitialize the the initiator string in
  // this object back to a null string. This way it is possible to use
  // the same object over and over again for different generations.

  public void initialize () {
    this.initiator = "";
  }

  public String generate (String initiator, String generator, int n) {
    /* Recursively calls the nextGeneration() method 'n' times. Each
       call to nextGeneration() will create the next generation's initiator
       string. This method returns the 'n'th generation string.
    */
    if(n > 0) {
      // Basically we degenerate n here so that we get the number of loops
      // right. Yes, a for statement would probably work a heck of a lot
      // easier, but this is an excercise in recursion.
      initiator=nextGeneration(initiator,generator);
      //      System.out.printf("Current initiator: %s\n", initiator);
      n--;
      generate(initiator, generator, n);
    }
    return this.initiator;
  }

  private String nextGeneration(String initiator, String generator) {
    /* Recursively constructs and returns the next generation string given
       a generator and an initiator. That is, this method traverses the
       initiator string constructing a new string. Every occurrence of the
       character 'F' is replaced with the generator string.

       For example: suppose our initiator is 'F-F++F-F' and the Generator
       is 'F-F++F-F'. This method should return the string
       'F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F'

       Basically we will use string functions to add in the initiator to
       the generator wherever one of them there pesky F's occur. Otherwise
       we just re-inject a hyphen or plus sign. We will also check to make
       sure that no other characters appear in the generator.
    */
    /* This is old code. Let's try something else instead...

    if (generator.length() != 0) {
      String command = generator.substring(0,1);
      if (command.equals("F")) {
        this.initiator.concat(initiator);
        return nextGeneration(initiator, generator.substring(1));
      } else if (command.equals("+") || command.equals("-")) {
        this.generator.concat(command);
        return nextGeneration(initiator, generator.substring(1));
      } else {
        return "Error!";
      }
    } else {
      return this.generator;
    }

    */

    if (initiator.length() == this.initiator.length()) {
      this.initialize();
    }
    if (initiator.length() != 0) {
      // Get the first character in the initiator string.
      String command = initiator.substring(0,1);
      // Parse the command.
      if (command.equals("F")) {
        // This next step took WAY too much time to figure out!
        this.initiator = this.initiator.concat(generator);
        // Recursively go back through this generation step, using the
        // current initiator value minus the first character. As we
        // step through it, the initiator string will get shorter and
        // shorter, eventually becoming nothing, at which point we
        // return the full value of this.initiator. Of course, we
        // could have simply done a for loop using the length of
        // the supplied initiator string as the count length, but again
        // this is a lesson in recursion.
        nextGeneration(initiator.substring(1), generator);
      } else if (command.equals("+") || command.equals("-")) {
        // Almost messed up here. This also need to be pushed into
        // itself.
        this.initiator = this.initiator.concat(command);
        nextGeneration(initiator.substring(1), generator);
      } //end if
    }//end big if (length != 0)
    return this.initiator;
  }//end next generation
}

InterpreterTurtle.java

public class InterpreterTurtle extends Turtle {
  /* The public drawTriangle(), drawRectangle(), drawPentagon(),
   * drawHexagon(), each utilize drawPolygon().
   *
   * In this case, all of the shape drawing methods receive a faceAngle
   * value. As far as I can determine, this faceAngle value is the angle
   * at which we should turn once we are done drawing the shape, and
   * therefore should not be passed onto the drawPolygon method. Instead,
   * the drawPolygon method should have sent to it an angle at which it
   * should use to make that particular polygon.
   */


  public void drawTriangle(String instruction, double faceLength, double
                      faceAngle) {
    /* Calls the drawPolygon() specifying to draw 3 sides.
     */
    drawPolygon(instruction, 3, faceLength, faceAngle, 120);
    this.turnRight(faceAngle);
  }

  public void drawRectangle(String instruction, double faceLength, double
                       faceAngle) {
    /* Calls the drawPolygon() specifying to draw 4 sides
     * Not sure why this is called a drawRectangle method, as in the
     * specification it states that there are only the three arguments.
     * How can you draw a rectangle if you only have one length value?
     * Basically, every rectangle we draw will in actuality be a specialized
     * version of a rectangle, commonly known as a square.
     */
    drawPolygon(instruction, 4, faceLength, faceAngle, 90);
    //this.turnRight(faceAngle);
  }

  public void drawPentagon(String instruction, double faceLength, double
                      faceAngle) {
    /* Calls the drawPolygon() specifying to draw 5 sides
     */
    drawPolygon(instruction, 5, faceLength, faceAngle, 72);
    this.turnRight(faceAngle);
  }

  public void drawHexagon(String instruction, double faceLength, double
                     faceAngle) {
    /* Calls the drawPolygon() specifying to draw 6 sides
     */
    drawPolygon(instruction, 6, faceLength, faceAngle, 60);
    this.turnRight(faceAngle);
  }

  private void drawPolygon(String instruction, int numberOfSides,
                           double faceLength, double faceAngle,
                           int sideAngle) {
    /* This method recursively applies the drawSide method to draw each
       side of the polygon, turning the appropriate angle (based on the
       number of sides) between each side.
    */
    if(numberOfSides > 0) {
      numberOfSides--;
      drawSide(instruction, faceLength, faceAngle);
      this.turnRight(sideAngle);
      drawPolygon(instruction, numberOfSides, faceLength, faceAngle,
                  sideAngle);
    }
  }

  private void drawSide(String instruction, double faceLength, double
                        faceAngle) {
    /* This method processes (using the method interpret) the instruction
       string one character at a time.
    */
    char command[];
    if (instruction.length() != 0) {
      command = instruction.toCharArray();
      interpret(command[0], faceLength, faceAngle);
      drawSide(instruction.substring(1), faceLength, faceAngle);
      //      System.out.printf("command %s\n", command[0]);
    }

  }//end drawSide

  private void interpret(char instruction, double faceLength, double
                         faceAngle) {
    /* This method should interpret the given instruction and command the
       turtle to draw a line of length faceLength or turn right or left the
       angle faceAngle.
    */
    if (instruction == 'F') {
      // Don't forget to put our tail down!
      this.tailDown();
      this.move(faceLength);
      this.tailUp();
    } else if (instruction == '+') {
      this.turnLeft(faceAngle);
    } else if (instruction == '-') {
      this.turnRight(faceAngle);
    }
    /* Need an error catch here! */
  }//end interpret method

  public void noDrawSide(String instruction, double faceLength, double
                        faceAngle) {
    /* This method processes (using the method interpret) the instruction
       string one character at a time.
    */
    char command[];
    if (instruction.length() != 0) {
      command = instruction.toCharArray();
      noDrawInterpret(command[0], faceLength, faceAngle);
      noDrawSide(instruction.substring(1), faceLength, faceAngle);
      //      System.out.printf("command %s\n", command[0]);
    }

  } //end noDrawSide

  private void noDrawInterpret(char instruction, double faceLength, double
                         faceAngle) {
    /* This method should interpret the given instruction and command the
       turtle to draw a line of length faceLength or turn right or left the
       angle faceAngle.
    */
    if (instruction == 'F') {
      // We don't want to draw this time around!
      this.move(faceLength);
    } else if (instruction == '+') {
      this.turnLeft(faceAngle);
    } else if (instruction == '-') {
      this.turnRight(faceAngle);
    }
  } //end noDrawInterpret method

}

Snowflake.java

public class Snowflake {
  public static void main (String[] args) {
    // Create strings for the initiator and generator.
    String initiator = "F";
    String generator = "F-F++F-F";
    // Create a constant GENERATIONS
    final int GENERATIONS = 3;
    // Create a constant FACEANGLE
    final int FACEANGLE = 60;
    // Create a constant SIDES.
    final int SIDES = 6;
    // Instantiate a Generator object and generate the specified generation
    // of the initiator string.
    Generator G0 = new Generator();
    G0.initialize();
    initiator = G0.generate(initiator, generator, GENERATIONS);

    // The initial faceLength should be 300. This should be scaled using
    // GENERATIONS and the scale() method provided above.
    final int FACELENGTH = 300;

    // Create an InterpreterTurtle, an Island, and associate them. The island
    // created should be 400x400.
    InterpreterTurtle T0 =  new InterpreterTurtle();
    Island I0 = new Island(400,400);
    I0.putTurtleAtCenter(T0);

    // Generate our scaleFactor
    int scaleFactor = 5 * SIDES * GENERATIONS;

    // Based on the value of SIDES, draw the appropriate fractal centered on
    // the island.

    // First, let's figure out where the center, or at least our starting
    // point relative to the center, should be. To do this, first we need
    // to find out just how long a distance we actually travel when drawing
    // a side...
    double X0 = T0.getPositionX(); // Our original X position
    double Y0 = T0.getPositionY(); // Our origin at Y
    T0.noDrawSide(initiator, scale(FACELENGTH, scaleFactor), FACEANGLE);
    double sideLength = T0.getPositionX() - X0; // Our distance travelled

    // Now we have a distance. So, depending on how many sides we have
    // we can now determine the best X and Y position to start at relative
    // to our origin. We can also draw the shape right after this.
    if (SIDES == 3) {
      double X1 = X0 - (sideLength / 2);
      double Y1 = Y0 - (3 * sideLength / 8); /* Needed some basic geometry
                                                for this one. */
      T0.moveTo(X1,Y1);
      T0.drawTriangle(initiator, scale(FACELENGTH, scaleFactor), FACEANGLE);
    } else if (SIDES == 4) {
      double X1 = X0 - (sideLength / 2);
      double Y1 = Y0 - (sideLength / 2);
      T0.moveTo(X1,Y1);
      T0.drawRectangle(initiator, scale(FACELENGTH, scaleFactor), FACEANGLE);
    } else if (SIDES == 5) {
      double X1 = X0 - (sideLength / 2);
      double Y1 = Y0 - ((sideLength / 2) * (Math.tan(Math.toRadians(54))));
      // Yes, more basic geometry
      T0.moveTo(X1,Y1);
      T0.drawPentagon(initiator, scale(FACELENGTH, scaleFactor), FACEANGLE);
    } else if (SIDES == 6) {
      double X1 = X0 - (sideLength / 2);
      double Y1 = Y0 - (sideLength * (4 / 3));
      T0.moveTo(X1,Y1);
      T0.drawHexagon(initiator, scale(FACELENGTH, scaleFactor), FACEANGLE);
    }
    // In our review, the TA will change the value of SIDES and GENERATIONS
    // so different fractals are drawn.
  }

  private static double scale(double length, int scaleFactor) {
    double newLength = length / scaleFactor;
    return newLength;
  }
}