research-article
Authors: Alexander Gellel and Penny Sweetser
FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games
September 2020
Article No.: 3, Pages 1 - 10
Published: 17 September 2020 Publication History
- 6citation
- 1,188
- Downloads
Metrics
Total Citations6Total Downloads1,188Last 12 Months328
Last 6 weeks40
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
Algorithmic generation of data, known as procedural content generation, is an attractive prospect within the game development industry as a means of creating infinitely fresh and varied content. In this paper, we present an approach to level generation for roguelike dungeon style levels, based on our examination of the suite of existing approaches used in formal research. Our generator aims to create simple dungeon style level layouts that are always playable. We utilise a hybrid technique combining context free grammars to generate a description of levels and a cellular automata inspired process to generate the physical space. The generator proves successful at consistently generating dungeon layouts that maintain completability at all times with sufficient variation, when accounting for the occasional need for corrective actions. We conclude that there is substantial value in hybrid approaches to automated level design and propose a new heuristic by which to assess dungeon style level content.
References
[1]
A. Alvarez, S. Dahlskog, J. Font, and J. Togelius. 2019. Empowering Quality Diversity in Dungeon Design with Interactive Constrained MAP-Elites. In 2019 IEEE Conference on Games (CoG). 1–8.
[2]
Flora Amato and Francesco Moscato. 2017. Formal Procedural Content Generation in Games Driven by Social Analyses. In 2017 31st International Conference on Advanced Information Networking and Applications Workshops (WAINA). 674–679. https://doi.org/10.1109/WAINA.2017.3
[3]
Daniel Ashlock, Colin Lee, and Cameron McGuinness. 2011. Search-Based Procedural Generation of Maze-Like Levels. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (Sep. 2011), 260–273. https://doi.org/10.1109/TCIAIG.2011.2138707
[4]
Eli Bendersky. 2010. Generating random sentences from a context free grammar. Retrieved January 21, 2020 from https://eli.thegreenplace.net/2010/01/28/generating-random-sentences-from-a-context-free-grammar/
[5]
Vojtech Cerny and Filip Dechterenko. 2015. Rogue-Like Games as a Playground for Artificial Intelligence – Evolutionary Approach. In Entertainment Computing - ICEC 2015, Konstantinos Chorianopoulos, Monica Divitini, Jannicke BaalsrudHauge, Letizia Jaccheri, and Rainer Malaka(Eds.). Springer International Publishing, Cham, 261–271.
Digital Library
[6]
Jonathon Doran and Ian Parberry. 2011. A Prototype Quest Generator Based on a Structural Analysis of Quests from Four MMORPGs. In Proceedings of the 2nd International Workshop on Procedural Content Generation in Games (Bordeaux, France) (PCGames ’11). Association for Computing Machinery, New York, NY, USA, Article 1, 8pages. https://doi.org/10.1145/2000919.2000920
Digital Library
[7]
Joris Dormans. 2010. Adventures in Level Design: Generating Missions and Spaces for Action Adventure Games. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games (Monterey, California) (PCGames ’10). Association for Computing Machinery, New York, NY, USA, Article 1, 8pages. https://doi.org/10.1145/1814256.1814257
Digital Library
[8]
Joris Dormans. 2011. Level Design as Model Transformation: A Strategy for Automated Content Generation. In Proceedings of the 2nd International Workshop on Procedural Content Generation in Games(Bordeaux, France) (PCGames ’11). Association for Computing Machinery, New York, NY, USA, Article 2, 8pages. https://doi.org/10.1145/2000919.2000921
Digital Library
[9]
Joris Dormans and Sander Bakkes. 2011. Generating Missions and Spaces for Adaptable Play Experiences. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (Sep. 2011), 216–228. https://doi.org/10.1109/TCIAIG.2011.2149523
[10]
Miguel Frade, FFernandez de Vega, and Carlos Cotta. 2010. Evolution of artificial terrains for video games based on obstacles edge length. In IEEE Congress on Evolutionary Computation. 1–8. https://doi.org/10.1109/CEC.2010.5586032
[11]
Epic Games. 2017. Fortnite Battle Royale. Game [Windows]. Epic Games.
[12]
Gaslamp Games. 1991. Dungeons of Dredmor. Windows, Mac, Linux. Gaslamp Games.
[13]
D. Gravina, A. Khalifa, A. Liapis, J. Togelius, and G.N. Yannakakis. 2019. Procedural Content Generation through Quality Diversity. In 2019 IEEE Conference on Games (CoG). 1–8.
Digital Library
[14]
id Software. 1996. Quake. Game [MS-DOS]. GT Interactive.
[15]
Lawrence Johnson, GeorgiosN. Yannakakis, and Julian Togelius. 2010. Cellular Automata for Real-Time Generation of Infinite Cave Levels. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games (Monterey, California) (PCGames ’10). Association for Computing Machinery, New York, NY, USA, Article 10, 4pages. https://doi.org/10.1145/1814256.1814266
Digital Library
[16]
Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. 2020. PCGRL: Procedural Content Generation via Reinforcement Learning. arxiv:cs.LG/2001.09212
[17]
Edmund McMillen. 2011. The Binding of Isaac. Game [Windows].
[18]
Mojang. 2011. Minecraft. Game [Windows]. Mojang.
[19]
Nintendo. 1985. Super Mario Bros.Game [NES]. Nintendo.
[20]
Nintendo. 1986. Kid Icarus. Game [Famicon]. Nintendo.
[21]
Nintendo. 1986. The Legend of Zelda. Game [Famicom]. Nintendo.
[22]
Nintendo. 1991. The Legend of Zelda: A Link to the Past. Game [SNES]. Nintendo.
[23]
Jonathan Roberts and Ke Chen. 2015. Learning-Based Procedural Content Generation. IEEE Transactions on Computational Intelligence and AI in Games 7, 1 (March 2015), 88–101. https://doi.org/10.1109/TCIAIG.2014.2335273
[24]
RogueBasin. 2009. Grid based Dungeon Generator. Retrieved January 21, 2020 from http://roguebasin.roguelikedevelopment.org/index.php?title=Grid_Based_Dungeon_Generator
[25]
Doug Smith. 1983. Lode Runner. Game [Famicom]. Broderbund.
[26]
Sam Snodgrass and Santiago Ontañón. 2017. Learning to Generate Video Game Maps Using Markov Models. IEEE Transactions on Computational Intelligence and AI in Games 9, 4 (Dec 2017), 410–422. https://doi.org/10.1109/TCIAIG.2016.2623560
[27]
SpeedTree. 2020. SpeedTree. Retrieved January 21, 2020 from https://store.speedtree.com/
[28]
BethesdaGame Studios. 2011. The Elder Scrolls V: Skyrim. Game [Windows]. Bethesda Softworks.
[29]
Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, AmyK. Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. 2018. Procedural Content Generation via Machine Learning (PCGML). IEEE Transactions on Games 10, 3 (Sep. 2018), 257–270. https://doi.org/10.1109/TG.2018.2846639
[30]
AdamJames Summerville and Michael Mateas. 2015. Sampling hyrule: Multi-technique probabilistic level generation for action role playing games. In Eleventh Artificial Intelligence and Interactive Digital Entertainment Conference.
[31]
AdamJames Summerville, Shweta Philip, and Michael Mateas. 2015. MCMCTS PCG 4 SMB: Monte Carlo Tree Search to Guide Platformer Level Generation. In Eleventh Artificial Intelligence and Interactive Digital Entertainment Conference.
[32]
Penny Sweetser. 2008. Emergence in Games. Nelson Education.
[33]
Penelope Sweetser and Janet Wiles. 2005. Combining Influence Maps and Cellular Automata for Reactive Game Agents. In Intelligent Data Engineering and Automated Learning - IDEAL 2005, Marcus Gallagher, JamesP. Hogan, and Frederic Maire(Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 524–531.
Digital Library
[34]
Penelope Sweetser and Janet Wiles. 2005. Scripting versus emergence: issues for game developers and players in game environment design. International Journal of Intelligent Games and Simulations 4, 1(2005), 1–9.
[35]
Julian Togelius, Mike Preuss, Nicola Beume, Simon Wessing, Johan Hagelbäck, GeorgiosN. Yannakakis, and Corrado Grappiolo. 2013. Controllable procedural map generation via multiobjective evolution. Genetic Programming and Evolvable Machines 14, 2 (2013), 245–277. https://doi.org/10.1007/s10710-012-9174-5
Digital Library
[36]
Julian Togelius, Jim Whitehead, and Rafael Bidarra. 2011. Guest Editorial: Procedural content generation in games. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (9 2011), 169–171. https://doi.org/10.1109/TCIAIG.2011.2166554
[37]
Julian Togelius, GeorgiosN Yannakakis, KennethO Stanley, and Cameron Browne. 2011. Search-Based Procedural Content Generation: A Taxonomy and Survey. IEEE Transactions on Computational Intelligence and AI in Games 3, 3(2011), 172–186. https://doi.org/10.1109/TCIAIG.2011.2148116
[38]
RubenRodriguez Torrado, Ahmed Khalifa, MichaelCerny Green, Niels Justesen, Sebastian Risi, and Julian Togelius. 2019. Bootstrapping Conditional GANs for Video Game Level Generation. arXiv preprint arXiv:1910.01603(2019).
[39]
Michael Toy and Glenn Wichman. 1980. Rogue. Game [Atari]. Apyx.
[40]
Unity. 2020. Unity for Games. Retrieved January 21, 2020 from https://unity.com/solutions/game
[41]
Valtchan Valtchanov and JosephAlexander Brown. 2012. Evolving Dungeon Crawler Levels with Relative Placement. In Proceedings of the Fifth International C* Conference on Computer Science and Software Engineering(Montreal, Quebec, Canada) (C3S2E ’12). Association for Computing Machinery, New York, NY, USA, 27–35. https://doi.org/10.1145/2347583.2347587
Digital Library
[42]
Roland Van DerLinden, Ricardo Lopes, and Rafael Bidarra. 2014. Procedural Generation of Dungeons. IEEE Transactions on Computational Intelligence and AI in Games 6, 1 (March 2014), 78–89. https://doi.org/10.1109/TCIAIG.2013.2290371
[43]
GeorgiosN Yannakakis and Julian Togelius. 2011. Experience-Driven Procedural Content Generation. IEEE Transactions on Affective Computing 2, 3 (July 2011), 147–161. https://doi.org/10.1109/T-AFFC.2011.6
Digital Library
Cited By
View all
- Pereira LViana BToledo C(2024)A System for Orchestrating Multiple Procedurally Generated Content for Different Player ProfilesIEEE Transactions on Games10.1109/TG.2022.321378116:1(64-74)Online publication date: Mar-2024
- Werning S(2024)Generative AI and the Technological Imaginary of Game DesignCreative Tools and the Softwarization of Cultural Production10.1007/978-3-031-45693-0_4(67-90)Online publication date: 18-Jan-2024
- Weeks MDavis JOgden CGamess E(2022)Procedural dungeon generation for a 2D top-down gameProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3520214(60-66)Online publication date: 18-Apr-2022
https://dl.acm.org/doi/10.1145/3476883.3520214
- Show More Cited By
A Hybrid Approach to Procedural Generation of Roguelike Video Game Levels
Applied computing
Computers in other domains
Personal computers and PC applications
Information systems
Information systems applications
Multimedia information systems
Software and its engineering
Software organization and properties
Contextual software domains
Virtual worlds software
Recommendations
- Procedural Content Generation for Game Props? A Study on the Effects on User Experience
Theoretical and Practical Computer Applications in Entertainment
This work demonstrates the potentials of procedural content generation (PCG) for games, focusing on the generation of specific graphic props (reefs) in an explorer game.
We briefly portray the state-of-the-art of PCG and compare various methods to ...
Read More
- Adaptable game experience through procedural content generation and brain computer interface
SIGGRAPH '16: ACM SIGGRAPH 2016 Posters
For high skilled players, an easy game might become boring and for low skilled players, a difficult game might become frustrating. This research's goal is to offer players a personalized experience adapted according to their performance and levels of ...
Read More
- Understanding procedural content generation: a design-centric analysis of the role of PCG in games
CHI '14: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems
Games that use procedural content generation (PCG) do so in a wide variety of ways and for different reasons. One of the most common reasons cited by PCG system creators and game designers is improving replayability by providing a means for ...
Read More
Comments
Information & Contributors
Information
Published In
FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games
September 2020
804 pages
ISBN:9781450388078
DOI:10.1145/3402942
- Editors:
- Georgios N. Yannakakis
University of Malta
, - Antonios Liapis
University of Malta
, - Penny Kyburz
Australian National University
, - Vanessa Volz
Modl.AI
, - Foaad Khosmood
California Polytechnic State University
, - Phil Lopes
École Polytechnique Fédèrale de Lausanne
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [emailprotected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 September 2020
Permissions
Request permissions for this article.
Check for updates
Author Tags
- PCG
- context free grammars
- dungeons
- game design
- procedural content generation
- roguelike
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
FDG '20
FDG '20: International Conference on the Foundations of Digital Games
September 15 - 18, 2020
Bugibba, Malta
Acceptance Rates
Overall Acceptance Rate 152 of 415 submissions, 37%
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
6
Total Citations
1,188
Total Downloads
- Downloads (Last 12 months)328
- Downloads (Last 6 weeks)40
Other Metrics
View Author Metrics
Citations
Cited By
View all
- Pereira LViana BToledo C(2024)A System for Orchestrating Multiple Procedurally Generated Content for Different Player ProfilesIEEE Transactions on Games10.1109/TG.2022.321378116:1(64-74)Online publication date: Mar-2024
- Werning S(2024)Generative AI and the Technological Imaginary of Game DesignCreative Tools and the Softwarization of Cultural Production10.1007/978-3-031-45693-0_4(67-90)Online publication date: 18-Jan-2024
- Weeks MDavis JOgden CGamess E(2022)Procedural dungeon generation for a 2D top-down gameProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3520214(60-66)Online publication date: 18-Apr-2022
https://dl.acm.org/doi/10.1145/3476883.3520214
- Viana BPereira LToledo Cdos Santos SMaia S(2022)Feasible–Infeasible Two-Population Genetic Algorithm to evolve dungeon levels with dependencies in barrier mechanicsApplied Soft Computing10.1016/j.asoc.2022.108586119:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.asoc.2022.108586
- Lazaridis LKollias KMaraslidis GMichailidis HPapatsimouli MFragulis G(2022)Auto Generating Maps ina2D EnvironmentHCI in Games10.1007/978-3-031-05637-6_3(40-50)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-05637-6_3
- Wu ZMao YLi Q(2021)Procedural Game Map Generation using Multi-leveled Cellular Automata by Machine learningProceedings of the 2nd International Symposium on Artificial Intelligence for Medicine Sciences10.1145/3500931.3500962(168-172)Online publication date: 29-Oct-2021
https://dl.acm.org/doi/10.1145/3500931.3500962
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatMedia
Figures
Other
Tables
