• If you are on linux, you can use peek
• On windows, try using screentogif
• On mac, use the built-in screen recorder to get a .mov. Then use this site to convert that to a .gif.

• Names of all group members
• instructions on running your project
• any libraries it depends on
• Key features added since the last submission (i.e. new features since MVP, since PoC)

    Download the following template zip
    NOTE:
    - new methods have been added to the ExpressionTreeClasses, skim over them

    Add the following:

    ExpressionTreeNode (these functions are short and straightforward:)
        - ExpressionTreeNode(int x, int y, String token)
        - int nodeTypeFromString(String token)

    ExpressionTree (this function is the complex one:)
        - ExpressionTreeNode makeTreePrefix(int x, int y, StringList tokens, int numLevels)

    
    HINTS:
        For laying out the nodes, makeParseTreePrefix takes a depth
        You can use depth like so:  float xoffset = width / (pow(2, depth+1));

        for the expressionTreeNode(..., String token) constructor:
        The call to this(...) will call the other constructor to initialize most of 
        instance variables. The "token" constructor just needs to set
        the type and value according to what token string is passed in.
        Do JUST the following:
            - set type = nodeTypeFromString(token)
            - if type is VAL, set value to the numeric value of the token string

        for makeParseTreePrefix():
            - the very first thing you should do is:
                - String currToken = tokens.remove(0);
                - make a node from the first token
            - then, think about how to recurse
            - it may be helpful to println(x, y, depth, tokens) as the first
              statement in makeParseTreePrefix, to see what it's doing on the recursions
        

    Challenge:

    To allow for infix expressions, make the following changes:

    Modify makeParseTreePrefix() to handle "(" and ")" in the token list.
        for prefix expressions, you can just ignore them. Test it on prefix2 in the driver

    Add a parameter to the ExpressionTree constructor to determine the type of expression.
        Example header: ExpressionTree(int x, int y, String expression, int expType).
    Write ExpressionTreeNode makeTreeInfix(int x, int y, StringList tokens, int numLevels)
        Generate an expression tree from an infix expression, using the algorithm described in class.

    Modify the driver file so that when it is run, 2 trees are created, one from the provided prefix expression and the second from the infix expression
    

• The left and right subtree chances are linked: i.e. either both children are present or both are null
• ExpressionTreeNodes no longer have a char data;, they now have a int type and a float value. makeTree initializes both of these to 0.

1. Fill in the function populateTree() to initialize the tree nodes to represent a random arithmetic expression.
2. Modify inOrder() to produce an infix expression string representing the tree, e.g. "(1.0 + (2.0 / 3.0))"
3. Fill in the function evaluate() to evalue the arithmetic value of the expression.

    Using processing to create a graphical program.
    Using the keyboard & mouse for input.
    Writing code using the major control structures in Java such as methods, conditional statements and loops.
    Writing classes. (All projects must include at least 1 class)
    Using subclasses and inheritence.
    Data structures:
        1 dimensional arrays.
        2 dimensional arrays.
        ArrayLists.
        Linked Lists.
        Trees
    Image processing.
    Genetic algorithms.
    Using processing libraries.

Phase 0: Proposal

• Names of all people working on the project.
• Pick one person to be the group's representative
• High level description of the project. (Include a link if applicable)
• Any processing libraries you might be using.
• An initial description of how topics from this course will be used to help create the project.

Phase 1: Design Document

• List of classes you will be using. Include a description of the purpose of each class/file.
  • For classes, be sure to describe to main features for that class. As well as the key methods.
