I consider mazes placed on a square lattice with rectangular border. The corridors of the maze are loop free and connected, so they form a tree. The basic element of the maze is a “tile”. One tile may have up to four neighboring tiles. Below is an example:

The following images are colored with this algorithm:
0. Label all dead ends with 0.
1. Check all tiles:
a) If a tile is unlabeled and has one labeled and one unlabeled neighbor, label it with the label of the labeled neighbor.
b) If a tile is unlabeled, has more than one labeled neighbor and at most one unlabeled neighbor, label it with max(neighborlabels)+1.
2. If there are still unlabeled tiles, go to step 1.

A similair operation may be performed on the walls instead of the corridors:

Colored corridors and colored walls combined:

Some more mazes colored with tree structure:

We return to our a basic maze:

Now we determine a path of maximal length (there may be several paths of maximal length, so we choose one at random). We color this path following a rainbow:

Now starting from the chosen path, we flood-fill the rest of the maze:

The farther away from the maximal path we get, the darker we paint:

We may combine this with the tree coloring from above:

Some more examples:

There are different algorithms to construct a maze; the next examples use a “hunt & seek” strategy to construct mazes:

A labyrinth is a maze without bifurcations. You get a labyrinth by taking a maze and replace every corridor with a thin wall, making the border between previous walls and previous corridors the new corridors. Since a labyrinth is a (trivial) maze, it is possible to repeat this process ad lib to create concentric circles:

Aplying this process to our very first maze gives us:

Such a labyrinth is basically a circle. Coloring it with a (repeated or nonrepeated) rainbow yields:

In the next image, the color of the wall indicate how far the two tiles separated by the wall are apart. If they are, for example, separated by a green wall, you have to move three tiles to go from one to the other.

Next, we consider mazes with more than one connection component, that is, several unconnected systems of corridors, like this:

The shape of a random area in the middle is usually some irregular blob, while the shape of areas touching the edge of the rectangle are restricted by the edge. To avoid this, the following maze is supposed to reside on a torus, that is, if you leave it on the right, you re-enter it on the left, and the same for the top and the bottom edge:

The next three mazes reside on rings, like the maps in the game civ.

Finally, instead of coloring mazes according to some algorithm, I created some tileset layouts. The mazes below are all the same, rendered with different layouts:

I made all the images above based on a small python script. If you are interested in generating your own images, you may download it here: laby.zip.
It comes with a rather extensive manual; when it talks about a “labyrinth”, read “maze” instead.

Jan Thor · www.janthor.de · jan@janthor.de · 29.9.2006