A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation

Author

Muhammad Hafis, Herman Tolle, Ahmad Afif Supianto

Abstract

Procedural Content Generation (PCG) is an emerging field of study in computer science that focuses on automating the process of generating content by using algorithm, making the content generation process with less human effort. However, a more specific empirical evidence on how it is being used in a game-related implementation are still lacking. This paper presents the findings of review performed in the past 5 years looking on how PCG are being applied in game-related content, whether it is from the basic paper characteristic to analyze the trends, the field of PCG itself, and the game domain of game model and game genre. The studies had shown that PCG are being used extensively in game-related content but has seen more uses on specific type of contents rather than being used ubiquitously in all sorts of contents. The result shown that there are not specific best type of PCG method or algorithm being used instead an array of approach can be used based on what content being created. Result also shown that PCG are being used in multiple type of games, but similarly, based on the paper found, only certain types of game benefits PCG extensively such as action and platforming games while other model and genre of games have not seen much PCG application yet. Further studies are also required to analyze how experimentation and evaluation of PCG are being done as well as PCG domain in educational games as well as game-based learning, the quality catachrestic being analyzed on the papers are also worth mentioning to understand the underlying result of PCG usage in game-related contents.

Full Text:

PDF

References


T. M. Connolly, E. A. Boyle, E. MacArthur, T. Hainey, and J. M. Boyle, “A systematic literature review of empirical evidence on computer games and serious games,” Comput. Educ., vol. 59, no. 2, pp. 661–686, 2012.

D. B. Clark, E. E. Tanner-Smith, and S. S. Killingsworth, “Digital Games, Design, and Learning: A Systematic Review and Meta-Analysis,” Rev. Educ. Res., vol. 86, no. 1, pp. 79–122, 2016.

A. Calderón and M. Ruiz, “A systematic literature review on serious games evaluation: An application to software project management,” Comput. Educ., vol. 87, no. 1, pp. 396–422, 2015.

M. Papastergiou, “Exploring the potential of computer and video games for health and physical education: A literature review,” Comput. Educ., vol. 53, no. 3, pp. 603–622, 2009.

M. Graafland, J. M. C. Schraagen, and M. P. Schijven, Serious Games in Surgical Education. 2012.

A. DeSmet, R. Shegog, D. Van Ryckeghem, G. Crombez, and I. De Bourdeaudhuij, “A Systematic Review and Meta-analysis of Interventions for Sexual Health Promotion Involving Serious Digital Games,” Games Health J., vol. 4, no. 2, pp. 78–90, 2015.

M. Waldrop, “More then Moore,” Nature, vol. 530, no. 7589, pp. 144–148, 2016.

K. Feenan, “Social Resiliency in Digital Games,” Int. Conf. Immersive Learn., pp. 189–197, 2018.

S. Greuter and A. Nash, “Game asset repetition,” in Proceedings of the 2014 Conference on Interactive Entertainment, 2014, pp. 1–5.

D. Karavolos, A. Liapis, and G. Yannakakis, “Learning the patterns of balance in a multi-player shooter game,” in Proceedings of the International Conference on the Foundations of Digital Games - FDG ’17, 2017, p. 70.

G. N. Yannakakis and J. Togelius, “Experience-Driven Procedural Content Generation,” in 2015 International Conference on Affective Computing and Intelligent Interaction (ACII), 2015, pp. 519–525.

J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, “Search-based procedural content generation: A taxonomy and survey,” IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 172–186, 2011.

N. Shaker, J. Togelius, and M. J. Nelson, Procedural Content Generation in Games. Switzerland: Springer, 2016.

P. Shi and K. Chen, “Online Level Generation in Super Mario Bros via Learning Constructive Primitives,” in 2016 IEEE Conference on Computational Intelligence and Games (CIG), 2016, pp. 1–8.

R. Lara-Cabrera, C. Cotta, and A. J. Fernández-Leiva, “Geometrical vs topological measures for the evolution of aesthetic maps in a RTS game,” Entertain. Comput., vol. 5, no. 4, pp. 251–258, 2014.

A. S. Ruela and F. G. Guimarães, “Procedural generation of non-player characters in massively multiplayer online strategy games,” Soft Comput., vol. 21, no. 23, pp. 7005–7020, 2017.

