“Image-guided maze construction” by Xu and Kaplan

  • ©Jie Xu and Craig S. Kaplan




    Image-guided maze construction



    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

ACM Digital Library Publication: