Our algorithm for creating random mazes works as follows:
- Suppose we have 5 rows and 8 columns ...
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
The perimeter of the maze will always remain in place
but we'll construct the maze by knocking down a number
of the interior walls.
- So, in this example, for each row, we have 7 (8 - 1)
interior walls => 5 rows * 7 per row => 35 vertical interior walls
We also have 8 horizontal interior walls for each row
(except the last one) => 4 (5 - 1) rows * 8 per row => 32
horizontal interior walls
For 'R' rows and 'C' columns we'll have:
(R - 1) * C + (C - 1) * R -> total interior walls
- We then put all our walls into an array and randomize
them. Afterwards, we start at the beginning of the array
and work our way through all the interior walls knocking
down any walls that would connect rooms not already
connected (reachable from each other currently)
- The way we determine if two rooms are connected is as follows:
- A group is a list of rooms
- We start with as many groups as there are rooms and
each group containing only one room. This reflects
the initial state of the maze with no rooms being
connected to any other rooms
- As we consider an interior wall, we see to which groups
the two rooms it separates belong to. If the rooms are
in the same group we leave the wall in place. If the rooms
are in different groups we knock down the wall and absorb
all members of the group room two belongs to into the
group room one belongs to.
- Finally, we also determine the longest possible path
through the maze and use that path to determine the maze's
start and end points. We find the longest path by:
- start with an empty list of the rooms we've already visited
- we begin with room(0, 0)
- each time we visit a room, we'll add that room to the list
of rooms we've already visited
- for each room, we'll examine if we have neighbors (rooms)
to the north, south, east and west and recursively visit
them if we've not already been to that room
- eventually, we'll run out of rooms to visit at which point
we report back where we ended up and how many hops it took
us to get there, we record the ending room that had the
largest number of hops
- using the above, we find the longest path from room(0, 0), but
this may not be the longest path through the maze overall, we
find that longest path by repeating the above steps but using
as the starting room, the room that was farthest from room(0, 0)
Usage:
maze { -size rowsXcolumns } { -ps }
-ps => postscript output (default is text)
-size 50x75 => 50 rows by 75 columns (default is 16x16)
-h => display help information
The program should be fairly portable, I have compiled it using
MicroSoft's Visual C++ compiler and G++:
- g++ -W -Wall -o maze maze.cpp
- cl -GX -W3 maze.cpp
The resulting .ps files can be readily converted to pdfs
(I use the utility 'ps2pdf' to do this on my linux machine).
Here are some useful links:
And here are some example mazes as pdf files. Each maze will have
two rooms containing a filled black circle, those rooms are the
start and end point of the maze respectively.
 Source Code
Windows Executable
Return to Main |
