Maze Design

We've been working on producing mazes by computer, with input from a human designer. We're interested in two complementary questions with respect to maze design:

Complexity: What makes a maze difficult to solve? The more we consider this question, the more elusive it becomes. It's certainly possible to begin defining mathematical measures of a maze's complexity, but complexity must depend on aspects of human perception as well. For example, the eye can easily become lost in a set of parallel passages. Complexity also depends on how the maze is to be solved. Are you looking down on the maze, solving it by eye? With a pencil? What if you're walking around inside the maze? And of course, complexity isn't necessarily what we want to measure. Ultimately we'd like to generate compelling puzzles, which may or may not have a high degree of complexity.
Aesthetics: How do we construct attractive mazes, particularly mazes that resemble real-world scenes? Here, maze design interacts with problems in non-photorealistic rendering. There are many great projects for producing line drawings from images. Our goal is similar, except that our lines must also contrive to have the geometry of a maze. This additional constraint affects how we think about creating a line drawing in the first place.

Gallery

We have addressed these two aspects of maze design in separate sub-projects. To study complexity, we set out to construct mazes that were as difficult as we could make them. We arrived at a system that assembled interconnected vortices, with the reasoning that a vortex does a good job of obscuring the relationship between a set of paths. You can click on any of the images below to download a PDF of the maze for solving on paper.

We then studied maze design as a problem in non-photorealistic rendering. Inspired by the work of Christopher Berg, we developed a system for constructing mazes from images. The human designer partitions the image manually into regions, assigns a small set of style parameters to each region, and sketches a rough solution path. The system then constructs a maze that respects the designer's choice of style, and is connected in the manner suggested by their solution path. We also include techniques for foreshortening and tone reproduction.

Clicking on the examples below will link you to a very high-res PNG. We hope to replace the PNGs with PDFs soon. The gate maze at the top of the page links to a PDF.

Papers

Image-guided maze construction. SIGGRAPH 2007.
Vortex maze construction. JMA 1(1), 2007.
Vortex maze construction. Bridges 2006.

Other resources

Karan Singh has put together an excellent page about maze and labyrinth design, motivated by his NPAR 2006 paper on labyrinths. Among the many useful links on the page, I recommend looking at Walter Pullen's Think Labyrinth! web page, which is a huge collection of maze-related resources and algorithms.

Mazes can be used to represent images in a couple of different ways. The most obvious is a kind of non-photorealistic line art, as in the fantastic examples by Christopher Berg. Less obvious are the great new Maze-a-pix puzzles being produced by Conceptis Puzzles. Thanks to Dave Green from Conceptis for letting us use a Maze-a-pix example in our vortex maze paper. I'm happy to put in a plug for them -- they produce a wide variety of great logic puzzles; Dave's name can be found next to the Sudoku puzzles in many newspapers.

Thank you to Ronald Koster and Claudio Pozas for the use of the source images for the snails and minotaur mazes.