Combining the Cellular Automata and Marching Square to Generate Maps

Viore; Wirawan Istiono

doi:10.29207/resti.v9i2.6241

Viore Universitas Multimedia Nusantara
Wirawan Istiono Universitas Multimedia Nusantara

DOI: https://doi.org/10.29207/resti.v9i2.6241

Keywords: Cellular Automata, Combining Algorithms, Marching Square, Procedural Content Generation, Video Game

Abstract

As computer technology advances, one of the entertainment media that has emerged is video games. The development of a video game is becoming more expensive and labor-intensive as technology itself continues to grow. One of the characteristics of a game as an entertainment medium is its replay value, which refers to the fact that the subject matter can be played more than once. Automating content through the use of procedural content generation is done with the goal of lowering expenses and reducing the amount of labour that is required. This research has two goals: designing and developing a Maze Game using the Procedural Content Generation method with the Cellular Automata and Marching Square algorithms, and determining the level of player satisfaction with the games developed using the Game User Experience Satisfaction Scale (GUESS) method. This research will utilize Cellular Automata and the Marching Square algorithm as a method for generating 3D game shapes through Procedural Content Generation. After the game has been developed, it will be performed by players, and the Game User Experience Satisfaction Scale will be used to measure the user experience. The result for overall satisfaction, based on the responses of 25 respondents, is 83.14%. Cellular Automata was effectively implemented to generate the map, while Marching Square was used to generate the 3D mesh, albeit with isolated rooms and graphical errors.

Downloads

Download data is not yet available.

Author Biography

Viore, Universitas Multimedia Nusantara

Viore is student of Universitas Multimedia Nusantara (UMN). He has finished an independent study program and interned as VR Developer. (email: viore@student.umn.ac.id).

References

R. Adellin, C. T. Khuan, and L. D. Gertrude, “Conceptual Framework Puzzle Game with High Replayability,” J. Phys. Conf. Ser., vol. 1228, no. 1, 2019, doi: 10.1088/1742-6596/1228/1/012070.

J. Sampurna and W. Istiono, “Virtual Reality Game for Introducing Pencak Silat,” Int. J. Interact. Mob. Technol., vol. 15, no. 1, pp. 199–207, 2021, doi: 10.3991/IJIM.V15I01.17679.

A. Khalifa, P. Bontrager, S. Earle, and J. Togelius, “PCGRL: Procedural content generation via reinforcement learning,” Proc. 16th AAAI Conf. Artif. Intell. Interact. Digit. Entertain. AIIDE 2020, pp. 95–101, 2020, doi: 10.1609/aiide.v16i1.7416.

Y. Bai, Y. Wang, Y. Tong, Y. Yang, Q. Liu, and J. Liu, “Boundary Content Graph Neural Network for Temporal Action Proposal Generation,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 12373 LNCS, pp. 121–137, 2020, doi: 10.1007/978-3-030-58604-1_8.

D. A. Ramadhan and A. D. Indriyanti, “Procedural Content Generation pada Game World Exploration Sandbox Menggunakan Alogoritma Perlin Noise,” J. Informatics Comput. Sci., vol. 4, no. 01, pp. 86–91, 2022, doi: 10.26740/jinacs.v4n01.p86-91.

H. Juwiantho, L. Liliana, and M. Budiono, “Procedural Content Generation pada Game Tower Defense menggunakan Perlin Noise dan Algoritma Floyd Warshall,” J. Animat. Games Stud., vol. 9, no. 1, pp. 11–28, 2023, doi: 10.24821/jags.v9i1.8100.

A. Gambi, M. Mueller, and G. Fraser, “Automatically testing self-driving cars with search-based procedural content generation,” ISSTA 2019 - Proc. 28th ACM SIGSOFT Int. Symp. Softw. Test. Anal., no. September, pp. 273–283, 2019, doi: 10.1145/3293882.3330566.

K. Cobbe, C. Hesse, J. Hilton, and J. Schulman, “Leveraging procedural generation to benchmark reinforcement learning,” 37th Int. Conf. Mach. Learn. ICML 2020, vol. PartF16814, pp. 2026–2034, 2020.

