Процедурна генерація 2D-карт на основі клітинних автоматів генерування 2D-карт
DOI:
https://doi.org/10.15330/itee.2026.4.06Ключові слова:
Процедурна генерація, клітинні автомати, двовимірні карти, ігрові середовища, генерація рівнів, алгоритми, сусідство Мура, С++Анотація
У роботі показано, що використання клітинних автоматів є ефективним підходом для процедурної генерації двовимірних ігрових карт, оскільки дозволяє формувати складні та природоподібні структури на основі простих локальних правил. Досліджено особливості побудови карт у вигляді дискретної сітки, де кожна клітина має бінарний стан — «стіна» або «прохід». Розглянуто вплив ключових параметрів алгоритму, зокрема початкової ймовірності появи стін, кількості ітерацій та порогового значення кількості сусідніх клітин у межах сусідства Мура.
Встановлено, що початкова ймовірність заповнення карти суттєво впливає на загальну структуру середовища: при низьких значеннях формуються відкриті простори, а при високих — щільні та непрохідні області. Оптимальним є діапазон 45–50 %, який забезпечує баланс між прохідністю та щільністю карти. До-слідження також показало, що кількість ітерацій клітинного автомата визначає ступінь згладжування структури: при недостатній кількості ітерацій зберігається хаотичність, а при надмірній — структура втрачає різноманітність. Найбільш збалансовані результати досягаються при виконанні 4–7 ітерацій.
Окрему увагу приділено правилам переходу клітин, які базуються на підрахунку кількості сусідів. Використання порогового значення, близького до п’яти сусідніх клітин, дозволяє отримати природні пере-ходи між областями та уникнути надмірної фрагментації карти. У роботі також реалізовано програмну модель алгоритму мовою C++ із використанням бібліотеки SFML для візуалізації процесу генерації.
Отримані результати підтверджують, що клітинні автомати забезпечують гнучкість налаштування параметрів, високу варіативність результатів та ефективність у задачах генерації ігрових середовищ. За-пропонований підхід може бути використаний у відеоіграх, навчальних симуляціях та дослідницьких проєктах, де необхідне автоматичне створення структурованих просторів.
Посилання
T. Gao, J. Zhang, and Q. Mi, “Procedural generation of game levels and maps: A review,” in Proc. 2022 Int. Conf. Artif. Intell. Inf. Commun. (ICAIIC), Jeju Island, Korea, Feb. 2022, pp. 248–253. doi: https://doi.org/10.1109/icaiic54071.2022.9722624 ..
B. M. F. Viana and S. R. dos Santos, “Procedural dungeon generation: A survey,” J. Interact. Syst., vol. 12, no. 1, pp. 83–101, 2021. doi: https://doi.org/10.5753/jis.2021.999.
E. W. Hidayat, E. N. F. Dewi, and I. S. Ramadhan, “Application of procedural content generation system in forming dungeon level in Dungeon Diver game,” J. Tek. Inform. (Jutif), vol. 5, no. 3, pp. 873–881, 2024. doi: https://doi.org/10.52436/1.jutif.2024.5.3.1465.
Z. Shen, “Procedural generation in games: Focusing on dungeons,” SHS Web Conf., vol. 144, p. 02005, 2022. doi: https://doi.org/10.1051/shsconf/202214402005.
J. Vijaya et al., “Analysis of maze generation algorithms,” in Proc. 2024 5th Int. Conf. Innov. Trends Inf. Technol. (ICITIIT), Kottayam, India, Feb. 2024, pp. 1–6. doi: https://doi.org/10.1109/ICITIIT61487.2024.10580178.
G. N. Yannakakis and J. Togelius, “Procedural content generation by content type,” in Artificial Intelli-gence and Games, Cham, Switzerland: Springer, 2025, pp. 287–312. doi: https://doi.org/10.1007/978-3-031-83347-2_9.
J. T. Balint and R. Bidarra, “Procedural generation of narrative worlds,” IEEE Trans. Games, vol. 15, no. 2, pp. 143–153, Jun. 2023. doi: https://doi.org/10.1109/tg.2022.3216582.
E. Soares de Lima, B. Feijó, and A. L. Furtado, “Procedural generation of quests for games using genetic algorithms and automated planning,” in Proc. 2019 18th Brazilian Symp. Comput. Games Digit. Entertain. (SBGames), Rio de Janeiro, Brazil, Oct. 2019, pp. 495–504. doi: https://doi.org/10.1109/sbgames.2019.00028. .
О. Трофименко, О. Задерейко, О. Янковський, В. Каіров, Г. Морозова, “Системний аналіз алгоритмів генерації лабіринтів для інтерактивних ігрових середовищ”, Кібербезпека: освіта, наука, техніка, т. 2, № 30, с. 259–279, 2025. doi: https://doi.org/10.28925/2663-4023.2025.30.972.
Wu, Z. Mao, Y. Li, Q. “Procedural game map generation using multi-leveled cellular automata by ma-chine learning”. In: Proceedings of the 2nd International Symposium on Artificial Intelligence for Medicine Sci-ences. 2021. p. 168-172.. doi: https://doi.org/10.1145/3500931.3500962
M. Metkar, N. Sah, Y. Zhou, “Cellular Automata: From Structural Principles to Transport and Correlation Methods”. arXiv preprint arXiv:2601.01278, 2026. doi: https://doi.org/10.48550/arXiv.2601.01278
K. Vayadande, et al. “Simulation of Conway’s game of life using cellular automata”. Simulation, 2022
H. Sayama, C. L Nehaniv,. “Self-reproduction and evolution in cellular automata: 25 years after evo-loops”. Artificial Life, 2024, 31.1: 81-95. doi: https://doi.org/10.1162/artl_a_00451
Joel Reyes, et al.” Game of sensors: An energy-efficient method to enhance network lifetime in wireless sensor networks using the game of life cellular automaton”. IEEE Access, 2022, 10: 129687-129701. doi: https://doi.org/10.1109/ACCESS.2022.3228585
Ю. Іляш. В. Горєлов, В.С. Антоняк , “Алгоритми клітинних автоматів для генерації рівнів у комп’ютерних іграх”. Вчені записки ТНУ імені В.І. Вернадського. Серія: Технічні науки, Том 37 (76) № 2 2026. Частина 1, с. 108 – 113 doi: https://doi.org/10.32782/2663-5941/2026.2.1/16
O. Zhezherun, B. Kalitovskyi, “Використання клітинних автоматів для вирішення задач фільтрації шумів та виявлення контурів зображень”. Наукові записки НаУКМА. Комп’ютерні науки, 2, 66–72. doi https://doi.org/10.18523/2617-3808.2019.2.66-72
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2026 Діана Козачок, Юрій Іляш

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.