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.

Design Space Exploration of Shell Structures Using Quality Diversity Algorithms

Konstantinos Sfikas, Antonios Liapis, Joel Hilmersson, Jeg Dudley, Edoardo Tibuzzi and Georgios N. Yannakakis

Abstract: Computer-aided optimization algorithms in structural engineering have historically focused on the structural performance of generated forms, often resulting in the selection of a single 'optimal' solution. However, diversity of generated solutions is desirable when those solutions are shown to a human user to choose from. Quality-Diversity (QD) search is an emerging field of Evolutionary Computation which can automate the exploration of the solution space in engineering problems. QD algorithms, such as MAP-Elites, operate by maintaining and expanding an archive of diverse solutions, optimising for quality in local niches of a multidimensional design space. The generated archive of solutions can help engineers gain a better overview of the solution space, illuminating which designs are possible and their trade-offs. In this paper we apply Quality Diversity search to the problem of designing shell structures. Since the design of shell structures comes with physical constraints, we leverage a constrained optimization variant of the MAP-Elites algorithm, FI-MAP-Elites. We implement our proposed methodology within the Rhino/Grasshopper environment and use the Karamba Finite Element Analysis solver for all structural engineering calculations. We test our method on case studies of parametric models of shell structures that feature varying complexity. Our experiments investigate the algorithm's ability to illuminate the solution space and generate feasible and high-quality solutions.

in Proceedings of the International Association for Shell and Spatial Structures Symposium, 2023. BibTex

A General-Purpose Expressive Algorithm for Room-based Environments

Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper presents a generative architecture for general-purpose room layouts that can be treated as geometric definitions of dungeons, mansions, shooter levels and more. The motivation behind this work is to provide a design tool for virtual environments that combines aspects of controllability, expressivity and generality. Towards that end, a two-tier level representation is realized, with a graph-based design specification constraining and guiding the generated geometries, facilitated by constrained evolutionary search. Expressivity is secured through quality-diversity search which can provide the designer with a broad variety of level layouts to choose from. Finally, the generator is general-purpose as it can produce layouts based on different types of static grid structures or as free-form, curved structures through an adaptive Voronoi diagram that is evolved along with the level itself. The method is tested on a variety of design specifications and grid types, and results show that even with complex design constraints or malleable grids the algorithm can produce a broad variety of levels.

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

Open-Ended Evolution for Minecraft Building Generation

Matthew Barthet, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper proposes a procedural content generator which evolves Minecraft buildings according to an open-ended and intrinsic definition of novelty. To realize this goal we evaluate individuals' novelty in the latent space using a 3D autoencoder, and alternate between phases of exploration and transformation. During exploration the system evolves multiple populations of CPPNs through CPPN-NEAT and constrained novelty search in the latent space (defined by the current autoencoder). We apply a set of repair and constraint functions to ensure candidates adhere to basic structural rules and constraints during evolution. During transformation, we reshape the boundaries of the latent space to identify new interesting areas of the solution space by retraining the autoencoder with novel content. In this study we evaluate five different approaches for training the autoencoder during transformation and its impact on populations' quality and diversity during evolution. Our results show that by retraining the autoencoder we can achieve better open-ended complexity compared to a static model, which is further improved when retraining using larger datasets of individuals with diverse complexities.

in IEEE Transactions on Games 15(4), 2022. BibTex

Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem

Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis

Abstract: A core challenge of evolutionary search is the need to balance between exploration of the search space and exploitation of highly fit regions. Quality-diversity search has explicitly walked this tightrope between a population's diversity and its quality. This paper extends a popular quality-diversity search algorithm, MAP-Elites, by treating the selection of parents as a multi-armed bandit problem. Using variations of the upper-confidence bound to select parents from under-explored but potentially rewarding areas of the search space can accelerate the discovery of new regions as well as improve its archive's total quality. The paper tests an indirect measure of quality for parent selection: the survival rate of a parent's offspring. Results show that maintaining a balance between exploration and exploitation leads to the most diverse and high-quality set of solutions in three different testbeds.

in Proceedings of the Genetic and Evolutionary Computation Conference, 2021. BibTex

