Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Patterns and procedural content generation in digital games: automatic level generation for digital games using game design patterns
Malmö högskola, Faculty of Technology and Society (TS).ORCID iD: 0000-0002-2644-2785
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The development of content in digital games, such as game worlds, quests, levels, 3D-models, and textures, is costly and time consuming. To address this, different approaches to automate the process of creating game content, often referred to as procedural content generation (PCG), has been suggested. However, PCG is a complex task and include challenges such as creating content with variation, coherent style, speed, and correctness. The research in the thesis is concerned with generating game content with the aid of game design patterns, both by establishing models and exploring different methods to generate actual game content for different games. The methods include implementations of evolutionary computation, i.e. a set of search-based approaches that searches for instances of game design patterns on different abstraction levels that make up Super Mario Bros. (SMB) levels and a learning algorithm implementation based on a model (n-grams) of patterns from the original SMB-game. The different generators were evaluated with metrics concerned with the expressive range of the generators and with user tests.

Place, publisher, year, edition, pages
Malmö university, Faculty of Technology and Society , 2016. , p. 269
Series
Studies in Computer Science ; 2
Keywords [en]
Procedural Content Generation, Search-based, Genetic Algorithms, Digital Games, Design Patterns
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mau:diva-7775Local ID: 20371ISBN: 978-91-7104-684-0 (print)ISBN: 978-91-7104-685-7 (print)OAI: oai:DiVA.org:mau-7775DiVA, id: diva2:1404716
Public defence
2016-06-10, Niagara, NI:B0E15, Malmö, 13:00 (English)
Opponent
Available from: 2020-02-28 Created: 2020-02-28 Last updated: 2022-06-27Bibliographically approved
List of papers
1. Patterns and procedural content generation: revisiting Mario in world 1 level 1
Open this publication in new window or tab >>Patterns and procedural content generation: revisiting Mario in world 1 level 1
2012 (English)In: Proceedings of the First Workshop on Design Patterns in Games, ACM Digital Library, 2012Conference paper, Published paper (Other academic)
Abstract [en]

Procedural content generation and design patterns could potentially be combined in several di erent ways in game design. This paper discusses how to combine the two, using automatic platform game level design as an example. The paper also present work towards a pattern-based level generator for Super Mario Bros, namely an analysis of the levels of the original Super Mario Bros game into 23 di erent patterns.

Place, publisher, year, edition, pages
ACM Digital Library, 2012
Keywords
procedural content generation, patterns, design, platform games, Super Mario Bros.
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16843 (URN)10.1145/2427116.2427117 (DOI)13931 (Local ID)13931 (Archive number)13931 (OAI)
Conference
Design Patterns in Games (DPG), North Carolina, USA (2012)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
2. Patterns as Objectives for Level Generation
Open this publication in new window or tab >>Patterns as Objectives for Level Generation
2013 (English)In: Proceedings of the Second Workshop on Design Patterns in Games, ACM Digital Library, 2013Conference paper, Published paper (Other academic)
Abstract [en]

This paper discusses how to use design patterns in procedural level generation, with particular reference to the classic console game Super Mario Bros. In a previous paper, we analyzed the levels in this game to nd a set of recurring level design patterns, and discussed an implementation where levels were produced from concatenation of these patterns. In this paper, we instead propose using patterns as design objectives. An implementation of this based on evolutionary computation is presented. In this implementation, levels are represented as a set of vertical slices from the original game, and the tness function count the number of patterns found. Qualitative analysis of generated levels is performed in order to identify strengths and challenges of this method.

Place, publisher, year, edition, pages
ACM Digital Library, 2013
Keywords
Game Design Patterns, Procedural Content Generation, Super Mario Bros., Genetic Algorithms
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16753 (URN)15713 (Local ID)15713 (Archive number)15713 (OAI)
Conference
Design Patterns in Games (DPG), Chania, Crete, Greece (2013)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
3. Procedural Content Generation Using Patterns as Objectives
Open this publication in new window or tab >>Procedural Content Generation Using Patterns as Objectives
2014 (English)In: APPLICATIONS OF EVOLUTIONARY COMPUTATION / [ed] Esparcia Alcazar, A I, Springer, 2014, p. 325-336Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we present a search-based approach for procedural generation of game levels that represents levels as sequences of micro-patterns and searched for meso-patterns. The micro-patterns are "slices" of original human-designed levels from an existing game, whereas the meso-patters are abstractions of common design patterns seen in the same levels. This method generates levels that are similar in style to the levels from which the original patterns were extracted, while still allowing for considerable variation in the geometry of the generated levels. The evolutionary method for generating the levels was tested extensively to investigate the distribution of micro-patterns used and meso-patterns found.

Place, publisher, year, edition, pages
Springer, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8602
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-39304 (URN)10.1007/978-3-662-45523-4_27 (DOI)000354874300027 ()978-3-662-45523-4 (ISBN)978-3-662-45522-7 (ISBN)
Conference
17th European Conference on Applications of Evolutionary Computation (EvpApplications), APR 23-25, 2014, Granada, SPAIN
Available from: 2021-01-18 Created: 2021-01-18 Last updated: 2021-06-07Bibliographically approved
4. A multi-level level generator
Open this publication in new window or tab >>A multi-level level generator
2014 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Generating content at multiple levels of abstraction simultaneously is an open challenge in procedural content generation. Representing and automatically replicating the style of a human designer is another. This paper addresses both of these challenges through extending a previously devised methodology for pattern-based level generation. This method builds on an analysis of Super Mario Bros levels into three abstraction levels: micro-, meso- and macro-patterns. Micro-patterns are then used as building blocks in a search-based PCG approach that searches for macro-patterns, which are defined as combinations of meso-patterns. Results show that we can successfully generate levels that replicate the macro-patterns of selected input levels, and we argue that this constitutes an approach to automatically analysing and replicating style in level design.

