Procedural Content Generation

Procedurally generated content has been used by the game industry since Rogue and Elite in the eighties, but research interest in this topic is only now emerging. Whether generating spaceships, game levels, dungeons or gameworlds, a major part of my research lies within the general area of search-based procedural game content generation through genetic algorithms.

Learning the Patterns of Balance in a Multi-Player Shooter Game

Daniel Karavolos, Antonios Liapis and Georgios N. Yannakakis

Abstract: A particular challenge of the game design process is when the designer is requested to orchestrate dissimilar elements of games such as visuals, audio, narrative and rules to achieve a specific play experience. Within the domain of adversarial first person shooter games, for instance, a designer must be able to comprehend the differences between the weapons available in the game, and appropriately craft a game level to take advantage of strengths and weaknesses of those weapons. As an initial study towards computationally orchestrating dissimilar content generators in games, this paper presents a computational model which can classify a matchup of a team-based shooter game as balanced or as favoring one or the other team. The computational model uses convolutional neural networks to learn how game balance is affected by the level, represented as an image, and each team's weapon parameters. The model was trained on a corpus of over 50,000 simulated games with artificial agents on a diverse set of levels created by 39 different generators. The results show that the fusion of levels, when processed by a convolutional neural network, and weapon parameters yields an accuracy far above the baseline but also improves accuracy compared to artificial neural networks or models which use partial information, such as only the weapon or only the level as input.

In Proceedings of the FDG workshop on Procedural Content Generation in Games, 2017. BibTex

Multi-segment Evolution of Dungeon Game Levels

Antonios Liapis

Abstract: This paper presents a generative technique for game levels, focusing on expansive dungeon levels. The proposed two-step evolutionary process creates a high-level overview of the map, which is then used to specify constraints and objectives on multiple constrained optimization algorithms which generate the high-resolution segments of the map. Results show how different types of segments are possible, and how the different connectivity constraints and objectives affect the performance of the algorithm. The modular approach, which allows for a high-level specification of the level first and the subsequent compartmentalized generation of the final map's components, is both scalable and more computationally efficient than a direct encoding, while it allows for more control and user intervention on either level of detail.

In Proceedings of the Genetic and Evolutionary Computation Conference, 2017. BibTex

Constructive generation methods for dungeons and levels

Noor Shaker, Antonios Liapis, Julian Togelius, Ricardo Lopes, and Rafael Bidarra

Abstract: This chapter addresses a specific type of game content, the dungeon, and a number of commonly used methods for generating such content. These methods are all "constructive", meaning that they run in fixed (usually short) time, and do not evaluate their output in order to re-generate it. Most of these methods are also relatively simple to implement. And while dungeons, or dungeon-like environments, occur in a very large number of games, these methods can often be made to work for other types of content as well. We finish the chapter by talking about some constructive generation methods for Super Mario Bros. levels.

In Procedural Content Generation in Games: A Textbook and an Overview of Current Research, Springer, 2016. BibTex

Mixed-initiative Content Creation

Antonios Liapis, Gillian Smith and Noor Shaker

Abstract: Algorithms can generate game content, but so can humans. And while PCG algorithms can generate some kinds of game content remarkably well and extremely quickly, some other types (and aspects) of game content are still best made by humans. Can we combine the advantages of procedural generation and human creation somehow? This chapter discusses mixed-initiative systems for PCG, where both humans and software have agency and co-create content. A small taxonomy is presented of different ways in which humans and algorithms can collaborate, and then three mixed-initiative PCG systems are discussed in some detail: Tanagra, Sentient Sketchbook, and Ropossum.

In Procedural Content Generation in Games: A Textbook and an Overview of Current Research, Springer, 2016. BibTex

A Holistic Approach for Semantic-Based Game Generation

Owen Sacco, Antonios Liapis and Georgios N. Yannakakis

Abstract: The Web contains vast sources of content that could be reused to reduce the development time and effort to create games. However, most Web content is unstructured and lacks meaning for machines to be able to process and infer new knowledge. The Web of Data is a term used to describe a trend for publishing and interlinking previously disconnected datasets on the Web in order to make them more valuable and useful as a whole. In this paper, we describe an innovative approach that exploits Semantic Web technologies to automatically generate games by reusing Web content. Existing work on automatic game content generation through algorithmic means focuses primarily on a set of parameters within constrained game design spaces such as terrains or game levels, but does not harness the potential of already existing content on the Web for game generation. We instead propose a holistic and more generally-applicable game generation solution that would identify suitable Web information sources and enrich game content with semantic meta-structures.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG). 2016. BibTex

