Description
P3: Random Walk
Contents
Project Overview
- 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.
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 followspublic 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)
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ÂstepEC
method.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.