• List of concepts from this course that will be used and how you will be using them.
• If applicable, any libraries you will be using and why.
• Description of how the user will interact with your program.
• Specific keyboard commands? Mouse interaction?
• Mock-up drawing of your program in action.
• If you will have different screens, a drawing for each one.
• Annotate your drawing by pointing out important features, interactions, etc.
• Come up with 3 distinct phases of development for your project:
  1. Phases are "proof of concept", "minimum viable project", "final goal"
  • Proof of Concept: Smallest set of features to get something interactive. e.g. for tetris, just get a grid, different block falling, keyboard to move left and right. No rotation, no stacking, no line clearing, nothing extra.
  • Minimum Viable Project: Smallest set of features you'd need to be able to say "it's ugly but it all works". e.g. for tetris, once you have block stacking, block rotating, and line clearing, you can say "this is a working game of tetris", even if not polished.
  • Final Goal: All the features and polish you would like to have at the end: e.g. for something like tetris, maybe a score indicator, levels, next-piece indicator, visual effects, improved user interaction, fast drop, etc.
  2. Each phase should have a description, as well as multiple specific bulletpoints and sub-points of things it should have
  3. Each phase should have a mock-up drawing of what it should look like

    Change makeTree so that left and right subtrees are only sometimes made.
        Near the root, the chance should be high, so subtrees are almost always made.
        At deeper levels, the chance should be lower.
    

    int numNodes(TreeNode current)
        Return the number of total nodes of the tree rooted at current.
    int getHeight(TreeNode current)
        Return the height of the tree rooted at current
    void colorCode(TreeNode current)
        Check the heights of currents left and right subtrees.
        If the heights are equal, change the color of the current node to yellow.
        Recursively colorCode the rest of the nodes in the tree rooted at current.
        

    Modify TreeNode to contain a char data instance variable.
    Modify makeTree so that it provides each new node with a randomly chosen character.
    Add a String preOrder(TreeNode tn) method to your Tree class. It should return the string created by doign a pre-order traversal of the tree rooted at tn.
    Then create postOrder and inOrder methods.


    Also: if you want to lay out your nodes evenly, use this code:

        float xoff = width / (pow(2, (this.totalLevels - numLevels) +2));
        float leftx = x - xoff;
        float rightx = x + xoff;

    Instance Variables:
        TreeNode root
        int totalLevels: The height of the tree

    Methods:
        Constructor: Tree(int x, int y, int numLevels)
            Set totalLevels to numLevels
            Use makeTree (describe below) to create a tree with numLevels,
            assign the return value from makeTree to root
        TreeNode makeTree(int x, int y, int numLevels)
            If numLevels is 0 or less, return null
            Create a new node at (x, y)
            Create a left subtree with numLevels-1 levels
            Create a right subtree with numLevels-1 levels
            return the root of the tree you just created
        void display(TreeNode current)
            Draw the tree rooted at current
    

    Tree fir;

    void setup() {
        size(800, 500);

        fir = new Tree(250, 20, 4);
        fir.display(fir.root);
    }//setup
    

In makeTree, create each node such that each level is evenly spaced across the screen. The space between sibling nodes should decrease with each level and always fit in the screen. The y values should increase by the same amount for each level.

• In your driver file, create at least 5 TreeNodes, and call display on them all in your draw() method.
• Link the .left and .right links of your treenodes together to make a tree with at least 3 levels.
• Write a function recursiveDisplay(TreeNode t), that displays the node t, then recurses on its .left child and its .right child. Change your draw() to only call recursiveDisplay() on the root node of the tree. Your recursive display should display all the nodes.

    Add the following 2 methods to OrbList
        OrbNode findNextNode(float x)
            Return the left-most OrbNode to the right of the coordinate x.
            front should never be returned, so if x is to the left of front, return the node after front.
        void insertBefore(OrbNode n, int x, int y, boolean fixed)
            Create a new OrbNode or FixedOrb at (x, y).
            Insert the new orb into the list before orb n.
            Youn can assume that n is an orb in the list and that it is not front.
    Use findNextNode and insertBefore in your driver file to modify how orbs are added to the list.
    

    void addFront(int x, int y, boolean fixed)
        - Create a new OrbNode or FixedOrbNode at position (x ,y).
            If fixed is true, make it a fixed node.
    void append(int x, int y, boolean fixed)
        - Create a new OrbNode or FixedOrbNode at position (x ,y).
            If fixed is true, make it a fixed node.
    void applyExternalForce(PVector f)
        - Apply f to every node in the list.
        

Create a single OrbList object;
- Add at least 4 orbs to the list.
    - Make at least 1 of the orbs fixed.
