Сучасна індустрія розробки відеоігор потребує ефективних методів автоматичного створення ігрового контенту. Ручне проектування рівнів є ресурсомістким процесом, тому процедурна генерація контенту (PCG) набуває все більшого практичного значення. Особливої актуальності набуває розробка гібридних систем, що поєднують переваги кількох алгоритмів для досягнення якісних та різноманітних результатів.
Метою роботи є розробка гібридної системи процедурної генерації ігрових рівнів, що поєднує алгоритми BSP, клітинного автомату та шуму Перліна, а також оригінальний алгоритм Trajectory Pattern Mapping (TPM) для генерації фінального патерн-замка на основі журналу дій гравця.
Процедурна генерація контенту – це метод автоматичного створення ігрового контенту за допомогою алгоритмів і математичних правил, що може бути формально описаний як функція: Content = f(seed, parameters), де seed – початкове числове значення що ініціалізує генератор псевдовипадкових чисел, parameters – набір налаштувань, що визначають характер генерованого контенту [1]. Це забезпечує нескінченну варіативність при збереженні детермінованості: однаковий seed завжди породжує ідентичний контент.
У розробленій системі застосовано чотири алгоритми. По-перше, алгоритм Binary Space Partitioning (BSP) здійснює рекурсивне розбиття ігрового простору для генерації кімнат і коридорів. Ключовою перевагою BSP є гарантія зв'язності всіх кімнат і відсутності їх перетинань [2]. За результатами проведених випробувань для карти 80×60 час генерації не перевищує 150 мс. По-друге, клітинний автомат (CA) використовується для розміщення ворогів: ітеративне застосування правил народження і смерті клітин за правилом Мура формує природні кластери, що забезпечують тактичну різноманітність [3]. По-третє, шум Перліна забезпечує просторово когерентний розподіл ключів і виходів, унеможливлюючи їх концентрацію в одній зоні карти [4].
Основним науковим внеском роботи є оригінальний алгоритм Trajectory Pattern Mapping (TPM). Він перетворює журнал просторових дій гравця у детермінований бінарний патерн на сітці методом витягування «слів» руху. Алгоритм складається з трьох фаз:
1) збір телеметрії переміщень гравця по рівню,
2) кодування траєкторій у послідовності символів напрямків,
3) проекція закодованих патернів на двовимірну булеву сітку фінального замка.
Таким чином, конфігурація фінального патерн-замка є унікальним просторовим відбитком індивідуальної поведінки гравця. Це принципово відрізняє TPM від існуючих підходів, де кінцевий рівень не залежить від попередніх дій.
Систему реалізовано у вигляді гри SIGNAL на платформі Unity 6 з використанням мови програмування C#, підтримкою Universal Render Pipeline 2D освітлення та системи тайлів Unity Tilemap. Проведено модульне та інтеграційне тестування всіх компонентів: підтверджено коректність роботи алгоритмів, стабільність генерації та відповідність результатів заданим параметрам.
Порівняльний аналіз показав, що розроблена система перевершує аналоги (Spelunky Generator, Dungeon Architect) за рахунок унікальної персоналізації фінального контенту на основі поведінки гравця. Гібридний підхід дозволяє поєднати структурованість BSP, органічність клітинного автомату та адаптивність TPM в єдиній архітектурі.
Практичне значення результатів полягає у можливості використання розробленої системи як основи для roguelike-ігор з процедурною генерацією, а алгоритму TPM – як підходу до генерації контенту на основі поведінкової телеметрії, що має потенціал застосування в адаптивних навчальних системах та інтерактивних симуляціях.
Перспективами подальшого розвитку роботи є: додавання алгоритму Recursive Backtracker для генерації лабіринтних коридорів; реалізація системи мета-прогресії; розширення TPM алгоритму додатковими типами дій та багатошаровими патернами; підтримка мобільних платформ.
Результати роботи можуть бути використані як основа для подальших досліджень у галузі процедурної генерації, орієнтованої на досвід гравця, а також як практичний приклад інтеграції кількох алгоритмів генерації в єдину систему.
Список літератури:
1. Shaker N., Togelius J., Nelson M. J. Procedural Content Generation in Games. Springer, 2016. 244 p.
2. de Berg M., Cheong O., van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed. Springer, 2008. 386 p.
3. Gardner M. Mathematical Games: The fantastic combinations of John Conway’s new solitaire game ‘life’. Scientific American. 1970. Vol. 223, No 4. P. 120–123.
4. Perlin K. An Image Synthesizer. ACM SIGGRAPH Computer Graphics. 1985. Vol. 19, No 3. P. 287–296.
5. Zamorano M., Cetina C., Sarro F. The Quest for Content: A Survey of Search-Based Procedural Content Generation for Video Games. arXiv:2311.04710 [cs.SE]. 2023. DOI: 10.48550/arXiv.2311.04710.
6. Farrokhi Maleki M., Zhao R. Procedural Content Generation in Games: A Survey with Insights on Emerging LLM Integration. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 2024. Vol. 20, No. 1. P. 167–178. DOI: 10.1609/aiide.v20i1.31877.
|
Голосування 
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter