# About StarMaze v1.0

StarMaze is a Java Applet game where you navigate a red star through a labyrinth. The entrance to the maze is along the top and the exit is along the bottom. The maze is stored as a matrix of vertical and horizontal walls. Prior to generating a maze, the walls are initialized to all be present, which results in a full grid as shown in the figure below.**Figure 1.**Initial maze grid prior to generation

Several steps are required in order to generate the maze:

- Randomly select an entrance location along the top row.
- Randomly select an exit location along the bottom row.
- Create the exit path via random walk from entrance to exit.
- Create dead-end paths via random walks.

## Create the Exit Path via Random Walk

The random walk begins at the entrance of the maze. A random number generator is used to select a direction in which to move in the maze from the previous location while taking care not to retrace steps or prevent the random walk from reaching the exit. The figure below shows an example of a random walk from entrance to exit and is outlined in green.**Figure 2.**Exit path via random walk

## Create Dead-end Paths via Random Walks

A dead-end path is a route from any point along the exit path to a point in the maze that does not have an outlet. First, a point is chosen at random out of the remaining unexplored locations in the maze. A random number generator is used as described above to randomly select a direction in which to move in the maze from the previous location. The random walk terminates once it reaches a point in the maze that has already been explored. The figure below demonstrates a dead-end path via random walk. It begins at a random point out of the unexplored territory of the maze, and it ends at a point along the exit path, which is shown in green.**Figure 3.**Dead-end path via random walk

Another point is chosen at random out of the unexplored locations and the process continues with random walks until the entire maze has been explored.