- Use applySprings() on the list.
- Use applyExternalForce to apply a downward gravity-like force to the list.
- Call run() on the list.
- Use display() on the list.
        

    OrbNode front
    OrbNode back

    Constructor: OrbList()
        Creates an empty OrbList
    void addFront(int x, int y)
        Create a new OrbNode at position (x ,y).
        Add the new node to the front of the list.
        Make sure to correctly set the next and previous of any impacted nodes.
        Also remember this will modify front, and may also modify back.
    void append(int x, int y)
        Create a new OrbNode at position (x ,y).
        Add the new node to the end of the list.
        Make sure to correctly set the next and previous of any impacted nodes.
        Modify back as needed (and possibly front).
    void run()
        Loop through the list to call run on each OrbNode object;
    void applySprings()
        Loop through the list to call applySpringForce on each OrbNode object;

    Create a single OrbList object;
    Add at least 3 orbs to the list.
    Call run() on the list.
    Use display() on the OrbList.

        OrbNode front
    

        Constructor: OrbList(int x, int y)
            Create a new OrbNode at the provided coordinates.
            Set front equal to the new node.
        void display()
            Start at front, call display().
            Continue to call display() on all subsequent nodes until you reach the end of the list.
            This is a new design pattern for you. Things to consider:
                How do you know when you have reached the end of the list?
                How will you repeatedly move to the next node? (hint: for loops are most often used with numeric counters, is there another kind of look you know about?)
        void addFront(OrbNode o)
            Add o to the front of the list.
            Make sure to correctly set the next and previous of any impacted nodes.
            Also remember this will modify front
        void append(OrbNode o)
            Add o to the end of the list.
            Make sure to correctly set the next and previous of any impacted nodes.
            Also, you’ll have to get to the end of the list using a simlar process to what you did in display.
    

        Create a single OrbList object;
        Create 3 OrbNodes, add them to the OrbList using a combination of addFront and append.
        Use display() on the OrbList.
    

        Member variables
            OrbNode next
            OrbNode prev
        Constructor
            set next and prev to null
        display()
            if there is an OrbNode attached at next, draw a line between this and next
            if there is an OrbNode attached at prev, draw a line between this and prev
            The lines should be different colors, and should be slightly offset so you can see both
        applySpringForce()
            if there is an OrbNode attached at next, use calculateSpringForce to find the force between this and next, and apply that force to this
            if there is an OrbNode attached at prev, use calculateSpringForce to find the force between this and prev, and apply that force to this
        

        Create 3 OrbNodes spaced horizontally, spaced appropriately apart so their springs are somewhat stretched.
        Connect each OrbNode to its neighbors using next and prev appropriately
        in runAStep(), have the right 2 nodes useApplySpringForce(), apply gravity to them, and run() them
        The leftmost node should stay fixed in place
        

• The current length of the spring is the distance between the center of this orb and the anchor orb. Make sure you use the euclidean distance formula, or use the built-in PVector.dist(...) to calculate this.
• Once you have the current length, calculating the displacement and thus the spring force should all be the same as yesterday's.
• When you go to return the PVector representing the force, you can't just make a new PVector(0, forceMagnitude). A spring can only apply force along its length, and so your PVector must be going in the same direction as the spring, i.e. from the center of this orb to the center of the other orb. Once you construct a PVector going in the right direction, you can set its magnitude to be your calculated force value by using the setMag() method.

        Instance Variables

            PVector pos //position
            PVector vel //velocity
            PVector nextAccel //acceleration for the next tick
            float psize

        Methods
            Constructor: Orb(int x, int y)
                Set position to a PVector <x, y>.
                Set velocity and acceleration to <0, 0>
            void display()
                Draw a circle at position with diameter psize.
                You may use whatever color you’d like, or add a color instance variable.
            void applyForce(PVector f)
                Add f to nextAccel.
            boolean checkHitXBound(), boolean checkHitYBound()
                2 separate methods, return true if position is past the borders of the screen, taking psize into account.
            void run()
                Add nextAccel to velocity.
                Check the bounds, if the position has gone beyond the screen, multiply the appropriate component of vel by -1.
                Add velocity to position.
                Set nextAccel back to <0, 0> 

        In your orb class
            Add the following constants for springs:
                static final float SPRING_LEN = 50; // "resting" length
                static final float SPRING_CONST = 0.005;
                static final float AIR_DAMPING = 0.995;
            Modify your run method: 
                just before adding velocity to position, slow down velocity by a factor of AIR_DAMPING
            add a method: PVector calculateSpringForceY(Orb other)
                should return the spring force for a spring connecting this and other
                only consider the y-coordinates (i.e. assume the two orbs are directly above each other)

        In your driver file:
            Modify your reset() to create 2 orbs, one above the other
            The top orb should be an "anchor" orb that doesn't move, so don't apply any forces or call run on it
            in your runAStep(), use calculateSpringForceY to apply a spring force to the bottom orb.  