Constrained Surprise Search for Content Generation

Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis

Abstract: In procedural content generation, it is often desirable to create artifacts which not only fulfill certain playability constraints but are also able to surprise the player with unexpected potential uses. This paper applies a divergent evolutionary search method based on surprise to the constrained problem of generating balanced and efficient sets of weapons for the Unreal Tournament III shooter game. The proposed constrained surprise search algorithm ensures that pairs of weapons are sufficiently balanced and effective while also rewarding unexpected uses of these weapons during game simulations with artificial agents. Results in the paper demonstrate that searching for surprise can create functionally diverse weapons which require new gameplay patterns of weapon use in the game.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG). 2016. BibTex

Evolving Missions to Create Game Spaces

Daniel Karavolos, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper describes a search-based generative method which creates game levels by evolving the intended sequence of player actions rather than their spatial layout. The proposed approach evolves graphs where nodes representing player actions are linked to form one or more ways in which a mission can be completed. Initially simple graphs containing the mission's starting and ending nodes are evolved via mutation operators which expand and prune the graph topology. Evolution is guided by several objective functions which capture game design patterns such as exploration or balance; experiments in this paper explore how these objective functions and their combinations affect the quality and diversity of the evolved mission graphs.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG). 2016. BibTex

Framing Tension for Game Generation

Phil Lopes, Antonios Liapis and Georgios N. Yannakakis

Abstract: Emotional progression in narratives is carefully structured by human authors to create unexpected and exciting situations, often culminating in a climactic moment. This paper explores how an autonomous computational designer can create frames of tension which guide the procedural creation of levels and their soundscapes in a digital horror game. Using narrative concepts, the autonomous designer can describe an intended experience that the automated level generator must adhere to. The level generator interprets this intent, bound by the possibilities and constraints of the game. The tension of the generated level guides the allocation of sounds in the level, using a crowdsourced model of tension.

in Proceedings of the International Conference on Computational Creativity. 2016. BibTex

Murder Mystery Generation from Open Data

Gabriella A. B. Barros, Antonios Liapis and Julian Togelius

Abstract: This paper describes a system for generating murder mysteries for adventure games, using associations between real-world people mined from Wikipedia articles. A game is seeded with a real-world person, and the game discovers suitable suspects for the murder of a game character instantiated from that person. Moreover, the game discovers characteristics of the suspects which can act as clues for the player to narrow down her search for the killer. The possible suspects and their characteristics are collected from Wikipedia articles and their linked data, while the best combination of suspects and characteristics for a murder mystery is found via evolutionary search. The paper includes an example murder mystery generated by the system revolving around the (hypothetical) death of a contemporary celebrity.

in Proceedings of the International Conference on Computational Creativity. 2016. BibTex

Playing with Data: Procedural Generation of Adventures from Open Data

Gabriella A. B. Barros, Antonios Liapis and Julian Togelius

Abstract: This paper investigates how to generate simple adventure games using open data. We present a system that creates a plot for the player to follow based on associations between Wikipedia articles which link two given topics (in this case people) together. The Wikipedia articles are transformed into game objects (locations, NPCs and items) via constructive algorithms that also rely on geographical information from OpenStreetMaps and visual content from Wikimedia Commons. The different game objects generated in this fashion are linked together via clues which point to one another, while additional false clues and dead ends are added to increase the exploration value of the final adventure game. This information is presented to the user via a set of game screens and images. Inspired by the "Where in the World is Carmen Sandiego?" adventure game, the end result is a generator of chains of followable clues.

in Proceedings of the International Joint Conference of DiGRA and FDG. 2016. BibTex

Exploring the Visual Styles of Arcade Game Assets

Antonios Liapis

