Managing the Maze

Making a Maze Plan

The 3D and 2D maze representations employed in Maze3D are created by the MazeManager object after reading in a maze plan from a text file. Here is the plan in maze1.txt:

                s     bbbbb bbbbb bbbbb bbbbb     b                     b     b                     b     bbbb  ccccc ccccc  bbbb        b        b        b 

Figure 25-3 shows that plan realized in Maze3D (via the call java Maze3D maze1.txt).

Figure 25-3. Maze3D using maze1.txt

The s character in the text plan specifies the user's starting position in the maze. By default, the viewpoint is set to point along the positive z-axis in the scene, corresponding to downward in the bird's-eye view. The b characters in the maze plan become blue textured blocks, and the c characters are drawn as green textured cylinders.

Generating a Maze Using Software

A maze plan, like the one in maze1.txt, can be prepared in various ways, the simplest being to type one manually using a text editor. As an alternative, one of my students, Nawapoom Lohajarernvanich, and I wrote a maze generation application, called MazeGen.java (stored in Maze3D/MazeGen/). It utilizes a recursive, depth-first search with backtracking to create a maze.

The program generates a maze in a 2D character array. It assumes the array has an even number of rows and columns, and it creates the outer walls of the maze offset by one cell from the left, right, top, and bottom (see Figure 25-4). This means that the maze boundaries are in the odd rows and columns of the array. These restrictions ensure that the maze will have a solid outer wall after the maze has been created. The program adjusts the user's supplied maze width and height values to ensure that these restrictions are enforced.

Figure 25-4. The maze's outer walls

A b is placed in every cell on the grid, and the program removes some of them to create the maze. The generated maze is a single, winding path with no disconnected areas (e.g., secret corridors or bricked-up rooms).

The cutting away of the bs to form the maze starts at a randomly chosen even coordinate in the array (e.g., (4, 4)). Then another cell is randomly chosen from the four cells that are two units away in the x- or y-directions. For example, if the current cell is (4, 4), then the next cell could be (2, 4), (6, 4), (4, 6), or (4, 2). The path is made by connecting the cells with spaces, deleting the bs. This process is illustrated in Figure 25-5.

Figure 25-5. Path generation in MazeGen

The path-making process is repeated at the new cell, except that a path cannot return to a cell that's been used or to a position on or outside the maze's outer walls. For example, from (6, 4) the algorithm can use (8, 4), (6, 6), and (6, 2), but not (4, 4). The path cannot revisit a cell that's been visited, so it's not possible to create a maze with loops.

The path is made by joining up cells at even coordinates. Since the outer maze wall is made from cells at odd coordinates, a cell from the outer wall will never be selected to join the maze. This means that the path cannot cut into the maze wall.

The algorithm continues until it reaches a cell that cannot be connected to any further cells. This occurs when all the possible next cells have been utilized or are on or outside the outer walls. At this stage, the algorithm backtracks to the previous cell and looks at it again. Backtracking will continue until a cell has a possible next cell or there is no previous cell to go to (i.e., execution has returned to the starting cell).

The relevant code inside MazeGen is contained in createPath( ):

     private void createPath(Point cell)     { RandomInRange rr = new RandomInRange(NUM_DIRS);       int dir;       while((dir = rr.getNumber(  )) != -1){         Point nextCell = nextPos(cell, dir);         if( !beenVisited(nextCell) ){           visit(nextCell, dir);           createPath(nextCell);  // recursive creation         }       }     } 

The RandomInRange constructor creates a sequence between 0 and one less than the supplied value, and each call to getNumber( ) randomly selects a number from that sequence. For this application, NUM_DIRS is 4, so getNumber( ) can choose from {0, 1, 2, 3}, which represent the four directions leaving a cell (up, down, left, or right).

createPath( ) passes this number to nextPos( ) to select the next cell. If the next cell hasn't been visited, then visit( ) extends the path and the recursive call to createPath( ) continues the path generation. Backtracking from the recursive call will return to this loop, which will try another direction. getNumber( ) returns -1 when its sequence is exhausted, causing createPath( ) to return to an earlier createPath( ) call. The generated path is remembered by visit( ) modifying a global maze[][] array, so backtracking won't undo its creation.

The program finishes by randomly changing about 20 percent of the maze's bs to cs, and adds an exit to the top row of the maze. Changing the letter corresponds to replacing some of the 3D maze's blocks with cylinders to make the maze look a bit more interesting.

The starting cell used for path creation is assigned an s to become the starting point for the user. Since the maze has no disconnected parts, we know that it's possible for the player to get from the starting point to the maze's exit.

A typical call to MazeGen, and its output, is shown below:

     > java MazeGen 21 13     Width: 23; Height: 15 (2 added for borders)     Saving maze to file: maze.txt     Starting point: (2, 20)          bbbbcbbbcb bbbbbbcbcc      b           b   b  sb      b bbbbbccbc b bbb ccb      b       c     b   b b      b bcbbb bbbcbbb cbc b      b   b   c       b   b      b bbb bbb bcbbbbb cbb      b b   b   b     b   b      b c b b bbbbb b b b b      b b b b       b b c b      c b bbccccbbbbb cbb b      b c                 b      cbbbbbbbcbbbbbbbbbccb         Maze written to file maze.txt