More Web Proxy on the site http://driver.im/

article

Image-guided maze construction

Authors:

Craig S. KaplanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 26, Issue 3

Pages 29 - es

https://doi.org/10.1145/1276377.1276414

Published: 29 July 2007 Publication History

Abstract

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.

Supplementary Material

JPG File (pps029.jpg)

Download
12.24 KB

MP4 File (pps029.mp4)

Download
82.32 MB

References

[1]

Berg, C. 2001. Amazeing Art: Wonders of the Ancient World. Harper Collins.

[2]

Berg, C., 2005. Amazeing art. http://www.amazeingart.com.

[3]

Cgal Editorial Board. 2006. CGAL-3.2 User and Reference Manual. http://www.cgal.org.

[4]

Conceptis Limited, 2006. Conceptis puzzles. http://www.conceptispuzzles.com.

[5]

Cormen, T. H., Leieserson, C. E., and Rivest, R. L. 1992. Introduction to Algorithms. MIT Press.

Digital Library

[6]

Fisher, A. 2006. The Amazing Book of Mazes. Harry N. Abrams, Inc.

[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.

Digital 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.

[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.

[10]

Kaplan, C. S., and Bosch, R. 2005. TSP art. In Bridges 2005: Mathematical Connections in Art, Music and Science, 301--308.

[11]

Karp, R. M. 1975. On the computational complexity of combinatorial problems. Networks, 5, 45--68.

Digital Library

[12]

Kern, H. 2000. Through the Labyrinth: designs and meanings over 5000 years. Prestel.

[13]

Morales, J. E., 2006. Virtual Mo. http://www.virtualmo.com.

[14]

Mortensen, E. N., and Barrett, W. A. 1995. Intelligent scissors for image composition. ACM Press, 191--198.

[15]

Ostromoukhov, V. 1999. Digital facial engraving. In SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, 417--424.

Digital Library

[16]

Peatfield, G., 2005. Maze creator, http://www.mazecreator.com/.

[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.

Digital Library

[18]

Pullen, W. D., 2005. Think labyrinth. http://www.astrolog.org/labyrnth/maze.htm.

[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.

Digital 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.

Digital 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.

[22]

Shivers, O., 2005. Maze generation. http://www.cc.gatech.edu/~shivers/mazes.html.

[23]

Stevens, P. S. 1974. Patterns in Nature. Little, Brown.

[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.

Digital 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.

Digital 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.

Digital Library

[27]

Xu, J., and Kaplan, C. S. 2007. Vortex maze construction. Journal of Mathematics and the Arts 1, 1 (March), 7--20.

[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.

Cited By

Okano KYamanaka KMatsuyama K(2022)Design and Implementation of Tools Making Storytelling Mazesおはなし迷路の制作を支援するツールのデザインと実装The Journal of the Society for Art and Science10.3756/artsci.21.19921:4(199-212)Online publication date: 4-Nov-2022
https://doi.org/10.3756/artsci.21.199
Yeh CLiu ZLin IZhang ELee T(2020)WYSIWYG Design of Hypnotic Line ArtIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.3032734(1-1)Online publication date: 2020
https://doi.org/10.1109/TVCG.2020.3032734
Kim PGrove JWurster SCrawfis RDeterding SKhosmood FPirker JApperley T(2019)Design-centric maze generationProceedings of the 14th International Conference on the Foundations of Digital Games10.1145/3337722.3341854(1-9)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3337722.3341854
Show More Cited By

Index Terms

Image-guided maze construction
1. Applied computing
  1. Arts and humanities
2. Computing methodologies
  1. Computer graphics

Recommendations

Image-guided maze construction
SIGGRAPH '07: ACM SIGGRAPH 2007 papers

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 ...
An Algorithm of Micromouse Maze Solving
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology

This paper proposes a maze exploring algorithm named “Partition-central Algorithm”, which is used to find the shortest path in a micromouse competition maze. A standard 16*16 units maze is divided into 12 partitions in this algorithm. Depending on the ...
Creating complex mazes quickly: Solution path first

A maze is a structure of passageways interconnected in a complex way, so that it presents at least one path to reach the designated end starting from a predefined location.

A new approach is proposed in this algorithm. First of all a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 26, Issue 3

July 2007

976 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1276377

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Published in TOG Volume 26, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
1,694
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Okano KYamanaka KMatsuyama K(2022)Design and Implementation of Tools Making Storytelling Mazesおはなし迷路の制作を支援するツールのデザインと実装The Journal of the Society for Art and Science10.3756/artsci.21.19921:4(199-212)Online publication date: 4-Nov-2022
https://doi.org/10.3756/artsci.21.199
Yeh CLiu ZLin IZhang ELee T(2020)WYSIWYG Design of Hypnotic Line ArtIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.3032734(1-1)Online publication date: 2020
https://doi.org/10.1109/TVCG.2020.3032734
Kim PGrove JWurster SCrawfis RDeterding SKhosmood FPirker JApperley T(2019)Design-centric maze generationProceedings of the 14th International Conference on the Foundations of Digital Games10.1145/3337722.3341854(1-9)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3337722.3341854
Ma CSun Z(2019)StitchGeneration: Modeling and creation of random-needle embroidery based on Markov chain modelMultimedia Tools and Applications10.1007/s11042-019-08053-778:23(34065-34094)Online publication date: 8-Aug-2019
https://doi.org/10.1007/s11042-019-08053-7
Alaguna CGomez JTakadama K(2018)Maze benchmark for testing evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208285(1321-1328)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208285
Chen ZChen WGuo JCao JZhang Y(2018)Orientation field guided line abstraction for 3D printingComputer Aided Geometric Design10.1016/j.cagd.2018.03.01462(253-262)Online publication date: May-2018
https://doi.org/10.1016/j.cagd.2018.03.014
Duncan NYu LYeung STerzopoulos D(2017)Approximate dissectionsACM Transactions on Graphics10.1145/3130800.313083136:6(1-13)Online publication date: 20-Nov-2017
https://dl.acm.org/doi/10.1145/3130800.3130831
Jeong KLee JKim J(2017)A Study on New Virtual Reality System in Maze TerrainInternational Journal of Human–Computer Interaction10.1080/10447318.2017.133153534:2(129-145)Online publication date: 3-Aug-2017
https://doi.org/10.1080/10447318.2017.1331535
Chen ZShen ZGuo JCao JZeng X(2017)Line drawing for 3D printingComputers & Graphics10.1016/j.cag.2017.05.01966(85-92)Online publication date: Aug-2017
https://doi.org/10.1016/j.cag.2017.05.019
Safak ABostanci ESoylucicek A(2016)Automated Maze Generation for Ms. Pac-Man Using Genetic AlgorithmsInternational Journal of Machine Learning and Computing10.18178/ijmlc.2016.6.4.6026:4(226-230)Online publication date: Aug-2016
https://doi.org/10.18178/ijmlc.2016.6.4.602
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents