Maze generating algorithms are standard CS projects. Using the definition for a maze being there is a single unique path from any point in the maze to any other point.

One of the methods for generating a maze that fits the above definition is to create an NxM grid, with each cell of the grid having a unique number.

+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
| 5 | 6 | 7 | 8 |
+---+---+---+---+
| 9 | 10| 11| 12|
+---+---+---+---+
| 13| 14| 15| 16|
+---+---+---+---+
| 17| 18| 19| 20|
+---+---+---+---+

From this, a random wall is selected that has different numbers on either side. This wall is removed. All numbers that are equal to the higher valued number are changed to the lower number. The following example removes the wall between '6' and '7', and then between '3' and '6', and finally the south wall of '2'.

+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| 1 | 2 | 3 | 4 | | 1 | 2 | 3 | 4 | | 1 | 2 | 2 | 4 |
+---+---+---+---+ +---+---+   +---+ +---+   +   +---+
| 5 | 6   6 | 8 | | 5 | 3   3 | 8 | | 5 | 2   2 | 8 |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| 9 | 10| 11| 12| | 9 | 10| 11| 12| | 9 | 10| 11| 12|
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| 13| 14| 15| 16| | 13| 14| 15| 16| | 13| 14| 15| 16|
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| 17| 18| 19| 20| | 17| 18| 19| 20| | 17| 18| 19| 20|
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+

At this point, the wall between the two '2's can not be removed, because it has the same number on each side.

This process continues until all of the cells have the value '1'.

+---+---+---+---+
| 1   1 | 1 | 1 |
+---+   +   +   +
| 1 | 1   1   1 |
+   +---+   +---+
| 1   1 | 1 | 1 |
+   +---+   +   +
| 1   1   1   1 |
+   +---+---+   +
| 1   1   1 | 1 |
+---+---+---+---+

See also Kruskal's algorithm for more on the graph theory relating to it.

Log in or registerto write something here or to contact authors.