Abstract：3D maze has reached a high level in terms of complexity and fun. By improving the algorithm of generating a 2D maze, we propose the concept of loop maze and the complexity formula of the maze. Then, an algorithm for designing a 3D maze is presented based on the quadrilateral mesh surface. This approach mainly consists of three steps:Firstly, the quadrilateral mesh is generated on the given 3D surface; Secondly, the start point and end point of the maze are chosen alternatively, and the maze on the quadrilateral mesh surface is obtained by the algorithm of generating a 2D maze which is based on a spanning tree algorithm; At last, the maze is turned into 3D structure, and 3D maze is generated by Boolean operation between the 3D structure and the original 3D model. Several personalized 3D maze toys are produced by 3D printer, which consumedly enhances fun and user experience.
[1] 余洋,张伶伶,杨晓军."迷宫"——景观的神秘体验[J].华中建筑,2010(2):29-31. YU Y, ZHANG L L, YANG X J. "Labyrinth":The landscape mystical experience[J]. Huazhong Architecture,2010(2):29-31.
[2] CHENG T K, XIANG L M, LYN T Y, et al. To?:journey or destination?[C]//Proceedings of the 12th International Conference on Advances in Computer Entertainment Technology. New York:ACM,2015:37.
[3] WANG D, ZHANG C, WANG H. T-maze:A tangible programming tool for children[C]//Proceedings of the 10th International Conference on Interaction Design and Children. Now York:ACM,2011:127-135.
[4] LLOTET J, KIRTON T. The maze EV:A two player installation game[C]//Proceedings of the 8th International Conference on Advances in Computer Entertainment Technology. New York:ACM,2011:1-2.
[5] HUANG T W, WU P C, WONG M D F. UI-route:An ultra-fast incremental maze routing algorithm[C]//Proceedings of SLIP (System Level Interconnect Prediction) on System Level Interconnect Prediction Workshop. New York:ACM,2014:1-8.
[6] PHILLIPS A. The topology of Roman mosaic mazes[J]. Leonardo,1993,25(3/4):65-73.
[7] MCCLENDON M S. The complexity and difficulty of a maze[C]//Bridges:Mathematical Connections in Art, Music, and Science. Bridges Conference,2001:213-222. http//archive.bridges mathart.org/2001/bridges2001-213pdf.
[8] XU J, KAPLAN C S. Vortex maze construction[J]. Journal of Mathematics and the Arts,2007,1(1):7-20.
[9] XU J, KAPLAN C S. Image-guided maze construction[J]. ACM Transactions on Graphics,2007,26(3):Article No.29.
[10] 袁开,友杨勇.平面迷宫地图随机生成树算法设计与实现[J].科学咨询,2013(1):138-139. YUAN K, YOU Y Y. Plane random tree algorithm design and implementation of maze map[J]. Scientific Consult,2013(1):138-139.
[11] 田翠花,许卫平,陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报,2013,29(3):19-24. TIAN C H, XU W P, CHEN Y M. Application of depth-first traversal, randomly distributed point algorithm and backtracking method to maze game[J]. Journal of Hebei North University:Natural Science Edition,2013,29(3):19-24.
[12] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007. YAN W M, WU W M. Data Structure (C Language Version)[M]. Beijing:Tsinghua University Press,2007.
2017, Vol. 44 
