SYSTEMATIC ANALYSIS OF MAZE GENERATION ALGORITHMS IN INTERACTIVE GAME ENVIRONMENTS
DOI:
https://doi.org/10.28925/2663-4023.2025.30.972Keywords:
algorithms; optimality of algorithms; graphs; maze generation; game development; maze; machine learningAbstract
Labyrinths in video games serve not only as navigation tools but also as complex design elements that combine technical, aesthetic, and gameplay functions. The use of procedural generation, interactive elements, and adaptive systems enables innovative approaches to construct virtual spaces. The purpose of this study is to develop a systematic classification of algorithms for the procedural generation of labyrinths for use in video game development and to determine their functional characteristics, advantages, and limitations, considering technical and game design requirements. The relevance of the research lies in the growing importance of procedural content in modern game development, which enhances replayability, adaptability, and reduces the cost of manual level design. This study presents a review and comparative analysis of modern maze generation algorithms, including classical approaches (DFS, Prim’s, Kruskal’s, Eller’s, Wilson’s, Aldous-Broder), cellular automata (Rule 4/5, Conway’s Game of Life, Maze CA, Mazectric, Hybrid CA), noise functions (Perlin, Simplex, Worley), fractal systems (L-systems, Hilbert curves), and machine learning-based algorithms (neuroevolution, Wave Function Collapse, Markov models). A classification of algorithms by the type of underlying structure (graph, grid, automaton, noise, ML model) is proposed, allowing for the systematization of maze generation approaches based on architectural and functional characteristics. It is established that classical algorithms offer high predictability and performance, while cellular automata and hybrid methods enable the creation of complex, organic, or decorative structures. The scientific novelty of the study lies in the development of a unified classification of maze generation algorithms that consider both structural and gameplay parameters, thus enabling informed choices of optimal solutions for specific game design tasks. The practical significance of this work lies in its applicability to build adaptive level generation systems, creating educational platforms for studying algorithms, and developing recommendation systems for selecting algorithms based on game genre, technical constraints, and desired complexity.
Downloads
References
Marchuk, G.V. & Liubchenko, D.V. (2024). Generation of mazes using the hunt-and-kill algorithm. Scientific notes of Taurida National V.I. Vernadsky University. Series: Technical Sciences, 35 (74), 3, 130-135. https://doi.org/10.32782/2663-5941/2024.3.1/20
Binayak, B. (2025). Interactive Maze Generation and Pathfinding Algorithms: An Educational Visualization Platform for Algorithmic Analysis. Zenodo. https://doi.org/10.5281/zenodo.15824242
Vijaya, J., Gopu, A., Vinayak, K., Singh, J., Malhotra, K. (2024). Analysis of Maze Generation Algorithms. 5th IEEE International Conference on Innovative Trends in Information Technology (ICITIIT), Kottayam, India, 15-16 March 2024, 1-6. https://doi.org/10.1109/ICITIIT61487.2024.10580178
Čarapina, M., Staničić, O., Dodig, I., & Cafuta, D. (2024). A Comparative Study of Maze Generation Algorithms in a Game-Based Mobile Learning Application for Learning Basic Programming Concepts. Algorithms, 17(9), 404. https://doi.org/10.3390/a17090404
Cahyakusuma, I. & Istiono, W. (2024). Algorithmic diversity in maze generation: Comparative study of Backtracking, Kruskal's, Prim's, and Eller's algorithms. International Journal of Intelligent Systems and Applications in Engineering, 12(3), 1281–1287. https://ijisae.org/index.php/IJISAE/article/view/5518
Marchuk, G. V., Graf, М. S., Levkivskyi, V. L., & Venhlovska, Yu. V. (2024). Analysis and comparison of existing maze generation methods in computer games. Visnyk of Kherson National Technical University, 3(90), 228-237. https://doi.org/10.35546/kntu2078-4481.2024.3.29
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(2), 37-47. https://ijisae.org/index.php/IJISAE/article/view/3557
Piao, J., Hu, X., & Zhou, Q. (2024). Maze and navigation algorithms in game development. Applied and Computational Engineering, 79, 11-19. https://doi.org/10.54254/2755-2721/79/20241081.
Malem, F. (2023). Wall Object Design in Maze Game Using Cellular Automata Algorithm. Journal of Computer Engineering: Progress, Application and Technology. 2(1), 27-35. https://doi.org/10.25124/cepat.v2i01.5781.
Yang, K., Lin, S., Dai, Yu., & Li, W. (2024). Optimization and comparative analysis of maze generation algorithm hybrid. Applied and Computational Engineering, 79, 20-33. https://doi.org/10.54254/2755-2721/79/20241082.
Trofymenko, O., Zadereyko О., Balandina, N., Tolocknov, A., & Huselnikov, I. (2024). Vector algebra for gamedev. Electronic Professional Scientific Journal «Cybersecurity: Education, Science, Technique», 2(26), 71-80. https://doi.org/10.28925/2663-4023.2024.26.626.
Xu, J. & Morris, J. (2023). Procedural generation in 2d metroidvania game with answer set programming and perlin noise. International Journal of Artificial Intelligence & Applications, 14, 21-35. https://doi.org/10.5121/ijaia.2023.14302.
Trofymenko, O.G., Zadereyko, О.V., Loginova, N.I., & Shevchenko, O.V. (2025). Artificial intelligence tools in the development of graphic elements, 3D models and other video game components. Informatics and mathematical methods in simulation, 15(2), 276-287. https://doi.org/10.15276/imms.v15.no2.276
Alaka, Sh. & Bidarra, R. (2023). Hierarchical Semantic Wave Function Collapse. FDG '23: Proceedings of the 18th International Conference on the Foundations of Digital Games, 68, 1-10. https://doi.org/10.1145/3582437.3587209.
Linden, R., Lopes, R., & Bidarra, R. (2014). Procedural Generation of Dungeons. IEEE Transactions on Computational Intelligence and AI in Games. Volume: 6, Issue: 1, March 2014, 78-89. https://doi.org/10.1109/TCIAIG.2013.2290371.
Tanaka T. & Simo-Serra E. Grammar-based Game Description Generation using Large Language Models. arXiv. https://doi.org/10.48550/.2407.17404
Shaker, N., Liapis, A., Togelius, Ju., Lopes, R., & Bidarra, R. (2016). Constructive generation methods for dungeons and levels. Computational Synthesis and Creative Systems (CSACS), 31-55. https://doi.org/10.1007/978-3-319-42716-4_3.
Markov Chains for Procedural Buildings. https://nickmcd.me/2019/10/30/markov-chains-for-procedural-buildings/
Dou, H., Du, J., Jiang, X., H, Li., Yao, W., & Deng, Y. (2025). Image-to-Image Bayesian Flow Networks With Structurally Informative Priors. IEEE Transactions on Image Processing, 34, 4968-4982. https://doi.org/10.1109/TIP.2025.3592546.
Setiadharma, E., Husniah, L., & Kholimi, A. S. (2024). Algoritma Maze Generator Recursive Backtracking Untuk Membuat Prosedural Labirin Pada Game Petualangan Labirin 3D. Jurnal Repositor, 2(3), 373-384. https://doi.org/10.22219/repositor.v2i3.30509
Duffy, Ch., Hillis, S., Khan, U., McQuillan, I., & Shan, S. (2025). Inductive inference of lindenmayer systems: algorithms and computational complexity. Natural Computing. 1-11. https://doi.org/10.1007/s11047-025-10024-x.
Yuichi, N., Akinori, I., & Norihiko, O. (2019). A Genetic Algorithm for the Picture Maze Generation Problem. Computers & Operations Research, 115, 104860. https://doi.org/10.1016/j.cor.2019.104860.
Krishnaa, K., Kaluri, J., Konjeti, S., Aravind, T., & Gurusamy, J. (2022). A Genetic Algorithm Framework to Solve Two-Dimensional Maze Problem. Proceedings of 3rd International Conference on Machine Learning, Advances in Computing, Renewable Energy and Communication, 2022, 18 September, 277-284. https://doi.org/10.1007/978-981-19-2828-4_27.
Trofymenko, O., Dyka, A., Loboda, Y., Tolocknov, A., & Bondarenko, M. (2025). Artificial intelligence in the gamedev. Electronic Professional Scientific Journal «Cybersecurity: Education, Science, Technique», 3(27), 109-119. https://doi.org/10.28925/2663-4023.2025.27.701.
Khalifa, A., Bontrager, P., Earle, S., & Togelius, J. PCGRL: Procedural Content Generation via Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 2020. 16(1), 95-101. https://doi.org/10.1609/aiide.v16i1.7416
Trofymenko, O., Dyka, A., Zadereyko О., & Shevchenko О. (2025). Areas of application of artificial intelligence in game development and testing. Electronic Professional Scientific Journal «Cybersecurity: Education, Science, Technique», 1(29), 41-58. https://doi.org/10.28925/2663-4023.2025.29.832
Summerville, A., et al. Procedural content generation via machine learning (PCGML). arXiv. 1702.00539. https://doi.org/10.48550/arXiv.1702.00539
Alaguna C., Gomez Jo. Maze benchmark for testing evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '18). 2018. 1321-1328. https://doi.org/10.1145/3205651.3208285
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Олена Трофименко, Олександр Задерейко, Олег Янковський, Володимир Каіров, Ганна Морозова
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
