P3: Random Walk Solution

Contents
Project Overview
Getting Started
Specification
Submitting Your Project
Project Overview
In this project, you will generate a random walk on a grid that starts at the bottom-left corner and ends up at the top-right corner.

Classes that you will create: RandomWalk.java, RandomWalkDriver.java
Existing interface that you will use: RandomWalkInterface.java
Existing classes that you will use: RandomWalkUnitTester.java, RandomWalkGUI.java, GridMap.java
Objectives
Write a class that implements methods of an interface, including overloaded constructors and a toString.
Write a driver class that uses the above class.
Use classes from the Java standard library.
Use existing classes.
Create a list of objects using the ArrayList class.

Getting Started
Create a new Eclipse project for this assignment.
The easiest way to import all the files into your project is to download and unzip the starter files directly into your project workspace directory (using the command-line or dolphin). The starter files are available here: http://cs.boisestate.edu/~cs121/projects/p3/stubs (You should download p3-stubs.zip)
After you unzip the files into your workspace directory outside of Eclipse, go back to Eclipse and refresh your project.
You should see the following files: RandomWalkInterface.java, GridMap.java, and RandomWalkGUI.java.
You will need to create a new class in your project called RandomWalk.
You will need to create a new driver class in your project called RandomWalkDriver. This will contain the main method.
There will be several errors, but these are expected until you finish implementing your RandomWalk.java class.
Specification
Generate a random walk on an n by n grid that starts at [0,n-1] (bottom-left corner) and ends up at [n-1,0] (top-right corner).
At each point, there are four potential directions in which we can walk: North, East, South, and West. To avoid getting stuck, we will only walk to the North or East with equal probability. This way, we will always be making progress towards the destination (the north-east corner).
See the figure at the top of the page for a sample random walk.
Part 1: Creating the RandomWalk class
If you haven't already, create a RandomWalk class. Think about the attributes this class will have:size of the grid,
a random number generator,
a boolean flag named done,
an ArrayList of points to represent the path of the random walk,
the start point of the walk,
the end point of the walk,
the current point of the walk,
as well as other instance variables as you may see fit.
Your class must implement the RandomWalkInterface.To implement the interface, you must modify your class header as follows

public class RandomWalk implements RandomWalkInterface
{
}
Use the Point class provided in the Java standard library (in the java.awt package) to represent each point on the path. For example, the start point can be represented as:
Point start = new Point(0,gridSize-1);

You can access the coordinates of the point using:
start.x
start.y

Use an ArrayList of Point objects to store the path. The ArrayList class is part of the java.util package and provides functionality for managing a list of objects. There are several methods available in the ArrayList class (e.g. add, remove, isEmpty, contains, etc.).You can construct an ArrayList instance for managing your Point objects as follows:


ArrayList<Point path = new ArrayList<Point();

Then, you can add new points to your path using the add(...) method of the ArrayList class as follows:
Point p1 = new Point(x, y);
path.add(p1);

Signatures for the methods you must implement in your RandomWalk class. The methods are also defined in theRandomWalkInterface.Note that while you must implement the methods as defined by their signatures, you may also implement additional methods as needed.

public RandomWalk(int gridSize)Initializes the instance variables and adds the starting point of the walk, but doesn't create the entire walk. Instantiates a random number generator without a seed.
public RandomWalk(int gridSize, long seed)Same as the above constructor except that we specify a seed for the random number generator. This is very useful for debugging and testing as the same seed will give the same random number sequence so that we can reproduce a bug! This constructor illustrates the concept of method overloading.
public void step()Makes the walk go one more step. To add a step to your path, you will add the new Point to your ArrayList. A new step should be added to your path every time the method is called.

If the step is the final step, set the value of the done instance variable to true to signal that you are done with the random walk.

It should not take a step if the done variable is set to true.

Note that you will walk North or East with equal probability (use the random number generator). If you are at one of the edges, then you may have only one direction in which you can walk. You can handle this case in multiple ways. For example, you can always pick one of North or East and then if you find you cannot go in that direction, just generate another random choice until you can move.
public void createWalk()Creates the entire walk in one call by internally using the step() method.
public boolean isDone()Returns the current value of the done variable. (Just returns the value of the variable. Does not actually check if the path is at the end, this happens in the step method.)
public int getGridSize()Returns the size of the grid.
public Point getStartPoint()Returns the starting point of the walk.
public Point getEndPoint()Returns the ending point of the walk.
public Point getCurrentPoint()Returns the current point of the walk.
public ArrayList<Point getPath()Getter that returns a copy of the random walk path ArrayList.
public String toString()Returns the path as a nicely formatted string as shown below:

[0,4] [0,3] [1,3] [1,2] [2,2] [3,2] [3,1] [4,1] [4,0]
 
