LIPIcs.CP.2021.27.pdf
- Filesize: 2.62 MB
- 16 pages
Document
The Dungeon Variations Problem Using Constraint Programming
Authors
-
Part of:
Volume:
27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles and Practice of Constraint Programming (CP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-10-15
Cite As Get BibTex
Gaël Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon. The Dungeon Variations Problem Using Constraint Programming. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.27
Abstract
The video games industry generates billions of dollars in sales every year. Video games can offer increasingly complex gaming experiences, with gigantic (but consistent) open worlds, thanks to larger and larger teams of developers and artists. In this paper, we propose a constraint-based approach for procedural dungeon generation in an open world/universe context, in order to provide players with consistent, open worlds with an excellent quality of storytelling. Thanks to a global description capturing all the possible rooms and situations of a given dungeon, our approach allows enumerating variations of this global pattern, which can then be presented to the player for more diversity. We formalise this problem in constraint programming by exploiting a graph abstraction of the dungeon pattern structure. Every path of the graph represents a possible variation matching a given set of constraints. We introduce a new propagator extending the "connected" graph constraint, which allows considering directed graphs with cycles. We show that thanks to this model and the proposed new propagator, it is possible to handle scenarios at the forefront of the game industry (AAA+ games). We demonstrate that our approach outperforms non-specialised solutions consisting of filtering only the relevant solutions a posteriori. We then conclude and offer several exciting perspectives raised by this approach to the Dungeon Variations Problem.
Subject Classification
ACM Subject Classification
- Theory of computation → Constraint and logic programming
Keywords
- constraint programming
- video games
- modelization
- procedural generation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Gilles Audemard, Frédéric Boussemart, Christophe Lecoutre, Cédric Piette, and Olivier Roussel. Xcsp^3 and its ecosystem. Constraints An Int. J., 25(1-2):47-69, 2020. URL: https://doi.org/10.1007/s10601-019-09307-9.
- Daniel Le Berre, Pierre Marquis, and Stéphanie Roussel. Planning personalised museum visits. In Daniel Borrajo, Subbarao Kambhampati, Angelo Oddi, and Simone Fratini, editors, Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS 2013, Rome, Italy, June 10-14, 2013. AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS13/paper/view/6025.
- Diego de Uña. Discrete optimization over graph problems. PhD thesis, University of Melbourne, Parkville, Victoria, Australia, 2018. URL: http://hdl.handle.net/11343/217321.
- Diego de Uña, Graeme Gange, Peter Schachte, and Peter J. Stuckey. A bounded path propagator on directed graphs. In Michel Rueher, editor, Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings, volume 9892 of Lecture Notes in Computer Science, pages 189-206. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-44953-1_13.
- Grégoire Dooms, Yves Deville, and Pierre Dupont. Cp(graph): Introducing a graph computation domain in constraint programming. In Peter van Beek, editor, Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, volume 3709 of Lecture Notes in Computer Science, pages 211-225. Springer, 2005. URL: https://doi.org/10.1007/11564751_18.
- Joris Dormans. A handcrafted feel: Unexplored explores cyclic dungeon generation. URL: https://ctrl500.com/tech/handcrafted-feel-dungeon-generation-unexplored-explores-cyclic-dungeon-generation/.
- Jean-Guillaume Fages. Exploitation de structures de graphe en programmation par contraintes. Theses, Ecole des Mines de Nantes, 2014. URL: https://tel.archives-ouvertes.fr/tel-01085253.
- Jean-Guillaume Fages. On the use of graphs within constraint-programming. Constraints An Int. J., 20(4):498-499, 2015. URL: https://doi.org/10.1007/s10601-015-9223-9.
- Gael Glorian, Jean-Marie Lagniez, and Christophe Lecoutre. NACRE - A nogood and clause reasoning engine. In Elvira Albert and Laura Kovács, editors, LPAR 2020: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Alicante, Spain, May 22-27, 2020, volume 73 of EPiC Series in Computing, pages 249-259. EasyChair, 2020. URL: https://easychair.org/publications/paper/rN67.
- Carsten Grabow, Stefan Grosskinsky, Jürgen Kurths, and Marc Timme. Collective relaxation dynamics of small-world networks. CoRR, abs/1507.04624, 2015. URL: http://arxiv.org/abs/1507.04624.
-
Ian Horswill and Leif Foged. Fast procedural level population with playability constraints. In Proceedings of the Eighth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE'12, page 20–25. AAAI Press, 2012.
-
R. Lavender. The zelda dungeon generator: Adopting generative grammars to create levels for action-adventure games, 2016.
- Brenton Prettejohn, Matthew Berryman, and Mark McDonnell. Methods for generating complex networks with selected structural properties for simulations: A review and tutorial for neuroscientists. Frontiers in Computational Neuroscience, 5:11, 2011. URL: https://doi.org/10.3389/fncom.2011.00011.
-
Patrick Prosser and Chris Unsworth. A connectivity constraint using bridges. In Gerhard Brewka, Silvia Coradeschi, Anna Perini, and Paolo Traverso, editors, ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings, volume 141 of Frontiers in Artificial Intelligence and Applications, pages 707-708. IOS Press, 2006.
- Luis Quesada, Peter Van Roy, Yves Deville, and Raphaël Collet. Using dominators for solving constrained path problems. In Pascal Van Hentenryck, editor, Practical Aspects of Declarative Languages, 8th International Symposium, PADL 2006, Charleston, SC, USA, January 9-10, 2006, Proceedings, volume 3819 of Lecture Notes in Computer Science, pages 73-87. Springer, 2006. URL: https://doi.org/10.1007/11603023_6.
- Gillian Smith and Jim Whitehead. Analyzing the expressive range of a level generator. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games, PCGames '10, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1814256.1814260.
- Thomas Smith, Julian A. Padget, and Andrew Vidler. Graph-based generation of action-adventure dungeon levels using answer set programming. In Steve Dahlskog, Sebastian Deterding, José M. Font, Mitu Khandaker, Carl Magnus Olsson, Sebastian Risi, and Christoph Salge, editors, Proceedings of the 13th International Conference on the Foundations of Digital Games, FDG 2018, Malmö, Sweden, August 07-10, 2018, pages 52:1-52:10. ACM, 2018. URL: https://doi.org/10.1145/3235765.3235817.
- Valtchan Valtchanov and Joseph Alexander Brown. Evolving dungeon crawler levels with relative placement. In Proceedings of the Fifth International C* Conference on Computer Science and Software Engineering, C3S2E '12, page 27–35, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2347583.2347587.
- Breno M. F. Viana and Selan R. dos Santos. A survey of procedural dungeon generation. In 18th Brazilian Symposium on Computer Games and Digital Entertainment, SBGames 2019, Rio de Janeiro, Brazil, October 28-31, 2019, pages 29-38. IEEE, 2019. URL: https://doi.org/10.1109/SBGames.2019.00015.