Abstract: This paper describes a method for evolving assets for video games based on their visuals properties. Focusing on assets for a space shooter game, a genotype consisting of turtle commands is transformed into a spaceship image composed of human-authored sprite components. Due to constraints on the final spaceships' plausibility, the paper investigates two-population constrained optimization and constrained novelty search methods. A sample of visual styles is tested, each a combination of visual metrics which primarily evaluate balance and shape complexity. Experiments with constrained optimization of a visual style demonstrate that a visually consistent set of spaceships can be generated, while experiments with constrained novelty search demonstrate that several distinct visual styles can be discovered by exploring along select, or all, visual dimensions.

in Proceedings of Evolutionary and Biologically Inspired Music, Sound, Art and Design (EvoMusArt). Springer, 2016. BibTex

Map Sketch Generation as a Service

Antonios Liapis

Abstract: This paper describes the structure of a webservice able to generate simple game levels via constrained evolutionary optimization. The provided webservice allows users to generate playable game levels without needing to understand the underlying process and without having to allocate computational resources for doing so; combined with the highly expressive and customizable generator, a broad range of levels for different genres and purposes can meet many user needs.

in Proceedings of the AIIDE workshop on Experimental AI in Games, 2015. BibTex

Targeting Horror via Level and Soundscape Generation

Phil Lopes, Antonios Liapis, Georgios N Yannakakis

Abstract: Horror games form a peculiar niche within game design paradigms, as they entertain by eliciting negative emotions such as fear and unease to their audience during play. This genre often follows a specific progression of tension culminating at a metaphorical peak, which is defined by the designer. A player's tension is elicited by several facets of the game, including its mechanics, its sounds, and the placement of enemies in its levels. This paper investigates how designers can control and guide the automated generation of levels and their soundscapes by authoring the intended tension of a player traversing them.

in Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference, 2015. BibTex

Refining the Paradigm of Sketching in AI-Based Level Design

Antonios Liapis, Georgios N. Yannakakis

Abstract: This paper describes computational processes which can simulate how human designers sketch and then iteratively refine their work. The paper uses the concept of a map sketch as an initial, low-resolution and low-fidelity prototype of a game level, and suggests how such map sketches can be refined computationally. Different case studies with map sketches of different genres showcase how refinement can be achieved via increasing the resolution of the game level, increasing the fidelity of the function which evaluates it, or a combination of the two. While these case studies use genetic algorithms to automatically generate levels at different degrees of refinement, the general method described in this paper can be used with most procedural generation methods, as well as for AI-assisted design alongside a human creator.

in Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference, 2015. BibTex

Multi-Level Evolution of Shooter Levels

William Cachia, Antonios Liapis, Georgios N. Yannakakis

Abstract: This paper introduces a search-based generative process for first person shooter levels. Genetic algorithms evolve the level's architecture and the placement of powerups and player spawnpoints, generating levels with one floor or two floors. The evaluation of generated levels combines metrics collected from simulations of artificial agents competing in the level and theory-based heuristics targeting general level design patterns. Both simulation-based and theory-driven evaluations target player balance and exploration, while resulting levels emergently exhibit several popular design patters of shooter levels.

in Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference, 2015. BibTex

Sonancia: Sonification of Procedurally Generated Game Levels

Phil Lopes, Antonios Liapis, Georgios N Yannakakis

Abstract: How can creative elements brought from level design effectively be coupled with audio in order to create tense and engaging player experiences? In this paper the above question is posed through the sonification of procedurally generated digital game levels. The paper details some initial approaches and methodologies for achieving this core aim.

in Proceedings of the ICCC workshop on Computational Creativity & Games, 2015. BibTex

A Constructive Approach for the Generation of Underwater Environments

Ryan Abela, Antonios Liapis, Georgios N. Yannakakis

Abstract: This paper introduces Coralize, a library of generators for marine organisms such as corals and sponges. Using constructive algorithms, Coralize can generate stony corals via L-system grammars, soft corals via leaf venation algorithms and sponges via nutrient-based mesh growth. The generative algorithms are parameterizable, allowing a user to adjust the parameters in order to create visually appealing 3D meshes. Such meshes can be used to automatically populate a seabed or reef, in order to create a biologically realistic and aesthetically pleasing underwater environment.

in Proceedings of the FDG workshop on Procedural Content Generation in Games, 2015. BibTex

Data Adventures