Part 2: Testing your RandomWalk class
Testing your RandomWalk class
Write a RandomWalkDriver class that does the following:Implement a main method that deals with the user input as follows:
Prompts the user for the grid size and checks to make sure that user enters a positive integer. If the entered value is invalid, ask the user to enter a different integer. Keep doing this until they enter a valid integer. You can do this with a loop.
Prompts the user for the random seed value and checks to make sure that the user enters a 0 or positive integer. If the entered value is invalid, ask the user to enter a different integer. Keep doing this until they enter a valid integer. You can also do this with a loop.
Creates a RandomWalk object with the appropriate constructor. If the seed is zero, then call the constructor with only grid size as an argument. Otherwise call the constructor with two arguments.
Create the walk using the createWalk() method and then print the walk (using the toString() method in theRandomWalk class).
Hints on testing:
Test for bad input like negative or zero for grid size, negative random seed to make sure your program catches the error and asks user to enter values again and again until they get it right!
Test for boundary cases:
Try small values like 1, 2, 3, 4 for grid size to see if the path generated is correct.
Try random seed like 1234 and verify that you generate the same path each time.
Try random seed input of zero and verify that you get different random paths each time.
Try a few larger grid sizes like 10, 20, 100 to see if your program stops normally. It is hard to check if the output is correct for large grid size but using the GUI program will make it easier. Can you think of how to write a method that checks if the generated path is valid?
Use the RandomWalkGUI program to make it easier to debug your program!
Sample Session
java RandomWalkDriver
Enter grid size:6
Enter random seed (0 for no seed):1234
[0,5] [0,4] [1,4] [1,3] [2,3] [2,2] [3,2] [4,2] [4,1] [5,1] [5,0]

For the same grid size and same seed, we should get the same output even though it is random!
java RandomWalkDriver
Enter grid size:6
Enter random seed (0 for no seed):1234
[0,5] [0,4] [1,4] [1,3] [2,3] [2,2] [3,2] [4,2] [4,1] [5,1] [5,0]

With a random seed of 0, we don't supply a seed to Random so the walk will be different each time we run the program
java RandomWalkDriver
Enter grid size:8
Enter random seed (0 for no seed):0
[0,7] [1,7] [1,6] [1,5] [2,5] [2,4] [3,4] [4,4] [4,3] [5,3] [5,2] [6,2] [6,1] [6,0] [7,0]

java RandomWalkDriver
Enter grid size:8
Enter random seed (0 for no seed):0
[0,7] [1,7] [2,7] [2,6] [3,6] [4,6] [4,5] [4,4] [4,3] [5,3] [5,2] [5,1] [5,0] [6,0] [7,0]

Now we show some error checking on the user supplied input
java RandomWalkDriver
Enter grid size:-5
Error: grid size must be positive!
Enter grid size:-6
Error: grid size must be positive!
Enter grid size:6
Enter random seed (0 for no seed):-233
Error: random seed must be = 0!
Enter random seed (0 for no seed):-455
Error: random seed must be = 0!
Enter random seed (0 for no seed):1234
[0,5] [0,4] [1,4] [1,3] [2,3] [2,2] [3,2] [4,2] [4,1] [5,1] [5,0]

Using the RandomWalkGUI class for testing and visualization
You can also use the provided RandomWalkGUI class (that uses the GridMap class) to see the results of your program in an animated form. Note that the RandomWalkGUI class expects your RandomWalk class to have properly implemented step(), isDone() and getPath() methods. The image shown above is a screenshot of the RandomWalkGUI program. You don't have to do anything to make the GUI work except implement the methods in the RandomWalk class as specified above!

Please note that the RandomWalkGUI uses command line arguments. So to use it, for example, you would type (on one line):


java RandomWalkGUI 8 1234

where 8 is the grid size and 1234 is the random seed. Note that you can skip the second input value (for the seed) and it would use the constructor without the seed and produce different random paths each time. 

Using the RandomWalkUnitTester class for testing methods
When you are done, you can also run the RandomWalkUnitTester to check if your methods meet all the requirements. It will execute several tests on your RandomWalk class and provide "PASS" or "FAIL" output with feedback.
Extra Credit (5 points)
If you choose to implement the extra credit, you must complete the basic version first. You will need to write two versions of the step() and createWalk() methods. Uncomment the methods in the RandomWalkInterface and implement them in your RandomWalk class.
Implement the stepEC method so that walks can also include moves that do not take us closer to the destination (that is, West and South are also possibilities). You will also need to implement a createWalkEC method to call your stepECmethod.We do not want to include the same location more than once, however, so we will need to check if the path already contains the point we are about to visit. If so, we will skip it and go back and try another point.

The ArrayList class provides a contains(...) method that makes it easy to check if a point is already in the path.


if (path.contains(new Point(x, y))
{
// do something
}

 

However, the path can still get stuck since we don't want the walker to visit the same point twice. If the path gets stuck, clear the path and start over at [0,n-1].

You will have to write a new private method that checks if we are stuck at a point. To make it likely that your program will find a path, we would recommend setting the probability for West or South moves to be no more than 10% each.