License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.27
URN: urn:nbn:de:0030-drops-153181
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15318/
Go to the corresponding LIPIcs Volume Portal

Glorian, Gaël ; Debesson, Adrien ; Yvon-Paliot, Sylvain ; Simon, Laurent

The Dungeon Variations Problem Using Constraint Programming

pdf-format:
LIPIcs-CP-2021-27.pdf (3 MB)

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.

BibTeX - Entry

@InProceedings{glorian_et_al:LIPIcs.CP.2021.27,
  author =	{Glorian, Ga\"{e}l and Debesson, Adrien and Yvon-Paliot, Sylvain and Simon, Laurent},
  title =	{{The Dungeon Variations Problem Using Constraint Programming}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15318},
  URN =		{urn:nbn:de:0030-drops-153181},
  doi =		{10.4230/LIPIcs.CP.2021.27},
  annote =	{Keywords: constraint programming, video games, modelization, procedural generation}
}

Keywords: constraint programming, video games, modelization, procedural generation
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code): https://bit.ly/3xSXK2B

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI