REVIEW AND ANALYSIS OF PROCEDURAL GAME WORLD GENERATION ALGORITHMS
DOI:
https://doi.org/10.32782/tnv-tech.2024.4.9Keywords:
Perlin Noise, Improved Noise, Simplex Noise, Diamond-Square, Fractal Noise, procedural generation, game development, location creation.Abstract
Computer games have become an essential part of modern culture and entertainment. One of the key elements influencing the player's perception of a game is the game world where the events unfold. With the growth of the gaming industry and the increasing popularity of video games, there is a need for rapid creation of new game worlds. In this context, the application of procedural generation algorithms proves useful, as they allow for the automatic creation of game environments with specific characteristics. Procedural generation of game worlds is a method that enables the creation of diverse game environments using algorithms and random processes. Today, various procedural generation algorithms exist, such as noise generation algorithms, fractal geometry, and cellular automata. The purpose of this research is to analyze algorithms, methods, and approaches to procedural generation of 3D game worlds, describe their operation, and identify their unique features. The study examined algorithms such as Perlin Noise, Improved Noise, Simplex Noise, Diamond-Square, and Fractal Noise. The chosen evaluation criteria included performance speed, generation quality, and memory efficiency. The quality of generation was assessed in terms of the realism and variety of the generated locations. For games where landscape generation speed is crucial, Simplex Noise and Diamond-Square are more suitable. While Diamond-Square is easy to implement, it is less flexible for large worlds. If a highly detailed map is required, Fractal Noise is the best choice, though it demands significant computational resources. For creating interesting and diverse game worlds, it is better to combine several algorithms, for instance, one for creating the base landscape and another for adding detail. Procedural generation algorithms allow the creation of vast, detailed worlds with minimal manual intervention, significantly saving time and resources while making the game more interactive and unpredictable.
References
Balint J. T., Bidarra R. Procedural Generation of Narrative Worlds. IEEE Transactions on Games. Vol. 15, no. 2. Pp. 262-272. June 2023. DOI: https://doi.org/10.1109/TG.2022.3216582.
Deitke M., VanderBilt E., Herrasti A. et all. ProcTHOR: Large-Scale Embodied AI Using Procedural Generation. Advances in Neural Information Processing Systems. Vol. 35. Pp. 5982-5994. 2022.
Gellel A., Sweetser P. A Hybrid Approach to Procedural Generation of Roguelike Video Game Levels. In Proceedings of the 15th International Conference on the Foundations of Digital Games (FDG '20). Association for Computing Machinery, New York, NY, USA, Article 3. Pp. 1–10. 2020. DOI: https://doi.org/10.1145/3402942.3402945.
Mark B., Berechet T., Mahlmann T., Togelius J. Procedural Generation of 3D Caves for Games on the GPU. Paper presented at Foundations of Digital Games, United States. 2015. URL: https://lucris.lub.lu.se/ws/portalfiles/portal/6067634/5464988.pdf.
Soares de Lima E., Feijó B., Furtado A. L. Procedural Generation of Quests for Games Using Genetic Algorithms and Automated Planning. 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), Rio de Janeiro, Brazil. Pp. 144-153. 2019. DOI: https://doi.org/10.1109/SBGames.2019.00028.
Fischer R., Dittmann P., Weller R. et al. AutoBiomes: procedural generation of multi-biome landscapes. The Visual Computer. Vol. 36. Pp. 2263–2272. 2020. DOI: https://doi.org/10.1007/s00371-020-01920-7.
Марчук Д.К., Левківський В.Л., Марчук Г.В., Голенко М.Ю. Система розпізнавання дактильної мови української абетки. Вчені записки Таврійського національного університету імені В.І. Вернадського. Серія: Технічні науки. Т. 33 (72), № 6. С. 109–114. 2022. DOI: https://doi.org/10.32782/2663-5941/2022.6/19
Levkivskyi V., Marchuk D., Lobanchykova N., Pilkevych I., Salamatov D. Available parking places recognition system. CEUR Workshop Proceedings 4th Workshop for Young Scientists in Computer Science & Software Engineering. Vol. 3077, Pp. 123–134. 2022. URL: http://ceur-ws.org/Vol-3077/paper07.pdf
Марчук Д.К. Аналіз сучасних алгоритмів виявлення і розпізнавання об’єктів з відеопотоку для систем управління паркуванням в реальному часі. Вісник Хмельницького національного університету. Серія: «Технічні науки». № 3. С. 339-347. 2023. DOI: https://www.doi.org/10.31891/2307-5732-2023-321-3-17-23
Perlin K. Improving noise. ACM Trans. Graph. 21, 3. Pp. 681–682. 2002. DOI: https://doi.org/10.1145/566654.566636.
Ryan J. S., Cowling P., Alfred Walker J. Procedural generation using spatial GANs for region-specific learning of elevation data. IEEE Conference on Games (CoG). IEEE, 2019.
Fournier A., Fussell D., Carpenter L. Computer rendering of stochastic models. Commun. ACM 25, 6. Pp. 371–384. 1982. DOI: https://doi.org/10.1145/358523.358553.
Lautakoski J. Procedurell generering av terräng Perlin noise eller Diamond-Square: med fokus på exekveringstid och framkomlighet. Dissertation. 2016. URL: https://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-12854.
Gavin S P Miller. The definition and rendering of terrain maps. SIGGRAPH Comput. Graph. 20, 4. Pp. 39–48. 1986. DOI: https://doi.org/10.1145/15886.15890.
Adrian C., Liarokapis F. Fractal nature-generating realistic terrains for games. 7th International Conference on Games and Virtual Worlds for Serious Applications (VS-Games). IEEE, 2015.
