Maze Threading [50C]

Contributed by George Wendle

The idea of this project is very simple; write a program that will thread a maze. The devil is in the details.

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 these with a cell identified as the start and another as the finish your program should determine the shortest route from start to finish and output a set of instructions in the form of {(turn n)(forward m)}.

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. After that you will need an algorithm to determine a route, and then prune it to being the shortest route.

Given the whole maze there is a neat way of using a 'flood fill' that both validates the maze as threadable and provides a useful starting point to determine the optimum route.

However a more complete solution would be one in which the threaders knowledge of the maze is limited to where they have been and what the can see.

If you have graphics available add visualization to your program. A nice touch would be to make this follow the steps of the solution so the user can see the false paths being blocked off (perhaps with a different colour)

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