Algorithms for procedural generation of game content using graphs

Abstract

Розробка унікальних ігрових середовищ з використанням алгоритмів на основі графових структур даних та процедурної генерації контенту дозволяє суттєво скоротити витрати при одночасному підви-щенні загальної продуктивності команди та усуненні ризику стагнації процесу розробки. Метою роботи є аналіз, розробка та візуалізація роботи алгоритмів процедурної генерації контенту, а також вивчення перспектив їх подальшого використання у практичній розробці ігрових проектів. Наукова новизна полягає у використанні графів для процедурної генерації ігрового контенту. Ця тема була обрана у зв’язку з тим, що створення ігрового оточення може бути однією з основних і найбільш ресурсоємних витрат у процесі виробництва гри. Процедурна генерація контенту може зменшити ці витрати та пришвидшити процес розробки. Практично неможливо підрахувати, яку конкретно частину продуктивності команди та бізнес-вигоди приносить процедурна генерація, оскільки більшість інновацій у цій сфері є комерційною таємницею ігрових студій, однак це говорить лише про можливості та переваги, які несе в собі цей підхід. Методологія базується на мові програмування The Python як основному інструменті для вивчення алгоритмів, який використовувався для розробки алгоритмів, створення візуалізацій та прикладів веб-серверів для обробки даних, згенерованих графами. Висновок: під час розробки були вивчені відмінності та спільні риси в деталях реалізації алгоритмів, а також результати генерації контенту. Також було продемонстровано відмінності у згенерованих графах. На прикладах веб-серверів проілюстровано потенціал подальшого практичного застосування розроблених алгоритмів. Результати дослідження можуть бути використані розробниками ігрових середовищ та дослідниками алгоритмів для підвищення ефективності виробничих процесів. Ключові слова: процедурна генерація, розробка ігор, ефективність розробки, оптимізація розробки.

Developing unique gaming environments using algorithms based on graph data structures and procedural content generation can significantly reduce costs while increasing overall team productivity and eliminating the risk of stagnation in the development process. The purpose of this research is to analyze, develop and visualize the operation of procedural content generation algorithms, as well as to study the prospects for their further use in the practical development of game projects. The scientific novelty is to use graphs for procedural generation of game content. This topic was chosen due to the fact that creating a game environment can be one of the main and most resource-intensive costs in the game production process. Procedural content generation can reduce these costs and speed up the development process. In fact, it is almost impossible to calculate what specific part of the team’s productivity and business benefits procedural generation brings, since most discoveries in this area are a trade secret of most game studios, however, this only speaks of the opportunities and benefits that this approach brings. The methodology is based on The Python programming language as the main tool for studying algorithms, which was used to develop algorithms, create visualizations and examples of web servers for processing data generated by graphs. Conclusion: during development, differences and commonalities in the details of the implementation of algorithms, as well as the results of content generation, were studied. Differences in the generated graphs were also demonstrated. Examples of web servers illustrate the potential for further practical application of the developed algorithms. The results of the study can be used by developers of gaming environments and algorithms researchers to improve the efficiency of production processes.