How to make a picturesque maze.
Proceedings of 21st Canadian Conference on Computational Geometry (CCCG 2009), 137-140.
Manuscript: PDF; 854178 bytes)
Written by Yoshio Okamoto (March 25, 2010)
The paper above proposed an algorithm to generate a maze in which the solution path reveals a hidden input (black-and-white) image.
The key idea of the algorithm is to turn each pixel into a 2-by-2 set of pixels.
This will allow us to find a solution path on the input image, and thus gives a desired maze.
The virtue of this algorithm is simplicity, and any connected raster image
can be handled.
However, there are a certain number of drawbacks.
- We cannot specify the entrance and the exit arbitrarily.
In particular, they need to be adjacent in the generated maze.
- The solution path can be found by a right-hand walk without turning back at any deadend. Thus, solving the maze will not be fun.
Recently, these drawbacks have been resolved by three groups of people.
Here, I'll summarize their approach.
These papers didn't appear in English, but were just presented at domestic
workshops in Japan.
If you look for a further detail, please contact me.
- Ryohei Nakai and I (Yoshio Okamoto) from Tokyo Institute of Technology
propose turning each pixel into a 4-by-4 set of pixels. This method can
handle any connected input image. Certainly, the size of a generated
maze will be big. This is a drawback.
- Kokolo Ikeda from Japan Advanced Institute of Science and Technology
proposed turning each pixel into a 3-by-3 set of
pixels. In this method, not all input images can be handled naturally, and
so we need to modify the image a little bit. This looks to be a drawback,
but he claims that this does not
reduce the quality of the image. The size of a generated maze is smaller
than the one by Nakai and me.
He also proposes some other heuristic methods to improve the quality of
- Koki Hamada, who graduated from Kyoto University, proposed keeping
a 2-by-2 set of pixels, as Okamoto and Uehara. But, by choosing the
connections cleverly he is able to resolve the problems above.
One drawback is that his method requires an input image to be