CS 261 Lab H - Random Art

Due Wed Mar 26 at 9:00am

Overview

In this lab you will practice working with recursively defined classes, using such recursive definitions to construct complex data structures out of simple components. Specifically, you will be creating classes that recursively model mathematical expressions (like the expressions you worked with in Lab F but with more complex operations, such as cos and sin). You'll be using this recursive definition of a mathematical expression to generate arbitrarily complex random expressions.

Why generate random mathematical expressions? Consider if you have an expression that uses some variables and that you are sure will evaluate to be between some specific bounds (say, between -1 and 1). For example, cos(𝜋 *x) of a number will always be between -1 and 1, as well avg(x,y) if the inputs are also within bounds.

Now take this expression and apply it to every pixel in an image (with the x and y being scaled down from the image width and height). Take the result of that expression and scale it a grayscale value of 0 - 255; in effect, you're creating a 3-dimensional graph of the function z = f(x,y), where the z value is represented by the "brightness" of the color. With a sufficiently complicated function, you can produce images such as the one below:


      cos(𝜋 * cos(𝜋 * sin(𝜋 * cos(𝜋 * cos(𝜋 * x)) * cos(𝜋 * avg(sin(𝜋 * x), cos(𝜋 * avg(sin(𝜋 * sin(𝜋 * sin(𝜋 * x))) * sin(𝜋 * sin(𝜋 * cos(𝜋 * y))), cos(𝜋 * sin(𝜋 * avg(cos(𝜋 * cos(𝜋 * cos(𝜋 * avg(x, x) * avg(x, y)))), cos(𝜋 * avg(avg(sin(𝜋 * y), avg(x, x)) * avg(sin(𝜋 * x), avg(y, y)), y))))))))))))

By applying different random expressions to each color channel (red, green, and blue), we can produce even more interesting effects:

This lab will let you use your recursive data structure for a mathematical expression to generate and evaluate random expressions in order to produce random artwork.

This lab will be completed in pairs. Remember to review the pair programming guidelines before you get started!

Objectives

To practice with recursion even more (I know!), specifically recursive data structures
To generate more pretty pictures!

Necessary Files

You will need to download the copy of the RandomArtLab.zip file. This file contains one classes you will need to import into Eclipse:

RandomArtFrame represents a window that will generate and show your random artwork. This class should look pretty familiar at this point, but take a moment to look at the createArtwork method. What classes are you going to need to implement? What methods will they have to have?
You should not modify this class. Note that although this class contains a main method, you will likely want to write your own tester class to make sure you are building expressions correctly!

Assignment Details

The key insight that lets us define expressions recursively is that an expression can be seen as an operation that is performed on other expressions. So the expression "2 * (3 + 2)" can be seen as applying the "*" operator to the existing expressions "2" and "3 + 4".
- Important point: a single value can be seen as a (super simple!) expression. This is known as a terminal, because it has no further evaluation required.
This means we can define an expression as being made up of an operation applied to other expressions, which themselves are operations on expressions... and recursion all the way down!
Your program will need to include the following expressions:
- Multiply, which is defined as the product of two expressions
- Average, which is defined as the average of two expressions (those expressions added and then divided by 2)
- Cosine, which is is the cos of 𝜋 times an expression, or cos(𝜋*expr). This is a unary expression--it only relies on one input expression.
- Sine, which is is the sin of 𝜋 times an expression, or sin(𝜋*expr). This is a unary expression--it only relies on one input expression.
- X which is an expression representing some single x value
- Y which is an expression representing some single y value.
Notice that all of the above operations, when given value(s) between -1 and 1, produce a value between -1 and 1. This is important.

Take a moment and consider these operations. Do you believe that you could produce arbitrarily complex mathematical expressions by combining them?
For this lab, you will be making a number of new classes: one for each different kind of expression.
- Because each of these classes are Expressions, you should use inheritance and polymorphism to enforce that fact. THINK: to best do this, should you make Expression a concrete class, an abstract class, or an interface? Look at the RandomArtFrame: what methods will Expressions have to have in its public interface, and how can you enforce that?
- Each Expression class is an ADT, and so will need a constructor.
  - Think about what parameters your constructors will need to take: what variables are required to produce the variable represented by your class? For example: what types of variables might we need to make a new Multiply object? Again, think about the recursive definition of an Expression--how did we define Multiply?
    - Remember to store these parameters as instance variables!