ARCH-Elites: Quality-Diversity for Urban Design

Theodoros Galanos, Antonios Liapis, Georgios N. Yannakakis and Reinhard Koenig

Abstract: This paper introduces ARCH-Elites, a MAP-Elites implementation that can reconfigure large-scale urban layouts at real-world locations via a pre-trained surrogate model instead of costly simulations. In a series of experiments, we generate novel urban designs for two real-world locations in Boston, Massachusetts. Combining the exploration of a possibility space with real-time performance evaluation creates a powerful new paradigm for architectural generative design that can extract and articulate design intelligence.

in Proceedings of the Genetic and Evolutionary Computation Conference, 2021. BibTex

10 Years of the PCG workshop: Past and Future Trends

Antonios Liapis

Abstract: As of 2020, the international workshop on Procedural Content Generation enters its second decade. The annual workshop, hosted by the international conference on the Foundations of Digital Games, has collected a corpus of 95 papers published in its first 10 years. This paper provides an overview of the workshop's activities and surveys the prevalent research topics emerging over the years.

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

Tabletop Roleplaying Games as Procedural Content Generators

Matthew Guzdial, Devi Acharya, Max Kreminski, Michael Cook, Mirjam Eladhari, Antonios Liapis and Anne Sullivan

Abstract: Tabletop roleplaying games (TTRPGs) and procedural content generators can both be understood as systems of rules for producing content. In this paper, we argue that TTRPG design can usefully be viewed as procedural content generator design. We present several case studies linking key concepts from PCG research – including possibility spaces, expressive range analysis, and generative pipelines – to key concepts in TTRPG design. We then discuss the implications of these relationships and suggest directions for future work uniting research in TTRPGs and PCG.

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

Artificial Intelligence for Designing Games

Antonios Liapis

Abstract: Making a game requires a diverse set of skills and talents: visual design, sound design, level design and narrative design require developers to be creative within their own domain but also to consider how their creations impact other facets of the game. Since games are interactive media, however, players also exercise their own creativity in order to overcome challenges introduced by the game's designers or by other players in multi-player settings. This chapter will analyze games under the prism of the six facets of creativity which go into the play experience: visuals, audio, narrative, levels, rules, and gameplay. Important examples of human creativity in commercial games will be highlighted for each facet, as well as how artificial intelligence has been applied to generate content for each facet. The chapter concludes with a discussion on how an artificially intelligent system can facilitate the collaboration of different generators, and possibly human designers and artists.

In The Handbook of Artificial Intelligence and the Arts, Penousal Machado, Juan Romero, and Gary Greenfield (Eds.). Springer, 2021. (in print) BibTex

A Multi-Faceted Surrogate Model for Search-based Procedural Content Generation

Daniel Karavolos, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper proposes a framework for the procedural generation of level and ruleset components of games via a surrogate model that assesses their quality and complementarity. The surrogate model combines level and ruleset elements as input and gameplay outcomes as output, thus constructing a mapping between three different facets of games. Using this model as a surrogate for expensive gameplay simulations, a search-based generator can adapt content towards a target gameplay outcome. Using a shooter game as the target domain, this paper explores how parameters of the players' character classes can be mapped to both the level's representation and the gameplay outcomes of balance and match duration. The surrogate model is built on a deep learning architecture, trained on a large corpus of randomly generated sets of levels, classes and simulations from gameplaying agents. Results show that a search-based generative approach can adapt character classes, levels, or both towards designer-specified targets. The model can thus act as a design assistant or be integrated in a mixed-initiative tool. Most importantly, the combination of three game facets into the model allows it to identify the synergies between levels, rules and gameplay and orchestrate the generation of the former two towards desired outcomes.

in Transactions on Games, vol. 13, no 1, pp. 11-22, 2021. BibTex

Procedural Content Generation through Quality-Diversity

Daniele Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius and Georgios N. Yannakakis