Y. Dong and T. Barnes, “Evaluation of a template-based puzzle generator for an educational programming game,” in Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference, 2017, pp. 1–4.

S. Snodgrass and S. Ontañón, “Learning to Generate Video Game Maps Using Markov Models,” IEEE Trans. Comput. Intell. AI Games, vol. 9, no. 4, pp. 410–422, 2017.

M. Hendrikx, S. Meijer, J. van Der Velden, and A. Iosup, “Procedural Content Generation for Games: A Survey,” ACM Trans. Multimed. Comput. Commun. Appl., vol. 9, no. 1, p. 1, 2013.

D. M. De Carli, F. Bevilacqua, C. T. Pozzer, and M. C. D’Ornellas, “A survey of procedural content generation techniques suitable to game development,” in 2011 Brazilian Symposium on Games and Digital Entertainment, 2011, pp. 26–35.

A. Summerville et al., “Procedural Content Generation via Machine Learning (PCGML),” IEEE Trans. Games, vol. 10, no. 3, pp. 257–270, 2018.

N. Shaker, G. N. Yannakakis, and J. Togelius, “Towards Automatic Personalized Content Generation for Platform Games,” in Sixth Artificial Intelligence and Interactive Digital Entertainment Conference, 2010, pp. 63–68.

J. Togelius, M. Preuss, and G. N. Yannakakis, “Towards multiobjective procedural map generation,” in Proceedings of the 2010 workshop on procedural content generation in games, 2010, p. 3.

S. Risi, J. Lehman, D. B. D’ambrosio, R. Hall, and K. O. Stanley, “Combining search-based procedural content generation and social gaming in the Petalz video Game,” in Eighth Artificial Intelligence and Interactive Digital Entertainment Conference, 2012.

N. Shaker, G. Yannakakis, and J. Togelius, “Evolving Personalized Content for Super Mario Bros Using Grammatical Evolution.,” Proc. 8th AAAI Conf. Artif. Intell. Interact. Digit. Entertain. - AIIDE ’12, no. 1, pp. 75–80, 2012.

J. Togelius, E. Kastbjerg, D. Schedl, and G. N. Yannakakis, “What is procedural content generation?: Mario on the borderline,” in Proceedings of the 2nd international workshop on procedural content generation in games, 2011, p. 3.

S. Das, A. Zook, and M. O. Riedl, “Examining Game World Topology Personalization,” in Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015, pp. 3731–3734.

P. Mawhorter, “Efficiency, realism, and representation in generated content,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 72.

C. Chakraborttii, L. N. Ferreira, and J. Whitehead, “Towards Generative Emotions in Games based on Cognitive Modeling,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 79.

I. H. Hsiao and C. Lopez, “Lessons learned from students’ cheat sheets: Generic models for designing programming study guides,” in 2016 IEEE 16th International Conference on Advanced Learning Technologies (ICALT), 2016, pp. 209–211.

K. Compton, “Little procedural people,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 75.

J. A. Brown, “Towards better personas in gaming : Contract based expert systems,” in 2015 IEEE Conference on Computational Intelligence and Games, 2015, pp. 540–541.

R. Craveirinha and L. Roque, “Designing Games with Procedural Content Generation,” in Proceedings of the 33rd Annual ACM Conference Extended Abstracts on Human Factors in Computing Systems, 2015, pp. 1199–1204.

M. Bennett, “Semantic content generation framework for game worlds,” in 6th International Conference on Games and Virtual Worlds for Serious Applications, VS-GAMES 2014, 2014, pp. 1–8.

N. Shaker, “Intrinsically motivated reinforcement learning: A promising framework for procedural content generation,” in IEEE Conference on Computatonal Intelligence and Games, CIG, 2016, pp. 1–8.

G. Berseth, M. B. Haworth, M. Kapadia, and P. Faloutsos, “Characterizing and optimizing game level difficulty,” in Proceedings of the Seventh International Conference on Motion in Games, 2014, pp. 153–160.

J. Kruse, R. Sosa, and A. M. Connor, “Procedural urban environments for FPS games,” in Proceedings of the Australasian computer science week multiconference, 2016, p. 77.