Gabriella A. B. Barros, Antonios Liapis, Julian Togelius

Abstract: This paper outlines a system for generating adventure games based on open data, and describes a sketch of the system implementation at its current state. The adventure game genre has been popular for a long time and differs significantly in design priorities from game genres which are commonly addressed in PCG research. In order to create believable and engaging content, we use data from DBpedia to generate the game's non-playable characters locations and plot, and OpenStreetMaps to create the game's levels.

in Proceedings of the FDG workshop on Procedural Content Generation in Games, 2015. BibTex

Procedural Personas as Critics for Dungeon Generation

Antonios Liapis, Christoffer Holmgard, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper introduces a constrained optimization method which uses procedural personas to evaluate the playability and quality of evolved dungeon levels. Procedural personas represent archetypical player behaviors, and their controllers have been evolved to maximize a specific utility which drives their decisions. A "baseline" persona evaluates whether a level is playable by testing if it can survive in a worst-case scenario of the playthrough. On the other hand, a Monster Killer persona or a Treasure Collector persona evaluates playable levels based on how many monsters it can kill or how many treasures it can collect, respectively. Results show that the implemented two-population genetic algorithm discovers playable levels quickly and reliably, while the different personas affect the layout, difficulty level and tactical depth of the generated dungeons.

in Applications of Evolutionary Computation, vol. 9028, LNCS. Springer, 2015. BibTex

Searching for Good and Diverse Game Levels

Mike Preuss, Antonios Liapis, Julian Togelius

Abstract: In procedural content generation, one is often interested in generating a large number of artifacts that are not only of high quality but also diverse, in terms of gameplay, visual impression or some other criterion. We investigate several search-based approaches to creating good and diverse game content, in particular approaches based on evolution strategies with or without diversity preservation mechanisms, novelty search and random search. The content domain is game levels, more precisely map sketches for strategy games, which are meant to be used as suggestions in the Sentient Sketchbook design tool. Several diversity metrics are possible for this type of content: we investigate tile-based, objective-based and visual impression distance. We find that evolution with diversity preservation mechanisms can produce both good and diverse content, but only when using appropriate distance measures. Reversely, we can draw conclusions about the suitability of these distance measures for the domain from the comparison of diversity preserving versus blind restart evolutionary algorithms.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), 2014. BibTex

Computational Game Creativity

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: Computational creativity has traditionally relied on well-controlled, single-faceted and established domains such as visual art, narrative and audio. On the other hand, research on autonomous generation methods for game artifacts has not yet considered the creative capacity of those methods. In this paper we position computer games as the ideal application domain for computational creativity for the unique features they offer: being highly interactive, dynamic and content-intensive software applications. Their multifaceted nature is key in our argumentation as the successful orchestration of different art domains (such as visual art, audio and level architecture) with game mechanics design is a grand challenge for the study of computational creativity in this multidisciplinary domain. Computer games not only challenge computational creativity and provide a creative sandbox for advancing the field but they also offer an opportunity for computational creativity methods to be extensively assessed (via a huge population of gamers) through commercial-standard products of high impact and financial value.

in Proceedings of the Fifth International Conference on Computational Creativity, 2014. BibTex

Characteristics of Generatable Games

Julian Togelius, Mark J. Nelson, Antonios Liapis

Abstract: We address the problem of generating complete games, rather than content for existing games. In particular, we try to answer the question which types of games it would be realistic or even feasible to generate. To begin to answer the question, we first list the different ways we see that games could be generated, and then try to discuss what characterises games that would be comparatively easy or hard to generate. The discussion is structured according to a subset of the characteristics discussed in the book Characteristics of Games by Elias, Garfield and Gutschera.

in Proceedings of the FDG Workshop on Procedural Content Generation, 2014. BibTex

Towards a Generic Method of Evaluating Game Levels

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper addresses the problem of evaluating the quality of game levels across different games and even genres, which is of key importance for making procedural content generation and assisted game design tools more generally applicable. Three game design patterns are identified for having high generality while being easily quantifiable: area control, exploration and balance. Formulas for measuring the extent to which a level includes these concepts are proposed, and evaluation functions are derived for levels in two different game genres: multiplayer strategy game maps and single-player roguelike dungeons. To illustrate the impact of these evaluation functions, and the similarity of impact across domains, sets of levels for each function are generated using a constrained genetic algorithm. The proposed measures can easily be extended to other game genres.

