Maze Creation [40C]

Contributed by George Wendle

The idea of this project is very simple; write a program that will create a maze.

Let us start with a simple maze that is constructed from square cells with entries/exits on one or more sides. Given a rectangular array of cells you will need to determine which adjacent cells are accessible to each other. Think of an array of rooms with doors between them; the basic program is to place those doors in such a way as to allow many paths but including one that goes from the designated start to the designated finish.

Your program should display the finished maze and be able to print it out. It should also be able to store the details in a file suitable for use with my other project on maze threading.

Program elements

You will need some form of container to hold the maze elements. You should note that you may need cells that have no entry/exit (inaccessible parts of the maze). You will need some form of validation mechanism to ensure the maze is threadable.

Given the whole maze there is a neat way of using a 'flood fill' that validates the maze as threadable. Just start at the start cell and mark all the reachable adjacent cells. Repeat that for each reachable cell and continue till a pass over all the newest cells produces no new ones. Now check that the finish cell is among the reachable ones.

Variants

There are a wide range of variations on this simple basic idea. Here are some of them:

• Use a hexagonal or triangular grid
• Use one way doors (i.e. exits from a cell that do not have a corresponding entry and vice versa
• Try 3D analogues. Cubical cells to start with then add other 3D latices
• Consider 'magic' connections that connect cells that are not adjacent