P. T. Ølsted, B. Ma, and S. Risi, “Interactive evolution of levels for a competitive multiplayer FPS,” in 2015 IEEE Congress on Evolutionary Computation (CEC), 2015, pp. 1527–1534.

M. C. Green, G. A. B. Barros, A. Liapis, and J. Togelius, “DATA agent,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 19.

A. Khalifa, D. Perez-Liebana, S. M. Lucas, and J. Togelius, “General video game level generation,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2016, p. 51.

E. Butler, K. Siu, and A. Zook, “Program synthesis as a generative method,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 6.

X. Neufeld, S. Mostaghim, and D. Perez-Liebana, “Procedural level generation with answer set programming for general Video Game playing,” in 2015 7th Computer Science and Electronic Engineering Conference, CEEC 2015 - Conference Proceedings, 2015, pp. 207–212.

A. Alvarez, S. Dahlskog, J. Holmberg, and S. Johansson, “Assessing Aesthetic Criteria in the Evolutionary Dungeon Designer,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 44.

J. R. Baron, “Procedural Dungeon Generation Analysis and Adaptation,” in Proceedings of the SouthEast Conference, 2017, pp. 168–171.

R. van Rozen and Q. Heijn, “Measuring quality of grammars for procedural level generation,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 56.

A. Liapis, G. N. Yannakakis, and J. Togelius, “Constrained Novelty Search: A Study on Game Content Generation,” Evol. Comput., vol. 23, no. 1, pp. 101–129, 2013.

D. Wheat, M. Masek, C. P. Lam, and P. Hingston, “Modeling perceived difficulty in game levels,” in Proceedings of the Australasian Computer Science Week Multiconference, 2016, p. 74.

R. J. V. De Medeiros and T. F. V. De Medeiros, “Procedural Level Balancing in Runner Games,” in 2014 Brazilian Symposium on Computer Games and Digital Entertainment, 2014, pp. 109–114.

A. Nagle, P. Wolf, and R. Riener, “Towards a system of customized video game mechanics based on player personality: Relating the Big Five personality traits with difficulty adaptation in a first-person shooter game,” Entertain. Comput., vol. 13, no. 1, pp. 10–24, 2016.

T. Georgiou and Y. Demiris, “Personalised track design in car racing games,” in IEEE Conference on Computatonal Intelligence and Games, CIG, 2016, pp. 1–8.

L. H. S. Lelis, W. M. P. Reis, and Y. K. Gal, “Procedural Generation of Game Maps with Human-in-the-Loop Algorithms,” IEEE Trans. Games, vol. 10, no. 3, pp. 271–280, 2018.

L. N. Ferreira and C. Toledo, “Tanager: A Generator of Feasible and Engaging Levels for Angry Birds,” IEEE Trans. Comput. Intell. AI Games, vol. 10, no. 3, pp. 304–316, 2018.

V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. Smith, and S. Risi, “Evolving Mario Levels in the Latent Space of a Deep Convolutional Generative Adversarial Network,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2018, pp. 221–228.

P. Shi and K. Chen, “Learning Constructive Primitives for Real-time Dynamic Difficulty Adjustment in Super Mario Bros,” IEEE Trans. Games, vol. 10, no. 2, pp. 155–169, 2018.

W. Xia and B. Anand, “Game balancing with ecosystem mechanism,” in 2016 International Conference on Data Mining and Advanced Computing (SAPIENCE), 2016, pp. 317–324.

A. Zook and M. O. Riedl, “Temporal Game Challenge Tailoring,” IEEE Trans. Comput. Intell. AI Games, vol. 7, no. 4, pp. 336–346, 2015.

P. H. Kim and R. Crawfis, “The Quest For The Perfect Maze,” in Computer Games: AI, Animation, Mobile, Multimedia, Educational and Serious Games (CGAMES), 2015, pp. 65–72.

C. Adams and S. Louis, “Procedural Maze Level Generation with Evolutionary Cellular Automata,” in IEEE Symposium Series on Computational Intelligence (SSCI), 2017, pp. 1–8.

A. Santamaria-Ibirika, X. Cantero, S. Huerta, I. Santos, and P. G. Bringas, “Procedural playable cave systems based on voronoi diagram and delaunay triangulation,” in International Conference on Cyberworlds, 2014, pp. 15–22.

