1 Search Results for "Debesson, Adrien"


Document
The Dungeon Variations Problem Using Constraint Programming

Authors: Gaël Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)


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.

Cite as

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)


Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2021.27},
  URN =		{urn:nbn:de:0030-drops-153181},
  doi =		{10.4230/LIPIcs.CP.2021.27},
  annote =	{Keywords: constraint programming, video games, modelization, procedural generation}
}
  • Refine by Author
  • 1 Debesson, Adrien
  • 1 Glorian, Gaël
  • 1 Simon, Laurent
  • 1 Yvon-Paliot, Sylvain

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 constraint programming
  • 1 modelization
  • 1 procedural generation
  • 1 video games

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail