Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming

Thomas Smith, Julian Padget, Andrew Vidler

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

14 Citations (SciVal)
2261 Downloads (Pure)


The construction of dungeons in typical action-adventure computer games entails composing a complex arrangement of structural and temporal dependencies. It is not simple to generate dungeons with correct lock-and-key structures. In this paper we sketch a controllable approach to building graph-based models of acyclic dungeon levels via declarative constraint solving, that is capable of satisfying a range of hard gameplay and design constraints. We use a quantitative expressive range analysis to characterise the initial output of the system, present an example of the degree to which the output may be altered, and show a comparison with an alternate approach.
Original languageEnglish
Title of host publicationProceedings of the 13th International Conference on the Foundations of Digital Games
EditorsSebastian Deterding, Mitu Khandaker, Sebastian Risi, Jose Font, Steve Dahlskog, Christoph Salge, Carl Magnus Olsson
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)978-1-4503-6571-0
Publication statusPublished - 7 Aug 2018
EventFoundations of Digital Games 2018 - Malmö, Malmö, Sweden
Duration: 7 Aug 201810 Aug 2018

Publication series

NameProceedings of the International Conference on the Foundations of Digital Games


ConferenceFoundations of Digital Games 2018
Abbreviated titleFDG
Internet address


  • Answer set programming
  • Expressive range
  • Generative methods
  • Procedural content generation

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Computer Networks and Communications
  • Computer Vision and Pattern Recognition
  • Software


Dive into the research topics of 'Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming'. Together they form a unique fingerprint.

Cite this