• Rocket
• Gene
• Individual
• Population
• (main driver file)

• Use a PVector object declared in the main driver file, which you can then pass into methods as needed. You will want to draw a rectangle at the location of the target in draw as well. This is a clean and straighforward approach.
• Create a new class to represent the target. The main advantage for this option is it provides a basis to have obstacle objects as well. It is not advised to do this unless you plan to add obstacles or other complications to the assignment.

Planning Stage

1. What parts of Gene, Individual and Population can be used exactly as they already are written? Why?
2. What parts of Gene, Individual and Population will need to be modified? How will you modify them?
3. How are you going to use Gene objects to encode the angles and magnitudes of each move?
4. How is the main driver file going to differ from the regulargon version?

Project

1. Upon starting, a random population of rockets should be created & displayed, along with a target.
2. The rockets should move according to their “programmed” angles and magnitudes until the maximum number of moves have been made.
3. Once the moves have been made, all rockets should calculate their fitness, and display them.
4. The console should display the generation #, along with the best and average fitness values.
5. Nothing should change until m is pressed, at which point a new generation will be created and those rockets will run until completion.
6. New generations should maintain the best rocket from the previous one.
7. Pressing p should result in a new random population.

• Randomize the target and/or starting locations when creating new random populations.
• Highlight the best rocket in some way.
• Allow for different selection mechanisms via a keyboard command.
• Control the mutation rate via keyboard command.
• Add a toggleable "continuous mode" to automatically run the simulation
• Include obstacles in your program. If a rocket hits an obstacle it should stop moving

    Individual mate(Individual partner)
        // Should create a new individual and inherit genes from the parents.
        // Genes should be "crossed over", i.e. pick a random number
        // of genes to copy from one parent, and have the rest
        // copied from the other parent. Also, make sure that
        // which parent goes first is determined randomly each time.
        // Don't forget to use the Gene copy constructor

    void updateFitness(Individual target)
        // Should update the fitness variable
        // fitness should be calculated based on how similar 
        // this individual is to the specified target
        // Make sure that the more similar it is, the higher the fitness
    

    void makeIndividuals()
        // Should initialize two Individuals and mate them
        // together to create a third.
        // Should call setFitness on them.
        // Print out all 3 individuals.

    void draw()
        // Don't need to add anything, but you will need 
        // to uncomment the calls to display
        
    

    Number of sides: Range should be [0, 31]
    Radius           Range should be [0, 63]
    Spin rate:       Range should be [-7,8]
    Red color:       Range should be [0, 255]
    Blue color:      Range should be [0, 255]
    Green color:     Range should be [0, 255] 

    Gene[] chromosome
    RegularGon phenotype
    float fitness // We wont use this just yet, but it will be necessary to implement a genetic algorithm.

    Individual(boolean randInd)
        Initialize chromosome to the correct size.
        If randInd is true:
            Populate chromosome with randomly generated Gene objects of the correct size (the Gene constructor will do all the work here).
            Once all the Gene objects have be created, call setPhenotype()

    void setPhenotype()
        Extract the values of each of the genes in chromosome.
        Create a RegularGon object using those values.
        Set phenotype equal to that object.
    void mutate(float rate)
        Loop through chromosome.
        Each Gene in chromosome should have a rate chance to call mutate on itself.
        call setPhenotype()
    String toString()
        Return a String where each line is the toString of a Gene from chromosome
    void display(int x, int y, boolean showFitness)
        Call display using x and y as parameters on phenotype.
        If showFitness is true write fitness using text at x y

Individual i0, i1;

void setup() {
  size(400, 200);
  i0 = new Individual(true);
  i1 = new Individual(true);

  println(i0);
  println(i1);
}//setup

