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

Thomas Smith, Julian Padget, Andrew Vidler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
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
Pages52:1-52:10
Number of pages10
ISBN (Electronic)978-1-4503-6571-0
DOIs
StatusPublished - 7 Aug 2018
EventFoundations of Digital Games 2018 - Malmö, Malmö, Sweden
Duration: 7 Aug 201810 Aug 2018
http://fdg2018.org/

Publication series

NameProceedings of the International Conference on the Foundations of Digital Games
PublisherACM

Conference

ConferenceFoundations of Digital Games 2018
Abbreviated titleFDG
CountrySweden
CityMalmö
Period7/08/1810/08/18
Internet address

Fingerprint

Computer games

Keywords

  • 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

Cite this

Smith, T., Padget, J., & Vidler, A. (2018). Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming. In S. Deterding, M. Khandaker, S. Risi, J. Font, S. Dahlskog, C. Salge, & C. M. Olsson (Eds.), Proceedings of the 13th International Conference on the Foundations of Digital Games (pp. 52:1-52:10). [52] (Proceedings of the International Conference on the Foundations of Digital Games). Association for Computing Machinery. https://doi.org/10.1145/3235765.3235817

Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming. / Smith, Thomas; Padget, Julian; Vidler, Andrew.

Proceedings of the 13th International Conference on the Foundations of Digital Games. ed. / Sebastian Deterding; Mitu Khandaker; Sebastian Risi; Jose Font; Steve Dahlskog; Christoph Salge; Carl Magnus Olsson. Association for Computing Machinery, 2018. p. 52:1-52:10 52 (Proceedings of the International Conference on the Foundations of Digital Games).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Smith, T, Padget, J & Vidler, A 2018, Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming. in S Deterding, M Khandaker, S Risi, J Font, S Dahlskog, C Salge & CM Olsson (eds), Proceedings of the 13th International Conference on the Foundations of Digital Games., 52, Proceedings of the International Conference on the Foundations of Digital Games, Association for Computing Machinery, pp. 52:1-52:10, Foundations of Digital Games 2018, Malmö, Sweden, 7/08/18. https://doi.org/10.1145/3235765.3235817
Smith T, Padget J, Vidler A. Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming. In Deterding S, Khandaker M, Risi S, Font J, Dahlskog S, Salge C, Olsson CM, editors, Proceedings of the 13th International Conference on the Foundations of Digital Games. Association for Computing Machinery. 2018. p. 52:1-52:10. 52. (Proceedings of the International Conference on the Foundations of Digital Games). https://doi.org/10.1145/3235765.3235817
Smith, Thomas ; Padget, Julian ; Vidler, Andrew. / Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming. Proceedings of the 13th International Conference on the Foundations of Digital Games. editor / Sebastian Deterding ; Mitu Khandaker ; Sebastian Risi ; Jose Font ; Steve Dahlskog ; Christoph Salge ; Carl Magnus Olsson. Association for Computing Machinery, 2018. pp. 52:1-52:10 (Proceedings of the International Conference on the Foundations of Digital Games).
@inproceedings{68ce949270dc487c8bc35b86c4ced34d,
title = "Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming",
abstract = "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.",
keywords = "Answer set programming, Expressive range, Generative methods, Procedural content generation",
author = "Thomas Smith and Julian Padget and Andrew Vidler",
year = "2018",
month = "8",
day = "7",
doi = "10.1145/3235765.3235817",
language = "English",
series = "Proceedings of the International Conference on the Foundations of Digital Games",
publisher = "Association for Computing Machinery",
pages = "52:1--52:10",
editor = "Sebastian Deterding and Mitu Khandaker and Sebastian Risi and Jose Font and Steve Dahlskog and Christoph Salge and Olsson, {Carl Magnus}",
booktitle = "Proceedings of the 13th International Conference on the Foundations of Digital Games",
address = "USA United States",

}

TY - GEN

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

AU - Smith, Thomas

AU - Padget, Julian

AU - Vidler, Andrew

PY - 2018/8/7

Y1 - 2018/8/7

N2 - 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.

AB - 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.

KW - Answer set programming

KW - Expressive range

KW - Generative methods

KW - Procedural content generation

UR - http://www.scopus.com/inward/record.url?scp=85055477379&partnerID=8YFLogxK

U2 - 10.1145/3235765.3235817

DO - 10.1145/3235765.3235817

M3 - Conference contribution

T3 - Proceedings of the International Conference on the Foundations of Digital Games

SP - 52:1-52:10

BT - Proceedings of the 13th International Conference on the Foundations of Digital Games

A2 - Deterding, Sebastian

A2 - Khandaker, Mitu

A2 - Risi, Sebastian

A2 - Font, Jose

A2 - Dahlskog, Steve

A2 - Salge, Christoph

A2 - Olsson, Carl Magnus

PB - Association for Computing Machinery

ER -