CS 261 Lab H - Random Art

Due Wed Mar 27 at 9:00am

Overview

Formal grammars can let us quickly construct random phrases in a context-free language. In this lab, you will be implementing a specific grammar that to generate phrases in the language of mathematics: specifically, random mathematical expressions. While this is moderately interesting in its own right, if we're careful about the definition of our mathematical language, we can do even cooler things with the result. For example, if we have a function f(x,y) that we are sure will evaluate to be between specific bounds (say, between -1 and 1), we can apply the expression to the coordinates of every pixel in an image and scale the result to a grayscale value of 0 - 255, to effectively plot this function on the image grid (with the f(x,y) represented by the brightness of the color). With a sufficiently complicated function, we can produce images such as the one below:


      cos(pi * cos(pi * sin(pi * cos(pi * cos(pi * x)) * cos(pi * avg(sin(pi * x), cos(pi * avg(sin(pi * sin(pi * sin(pi * x))) * sin(pi * sin(pi * cos(pi * y))), cos(pi * sin(pi * avg(cos(pi * cos(pi * cos(pi * avg(x, x) * avg(x, y)))), cos(pi * avg(avg(sin(pi * y), avg(x, x)) * avg(sin(pi * 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:

In this lab, you will be writing a program to recursively generate, print, and evaluate random mathematical expressions (based on a specific grammar) in order to produce random artwork.

This lab will be completed in pairs. Review the pair programming guidelines!

Objectives

To practice recursion even more (I know!)
To create data structures in terms of formal grammars.
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:

Expression is an abstract class that represents an Expression. You do not need to modify this class, but you will need to extend it. Food for thought: could this class be an interface? Does it make more sense as an interface or an abstract class?
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 need to 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!

Details

Your program will need to respect the following grammar (presented in a pseudo-Backus-Naur Form; all mathematical symbols represent themselves):
```
<expression> ::= <multiply> | <average> | <sine> | <cosine> | <terminal> 
<multiply> ::= <expression> * <expression>
<average> ::= ( <expression> + <expression> )/2
<sine> ::= sin(pi * <expression> )
<cosine> ::= cos(pi * <expression> )
<terminal> ::= x | y
```
- Take a moment to study the grammar. Do you believe that you can produce arbitrarily complex mathematical expressions out of it?
- Notice that all of the above functions, when given value(s) between -1 and 1, produce a value between -1 and 1. This is important. You will be askedd to add one more function to this grammar--this function should also produce a value between -1 and 1
For this lab, you will be making a number of new classes: one for each variable in the grammar. The Expression class has already been provided for you--as an Expression in the grammar is always substituted by one and only one other variable, it makes sense to have this be an abstract class that is extended by the others. The other classes should be concrete
- Each new class you make should extend the provided Expression class.
- Your life may be more pleasant if you make TerminalX and TerminalY separate classes, but it is not strictly necessary.
- Each class will need three methods: a constructor, evaluate() (required by the parent class), and a toString() method.
  - 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? Remember to store these parameters as fields!
  - Your toString() method will want 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 is recursion across multiple functions, rather than treating a single function as a recursive loop. What is the stopping condition for this sequence of calls? What method is going to NOT have a recursive call?
  - Your evaluate() method will work similarly, but instead of returning a String, you will be calculating a double. Note that you can recurse into other 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 small mathematical expressions (without a lot of nesting), and then using toString() to test that you can print out the expression
- In addition to the classes listed in the grammar, you should make one more class representing another function that fits the grammar's requirements (i.e., the function maps an input of -1 to 1 to an output of -1 to 1).
  - In the class comment include a description of this function in BNF format (like in the grammar above).
  - Be creative! You are allowed to do anything you want here! Look through the other functions in the Math class for inspiration
  - Things that are less creative: simple variants of existing operators (e.g., (... + ... + ...)/3 or sin(2 * pi * ...)); functions that can be built out of existing functions (e.g., (... * ... * ...)). You don't want to be less creative, do you?
  - Note that your operators can be non-continuous, but this is not required.
  - I recommend you do this step last, after you have everything else working!
You'll also need to create a RandomExpression class to represent a randomly constructed expression. This expression will be made by randomly expanding the grammar: for example, you may start with <sine>, then fill the expression of that with <cosine>, then fill the expression of that with <average>, and then fill the expressions of that, and so on. Eventually you will reach a <terminal> variable and your overall expression will be complete.
- This class should also extend Expression. Why?
- In addition to a Constructor, evaluate(), and toString() methods, you'll need to include a recursive method to randomly construct a new expression from the grammar 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 variables 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!
  - Although not reflected in the grammar listing above, you can pick expressions at a different frequency. For example, maybe you use <sine> 50% of the time and <cosine> 30% of the time. I picked each non-terminal variable with equal frequency, but you are welcome to play around with it. Try to write your code such that it is easy to modify!
  - Note that the best results seem to occur if you pick 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 grammar, 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, 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
    - You could also include a minimum depth, 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.

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 (even a minute or two)--you may need to use a smaller frame, a less complex expression, 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.

Submitting

Submit all of your classes 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.

Remember to fill out your lab partner evaluation!

Grading

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

You have created classes for each of the variables in the grammar [10%]
You have included a bonus function of your own design in the grammar, with a BNF definition in the class comment [5%]
Your classes include recursive toString() methods [15%]
Your classes include recursive evaluate() methods [15%]
Your RandomExpression class can recursively generate random expressions [30%]
Your RandomExpression class can be converted to a string and evaluated [10%]
Your code is well documented and follows the edicts of good style [10%]
You completed your lab partner evaluation [5%]