Enhancing wave function collapse algorithm for procedural map generation problem

Abstract

In this study, the Improved Map Generation Algorithm (IMGA) method is presented to improve traditional methods in procedural map creation. Traditional procedural map generation techniques using noise generation exhibit shortcomings in the consistent composition of a real map with its uniformly distributed features. On the other hand, procedural map creation techniques that use wave function collapse require that some map pieces already exist to create a map. The observed disadvantages were eliminated by using a hybrid technique with the designed IMGA method. The developed algorithm is similar to real maps in terms of the distribution of map regions, does not need 3D model parts, and performs map creation operations without increasing the algorithm's time complexity. The evaluation of IMGA was carried out by coding the method into the Unity game engine.

Keywords

• Procedural terrain generation
• Wave function collapse
• Noise
• Algorithm.

Prosedürel harita oluşturma problemi için dalga fonksiyonu yığılma algoritmasının geliştirilmesi

Öz

Bu çalışmada, prosedürel harita oluşturma alanındaki geleneksel metotları geliştirmek amacıyla Geliştirilmiş Harita Oluşturma Algoritması (Improved Map Generation Algorithm, IMGA) metodunu sunulmuştur. Gürültü üretme yöntemini kullanan geleneksel prosedürel harita oluşturma teknikleri, düzgün dağılmış özellikleriyle gerçek bir haritanın tutarlı bileşiminde eksiklikler sergiler. Öte yandan dalga fonksiyon çöküşü kullanan prosedürel harita oluşturma teknikleri ise harita oluşturabilmek için harita parçalarının bir kısmının hâlihazırda bulunmasını gerektirmektedir. Tasarlanan IMGA metoduyla hibrit bir teknik kullanılarak gözlemlenen dezavantajlar giderilmiştir. Tasarlanan algoritma, harita bölgelerinin dağılımı açısından gerçek haritalara benzeyen, 3D model parçalarına ihtiyaç duymayan ve harita oluşturma işlemlerini algoritma zaman karmaşıklığını arttırmadan gerçekleştirmektedir. IMGA’nın değerlendirilmesi ise, metodun Unity oyun motoruna kodlanması ile gerçekleştirilmiştir.

Anahtar Kelimeler

• Prosedürel harita oluşturma
• Dalga fonksiyonu yığılma
• Gürültü
• Algoritma

Kaynakça

1. R. M. Smelik, K. J. De Kraker, T. Tutenel, R. Bidarra, and S. A. Groenewegen, A survey of procedural methods for terrain modelling. In Proceedings of the CASA Workshop on 3D Advanced Media In Gaming And Simulation (3AMIGAS), pp. 25-34, Amsterdam, The Netherlands, 2009.
2. M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup, Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 9 (1), 1-22, 2013. https://doi.org/10.1145/2422956.2422957.
3. K. Perlin, Improving noise. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pp. 681-682, San Antonio Texas, USA, 2002.
4. C. Adams, H. Parekh, and S. J. Louis, Procedural level design using an interactive cellular automata genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 85-86, Berlin, Germany, 2017.
5. R. Zmugg, W. Thaller, U. Krispel, J. Edelsbrunner, S. Havemann, and D. W. Fellner, Procedural architecture using deformation-aware split grammars. The Visual Computer, 30, 1009-1019, 2014. https://doi.org/10.1007/s00371-013-0912-3
6. De Pontes, R. G., Gomes, H. M., and Seabra, I. S. R., Particle swarm optimization for procedural content generation in an endless platform game. Entertainment Computing, 43, 100496., 2022. https://doi.org/10.1016/j.entcom.2022.100496
7. Volz, V., Naujoks, B., Kerschke, P., and Tušar, T., Tools for landscape analysis of optimisation problems in procedural content generation for games. Applied Soft Computing, 136, 110121., 2023. https://doi.org/10.1016/j.asoc.2023.110121
8. C. Beckham, and C. Pal, A step towards procedural terrain generation with gans. arXiv preprint, arXiv:1707.03383, 2017. https://doi.org/10.48550/arXiv.1707.03383

