Class RandomMazeRunner

java.lang.Object
  RandomMazeRunner

All Implemented Interfaces:

MazeRunner

public class RandomMazeRunner
extends java.lang.Object
implements MazeRunner

The RandomMazeRunner implements a naive search algorithm. At each location in the maze, we randomly pick a direction to go, until we find the donut. In all likelihood, if a path exists, the runner will find it, but it could take a very long time! Your implementations of BFS, DFS and BestFS will (hopefully!) be far more efficient.

Author:

Albert J. Wong (awong@cs), Hannah C. Tang (hctang@cs)

Nested Class Summary

private static class

RandomMazeRunner.SolutionPathInfo We can store some information in each cell of the maze to keep track of our solution path.

Field Summary

private static java.util.Random

randSeq A random number generator, which we use to choose the next direction at each step in our random search.

Constructor Summary

RandomMazeRunner()

Method Summary

private MazeCell	getRandomNeighbor(Maze maze, MazeCell curCell) A helper method that chooses a random neighboring node of the current cell.
private static RandomMazeRunner.SolutionPathInfo	getSolutionPathInfo(MazeCell curCell) A helper method that returns a pointer to the SolutionPathInfo associated with a given cell.
private void	printSolution(Maze maze, int cellsVisited, java.io.PrintWriter writer) Print the solution path and mark each cell on the path as ON_SOLUTION_PATH.
void	solveMaze(Maze maze, java.io.PrintWriter writer) Tries to find a solution to the given maze.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

randSeq

private static java.util.Random randSeq

A random number generator, which we use to choose the next direction at each step in our random search.

Constructor Detail

RandomMazeRunner

public RandomMazeRunner()

Method Detail

getSolutionPathInfo

private static RandomMazeRunner.SolutionPathInfo getSolutionPathInfo(MazeCell curCell)

A helper method that returns a pointer to the SolutionPathInfo associated with a given cell. This method takes care of initializing the cell's extraInfo field if it is null.

Parameters:

curCell - The cell for which to get the SolutionPathInfo

solveMaze

public void solveMaze(Maze maze,
                      java.io.PrintWriter writer)

Tries to find a solution to the given maze. This function is the core of the random maze runner. It chooses a random neighboring node to expand and goes that way. Think of it as a lost child in the woods looking for the way home stumbling around from spot to spot until it runs out of enery...err maybe not.

Specified by:

solveMaze in interface MazeRunner

Parameters:

maze - the maze to solve.

writer - the PrintWriter on which to output the solution.

printSolution

private void printSolution(Maze maze,
                           int cellsVisited,
                           java.io.PrintWriter writer)

Print the solution path and mark each cell on the path as ON_SOLUTION_PATH.

Parameters:

maze - the Maze being solved.

cellsVisited - the total number of cells visited while searching.

writer - the PrintWriter on which to output the solution.

getRandomNeighbor

private MazeCell getRandomNeighbor(Maze maze,
                                   MazeCell curCell)

A helper method that chooses a random neighboring node of the current cell.

Parameters:

maze - The maze that we are solving

curCell - The current cell we are on. We choose a random neighbor of this cell in the previous maze.