- Each Expression class will also need a toString() method to return a string representation of the mathematical function.
  - Note that you can use recursion to also include the string representation of any component variables. This works very similarly to any other recursive toString() method, but instead of recursing in a single method, you're recursing across multiple methods in multiple classes.
    - What is the stopping condition for this sequence of calls? What class(es)' toString() method is going to NOT have a recursive call?
    - Don't overcomplicate this! The recursive structure of your classes means that these methods will be really short and simple!
- Finally, you can fill the remaining required method of your Expression type. This method will work similarly to toString(), but instead of returning a String, you will be calculating a double. Note that you can recurse into other objects' methods to get doubles from them as well.
  - These methods should be short.
  - Don't overcomplicate this! The recursive structure will mean that everything should come together simply.
- Be sure to test your classes by manually constructing a few small mathematical expressions (without a lot of nesting), and then using toString() to test that you can print out the expression. You can also call other methods and make sure you get the right answer.
You'll also need to create a RandomExpression class to represent a randomly constructed expression. This expression will be made by randomly creating new Expression objects, the parameters for which are also randomly created new Expression objects. For example, you may start with a Sine object, making its parameter a Cosine object, then make that's parameter an Average object, and so on. Eventually you will reach a terminal object (X or Y) that doesn't require a parameter, and your object will be built.
- This class should also use polymorphism to be an Expression. Why?
- In addition to the constructor, toString(), etc. methods, you'll need to include a recursive method to randomly build a new expression using the process described above. You might call this method... I don't know... buildRandomExpression() sound good? This method will need to create a new random expression, and then recursively call itself in order to create random expressions to fill in the parameters when appropriate.
  - This is the most complicated part of the lab, but it's not really that bad. Just remember your recipe for making recursive methods!
  - To customize your artwor, you can pick which expression to use with different frequencies. For example, maybe you use Sine 50% of the time and Cosine 30% of the time. I picked each non-terminal expression with equal frequency, but you are welcome to play around with it. Try to write your code such that these percentages are easy to modify!
  - Note I got the best results by picking a terminal 15% or less of the time.
  - The algorithm described above has the potential for infinite recursion. This is a desired behavior of a good recursive data structure, but won't exactly help your program. In order to avoid StackOverflowErrors, you'll want to keep track of your current "depth" in the recursion (e.g., how many times to add in another level of nested Expression), and add an extra stopping condition if you hit some maximum. I've heard that 8-10 is a good maximum, though 16 worked well for me. Note that the higher your maximum, the longer your program will take to produce a random expression, and hence to create random artwork.
    - You could also include a minimum depth to avoid boring expressions, but that isn't required.
- Be sure to test your random expression generation by printing it out! You'll need to run the program multiple times to account for the randomness, or use a Random object with a specified seed.
Once you have your RandomExpression working, you should be able to to run the RandomArtFrame class and begin to look at beautiful random artwork!
- Depending on the complexity of your expression, producing a piece of artwork can take a few seconds, or even a minute or two. You may need to use a smaller frame (less pixels to evaluate), a less complex expression (less math to do), or just be patient.
- Note that not every image will look cool--if you get a lemon, just try again!
- I've included a "Save" button so you can save any images you produce to disk! Feel free to submit your favorite images along with your assignment--I would love to see them!

Extensions

You might consider creating other Expressions to add to your data structure. Any mathematical function that, when given input(s) between -1 and 1 produces a value between -1 and 1 would work. For example the absolute value function would be an option, though will cut off the "dark" end of your picture. Consider making discontinuous functions, or functions that involve 3 or more expressions!

Submitting

Make sure your name is in a class comment at the top of your all of your classes, and upload the entire src folder to the LabH submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

After you have submitted your solution, log onto Moodle and submit the Lab H Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded based on approximately the following criteria:

You have created classes for each of the required expressions [10%]
You have created a proper Expression class to enable polymorphism [10%]
Your classes include recursive toString() methods [20%]
Your classes include recursive evaluate() methods [20%]
Your RandomExpression class can recursively generate random expressions [30%]
Your RandomExpression class can be converted to a String and evaluated [5%]
You completed your lab partner evaluation [5%]