void draw() {
  background(255);

  i0.display(100, 100, false);
  i1.display(300, 100, true);
}//draw

void keyPressed() {
  if (key == 'p') {
    i0 = new Individual(true);
    i1 = new Individual(true);
  }
  if (key == 'm') {
    i0.mutate(0.1);
    i1.mutate(0.3);
  }
}//keyPressed

• Instance Variables:

    int genotype[]

• Constructors:

    Gene(int gl)
        Generate a new Gene of the given length.
        Initialize the array accordingly.
        Randomly populate the gene with 1s or 0s.
    Gene(Gene copyFrom)
        Create a new Gene that is a copy of copyFrom.
        Remember that arrays work like objects, so genotype = copyFrom.genotype will not create a new copy of the array and will not copy the values over.

• Methods:

    int getValue()
        Loop through genotype as if it were a binary number, generating a single decimal (base 10) value to return.
        You may find it easier to think of genotype in reverse, that is ok. For further clarification, both of theses are valid ways of converting, you just need to pick one:
            {1,0,1,1,0}
                could be 16 + _ + 4 + 2 + _ or 22
                could be  1 + _ + 4 + 8 or 13
    void mutate()
        Randomly select a single element in genotype and flip it, meaning turn a 0 into a 1 or a 1 into a 0.
    String toString()
        Return genotype as a binary string followed by value. 
        You should specify whether the start of the string is the big or little end. 
        Using the examples above, the following would be vaild return values:
            "BE->10110 22"
            "LE->10110 13"

• RegularGon
• Should represent a regular polygon as defined by a center, number of sides, and radius.
• New Instance Variables:

  int numSides, int radius

• New methods:

  generateRegularPolygon()
      Adds points to xs and ys to create a regular polygon defined by 
      the instance variables numSides and radius. You can generate 
      the appropriate points for a regular polygon by performing the 
      following calculations:
          x = radius * cos(theta * i) + cx
          y = radius * sin(theta * i) + cy
      Where theta = radians(360 / numSides)
      and (cx, cy) is the center of the bounding box bx,by,bw,bh
  
  RegularGon(int bx, int by, int bw, int bh, int sides, int length)
      Sets centroid to be the center of the rectangle defined by bx,by,bw,bh
      Sets numSides and radius to sides and length.
      Calls generateRegularPolygon() 

• TriangleGon
• No new instance variables
• No new methods.
• Overridden methods:

  setCentroid()
      The centroid of a triangle can be found by averaging the x and y 
      coordinates of each vertex. This is a much simpler calculation 
      than the general form used in PathShape, and also doesn't involve 
      area at all.
  
  addPoint()
      If there are already three points in the vertex lists, then 
      addPoint should do nothing.  
  

    //Add 4 instance variables to record the bounding box of the PathShape
    int bX, bY, bW, bH; 

    //Modify your PathShape's constructor to take 4 parameters to set the bounding box of the PathShape
    PathShape(int bX, int bY, int bW, int bH);

        

• For each point from 0 to the number of points - 1, take the sum of the following, stored separately (like in sumX and sumY variables):


• When i gets to the last point, perform the calculations above replacing i + 1 with 0. That is to say: the correct calculation requires the last point to loop back around to the first.
• Take both of those sums and divide each by ( 6 times the signed area of the polygon ).

• For each point from 0 to the number of points - 1, take the sum of the following. (This is a single calculation, as opposed to the previous calculations)


• When i gets to the last point, perform the calculations above replacing i + 1 with 0. That is to say: the correct calculation requires the last point to loop back around to the first.
• At the end, take the cumulative sum and divide it by 2.

    2 new instance variables:
        int[] centroid: an array to store the x and y values of the centroid. (shoud be a `new int[2];`, centroid[0] holds x, centroid[1] holds y)
        float area: stores the signed area, as defined above.
    3 modified methods:
        Constructor
            Initiliazes the centroid array, and sets both it and area to 0s.
        display
            Draws a circle of diameter 5 at the centroid. Use a different color than the inside instance variable.
        addPoint
            Should modify the area and centroid using the 2 new functions defined below.
    2 new methods:
        void setArea()
            Sets the area instance variable as defined above.
        void setCentroid()
            Sets the centroid instance variable.