N. A. Barriga, “A Short Introduction to Procedural Content Generation Algorithms for Videogames,” Int. J. Artif. Intell. Tools, vol. 28, no. 2, 2019, doi: 10.1142/S0218213019300011.

S. Risi and J. Togelius, “Increasing generality in machine learning through procedural content generation,” Nat. Mach. Intell., vol. 2, no. 8, pp. 428–436, 2020, doi: 10.1038/s42256-020-0208-z.

K. Vayadande, R. Pokarne, M. Phaldesai, T. Bhuruk, T. Patil, and P. Kumar, “Simulation of Conway’S Game of Life Using Cellular Automata,” Int. Res. J. Eng. Technol., no. March, pp. 327–331, 2022, [Online]. Available: www.irjet.net

S. Earle, J. Snider, M. C. Fontaine, and J. Togelius, Illuminating Diverse Neural Cellular Automata for Level Generation, vol. 1, no. 1. Association for Computing Machinery, 2022.

W. Istiono, “Bilingual Color Learning Application as Alternative Color Learning for Preschool Student,” Int. J. Interact. Mob. Technol., vol. 16, no. 5, pp. 224–233, 2022, doi: 10.3991/ijim.v16i05.28319.

B. Lopez, J. Munoz, F. Quevedo, C. A. Monje, S. Garrido, and L. Moreno, “4D Trajectory Planning Based on Fast Marching Square for UAV Teams,” IEEE Trans. Intell. Transp. Syst., vol. 25, no. 6, pp. 5703–5717, 2024, doi: 10.1109/TITS.2023.3336008.

W. A. Rohmah and W. Apriyandari, “Implementation of the Algorithm Fisher Yates Shuffle on Game Quiz Environment,” J. Informatics Telecommun. Eng., vol. 4, no. 1, pp. 161–172, 2020.

J. R. Keebler Assoc, W. J. Shelstad, D. C. S. Google, B. S. Chaparro, and M. H. Phan Google, “Validation of the GUESS-18: A Short Version of the Game User Experience Satisfaction Scale (GUESS),” J. Usability Stud., vol. 16, no. 1, pp. 49–62, 2020.

O. Tekik, E. Surer, and A. Betin Can, “Verifying Maze-Like Game Levels With Model Checker SPIN,” IEEE Access, vol. 10, no. May, pp. 66492–66510, 2022, doi: 10.1109/ACCESS.2022.3185109.

Z. Wu, Y. Mao, and Q. Li, “Procedural Game Map Generation using Multi-leveled Cellular Automata by Machine learning,” ACM Int. Conf. Proceeding Ser., no. October 2021, pp. 168–172, 2021, doi: 10.1145/3500931.3500962.

A. Gharaibeh, A. Shaamala, R. Obeidat, and S. Al-Kofahi, “Improving land-use change modeling by integrating ANN with Cellular Automata-Markov Chain model,” Heliyon, vol. 6, no. 9, p. e05092, 2020, doi: 10.1016/j.heliyon.2020.e05092.

J. Öhman, “Procedural Generation of Tower Defense levels,” pp. 1–10, 2020, [Online]. Available: http://www.ep.liu.se/.

A. Sabanovic and A. Khodabakhshi, “Evolved cellular automata for 2D video game level generation,” 2022.

P. Chen, Y. Huang, E. Papadimitriou, J. Mou, and P. van Gelder, “Global path planning for autonomous ship: A hybrid approach of Fast Marching Square and velocity obstacles methods,” Ocean Eng., vol. 214, no. February, p. 107793, 2020, doi: 10.1016/j.oceaneng.2020.107793.

J. Muñoz, B. López, F. Quevedo, S. Garrido, C. A. Monje, and L. E. Moreno, “Gaussian processes and Fast Marching Square based informative path planning,” Eng. Appl. Artif. Intell., vol. 121, no. July 2022, p. 106054, 2023, doi: 10.1016/j.engappai.2023.106054.