Paul Miller

# NAME

Games::RolePlay::MapGen::Generator::Perfect - The perfect maze generator

# SYNOPSIS

use Games::RolePlay::MapGen;

my \$map = new Games::RolePlay::MapGen;

\$map->set_generator( "Games::RolePlay::MapGen::Generator::Perfect" );

generate \$map;

# DESCRIPTION

This is the Perfect Maze portion of Jamis Buck's Dungeon Generator.

http://www.aarg.net/~minam/dungeon_design.html

## Jamis Buck's Dungeon Generator Algorithm

1. Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.

2. Pick a random cell in the grid and mark it visited. This is the current cell.

3. From the current cell, pick a random direction (north, south, east, or west). If (1) there is no cell adjacent to the current cell in that direction, or (2) if the adjacent cell in that direction has been visited, then that direction is invalid, and you must pick a different random direction. If all directions are invalid, pick a different random visited cell in the grid and start this step over again.

4. Let's call the cell in the chosen direction C. Create a corridor between the current cell and C, and then make C the current cell. Mark C visited.

5. Repeat steps 3 and 4 until all cells in the grid have been visited.