in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2013. BibTex

Adaptive Game Level Creation through Rank-based Interactive Evolution

Antonios Liapis, Hector P. Martinez, Julian Togelius, Georgios N. Yannakakis

Abstract: This paper introduces Rank-based Interactive Evolution (RIE) which is an alternative to interactive evolution driven by computational models of user preferences to generate personalized content. In RIE, the computational models are adapted to the preferences of users which, in turn, are used as fitness functions for the optimization of the generated content. The preference models are built via ranking-based preference learning, while the content is generated via evolutionary search. The proposed method is evaluated on the creation of strategy game maps, and its performance is tested using artificial agents. Results suggest that RIE is both faster and more robust than standard interactive evolution and outperforms other state-of-the-art interactive evolution approaches.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), 2013. BibTex

Transforming Exploratory Creativity with DeLeNoX

Antonios Liapis, Hector P. Martinez, Julian Togelius, Georgios N. Yannakakis

Abstract: We introduce DeLeNoX (Deep Learning Novelty Explorer), a system that autonomously creates artifacts in constrained spaces according to its own evolving interestingness criterion. DeLeNoX proceeds in alternating phases of exploration and transformation. In the exploration phases, a version of novelty search augmented with constraint handling searches for maximally diverse artifacts using a given distance function. In the transformation phases, a deep learning autoencoder learns to compress the variation between the found artifacts into a lower-dimensional space. The newly trained encoder is then used as the basis for a new distance function, transforming the criteria for the next exploration phase. In the current paper, we apply DeLeNoX to the creation of spaceships suitable for use in two-dimensional arcade-style computer games, a representative problem in procedural content generation in games. We also situate DeLeNoX in relation to the distinction between exploratory and transformational creativity, and in relation to Schmidhuber's theory of creativity through the drive for compression progress.

in Proceedings of the Fourth International Conference on Computational Creativity, 2013, pp. 56-63. BibTex

Generating Map Sketches for Strategy Games

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: How can a human and an algorithm productively collaborate on generating game content? In this paper, we try to answer this question in the context of generating balanced and interesting low-resolution sketches for game levels. We introduce six important criteria for successful strategy game maps, and present map sketches optimized for one or more of these criteria via a constrained evolutionary algorithm. The sketch-based map representation and the computationally lightweight evaluation methods are geared towards the integration of the evolutionary algorithm within a mixed-initiative tool, allowing for the co-creation of game content by a human and an artificial designer.

in Proceedings of Applications of Evolutionary Computation, vol. 7835, LNCS. Springer, 2013, pp. 264-273. BibTex

Optimizing Visual Properties of Game Content through Neuroevolution

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper presents a search-based approach to generating game content that satisfies both gameplay requirements and user-expressed aesthetic criteria. Using evolutionary constraint satisfaction, we search for spaceships (for a space combat game) represented as compositional pattern-producing networks. While the gameplay requirements are satisfied by ad-hoc defined constraints, the aesthetic evaluation function can also be informed by human aesthetic judgement. This is achieved using indirect interactive evolution, where an evaluation function re-weights an array of aesthetic criteria based on the choices of a human player. Early results show that we can create aesthetically diverse and interesting spaceships while retaining in-game functionality.

in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2011. BibTex

Neuroevolutionary Constrained Optimization for Content Creation

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper presents a constraint-based procedural content generation (PCG) framework used for the creation of novel and high-performing content. Specifically, we examine the efficiency of the framework for the creation of spaceship design (hull shape and spaceship attributes such as weapon and thruster types and topologies) independently of game physics and steering strategies. According to the proposed framework, the designer picks a set of requirements for the spaceship that a constrained optimizer attempts to satisfy. The constraint satisfaction approach followed is based on neuroevolution; Compositional Pattern-Producing Networks (CPPNs) which represent the spaceship's design are trained via a constrain-based evolutionary algorithm. Results obtained in a number of evolutionary runs using a set of constraints and objectives show that the generated spaceships perform well in movement, combat and survival tasks and are also visually appealing.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), 2011, pp. 71-78. BibTex