Procedural Dungeon Generation: A Survey

Breno M. F. Viana; Selan R. dos Santos

doi:10.5753/jis.2021.999

Authors

Breno M. F. Viana Universidade de São Paulo https://orcid.org/0000-0003-3441-508X
Selan R. dos Santos Universidade Federal do Rio Grande do Norte https://orcid.org/0000-0002-8056-1101

DOI:

https://doi.org/10.5753/jis.2021.999

Keywords:

Survey, Procedural Content Generation, Dungeon, Game

Abstract

Procedural content generation (PCG) is a method of content creation entirely or partially done by computers. PCG is popularly employed in game development to produce game content, such as maps and levels. Representative examples of games using PCG are Rogue (1998), which introduced the roguelike genre, and No Man’s Sky (2016), which generated whole worlds with fauna and flora. PCG may generate final contents, ready to be added to a game, or intermediate contents, which might be polished by human designers or work as an input level sketch to be interpreted by a level translator. In this paper, we survey the current state of procedural dungeon generation (PDG) research, a PCG subarea, applied in the context of games. For each work we selected in this survey, we examined and compared how they created game features, what type of level structure and representation they propose, which content generation strategy they applied, and, finally, we classify them according to the taxonomy of procedural content generation proposed by Togelius et al. (2016). The most relevant findings of our survey are: (1) PDG for 3D levels has been little explored; (2) few works supported levels with barriers, a game mechanic which temporarily blocks the player progression, and; (3) mixed-initiative approaches, i.e., software that helps human designers by making suggestions to the levels being created, are little explored.

Downloads

Download data is not yet available.

References

Adams, C. and Louis, S. (2017). Procedural maze level generation with evolutionary cellular automata. In Computational Intelligence (SSCI), 2017 IEEE Symposium Series on, pages 1–8. IEEE.

Alvarez, A., Dahlskog, S., Font, J., Holmberg, J., and Johansson, S. (2018). Assessing aesthetic criteria in the evolutionary dungeon designer. In Proceedings of the 13th International Conference on the Foundations of Digital Games, page 44. ACM.

Alvarez, A., Dahlskog, S., Font, J., and Togelius, J. (2019). Empowering quality diversity in dungeon design with interactive constrained mapelites. In 2019 IEEE Conference on Games (CoG), pages 1–8. IEEE.

Antoniuk, I., Hoser, P., and Strzęciwilk, D. (2018). L-system application to procedural generation of room shapes for 3d dungeon creation in computer games. In International MultiConference on Advanced Computer Systems, pages 375–386. Springer.

Ashlock, D. (2015). Evolvable fashion-based cellular automata for generating cavern systems. In Computational Intelligence and Games (CIG), 2015 IEEE Conference on, pages 306–313. IEEE.

Ashlock, D., Lee, C., and McGuinness, C. (2011a). Search-based procedural generation of mazelike levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):260–273.

Ashlock, D., Lee, C., and McGuinness, C. (2011b). Simultaneous dual level creation for games. IEEE Computational Intelligence Magazine, 6(2):26–37.

Ashlock, D. and McGuinness, C. (2014). Automatic generation of fantasy role-playing modules. In Computational Intelligence and Games (CIG), 2014 IEEE Conference on, pages 1–8. IEEE.

Assadi, H., Jones, R., Swift, A. J., Al-Mohammad, A., and Garg, P. (2020). Cardiac mri for the prognostication of heart failure with preserved ejection fraction: A systematic review and metaanalysis. Magnetic Resonance Imaging.

Baghdadi, W., Eddin, F. S., Al-Omari, R., Alhalawani, Z., Shaker, M., and Shaker, N. (2015). A procedural method for automatic generation of spelunky levels. In European Conference on the Applications of Evolutionary Computation, pages 305–317. Springer.

Baldwin, A., Dahlskog, S., Font, J. M., and Holmberg, J. (2017a). Mixed-initiative procedural generation of dungeons using game design patterns. In Computational Intelligence and Games (CIG), 2017 IEEE Conference on, pages 25–32. IEEE.

Baldwin, A., Dahlskog, S., Font, J. M., and Holmberg, J. (2017b). Towards pattern-based mixedinitiative dungeon generation. In Proceedings of the 12th International Conference on the Foundations of Digital Games, page 74. ACM.

Baron, J. R. (2017). Procedural dungeon generation analysis and adaptation. In Proceedings of the SouthEast Conference, pages 168–171. ACM.

Blizzard Entertainment (1996). Diablo. Accessed in: 2020-11-02.

Brace Yourself Games (2015). Crypt of the necrodancer. Accessed in: 2020-11-02.

Charity, M., Green, M. C., Khalifa, A., and Togelius, J. (2020). Mech-elites: Illuminating the mechanic space of gvgai. arXiv preprint arXiv:2002.04733.

Chomsky, N. (2006). Language and mind. Cambridge University Press.

De Kegel, B. and Haahr, M. (2019). Procedural puzzle generation: a survey. IEEE Transactions on Games, 12(1):21–40.

