“Image-guided maze construction” by Xu and Kaplan

We present a set of graphical and combinatorial algorithms for designing mazes based on images. The designer traces regions of interest in an image and annotates the regions with style parameters. They can optionally specify a solution path, which provides a rough guide for laying out the maze’s actual solution. The system uses novel extensions to well-known maze construction algorithms to build mazes that approximate the tone of the source image, express the desired style in each region, and conform to the user’s solution path.

1. Berg, C. 2001. Amazeing Art: Wonders of the Ancient World. Harper Collins.Google Scholar
2. Berg, C., 2005. Amazeing art. http://www.amazeingart.com.Google Scholar
3. Cgal Editorial Board. 2006. CGAL-3.2 User and Reference Manual. http://www.cgal.org.Google Scholar
4. Conceptis Limited, 2006. Conceptis puzzles. http://www.conceptispuzzles.com.Google Scholar
5. Cormen, T. H., Leieserson, C. E., and Rivest, R. L. 1992. Introduction to Algorithms. MIT Press. Google ScholarDigital Library
6. Fisher, A. 2006. The Amazing Book of Mazes. Harry N. Abrams, Inc.Google Scholar
7. Hays, J., and Essa, I. 2004. Image and video based painterly animation. In NPAR ’04: Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, ACM Press, 113–120. Google ScholarDigital Library
8. Huang, J., and Feigenson, G. W. 1999. A microscopic interaction model of maximum solubility of cholesterol in lipid bilayers. Biophysical Journal 76, 4, 2142–2157.Google ScholarCross Ref
9. Jobard, B., and Lefer, W. 1997. Creating evenly-spaced streamlines of arbitrary density. In Visualization in Scientific Computing ’97. Proceedings of the Eurographics Workshop in Boulogne-sur-Mer, France, Springer Verlag, 43–56.Google Scholar
10. Kaplan, C. S., and Bosch, R. 2005. TSP art. In Bridges 2005: Mathematical Connections in Art, Music and Science, 301–308.Google Scholar
11. Karp, R. M. 1975. On the computational complexity of combinatorial problems. Networks, 5, 45–68.Google ScholarDigital Library
12. Kern, H. 2000. Through the Labyrinth: designs and meanings over 5000 years. Prestel.Google Scholar
13. Morales, J. E., 2006. Virtual Mo. http://www.virtualmo.com.Google Scholar
14. Mortensen, E. N., and Barrett, W. A. 1995. Intelligent scissors for image composition. ACM Press, 191–198.Google Scholar
15. Ostromoukhov, V. 1999. Digital facial engraving. In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, 417–424. Google ScholarDigital Library
16. Peatfield, G., 2005. Maze creator, http://www.mazecreator.com/.Google Scholar
17. Pedersen, H., and Singh, K. 2006. Organic labyrinths and mazes. In NPAR ’06: Proceedings of the 4th international symposium on Non-photorealistic animation and rendering, ACM Press, 79–86. Google ScholarDigital Library
18. Pullen, W. D., 2005. Think labyrinth. http://www.astrolog.org/labyrnth/maze.htm.Google Scholar
19. Robertson, N., and Seymour, P. D. 1986. Graph minors. VI. disjoint paths across a disc. J. Comb. Theory Ser. B 41, 1, 115–138. Google ScholarDigital Library
20. Salisbury, M. P., Wong, M. T., Hughes, J. F., and Salesin, D. H. 1997. Orientable textures for image-based pen-and-ink illustration. In SIGGRAPH ’97: Proceedings of the 24th annual conference on Computer graphics and interactive techniques, 401–406. Google ScholarDigital Library
21. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press.Google Scholar
22. Shivers, O., 2005. Maze generation. http://www.cc.gatech.edu/~shivers/mazes.html.Google Scholar
23. Stevens, P. S. 1974. Patterns in Nature. Little, Brown.Google Scholar
24. Suzuki, H., Akama, T., and Nishizeki, T. 1990. Finding steiner forests in planar graphs. In SODA ’90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 444–453. Google ScholarDigital Library
25. Turk, G. 1991. Generating textures on arbitrary surfaces using reaction-diffusion. In SIGGRAPH ’91: Proceedings of the 18th annual conference on Computer graphics and interactive techniques, ACM Press, 289–298. Google ScholarDigital Library
26. Winkenbach, G., and Salesin, D. H. 1994. Computer-generated pen-and-ink illustration. In SIGGRAPH ’94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, ACM Press, 91–100. Google ScholarDigital Library
27. Xu, J., and Kaplan, C. S. 2007. Vortex maze construction. Journal of Mathematics and the Arts 1, 1 (March), 7–20.Google ScholarCross Ref
28. Zhang, L., Dugas-Phocion, G., Samson, J., and Seitz, S. 2001. Single view modeling of free-form scenes. In Proc. of CVPR, 2001, vol. 1, 990–997.Google Scholar