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.

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,

as well as other instance variables as you may see fit.

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,size-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 path = new ArrayList(); 

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. Please note that while you must implement the methods below exactly as defined by their signatures, you may also implement additional methods as needed:public RandomWalk(int gridSize)

Initializes the instance variables and the starting point of the walk, but doesn't create the walk. Creates 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 this 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.

Note that we 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 ArrayList getPath()

Getter to get reference to the random walk path.

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]