Abstract: Quality-diversity (QD) algorithms search for a set of good solutions which cover a space as defined by behavior metrics. This simultaneous focus on quality and diversity with explicit metrics sets QD algorithms apart from standard single- and multi-objective evolutionary algorithms, as well as from diversity preservation approaches such as niching. These properties open up new avenues for artificial intelligence in games, in particular for procedural content generation. Creating multiple systematically varying solutions allows new approaches to creative human-AI interaction as well as adaptivity. In the last few years, a handful of applications of QD to procedural content generation and game playing have been proposed; we discuss these and propose challenges for future work.

in Proceedings of the IEEE Conference on Games, 2019. BibTex

Two-step Constructive Approaches for Dungeon Generation

Michael Cerny Green, Ahmed Khalifa, Athoug Alsoughayer, Divyesh Surana, Antonios Liapis and Julian Togelius

Abstract: This paper presents a two-step generative approach for creating dungeons in the rogue-like puzzle game MiniDungeons 2. Generation is split into two steps, initially producing the architectural layout of the level as its walls and floor tiles, and then furnishing it with game objects representing the player's start and goal position, challenges and rewards. Three layout creators and three furnishers are introduced in this paper, which can be combined in different ways in the two-step generative process for producing diverse dungeons levels. Layout creators generate the floors and walls of a level, while furnishers populate it with monsters, traps, and treasures. We test the generated levels on several expressivity measures, and in simulations with procedural persona agents.

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

Fusing Level and Ruleset Features for Multimodal Learning of Gameplay Outcomes

Antonios Liapis, Daniel Karavolos, Konstantinos Makantasis, Konstantinos Sfikas and Georgios N. Yannakakis

Abstract: Which features of a game influence the dynamics of players interacting with it? Can a level's architecture change the balance between two competing players, or is it mainly determined by the character classes and roles that players choose before the game starts? This paper assesses how quantifiable gameplay outcomes such as score, duration and features of the heatmap can be predicted from different facets of the initial game state, specifically the architecture of the level and the character classes of the players. Experiments in this paper explore how different representations of a level and class parameters in a shooter game affect a deep learning model which attempts to predict gameplay outcomes in a large corpus of simulated matches. findings in this paper indicate that a few features of the ruleset (i.e. character class parameters) are the main drivers for the model's accuracy in all tested gameplay outcomes, but the levels (especially when processed) can augment the model.

in Proceedings of the IEEE Conference on Games, 2019. BibTex

Deciphering Generated Symbols as a Game Mechanic: The Design of Alien Transmission

Antonios Liapis

Abstract: This article describes the gameplay and the design rationale of the Alien Transmission game, where generated symbols are used as a form of communication between players in a co-operative board game. The symbols are abstract black-and-white blobs, generated by the computer via cellular automata, but players must use these symbols to convey information regarding upcoming threats. As gameplay progresses, symbols gain a meaning due to their visual associations and past gameplay experiences. The work highlights how procedural content generation can be elevated into a mechanic rather than used to randomize the initial game state.

in Seeds: The Procjam Zine 3. 2018. BibTex

Real-world Data as a Seed

Antonios Liapis

Abstract: This article proposes the use of real-world data for game generation, and describes the design priorities of DATA Agent as an example of data-driven game generation. Due to the use (and transformation) of real-world data, DATA Agent weaves a narrative of a time-travelling doppelganger murderer and a time-traveling detective intent on catching the murder in a lie about its presumed identity. DATA Agent shows how real-world data from Wikipedia, Wikimedia Commons and OpenStreetMap can be transformed into NPCs, levels, plot points and exposition dialog.

in Seeds: The Procjam Zine 3. 2018. BibTex

Orchestrating Game Generation

Antonios Liapis, Georgios N. Yannakakis, Mark J. Nelson, Mike Preuss and Rafael Bidarra

