Journals / Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi / 2026 / Cilt: 13 Sayı: 3

Enhancing wave function collapse algorithm for procedural map generation problem

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

Osman Büyükşar(ONDOKUZ MAYIS UNIVERSITY)0009-0006-6974-7761
Doğan Yıldız(ONDOKUZ MAYIS UNIVERSITY)0000-0001-9670-4173
Sercan Demirci(ONDOKUZ MAYIS UNIVERSITY)0000-0001-6739-7653
Pages
806–814
Publication Date
2024-07-15
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The evaluation of IMGA was carried out by coding the method into the Unity game engine.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:In this study, the Improved Map Generation Algorithm (IMGA) method is presented to improve traditional methods in procedural map creation.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:The evaluation of IMGA was carried out by coding the method into the Unity game engine.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Prosedürel harita oluşturma · Dalga fonksiyonu yığılma · Gürültü

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.

Özet

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.

🔖

Cite This Article

Büyükşar, O., Yıldız, D., Demirci, S. (2024). Enhancing wave function collapse algorithm for procedural map generation problem. Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 13 Sayı: 3, 806–814. https://doi.org/10.28948/ngumuh.1361413

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (26)

  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
  26. 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