Yoshio Okamoto, and Ryuhei Uehara,
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.

  1. We cannot specify the entrance and the exit arbitrarily. In particular, they need to be adjacent in the generated maze.
  2. 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.

[Research Top] [Top]