9. T. J. Rose, and A. G. Bakaoukas, Algorithms and approaches for procedural terrain generation-a brief review of current techniques. In 2016 8th International Conference on Games and Virtual Worlds for Serious Applications (VS-GAMES). pp. 1-2, Barcelona, Spain, 2016.
10. F. Gürler and E. Onbaşioğlu, Applying Perlin noise on 3D hexagonal tiled maps. In 2022 International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), pp. 670-673, Ankara, Turkey, 2022.
11. R. Fischer, P. Dittmann, R. Weller and G. Zachmann, AutoBiomes: procedural generation of multi-biome landscapes. The Visual Computer, 36, 2263-2272, 2020. https://doi.org/10.1007/s00371-020-01920-7
12. A. Petrovas and R. Bausys, Procedural video game scene generation by genetic and neutrosophic WASPAS algorithms.. Applied Sciences, 12(2), 772, 2022. https://doi.org/10.3390/app12020772
13. E. Panagiotou and E. Charou, Procedural 3D terrain generation using Generative Adversarial Networks. arXiv preprint arXiv:2010.06411, 2020. https://doi.org/10.48550/arXiv.2010.06411
14. A. Wulff-Jensen, N. N. Rant, T. N. Møller and J. A. Billeskov, Deep convolutional generative adversarial network for procedural 3D landscape generation based on DEM. In Interactivity, Game Creation, Design, Learning, and Innovation: 6th International Conference, ArtsIT 2017, and Second International Conference, pp. 85-94, Heraklion, Crete, Greece, 2017.
15. J. Olsen, Realtime procedural terrain generation. 2004.
16. G. C. Backes, T. A. Engel, and C. T. Pozzer, Real-Time Massive Terrain Generation using Procedural Erosion on the GPU. In Proceedings of 17th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), pp. 675-678, Foz do Iguaçu, Brazil, 2018.
17. H. Zhang, D. Qu, Y. Hou, F. Gao and F. Huang, Synthetic modeling method for large scale terrain based on hydrology. IEEE Access, 4, 6238-6249, 2016. 10.1109/ACCESS.2016.2612700
18. J. D. Génevaux, É. Galin, E. Guérin, A. Peytavie and B. Benes, Terrain generation using procedural models based on hydrology. ACM Transactions on Graphics (TOG), 32(4), 1-13, 2013. https://doi.org/10.1145/2461912.2461996
19. J. Doran and I. Parberry, Controlled procedural terrain generation using software agents. IEEE Transactions on Computational Intelligence and AI in Games, 2(2), 111-119, 2010. 10.1109/TCIAIG.2010.2049020
20. T. S. L. Langendam and R. Bidarra, miWFC-Designer empowerment through mixed-initiative Wave Function Collapse. In Proceedings of the 17th International Conference on the Foundations of Digital Games, pp. 1-8, Athens, Greece, 2022.
21. Q. E. Morris, Modifying Wave function collapse for more complex use in game generation and design. Computer Science Honors Theses. USA, 2021.
22. S. Alaka and R. Bidarra, Hierarchical Semantic Wave function collapse. In Proceedings of the 18th International Conference on the Foundations of Digital Games, pp. 1-10, Lisbon, Portugal, 2023.
23. Wu, Z., Mao, Y., and Li, Q., Procedural game map generation using multi-leveled cellular automata by machine learning. In Proceedings of the 2nd International Symposium on Artificial Intelligence for Medicine Sciences,pp. 168-172. https://doi.org/ 10.1145/3500931.3500962
24. K. PERLIN, An image synthesizer. ACM Siggraph Computer Graphics, 1985, 19 (3), 287-296. https://doi.org/10.1145/325165.325247
25. Gumin, M. 2016. Wave Function Collapse Algorithm (Version 1.0) [Computer software]. https://github.com/mxgmn/WaveFunctionCollapse, Accessed: 15 September 2023