De Kok, T., Van Kreveld, M., and Löffler, M. (2007). Generating realistic terrains with higherorder delaunay triangulations. Computational Geometry, 36(1):52–65.

Delaunay, B. et al. (1934). Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793800):1–2.

Digital Sun (2018). Moonlighter. Accessed in: 2020-07-25.

Dormans, J. and Bakkes, S. (2011). Generating missions and spaces for adaptable play experiences. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):216–228.

Forsyth, W. (2016). Globalized random procedural content for dungeon generation. Journal of Computing Sciences in Colleges, 32(2):192–201.

Gellel, A. and Sweetser, P. (2020). A hybrid approach to procedural generation of roguelike video game levels. In International Conference on the Foundations of Digital Games, pages 1–10.

Gendreau, M., Potvin, J.-Y., et al. (2010). Handbook of metaheuristics, volume 2. Springer.

Goandy, H., Young, J. C., and Hansun, S. (2020). No escape: A 2d top-down shooting roguelike game embedded with drunkard walk algorithm. International Journal of Advanced Trends in Computer Science and Engineering.

Gravina, D., Khalifa, A., Liapis, A., Togelius, J., and Yannakakis, G. N. (2019). Procedural content generation through quality diversity. In 2019 IEEE Conference on Games (CoG), pages 1–8. IEEE.

Green, M. C., Khalifa, A., Alsoughayer, A., Surana, D., Liapis, A., and Togelius, J. (2019). Two-step constructive approaches for dungeon generation. In Proceedings of the 14th International Conference on the Foundations of Digital Games, pages 1–7.

Gutierrez, J. and Schrum, J. (2020). Generative adversarial network rooms in generative graph grammar dungeons for the legend of zelda. arXiv preprint arXiv:2001.05065.

Halatsch, J., Kunze, A., and Schmitt, G. (2008). Using shape grammars for master planning. In Design Computing and Cognition’08, pages 655–673. Springer.

Harper, S. L., Cunsolo, A., Babujee, A., Coggins, S., Aguilar, M. D., and Wright, C. J. (2021). Climate change and health in north america: literature review protocol. Systematic Reviews, 10(1):1–13.

Hell, J., Clay, M., and ELAarag, H. (2017). Hierarchical dungeon procedural generation and optimal path finding based on user input. Journal of Computing Sciences in Colleges, 33(1):175–183.

Hilliard, N., Salis, J., and ELAarag, H. (2017). Algorithms for procedural dungeon generation. Journal of Computing Sciences in Colleges, 33(1):166–174.

Johnson, L., Yannakakis, G. N., and Togelius, J. (2010). Cellular automata for real-time generation of infinite cave levels. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games, pages 1–4.

Karavolos, D., Liapis, A., and Yannakakis, G. N. (2016). Evolving missions for dwarf quest dungeons. In 2016 IEEE Conference on Computational Intelligence and Games (CIG), pages 1–2.

Kimbrough, S. O., Koehler, G. J., Lu, M., and Wood, D. H. (2005). Introducing a feasible-infeasible two-population (fi2pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. European Journal of Operational Research.

Klei Entertainment (2013). Don’t starve. Accessed in: 2020-11-02.

Kreitzer, M., Ashlock, D., and Pereira, R. (2019). Automatic generation of diverse cavern maps with morphing cellular automata. In 2019 IEEE Conference on Games (CoG), pages 1–8. IEEE.

Lavender, B. and Thompson, T. (2017). A generative grammar approach for action-adventure map generation in the legend of zelda.

Liapis, A. (2017). Multi-segment evolution of dungeon game levels. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 203–210. ACM.

Liapis, A., Holmgård, C., Yannakakis, G. N., and Togelius, J. (2015). Procedural personas as critics for dungeon generation. In European Conference on the Applications of Evolutionary Computation, pages 331–343. Springer.

Liberati, A., Altman, D. G., Tetzlaff, J., Mulrow, C., Gøtzsche, P. C., Ioannidis, J. P., Clarke, M., Devereaux, P. J., Kleijnen, J., and Moher, D. (2009). The prisma statement for reporting systematic reviews and meta-analyses of studies that evaluate health care interventions: explanation and elaboration. Journal of clinical epidemiology, 62(10):e1–e34.

Masotta, V., Dante, A., Marcotullio, A., Bertocchi, L., La Cerra, C., Caponnetto, V., Petrucci, C., and Alfes, C. M. (2020). The concept of high-fidelity simulation and related factors in nursing education: A scoping review. In International Conference in Methodologies and intelligent Systems for Techhnology Enhanced Learning, pages 119–126. Springer.

McGuinness, C. and Ashlock, D. (2011). Decomposing the level generation problem with tiles. In Evolutionary Computation (CEC), 2011 IEEE Congress on, pages 849–856. IEEE.

McMillen, E. and Himsl, F. (2011). The binding of Isaac. Accessed in: 2020-11-02.

Melotti, A. S. and de Moraes, C. H. V. (2018). Evolving roguelike dungeons with deluged novelty search local competition. IEEE Transactions on Games, 11(2):173–182.

Moher, D., Liberati, A., Tetzlaff, J., and Altman, D. G. (2009). Preferred reporting items for systematic reviews and meta-analyses: the prisma statement. Annals of internal medicine, 151(4):264–269.

Moray, K. V., Chaurasia, H., Sachin, O., and Joshi, B. (2021). A systematic review on clinical effectiveness, side-effect profile and meta-analysis on continuation rate of etonogestrel contraceptive implant. Reproductive Health, 18(1):1–24.

Motion Twin (2018). Dead cells. Accessed in: 2020-07-25.

Mulrow, C. D. (1994). Systematic reviews: rationale for systematic reviews. Bmj, 309(6954):597–599.

Nepožitek, O. and Gemrot, J. (2018). Fast configurable tilebased dungeon level generator.

Nintendo (1986). The legend of zelda - franchise. Accessed in: 2020-09-04.

Nintendo (1996). Pokémon - franchise. Accessed in: 2020-09-10.

Olsen, J. (2004). Realtime procedural terrain generation.

Pech, A., Hingston, P., Masek, M., and Lam, C. P. (2015). Evolving cellular automata for maze generation. In Australasian Conference on Artificial Life and Computational Intelligence, pages 112–124. Springer.

Pech, A., Masek, M., Lam, C.-P., and Hingston, P. (2016). Game level layout generation using evolved cellular automata. Connection Science, 28(1):63–82.

Pereira, L. T., Prado, P. V., and Toledo, C. (2018). Evolving dungeon maps with locked door missions. In 2018 IEEE Congress on Evolutionary Computation (CEC), pages 1–8. IEEE.

Prim, R. C. (1957). Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):1389–1401.