Abstract: The design process is often characterized by and realized through the iterative steps of evaluation and refinement. When the process is based on a single creative domain such as visual art or audio production, designers primarily take inspiration from work within their domain and refine it based on their own intuitions or feedback from an audience of experts from within the same domain. What happens, however, when the creative process involves more than one creative domain such as in a digital game? How should the different domains influence each other so that the final outcome achieves a harmonized and fruitful communication across domains? How can a computational process orchestrate the various computational creators of the corresponding domains so that the final game has the desired functional and aesthetic characteristics? To address these questions, this article identifies game facet orchestration as the central challenge for AI-based game generation, discusses its dimensions and reviews research in automated game generation that has aimed to tackle it. In particular, we identify the different creative facets of games, we propose how orchestration can be facilitated in a top-down or bottom-up fashion, we review indicative preliminary examples of orchestration, and we conclude by discussing the open questions and challenges ahead.

in Transactions on Games, vol. 11, no 1, pp. 48-68, 2019. BibTex

DATA Agent

Michael Cerny Green, Gabriella A. B. Barros, Antonios Liapis and Julian Togelius

Abstract: This paper introduces DATA Agent, a system which creates murder mystery adventures from open data. In the game, the player takes on the role of a detective tasked with finding the culprit of a murder. All characters, places, and items in DATA Agent games are generated using open data as source content. The paper discusses the general game design and user interface of DATA Agent, and provides details on the generative algorithms which transform linked data into different game objects. findings from a user study with 30 participants playing through two games of DATA Agent show that the game is easy and fun to play, and that the mysteries it generates are straightforward to solve.

in Proceedings of the 13th Conference on the Foundations of Digital Games, 2018. BibTex

Pairing Character Classes in a Deathmatch Shooter Game via a Deep-Learning Surrogate Model

Daniel Karavolos, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper introduces a surrogate model of gameplay that learns the mapping between different game facets, and applies it to a generative system which designs new content in one of these facets. Focusing on the shooter game genre, the paper explores how deep learning can help build a model which combines the game level structure and the game's character class parameters as input and the gameplay outcomes as output. The model is trained on a large corpus of game data from simulations with artificial agents in random sets of levels and class parameters. The model is then used to generate classes for specific levels and for a desired game outcome, such as balanced matches of short duration. findings in this paper show that the system can be expressive and can generate classes for both computer generated and human authored levels.

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

Using a Surrogate Model of Gameplay for Automated Level Design

Daniel Karavolos, Antonios Liapis and Georgios N. Yannakakis

Abstract: This paper describes how a surrogate model of the interrelations between different types of content in the same game can be used for level generation. Specifically, the model associates level structure and game rules with gameplay outcomes in a shooter game. We use a deep learning approach to train a model on simulated playthroughs of two-player deathmatch games, in diverse levels and with different character classes per player. findings in this paper show that the model can predict the duration and winner of the match given a top-down map of the level and the parameters of the two players' character classes. With this surrogate model in place, we investigate which level structures would result in a balanced match of short, medium or long duration for a given set of character classes. Using evolutionary computation, we are able to discover levels which improve the balance between different classes. This opens up potential applications for a designer tool which can adapt a human authored map to fit the designer's desired gameplay outcomes, taking account of the game's rules.

in Proceedings of the IEEE Conference on Computational Intelligence and Games, 2018. BibTex

Data-driven Design: A Case for Maximalist Game Design

Gabriella A. B. Barros, Michael Cerny Green, Antonios Liapis and Julian Togelius

Abstract: Maximalism in art refers to drawing on and combining multiple different sources for art creation, embracing the resulting collisions and heterogeneity. This paper discusses the use of maximalism in game design and particularly in data games, which are games that are generated partly based on open data. Using Data Adventures, a series of generators that create adventure games from data sources such as Wikipedia and OpenStreetMap, as a lens we explore several tradeoffs and issues in maximalist game design. This includes the tension between transformation and fidelity, between decorative and functional content, and legal and ethical issues resulting from this type of generativity. This paper sketches out the design space of maximalist data-driven games, a design space that is mostly unexplored.

in Proceedings of the International Conference of Computational Creativity, 2018. BibTex

Who Killed Albert Einstein? From Open Data to Murder Mystery Games

Gabriella A. B. Barros, Michael Cerny Green, Antonios Liapis and Julian Togelius

