Procedural Map Generation for 'Splatted': Enhancing Player Experience through Genetic Algorithms and AI Finite State Machines in a Snowball Throwing Game
DOI:
https://doi.org/10.52985/insyst.v6i1.353Keywords:
Game, Genetic Algorithm, Map, Procedural Map GenerationAbstract
Games, a now extremely prevalent form of global entertainment, have emerged as a leading industry in the entertainment media, surpassing other entertainment media such as books, films, and music. However, game development is a complex endeavor, requiring a diverse set of talents to create a decent game for people to enjoy. Some of the talents needed to create a good game is a game designer, which dictates how a player can interact with the world, a writer, which pours a meaningful story inside said world, and a composer, which uses music to elevate the emotions evoked by the game and its events. With that being said, this research aims to streamline the creation process of the game designers, specifically the level designers by focusing on procedural map generation and artificial intelligence to create a map that is in a playable state for the players to play in. Procedural map generation, facilitated by a genetic algorithm inspired by Darwin's evolutionary theory, expedites the level design process. The research explores two types of map generation—tile-based and template-based, each with distinct advantages and disadvantages. Through user acceptance tests and expert-level analysis, it is evident that the genetic algorithm performs effectively, achieving a noteworthy level of player satisfaction.
References
J. Schell, The Art of Game Design: A Book of Lenses, Third Edition. CRC Press, 2019.
E. Adams, Fundamentals of Game Design. Pearson Education, 2010.
M. Moore, Basics of Game Design. CRC Press, 2016.
N. A. Barriga, A Short Introduction to Procedural Content Generation Algorithms for Videogames. 2018.
V. Kraner, I. Fister jr, and L. Brezočnik, “Procedural Content Generation of Custom Tower Defense Game Using Genetic Algorithms,” 2021, pp. 493–503.
S. Putra and W. Istiono, “Implementation Simple Additive Weighting in Procedural Content Generation Strategy Game,” vol, vol. 4, pp. 9–18, 2022.
E. Frank and N. Olsson, “Procedural city generation using Perlin noise.” 2017.
N. Sainio, “TERRAIN GENERATION ALGORITHMS,” 2023.
A. Lambora, K. Gupta, and K. Chopra, “Genetic Algorithm- A Literature Review,” in 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), 2019, pp. 380–384, doi: 10.1109/COMITCon.2019.8862255.
L. Haldurai, T. Madhubala, and R. Rajalakshmi, “A study on genetic algorithm and its applications,” Int. J. Comput. Sci. Eng, vol. 4, no. 10, pp. 139–143, 2016.
S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed. Tools Appl., vol. 80, no. 5, pp. 8091–8126, 2021, doi: 10.1007/s11042-020-10139-6.
H. Armanto, H. A. Rosyid, M. Muladi, and G. Gunawan, “Evolutionary Algorithm in Game – A Systematic Review,” Kinet. Game Technol. Inf. Syst. Comput. Network, Comput. Electron. Control, May 2023, doi: 10.22219/kinetik.v8i2.1714.
W. Alfonsus, A. Hendrawan, and T. J. Gunawan, “Focused Web Crawler Using Genetic Algorithms and Symbiotic Organism Search,” 革新的コンピューティング・情報・制御に関する速報, vol. 15, no. 12, p. 1345, 2021.
H. Armanto, K. Setiabudi, and C. Pickerling, “Komparasi Algoritma WOA, MFO dan Genetic pada Optimasi Evolutionary Neural Network dalam Menyelesaikan Permainan 2048,” J. Inov. Teknol. dan Edukasi Tek., vol. 1, no. 9, pp. 676–684, 2021.
H. Armanto, R. D. Putra, and C. Pickerling, “MVPA and GA Comparison for State Space Optimization at Classic Tetris Game Agent Problem,” Inf. J. Ilm. Bid. Teknol. Inf. dan Komun., vol. 7, no. 1, pp. 73–80, 2022.
S. Prayudani, A. Hizriadi, E. B. Nababan, and S. Suwilo, “Analysis effect of tournament selection on genetic algorithm performance in traveling salesman problem (TSP),” in Journal of Physics: Conference Series, 2020, vol. 1566, no. 1, p. 12131.
S. L. Yadav and A. Sohal, “Comparative study of different selection techniques in genetic algorithm,” Int. J. Eng. Sci. Math., vol. 6, no. 3, pp. 174–180, 2017.
J. Y. Setiawan, D. E. Herwindiati, and T. Sutrisno, “Algoritma Genetika Dengan Roulette Wheel Selection dan Arithmetic Crossover Untuk Pengelompokan,” J. Ilmu Komput. dan Sist. Inf., vol. 7, no. 1, pp. 58–64, 2019.
J. L. Pachuau, A. Roy, and A. Kumar Saha, “An overview of crossover techniques in genetic algorithm,” Model. Simul. Optim. Proc. CoMSO 2020, pp. 581–598, 2021.
P. Kora and P. Yadlapalli, “Crossover operators in genetic algorithms: A review,” Int. J. Comput. Appl., vol. 162, no. 10, 2017.
A. Malik, “A study of genetic algorithm and crossover techniques,” Int. J. Comput. Sci. Mob. Comput., vol. 8, no. 3, pp. 335–344, 2019.
L. Manzoni, L. Mariot, and E. Tuba, “Balanced crossover operators in genetic algorithms,” Swarm Evol. Comput., vol. 54, p. 100646, 2020.
B. H. Abed-alguni, “Island-based cuckoo search with highly disruptive polynomial mutation,” Int. J. Artif. Intell., vol. 17, no. 1, pp. 57–82, 2019.
A. Hassanat, K. Almohammadi, E. Alkafaween, E. Abunawas, A. Hammouri, and V. B. S. Prasath, “Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach,” Information, vol. 10, no. 12, p. 390, 2019.
G. Guariso and M. Sangiorgio, “Improving the performance of multiobjective genetic algorithms: An elitism-based approach,” Information, vol. 11, no. 12, p. 587, 2020.
H. Du, Z. Wang, W. E. I. Zhan, and J. Guo, “Elitism and distance strategy for selection of evolutionary algorithms,” IEEE Access, vol. 6, pp. 44531–44541, 2018.
Downloads
Additional Files
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 INSYST: Journal of Intelligent System and Computation
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