Pugh, J. K., Soros, L. B., and Stanley, K. O. (2016). Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3:40.

Rozenberg, G. (1997). Handbook of Graph Grammars and Comp., volume 1. World scientific.

Sampaio, P., Baffa, A., Feijó, B., and Lana, M. (2017). A fast approach for automatic generation of populated maps with seed and difficulty control. In 2017 16th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), pages 10–18. IEEE.

Santamaria-Ibirika, A., Cantero, X., Huerta, S., Santos, I., and Bringas, P. G. (2014). Procedural playable cave systems based on voronoi diagram and delaunay triangulation. In Cyberworlds (CW), 2014 International Conference on, pages 15–22. IEEE.

Sheffield, E. C. and Shah, M. D. (2018). Dungeon digger: Apprenticeship learning for procedural dungeon building agents. In Proceedings of the 2018 Annual Symposium on ComputerHuman Interaction in Play Companion Extended Abstracts, pages 603–610.

Smith, A. J. and Bryson, J. J. (2014). A logical approach to building dungeons: Answer set programming for hierarchical procedural content generation in roguelike games. In Proceedings of the 50th Anniversary Convention of the AISB.

Smith, T., Padget, J., and Vidler, A. (2018). 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, page 52. ACM.

Sony (2005). God of war. Accessed in: 2021-03-30.

Summerville, A., Snodgrass, S., Guzdial, M., Holmgård, C., Hoover, A. K., Isaksen, A., Nealen, A., and Togelius, J. (2018). Procedural content generation via machine learning (pcgml). IEEE Transactions on Games, 10(3):257–270.

Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.

Togelius, J., Justinussen, T., and Hartzen, A. (2012). Compositional procedural content generation. In Proceedings of The third workshop on Procedural Content Generation in Games, page 16. ACM.

Togelius, J., Shaker, N., and Nelson, M. J. (2016). Introduction. In Shaker, N., Togelius, J., and Nelson, M. J., editors, Procedural Content Generation in Games: A Textbook and an Overview of Current Research, pages 1–15. Springer.

Togelius, J., Yannakakis, G. N., Stanley, K. O., and Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):172–186.

Toy, M. and Wichman, G. (1980). Rogue. Accessed in: 2020-07-25.

Valtchanov, V. and Brown, J. A. (2012). Evolving dungeon crawler levels with relative placement. In Proceedings of the Fifth International C* Conference on Computer Science and Software Engineering, pages 27–35. ACM.

Valve Corporation (2009). Left 4 dead 2. Acessado em: 2020-11-02.

van der Linden, R., Lopes, R., and Bidarra, R. (2013). Designing procedurally generated levels. In Proceedings of the second workshop on Artificial Intelligence in the Game Design Process.

van der Linden, R., Lopes, R., and Bidarra, R. (2014). Procedural generation of dungeons. IEEE Transactions on Computational Intelligence and AI in Games, 6(1):78–89.

Van Laarhoven, P. J. and Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications, pages 7–15. Springer.

Viana, B. M. and dos Santos, S. R. (2019). A survey of procedural dungeon generation. In 2019 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), pages 29–38. IEEE.

Voronoi, G. (1908). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik (Crelles Journal), 1908(134):198–287.

Whitehead, J. (2020). Spatial layout of procedural dungeons using linear constraints and smt solvers. In International Conference on the Foundations of Digital Games, pages 1–9.

Wild Card Games (2013). Dwarf quest. Accessed in: 2020-08-10.

Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of modern physics, 55(3):601.

Yu, D. (2008). Spelunky. Accessed in: 2020-08-10.