L. Cardamone, P. L. Lanzi, and D. Loiacono, “TrackGen: An interactive track generator for TORCS and Speed-Dreams,” Appl. Soft Comput. J., vol. 28, no. 1, pp. 550–558, 2015.

E. Teng and R. Bidarra, “A semantic approach to patch-based procedural generation of urban road networks,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 71.

N. Hilliard, J. Salis, and H. Elaarag, “Algorithms for Procedural Dungeon Generation *,” J. Comput. Sci. Coll., vol. 33, no. 1, pp. 166–174, 2017.

J. Hell, M. Clay, and H. Elaarag, “Hierarchical Dungeon Procedural Generation and Optimal Path Finding Based on User Input,” J. Comput. Sci. Coll., vol. 33, no. 1, pp. 175–183, 2017.

W. Forsyth, “Globalized Random Procedural Content for Dungeon Generation,” J. Comput. Sci. Coll., vol. 32, no. 2, pp. 192–201, 2016.

C. Holmgård, A. Liapis, J. Togelius, and G. N. Yannakakis, “Evolving models of player decision making: Personas versus clones,” Entertain. Comput., vol. 16, no. 1, pp. 95–104, 2016.

M. Cook, S. Colton, and J. Gow, “The ANGELINA videogame design system-part i,” IEEE Trans. Comput. Intell. AI Games, vol. 9, no. 2, pp. 192–203, 2017.

M. Cook, S. Colton, and J. Gow, “The ANGELINA videogame design system-part ii,” IEEE Trans. Comput. Intell. AI Games, vol. 9, no. 3, pp. 254–266, 2017.

A. S. Ruela and F. G. Guimarães, “Coevolutionary Procedural Generation of Battle Formations in Massively Multiplayer Online Strategy Games,” in 2014 Brazilian Symposium on Computer Games and Digital Entertainment2, 14AD, pp. 89–98.

Q. Yu and R. Crawfis, “Gameplay-driven terrain generation in Scorched Earth,” in 2015 Computer Games: AI, Animation, Mobile, Multimedia, Educational and Serious Games (CGAMES), 2015, pp. 126–130.

R. Craveirinha and L. Roque, “Exploring the Design-Space: The Authorial Game Evolution Tool Case-Study,” in Proceedings of the 13th International Conference on Advances in Computer Entertainment Technology, 2016, p. 21.

A. Sullivan, M. P. Eladhari, and M. Cook, “Tarot-Based Narrative Generation,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, pp. 54–61.

R. Alexander and C. Martens, “Deriving Quests from Open World Mechanics Ryan,” 2017, p. 12.

M. Scirea, Y.-G. Cheong, M. J. Nelson, and B.-C. Bae, “Evaluating Musical Foreshadowing of Videogame Narrative Experiences,” in Proceedings of the 9th Audio Mostly: A Conference on Interaction With Sound, 2014, p. 8.

M. C. Green, A. Khalifa, G. A. B. Barros, T. Machado, A. Nealen, and J. Togelius, “AtDelfi: Automatically Designing Legible, Full Instructions For Games,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 17.

T. Smith, J. Padget, and A. Vidler, “Graph-based generation of action-adventure dungeon levels using answer set programming,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 52.

E. S. de Lima, B. Feijó, and A. L. Furtado, “Player behavior and personality modeling for interactive storytelling in games,” Entertain. Comput., vol. 28, no. 1, pp. 32–48, 2018.

O. Correa, C. Cuervo, P. C. Perez, and A. Arias, “A new approach for self adaptive video game for rehabilitation. Experiences in the Amblyopia treatment,” in 2014 IEEE 3nd International Conference on Serious Games and Applications for Health, 2014, pp. 1–5.

P. A. Nogueira, V. Torres, R. Rodrigues, E. Oliveira, and L. E. Nacke, “Vanishing scares: biofeedback modulation of affective player experiences in a procedural horror game,” J. Multimodal User Interfaces, vol. 10, no. 1, pp. 31–62, 2016.

F. Bicho and C. Martinho, “Multi-dimensional Player Skill Progression Modelling for Procedural Content Generation,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 1.

