John F. Dumas Vulcan Ware
_blank_

Maze Generator


 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