Method for generating mazes from images

The following image (left) is the image of a maze generated from the classic Tux logo, downsized to show the result more clearly. At the right hand, a smaller thumbnail is shown for reference. At right, bottom, the original image used to generate the maze is shown.

Small version of the maze (best seen from around 2 meters / 7 feet):

Smaller thumbnail: Original image by Larry Ewing:

The complete, solvable maze in its original resolution (2438x2793 pixels) can be downloaded from here.

Generating the maze

Generating a maze is a known problem, that many known algorithms solve. There is some interesting previous work on generating mazes from input images, that I link to in the references at the bottom. Nevertheless, I think the simple technique described here is new, which is why I think it deserves some explanation. Please let me know if you have any feedback about this article.

Generating a maze from a known grid or graph is very simple; many known algorithms can be used to solve that problem, one of which is Depth-first search. It's a simple recursive algorithm that starts from the exit cell, and recursively marks a cell as visited, before visiting its neighbours in a random order. There are more details about this algorithm in Depth-first search.

The problem, in this case, is how to create a graph for the maze to be created in, such that the graph itself resembles the input image when it's plotted on the screen. We can do this by dividing the grid we'll draw the maze on in multiple grids:

Dividing the grid in multiple pieces is useful since it allows us to have different resolutions for different parts of the full grid:

The only problem so far is that those grids are disconnected pieces; we need to connect grids of different sizes. It's also easy to find a criteria that connects vertices from a grid to vertices of a neighbor grid; for example here we connect a 3x3 grid to a 10x10 grid:

Now we show how the previous 4 grids look when they are connected:

Using this idea, we can easily convert an input image to a table of grids. Each pixel in a NxM image can be converted to a grid, in a resolution that is inversely proportional to the pixel brightness. Let's see a short gradient from white to black for example:

Here we have a 4x1 table of grids, that is representing a grayscale 4x1 image. The leftmost grid is perceived as white, the rightmost grid is perceived as black, everything in-between is perceived as gray. Notice that we are converting pixel brightness to resolution in a grid.

Now we are going to use the previous ideas to build a very small resolution of the following image:

The small resolution table of grids is shown next. For the big resolution version of the maze see at the beginning of this document.

Using the previous ideas we have built a table of connected grids, that is, a graph that can be conveniently shown as something closely resembling a grid. Now we can use the depth-first search maze generation algorithm to remove a number of edges in the graph so that the remaining edges are a maze (black lines are the maze, gray lines are the grids lines and their connections):

Another maze, now without the gray lines:

If a big enough resolution is used, the results are much better, like in the images that started this article.

Small version of the maze (best seen from around 2 meters / 7 feet):

Smaller thumbnail: Original image by Larry Ewing:

The complete, solvable maze in its original resolution (2438x2793 pixels) can be downloaded from here.

Source code

The Mathematica source code used for generating these mazes can be downloaded from here. Porting to other languages is planned, and any ports provided by readers are welcome.

References:

Image-Guided Maze Construction: by Jie Xu and Craig S. Kaplan (also see the mazes page).

Organic Labyrinths and Mazes: by Hans Pedersen, Karan Singh (also see the labyrinths and mazes page).

How to make a picturesque maze: by Yoshio Okamoto, Ryuhei Uehara.

Evolving Mazes from Images: by Liang Wan, Xiaopei Liu, Tien-Tsin Wong, Chi-Sing Leung.

Think Labyrinth!

Notes

First version: December 26, 2009. Author: H. Hernan Moraldo.