D. Hooshyar, M. Yousefi, and H. Lim, “A Procedural Content Generation-Based Framework for Educational Games: Toward a Tailored Data-Driven Game for Developing Early English Reading Skills,” J. Educ. Comput. Res., vol. 56, no. 2, pp. 293–310, 2018.

A. Zook and M. Riedl, “Learning How Design Choices Impact Gameplay Behavior,” IEEE Trans. Games, p. 1, 2018.

N. Hocine, A. Gouaïch, S. A. Cerri, D. Mottet, J. Froger, and I. Laffont, “Adaptation in serious games for upper-limb rehabilitation: an approach to improve training outcomes,” User Model. User-adapt. Interact., vol. 25, no. 1, pp. 65–98, 2015.

F. De Mesentier Silva, S. Lee, J. Togelius, and A. Nealen, “Evolving Maps and Decks for Ticket to Ride,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 48.

A. Bhojan and H. W. Wong, “TITAL - Asynchronous multiplayer shooter with procedurally generated maps,” Entertain. Comput., vol. 16, no. 1, pp. 81–93, 2016.

R. Lopes, E. Eisemann, and R. Bidarra, “Authoring adaptive game world generation,” IEEE Trans. Games, vol. 10, no. 1, pp. 42–55, 2018.

S. Snodgrass and S. Ontañón, “Procedural level generation using multi-layer level representations with MdMCs,” in 2017 IEEE Conference on Computational Intelligence and Games, CIG 2017, 2017, pp. 280–287.

D. Maggiorini, M. Mannalà, M. Ornaghi, and L. A. Ripamonti, “FUN PLEdGE: a FUNny Platformers LEvels GEnerator,” in Proceedings of the 11th Biannual Conference on Italian SIGCHI Chapter, 2015, pp. 138–145.

T. Day et al., “Torchless: Asymmetry in a Shared Screen Dungeon Crawler,” in Proceedings of the 2016 Annual Symposium on Computer-Human Interaction in Play Companion Extended Abstracts, 2016, pp. 47–53.

H. A. Rosyid, M. Palmerlee, and K. Chen, “Deploying learning materials to game content for serious education game development: A case study,” Entertain. Comput., vol. 26, no. 1, pp. 1–9, 2018.

T. Thompson and M. Syrett, “‘Play your own way’: adapting a procedural framework for accessibility,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 53.

S. Dahlskog, J. Togelius, and M. J. Nelson, “Linear levels through n-grams,” in Proceedings of the 18th International Academic MindTrek Conference: Media Business, Management, Content & Services, 2014, pp. 200–206.

D. Karavolos, A. Liapis, and G. N. Yannakakis, “Pairing Character Classes in a Deathmatch Shooter Game via a Deep-Learning Surrogate Model,” in Proceedings of the 13th International Conference on the Foundations of Digital Games, 2018, p. 51.

J. Roberts and K. Chen, “Learning-based procedural content generation,” in IEEE Transactions on Computational Intelligence and AI in Games, 2015, vol. 7, no. 1, pp. 88–101.

J. Valls-Vargas, J. Zhu, and S. Ontañón, “Graph grammar-based controllable generation of puzzles for a learning game about parallel programming,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 7.

J. Grinblat and C. B. Bucklew, “Subverting historical cause & effect Generation of Mythic Biographies in Caves of Qud,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 76.

M. R. F. Mendonça and A. Ziviani, “Network-Based Procedural Story Generation,” Comput. Entertain., vol. 16, no. 3, 2018.

B. Kybartas and C. Verbrugge, “Analysis of ReGEN as a Graph Rewriting System for Quest Generation,” IEEE Trans. Comput. Intell. AI Games, vol. 6, no. 2, pp. 228–242, 2014.

E. Butler, E. Andersen, A. M. Smith, S. Gulwani, and Z. Popović, “Automatic Game Progression Design through Analysis of Solution Features,” in Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015, pp. 2407–2416.

D. Lessin and S. Risi, “Darwin’s Avatars: a Novel Combination of Gameplay and Procedural Content Generation,” in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 2015, pp. 329–336.

J. Lessard, E. Brunelle-Leclerc, T. Gottschalk, M.-A. Jetté-Léger, O. Prouveur, and C. Tan, “Striving for author-friendly procedural dialogue generation,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017, p. 67.




DOI: http://dx.doi.org/10.25126/jitecs.201943134