Abstract: This paper presents a framework for generating adventure games from open data. Focusing on the murder mystery type of adventure games, the generator is able to transform open data from Wikipedia articles, OpenStreetMap and images from Wikimedia Commons into WikiMysteries. Every WikiMystery game revolves around the murder of a person with a Wikipedia article, and populates the game with suspects who must be arrested by the player if guilty of the murder or absolved if innocent. Starting from only one person as the victim, an extensive generative pipeline finds suspects, their alibis, and paths connecting them from open data, transforms open data into cities, buildings, non-player characters, locks and keys and dialog options. The paper describes in detail each generative step, provides a specific playthrough of one WikiMystery where Albert Einstein is murdered, and evaluates the outcomes of games generated for the 100 most influential people of the 20th century.

in Transactions on Games, vol. 11, no 1, pp. 79-89, 2019. BibTex

Piecemeal Evolution of a first Person Shooter Level

Antonios Liapis

Abstract: This paper describes an iterative process for generating multi-story shooter game levels by means of interlocking rooms evolved individually. The process is highly controllable by a human designer who can specify the entrances to this room as well as its size, its distribution of game objects and its architectural patterns. The small size of each room allows for computationally fast evaluations of several level qualities, but these rooms can be combined into a much larger shooter game level. Each room has two floors and is generated iteratively, with two stages of evolution and two stages of constructive post-processing. Experiments in generating an arena-based level for two teams spawning in different rooms demonstrate that the placement and allocation of entrances on each floor have a strong effect on the patterns of the final level.

in Applications of Evolutionary Computation. Springer, 2018. BibTex

Recomposing the Pokemon Color Palette

Antonios Liapis

Abstract: In digital games, the visual representation of game assets such as avatars or game levels can hint at their purpose, in-game use and strengths. In the Pokemon games, this is particularly prevalent with the namesake creatures' type and the colors in their sprites. To win these games, players choose Pokemon of the right type to counter their opponents' strengths; this makes the visual identification of type important. In this paper, computational intelligence methods are used to learn a mapping between a Pokemon's type and its in-game sprite, colors and shape. This mapping can be useful for a designer attempting to create new Pokemon of certain types. In this paper, instead, evolutionary algorithms are used to create new Pokemon sprites by using existing color information but recombining it into a new palette. Results show that evolution can be applied to Pokemon sprites on a local or global scale, to exert different degrees of designer control and to achieve different goals.

in Applications of Evolutionary Computation. Springer, 2018. BibTex

Mapping Chess Aesthetics onto Procedurally Generated Chess-like Games

Jakub Kowalski, Antonios Liapis and Lukasz Zarczynski

Abstract: Variants of chess have been generated in many forms and for several reasons, such as testbeds for artificial intelligence research in general game playing. This paper uses the visual properties of chess pieces as inspiration to generate new shapes for other chess-like games, targeting specific visual properties which allude to the pieces' in-game function. The proposed method uses similarity measures in terms of pieces' strategic role and movement in a game to identify the new pieces' closest representatives in chess. Evolution then attempts to minimize the distance from chess pieces' visual properties, resulting in new shapes which combine one or more chess pieces' visual identities. While experiments in this paper focus on two chess-like games from previous publications, the method can be used for broader generation of game visuals based on functional similarities of components to known, popular games.

in Applications of Evolutionary Computation. Springer, 2018. BibTex

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, Noor Shaker, Julian Togelius and Mark J. Nelson (Eds.). 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, Noor Shaker, Julian Togelius and Mark J. Nelson (Eds.). Springer, 2016. BibTex

Sonancia: a Multi-Faceted Generator for Horror

Phil Lopes, Antonios Liapis and Georgios N. Yannakakis

Abstract: Fear and tension are the primary emotions elicited by the genre of horror, a peculiar characteristic for media whose sole purpose is to entertain. The audience is often lead into tense and fearful situations, meticulously crafted by the authors using a narrative progression and a combination of visual and auditory stimuli. This paper presents a playable demonstration of the Sonancia system, a multi-faceted content generator for 3D horror games, with the capability of generating levels and their corresponding soundscapes. Designers can also guide the level generation process, by defining an intended progression of tension, which the level generator and sonification will adhere to.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG). 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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