Making a maze....

[Phil Schmidt]

I did this 20+ years ago, in Z80 assembly on a TRS-80. It drove an
Epson MX-80 lineprinter to produce the output. I later converted it to
C when I was learning that language around '88, and had the maze
generate and display on the screen, using different colored cells for
different cell states. The resulting display resembles a grass fire on
a calm day (hmm, what if the algorithm considered "wind"? But I
digress), in that it starts as a point at a random location, and grows
out from that point in a random fashion, spreading out until all cells
are part of the maze (they are "burned out").

Anyway, here is the algorithm. Hopefully I haven't forgotten any
steps:

1) Start with a grid of cells, with each cell being marked as "virgin
territory".
2) Pick any cell at random, and mark it as "explored". From that cell,
identify all the adjacent "virgin territory" cells, and mark them as
"frontier".
3) Pick any random "frontier" cell X from the maze, and choose from X
at random any wall that adjoins an "explored" cell. Remove that wall,
and mark cell X as "explored". Also from cell X, identify all the
adjacent "virgin territory" cells, and mark them as "frontier".
4) Repeat (3) until there are no more "frontier" cells.

You will need to deal with the boundaries. The "virtual" cells just
outside the boundaries have the property that they can't become
"frontier" cells, and therefore can't become part of the maze.

This will produce a maze with the property that there will be one and
only one path from any cell to any other cell in the maze. So, to have
an entry and exit to the maze, just open the walls of two cells at the
boundaries of the maze.

I never tried this with anything but a rectangular grid. It would be
fun to use a hexagonal grid. It would also be interesting to do it in
3-D.

Sometimes I wish I were still a kid, and had time to play with this
kind of stuff...   :)