Place, publisher, year, edition, pages
IEEE, 2014
Keywords
Procedural Content Generation, Super Mario Bros., Level Generation, Digital Games
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16768 (URN)17650 (Local ID)17650 (Archive number)17650 (OAI)
Conference
IEEE Conference on Computational Intelligence and Games, Dortmund, Germany (2014)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
5. A Comparative Evaluation of Procedural Level Generators in the Mario AI Framework
Open this publication in new window or tab >>A Comparative Evaluation of Procedural Level Generators in the Mario AI Framework
Show others...
2014 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Evaluation is an open problem in procedural content generation research. The eld is now in a state where there is a glut of content generators, each serving di erent purposes and using a variety of techniques. It is difficult to understand, quantitatively or qualitatively, what makes one generator di erent from another in terms of its output. To remedy this, we have conducted a large-scale comparative evaluation of level generators for the Mario AI Benchmark, a research-friendly clone of the classic platform game Super Mario Bros. In all, we compare the output of seven different level generators from the literature, based on different algorithmic methods, plus the levels from the original Super Mario Bros game. To compare them, we have de ned six expressivity metrics, of which two are novel contributions in this paper. These metrics are shown to provide interestingly di erent characterizations of the level generators. The results presented in this paper, and the accompanying source code, is meant to become a benchmark against which to test new level generators and expressivity metrics.

Place, publisher, year, edition, pages
Society for the Advancement of the Science of Digital Games, 2014
Keywords
Procedural Content Generation, Level Generators
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16786 (URN)17062 (Local ID)17062 (Archive number)17062 (OAI)
Conference
Foundations of Digital Games 2014, Ft. Lauderdale, Florida, USA (2014)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
6. Linear Levels Through n-grams
Open this publication in new window or tab >>Linear Levels Through n-grams
2014 (English)Conference paper, Published paper (Refereed)
Abstract [en]

We shown that novel, linear game levels can be created using n- grams that have been trained on a corpus of existing levels. The method is fast and simple, and produces levels that are recognisably in the same style as those in the corpus that it has been trained on. We use Super Mario Bros. as an example domain, and use a selection of the levels from the original game as a training corpus. We treat Mario levels as a left-to-right sequence of vertical level slices, allowing us to perform level generation in a setting with some formal similarities to n-gram-based text generation and music generation. In empirical results, we investigate the effects of corpus size and n (sequence length). While the applicability of the method might seem limited to the relatively narrow domain of 2D games, we argue that many games in effect have linear levels and n-grams could be used to good effect, given that a suitable alphabet can be found.

Place, publisher, year, edition, pages
ACM Digital Library, 2014
Keywords
Procedural content generation, n-grams, videogames
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16744 (URN)18048 (Local ID)18048 (Archive number)18048 (OAI)
Conference
Academic MindTrek Conference, Tampere, Finland (2014)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
7. Patterns, Dungeons and Generators
Open this publication in new window or tab >>Patterns, Dungeons and Generators
2015 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This paper analyses dungeons, of the varieties commonly found in role-playing games, into several sets of design patterns at different levels of abstraction. The analysis focuses on mechanical patterns that could be either straightforwardly instantiated or recognized by a well-defined process. At the most concrete level a set of fundamental components were identified, followed by a long list of micropatterns which can be directly instantiated. Shorter lists of meso- and macro-patterns, which can be identified mechanically, are also identified. The direct motivation for this analysis is to find building blocks and objectives for a search-based procedural dungeon generator, however we believe the analysis can be useful for understanding this class of game artifacts in general. In particular, the constraints on patterns being instantiable or recognizable leads to a stricter pattern analysis than many other attempts at analyzing game design.

Place, publisher, year, edition, pages
Foundations of Digital Games, 2015
Keywords
design patterns, dungeons, Procedural content generation
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mau:diva-16749 (URN)19162 (Local ID)19162 (Archive number)19162 (OAI)
Conference
Foundations of Digital Games Conference, FDG, Pacific Grove, U.S.A. (2015)
Available from: 2020-03-30 Created: 2020-03-30 Last updated: 2022-06-27Bibliographically approved
8. Player Experience Evaluation of Level Generators in the Mario AI Framework
Open this publication in new window or tab >>Player Experience Evaluation of Level Generators in the Mario AI Framework
2016 (English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-18164 (URN)
Available from: 2020-09-02 Created: 2020-09-02 Last updated: 2022-06-27Bibliographically approved

Open Access in DiVA

fulltext(9169 kB)506 downloads
File information
File name FULLTEXT01.pdfFile size 9169 kBChecksum SHA-512
373ccce66fb30377b0c16347d0b68edbc3df456214ee72169e40544c702f6e8edd7083d5c034848a8ea6064dfa8b021e2c749ae328f569ff5b1503d5a2aab3a0
Type fulltextMimetype application/pdf

Authority records

Dahlskog, Steve

Search in DiVA

By author/editor
Dahlskog, Steve
By organisation
Faculty of Technology and Society (TS)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 506 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 646 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf