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 solution path is carved on the opposite edges of the board in order to meet maze definition. Later, walls are built up on the even lines (or odd lines) and some parts of these lines randomly break off. Finally passages are constructed randomly between broken even lines. This technique opens new era to produce different versions of it for maze construction.
The algorithm is applied to a 100 100 board and evaluation compared with the well-known maze algorithms. Its prominent features are being more speedy (3.5 second) to construct and more complicated (10.32% dead ends) to solve.
PedersenHSinghK. Organic labyrinths and mazes. In Proceedings of the 4th International Symposium on Non-Photorealistic Animation and Rendering, 2006 June 05-07, Annecy, France: Association for Computing Machinery: 2006. pp. 79-86.
2.
PechAMasekMLamCPHingstonP. Game level layout generation using evolved cellular automata. Connection Science. 2016 Feb 12; 28(1): 63-82.
3.
AshlockDLeeCMcGuinnessC. Search-based procedural generation of maze-like levels. IEEE Transactions on Computational Intelligence and AI in Games. 2011 April 5; 3(3): 260-273.
4.
LeeH-LLeeC-FChenL-H. An improved method for hiding data in a maze. In Proceedings of Seventh International Conference on Machine Learning and Cybernetics; 2008 July 12–15, Kunming, China: IEEE, 2008. pp. 3161-3165.
5.
SukumarTSanthaKR. Maze based data hiding using back tracker algorithm. International Journal of Engineering Research and Applications (IJERA). 2012 July-August; 2(4): 499-504.
6.
Wyard-ScottLMengQ-HM. A potential maze solving algorithm for a micromouse robot. In Proceedings of Pacific Rim Conference on Communications, Computers, and Signal Processing, 1995 May 17-19, Victoria, BC, Canada: IEEE, 1995. pp. 614-618.
7.
ElshamarkaISamanABS. Design and implementation of a robot for maze-solving using flood-fill algorithm. International Journal of Computer Applications. 2012 October; 56(5): 8-13.
8.
PrimRC. Shortest connection networks and some generalizations. Bell System Technical Journal. 1957 November; 36(6): 1389-1401.
9.
GrossJLYellenJ. Graph theory and its applications. 2nd ed. New York: Chapman and Hall/CRC; 2005.
10.
KruskalJB. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 1956; 7: 48-50.
BitnerJRReingoldE. Backtracking programming techniques. Communications of the ACM. 1975 November; 18(11): 651-656.
13.
KnuthDE. Estimating the efficiency of backtrack programs. Mathematics of Computation. 1975 January; 29(129): 121-136.
14.
AldousDJ. A random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics. 1990 January 25; 3(4): 450-465.
15.
BroderA. Generating random spanning trees. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989 October 30–November 1; Research Triangle Park, NC, USA: IEEE: 2002. pp. 442-447.
16.
WilsonDB. Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996 May 22-24; Philadelphia, Pennsylvania, USA: Association for Computing Machinery: 1996. pp. 296-303.
17.
NiwayamaNChenNOgiharaTKenedaY. A steganographic method for mazes. In Proceedings of Pacific Rim Workshop on Digital Steganography, 2002 July 11-12, Kitakyushu, Japan. pp. 146-152.
18.
GrahamRLHellP. On the history of the minimum spanning tree problem. Annals of the History of Computing. 1985 January-March; 7(1): 43-57.
19.
RiskinEAGrayRM. A greedy tree growing algorithm for the design of variable rate vector quantizers. IEEE Transactions on Signal Processing. 1991 November; 39(11): 2500-2507.
20.
HazewinkelM, editor. Binary tree. Encyclopedia of Mathematics. London: Springer Science & Business Media; 2001.
21.
ZhangXO. Improvement of binary non-recursive algorithm. Journal of Jiamusi University (Natural Science Edition). 2012; 31: 926-928.
22.
HuJRoyJAMarkovIL. Sidewinder: A scalable ILP based router. In Proceedings of ACM Workshop on System Level Interconnect Prediction, 2008 April 5-8, Newcastle, United Kingdom, USA: Association for Computing Machinery: 2008. pp. 73-80.
23.
JanssenPLohPRaonicASchnabelMA. Protocols, flows and glitches. In: JahssenP, editors. Proceedings of the 22nd International Conference of the Association for Computer-Aided Architectural Design Research in Asia, 2017 April 5–8, Hong Kong, China. pp. 479-488.
24.
BuckJ. Mazes for programmers. 1st ed. USA: Pragmatic Bookshelf; 2015.
25.
McClendonMS. The complexity and difficulty of a maze. In: SarhangiRJablanS, editors. Proceedings of Bridges 2001: Mathematical Connections in Art, Music, and Science, 2001 July 27-29, Winfield, Kansas, USA. pp. 213-222.
26.
ShahSHMohiteJMMusaleAGBoradeJL. Survey paper on maze generation algorithms for puzzle solving games. International Journal of Scientific & Engineering Research. 2017 February; 8(2): 1064-1067.
27.
BellotVCautrèsMFavreauJ-MThauvinMGLafourcadePCornecKLMosnierBWeksteinSR. How to Generate Perfect Mazes?Information Sciences. 2021 September; 572(3): 444-459.
28.
BieniasŁSzczepanskiKDuchP. Maze exploration algorithm for small mobile platforms. Image Processing & Communications. 2016 September; 21(3): 15-26.
29.
Google play store for games [Internet]. stanbul: Emircan Pekyürek; 2017 [cited 2020 Nov 13]. Available from https://play.google.com/store/apps/details?id=com.escape.labyrinth.
30.
BoldovsIVinogradovsJ. Comparison of maze generation algorithms. In 20th International Scientific Practical Conference of Students, Human, Environment, Technology, 2016 April 20, Rezekne, Latvia. pp. 40-43.
31.
Maze algorithms [Internet]. USA: Astrolog.org; [cited 2021 Oct 29]. Avaliable from https://www.astrolog.org/labyrnth/algrithm.htm.
