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

Thomas Smith; Julian Padget; Andrew Vidler

doi:10.1145/3235765.3235817

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

Thomas Smith, Julian Padget, Andrew Vidler

Ninja Theory Ltd

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

17 Citations (SciVal)

2622 Downloads (Pure)

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.

Original language	English
Title of host publication	Proceedings of the 13th International Conference on the Foundations of Digital Games
Editors	Sebastian Deterding, Mitu Khandaker, Sebastian Risi, Jose Font, Steve Dahlskog, Christoph Salge, Carl Magnus Olsson
Publisher	Association for Computing Machinery
Pages	52:1-52:10
Number of pages	10
ISBN (Electronic)	978-1-4503-6571-0
DOIs	https://doi.org/10.1145/3235765.3235817
Publication status	Published - 7 Aug 2018
Event	Foundations of Digital Games 2018 - Malmö, Malmö, Sweden Duration: 7 Aug 2018 → 10 Aug 2018 http://fdg2018.org/

Publication series

Name	Proceedings of the International Conference on the Foundations of Digital Games
Publisher	ACM

Conference

Conference	Foundations of Digital Games 2018
Abbreviated title	FDG
Country/Territory	Sweden
City	Malmö
Period	7/08/18 → 10/08/18
Internet address	http://fdg2018.org/

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

Access to Document

10.1145/3235765.3235817

Graph-based Generation of Action-Adventure Dungeon Levels using Answer Set Programming
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Final published version, 885 KB

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). Article 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 or section in a book/report/conference proceeding › Chapter in a published conference proceeding

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). doi: 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 = aug,

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",

note = "Foundations of Digital Games 2018, FDG ; Conference date: 07-08-2018 Through 10-08-2018",

url = "http://fdg2018.org/",

}

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 - Chapter in a published conference proceeding

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

T2 - Foundations of Digital Games 2018

Y2 - 7 August 2018 through 10 August 2018

ER -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this