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.
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
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.
Copyright © 2008 Pierre Dufilie IV. All Rights Reserved.