СИСТЕМНИЙ АНАЛІЗ АЛГОРИТМІВ ГЕНЕРАЦІЇ ЛАБІРИНТІВ ДЛЯ ІНТЕРАКТИВНИХ ІГРОВИХ СЕРЕДОВИЩ

Олена Трофименко; Олександр Задерейко; Олег Янковський; Володимир Каіров; Ганна Морозова

doi:10.28925/2663-4023.2025.30.972

Автор(и)

Олена Трофименко Національний університет «Одеська юридична академія» https://orcid.org/0000-0001-7626-0886
Олександр Задерейко Національний університет «Одеська юридична академія» https://orcid.org/0000-0003-0497-9861
Олег Янковський Kruty Heroes Military Institute of Telecommunications and Information Technology https://orcid.org/0000-0001-8041-1843
Володимир Каіров Національний університет кораблебудування імені адмірала Макарова https://orcid.org/0000-0003-0502-7942
Ганна Морозова Національний університет кораблебудування імені адмірала Макарова https://orcid.org/0009-0005-9149-7378

DOI:

https://doi.org/10.28925/2663-4023.2025.30.972

Ключові слова:

алгоритми; оптимальність алгоритмів; графи; генерація лабіринтів; розробка ігор; лабіринт; машинне навчання

Анотація

Лабіринти у відеоіграх слугують не лише інструментом навігації, а й комплексним елементом дизайну, який поєднує технічні, естетичні та ігрові функції. Використання процедурної генерації, інтерактивних елементів та адаптивних систем дозволяє реалізувати інноваційні підходи до побудови віртуального простору. Мета дослідження полягає у формуванні системної класифікації алгоритмів процедурної генерації лабіринтів для застосування в розробці відеоігор, а також у визначенні їх функціональних характеристик, переваг і обмежень з урахуванням технічних і геймдизайнерських вимог. Актуальність теми дослідження зумовлена зростанням ролі процедурного контенту в сучасному геймдеві, що забезпечує підвищену реіграбельність, адаптивність і зниження витрат на ручне проєктування рівнів. У межах дослідження проведено огляд і порівняльний аналіз сучасних алгоритмів генерації лабіринтів, зокрема класичних (DFS, Прима, Крускала, Еллера, Вілсона, Олдоса-Бродера), клітинних автоматів (Rule 4/5, Conway CA, Maze CA, Mazectric, Hybrid CA), шумових функцій (Perlin, Simplex, Worley), фрактальних систем (L-системи, криві Гільберта) та алгоритмів на основі машинного навчання (нейроеволюція, WFC, марковські моделі). Запропоновано класифікацію алгоритмів за типом базової структури (граф, решітка, автомат, шум, ML-модель), що дозволяє систематизувати підходи до генерації лабіринтів залежно від архітектурних і функціональних ознак. Встановлено, що класичні алгоритми забезпечують високу передбачуваність і продуктивність, тоді як клітинні автомати та гібридні підходи дозволяють створювати складні, органічні або декоративні структури. Наукова новизна полягає у створенні уніфікованої класифікації алгоритмів генерації лабіринтів, яка враховує як структурні, так і геймплейні параметри, що дозволяє обґрунтовано вибирати оптимальні рішення для конкретних ігрових задач. Практичне значення роботи полягає в можливості використання результатів для побудови адаптивних систем генерації рівнів, створення навчальних платформ для вивчення алгоритмів, а також розробки рекомендаційних систем вибору алгоритмів залежно від жанру гри, технічних обмежень та очікуваної складності.

Завантаження

Дані завантаження ще не доступні.

Посилання

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