Maze Design
![[gate]](/contents/118/023/798.mime5)
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
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.
All images are copyright 2005 by Jie Xu and Craig S. Kaplan. You are
free to use them for personal and non-commercial purposes.
Please check with me about any other uses.
