CS 261 Lab H - Random Art

Due Wed Nov 05 at 3:00pm

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. 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. Partner assignments for this lab can be found on Moodle

Remember to review the pair programming guidelines

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 two 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 you might take a moment to look at the createArtwork method.
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!
Expression is an interface representing a mathematical expression. In particular, an expression can be evaluted at a particular x and y value---that is, if the Expression represents a function f(x,y), I can plug in values for x and y and see what the result is.

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. For example, "x" is an expression that just evalues to whatever x-value you pass in.
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:
1. Multiply, which is defined as the product of two expressions. In other words: f(x,y) = g(x,y)*h(x,y), where g and h are other expressions.
2. Average, which is defined as the average of two expressions (those expressions added and then divided by 2). In other words: f(x,y) = (g(x,y) + h(x,y)) / 2, where g and h are other expressions.
3. 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. In other words: f(x,y) = cos(pi * g(x,y)), where g is another expression.
4. 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. In other words: f(x,y) = sin(pi * g(x,y)), where g is another expression.
5. X which is an expression representing some single x value. In other words: f(x,y) = x.
6. Y which is an expression representing some single y value. In other words: f(x,y) = y.
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, be sure to implement the provided interface! That way each class will be able to be evaluated.
- 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? (Hint: in terms of two Expressions that are multiplied).
    - Remember to store these parameters as instance variables!
    - This is what makes the classes recursive data structures!
    - Note that this is the conceptually difficult part of the program; if you get stuck, ask for help!
- 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 Expression variables. This works very similarly to any other recursive toString() method, but instead of repeatedly calling a single recursive method, you'll be 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? (Hint: which classes are not composed of other Expressions?)
    - 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 evaluate() method required by the Expression interface. This method will work similarly to toString(), but instead of returning a String, you will be calculating a double (the value of the expression at the given x and y). Note that you can recurse into other objects' methods to get doubles from them as well; e.g., if you need to evaluate component expressions.
  - These methods should be short.
  - Remember, the terminal expressions (X and Y) just return the appropriate value!
  - Tip: Note that your Sine and Cosine expressions should evaluate Math.PI times the operand Expression! Forgetting that Math.PI will cause your program to misbehave.
  - Again, 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.
Finally, 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 Expression'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 recursive method will stop.
- This class should also implement the Expression interface. Why?
- In addition to the constructor, toString(), etc. methods, you'll need to include a recursive helper 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 artwork, 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---but also the more intricate your artwork will be!
    - You could also include a minimum depth to avoid boring expressions, but that isn't required; but is worth a point of extra credit!
- 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.
  - The frame will print out the expressions it is drawing to help you with debugging.
- 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 (yes, all) of your classes, and upload the entire src folder to the LabH submission folder on vhedwig. 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 out of 16 points:

[1pt] You have created classes for each of the required Expressions
[2pt] Your Expression classes have appropriate constructors and instance variables
[3pt] Your Expression classes include recursive toString() methods
[4pt] Your Expression classes include recursive evaluate() methods
[1pt] Your RandomExpression class is an Expression with a toString() method
[2pt] Your RandomExpression class can recursively generate random expressions
[1pt] RandomExpressions have reasonably distributed choices of Expression operands
[1pt] Your RandomExpressions do not go beyond a given "depth"
[1pt] You have completed your lab partner evaluation