An Extensive Comparative Analysis on Different Maze Generation Algorithms

Authors

  • Deepak Mane Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India
  • Rajat Harne Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India
  • Tanmay Pol Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India
  • Rashmi Asthagi Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India
  • Sandip Shine Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India
  • Bhushan Zope Vishwakarma Institute of Technology, Pune-411037, Maharashtra, India

Keywords:

Artificial Intelligence, Maze Generation, robot, maze, genetic algorithms

Abstract

In this paper, we compared maze generation algorithms. The nature of maze generation algorithms is analyzed, and the best amongst them is determined. The algorithms studied are Prim's algorithm, Kruskal's algorithm, DFS algorithm (Depth First Search), Ellers algorithm, Wilson's Algorithm, Hunt and Kill algorithm, and Aldous-Broder algorithm. The performance evaluation of the algorithms is determined by two parameters: the time taken by the algorithm to generate the maze and the space complexity of the maze. Evaluations are done based on the number of variables, including the number of intersections and dead ends visited, along with the overall steps taken by the agents, to determine how tough a maze is to navigate. The maze-generating algorithms are scored based on the performance of the agents. The algorithms' performance determines the most effective algorithms. The outcome is laid out analytically and graphically, showing a detailed analysis report of the algorithms' advantages and disadvantages. This report can be helpful in the field of gaming development, AI training, robotics, and automation. Such detailed comparative analyses have yet to be carried out on maze generation. Our research has bridged this research gap on maze generation algorithms and provided a detailed comparative analysis of maze generation algorithms.

Downloads

Download data is not yet available.

References

Gailand Macqueen. The spirituality of mazes andlabyrinths. Wood Lake Publishing Inc., 2005.

M. Karova, I. Penev and N. Kalcheva, "Comparative analysis of algorithms to search for the shortest path in a maze," 2016 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), Varna, Bulgaria, 2016, pp. 1-4, doi: 10.1109/BlackSeaCom.2016.7901597.

-m. Bae, E. K. Kim, J. Lee, K. -J. Kim and J. -C. Na, "Generation of an arbitrary shaped large maze by assembling mazes," 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan, 2015, pp. 538-539, doi: 10.1109/CIG.2015.7317901.

K. Susanto, R. Fachruddin, M. I. Diputra, D. Herumurti and A. A. Yunanto, "Maze Generation Based on Difficulty using Genetic Algorithm with Gene Pool," 2020 International Seminar on Application for Technology of Information and Communication (iSemantic), Semarang, Indonesia, 2020, pp. 554-559, doi: 10.1109/iSemantic50169.2020.9234216.

K. Okano and K. Matsuyama, "A Method for Generating Mazes with Length Constraint using Genetic Programming," 2020 Nicograph International (NicoInt), Tokyo, Japan, 2020, pp. 39-42, doi: 10.1109/NicoInt50878.2020.00014.

Kozlova, J. A. Brown and E. Reading, "Examination of representational expression in maze generation algorithms," 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan, 2015, pp. 532-533, doi: 10.1109/CIG.2015.7317902.

K. Wei, Y. Gao, W. Zhang and S. Lin, "A Modified Dijkstra’s Algorithm for Solving the Problem of Finding the Maximum Load Path," 2019 IEEE 2nd International Conference on Information and Computer Technologies (ICICT), Kahului, HI, USA, 2019, pp. 10-13, doi: 10.1109/INFOCT.2019.8711024.

X. He, Y. Wang and Y. Cao, "Researching on AI path-finding algorithm in the game development," 2012 International Symposium on Instrumentation & Measurement, Sensor Network and Automation (IMSNA), Sanya, China, 2012, pp. 484-486, doi: 10.1109/MSNA.2012.6324627.

Jain, "Evacuation map generation using maze routing," 2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT), Tiruchengode, India, 2013, pp. 1-6, doi: 10.1109/ICCCNT.2013.6726648.

S. Hidayatullah, A. N. Jati and C. Setianingsih, "Realization of depth first search algorithm on line maze solver robot," 2017 International Conference on Control, Electronics, Renewable Energy and Communications (ICCREC), Yogyakarta, Indonesia, 2017, pp. 247-251, doi: 10.1109/ICCEREC.2017.8226690.

Agnesia, and Wirawan Istiono, "Wall Pattern Detection with Prim�S Algorithm to Create Perfect Random Maze" Journal of Theoretical and Applied Information Technology 101, no.9.(2023)

V. Bellot, M. Cautrès, J-M. Favreau, M. Gonzalez-Thauvin, P. Lafourcade, K. Le Cornec, B. Mosnier, S. Rivière-Wekstein, “How to generate perfect mazes?” Information Sciences, Volume 572, 2021, pp. 444-459

Andrew Hernandez, Stephen Wright, Yosef Ben-David, Rodrigo Costa, David Botha. Optimizing Resource Allocation using Machine Learning in Decision Science. Kuwait Journal of Machine Learning, 2(3). Retrieved from http://kuwaitjournals.com/index.php/kjml/article/view/195

Timande, S., Dhabliya, D. Designing multi-cloud server for scalable and secure sharing over web (2019) International Journal of Psychosocial Rehabilitation, 23 (5), pp. 835-841.

Downloads

Published

27.10.2023

How to Cite

Mane, D. ., Harne, R. ., Pol, T. ., Asthagi, R. ., Shine, S. ., & Zope, B. . (2023). An Extensive Comparative Analysis on Different Maze Generation Algorithms. International Journal of Intelligent Systems and Applications in Engineering, 12(2s), 37–47. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/3557

Issue

Vol. 12 No. 2s (2024)

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.