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
Visualisation of all feasible solutions found in a single run of the FI-MAP-Elites algorithm on a complex test case which is comparable to real-world engineering problems. Meshes in yellow have a higher fitness (i.e. lower elastic energy). The two dimensions of diversity are height deviations of the four external arches (BC1), and height deviations of control points near the center of the vault (BC2).
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
Examples of different level layouts for design specifications with 8 rooms.
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
The exploration phase performs novelty search on the latent space by encoding the Minecraft buildings that are being evolved.
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
Feature maps at different stages of evolution for the 6D Rastrigin function, showing the different coverage and fitness score of elites when selecting parents uniformly (R), based on the curiosity score (C), or based on a UCB formula that balances exploration and exploitation (U).
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
Evolution in ARCH-Elites: A geographic location is selected by the user (a) and building geometries and metadata are extracted (b). The location is then split into cells (c); two cells are selected and geometric blending takes place (d).
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
A word cloud of keywords in published papers at the PCG workshop. The size is proportionate to the number of appearances in published papers. Note that the generic keywords "procedural content generation", "procedural generation", "procedural content" and "PCG" have been omitted.
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
A fruitful void diagram of the tabletop game Dogs in the Vineyard, showing how mechanics feed into one another to keep play "in orbit" around an unsystematized central theme. figure based on a figure in Vincent Baker's blog.
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
Using a human-made level as a seed, multi-objective evolution based on a surrogate model of quality manages to improve the level towards longer matches with a balanced match outcome between a Scout (as Player 1) and a Heavy (as Player 2).
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
Cases of PCG through Quality Diversity.
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
Levels for MiniDungeons 2 generated by different combinations of layout creators (which generate the wall/floor architecture) and furnishers (which distribute game objects).
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
Explaining the parts of a level which most activate the win ratio prediction for the player in the bottom-left base. Left activation map is a matchup between a Sniper class (bottom-left base) and a Scout class (top-right base); right activation map is a matchup between a Heavy class (bottom-left base) and a Scout class (top-right base).
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
Generated symbols used as cards by the lookout player in the Alien Transmission boardgame, in order to communicate threats and counter-actions to teammates.
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
Screenshot of the DATA Agent game, where a player tries to identify the location of a murder suspect.
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
The key questions of facet orchestration: where does the inspiration come from, what is orchestrated and how, and who is the intended audience?
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
Screenshot of the user interface of the DATA Agent game: in this example game, Albert Einstein has been murdered by a time-travelling doppelganger, and the suspects are physicists Walter Bothe, Lise Meitner and Max von Laue. Here, the player interrogates Walter Bothe, checking whether the facts collected from other sources match the facts uttered by the suspect.
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
Trends of a player's class parameters, evolved towards longer or shorter matches. Results are averaged from evolutionary runs on 20 different levels.
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
Initial maps (generated: top left, designed: top right) and their adapted versions (bottom) via surrogate-based evolution. The bottom left map is evolved towards balanced, medium duration matches with player 1 as a Heavy and player 2 as a Scout. The bottom right map is evolved towards balanced, long duration matches with player 1 as a Scout and player 2 as a Pyro.
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
Examples of games along the dimensions of data versus game fidelity and functional versus decorative role.
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
flowchart of WikiMystery and its open data sources.
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
Generative pipeline, in multiple evolutionary and post-processing steps, starting from a designer specification of an arena-type room with 6 entrances (4 on the bottom floor and 2 on the top floor).
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
Differences between the original color palette (top) and the evolved color palette (bottom), which removes the water type from all 141 water Pokemon in the dataset, assigning them instead to different types (and dual types).
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
Indicative evolved pieces targeting the original chess visuals. The average piece (darker background) is a stepping stone targeted in the first evolutionary step, and it is the starting seed for individual evolution towards each individual piece.
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
Architecture of the convolutional neural network that predicts whether a shooter game matchup will be balanced based on the visual layout of the level and the parameters of two teams' weapons.
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
The generative pipeline, with the dungeon sketch evolved first. Each tile on the dungeon sketch, and its connectivity with adjacent tiles, is used to define the embryogeny, constraints and objectives of each segment which is evolved piecemeal and recombined into the full dungeon.
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
Gameplay footage of a Sonancia level generated and sonified by a generative process.
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
An outline of the vision for game generation from semantic information in game repositories.
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
A 'mine-laying' weapon evolved via constrained surprise search.
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
An evolved mission graph (left) and the dungeon it creates in the Dwarf Quest game (right).
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
The creative process of the Sonancia system: a randomly selected tension frame is used to evaluate an evolving tension progression, which guides the evolution of a level generator which attempts to place monsters and items to match the tension curve. finally, the evolved level and its derived tension curve are used to deterministically allocate sounds based on a crowdsourced model of aural tension.
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
Screenshot of the 'house of Bobby Andonov' location with the NPC Bobby Andonov. In the generated game, this NPC is a suspect for the murder of the NPC Justin Bieber.
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
User interface of the building screen, showing Albert Einstein's house: the player can ask for directions from Albert Einstein to find Margaret Thatcher.
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
Spaceship styles in different colors, evolved by several fi-2pop genetic algorithms optimizing different style objectives.
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
Map sketch result from the online generator, along with its detailed evaluations.
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
Horror levels of different sizes, evolved according to a linearly increasing tension model. Levels contain monsters (green triangles), the main quest item (blue square) and subquest items (pink circles); the player starts the level from the darker room and must reach the main quest item to finish the level.
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
Iterative refinement of map sketches for first person shooter games: the rough map sketch of the first floor (left) instantiates a second floor (middle) via a constructive method, which is used as a seed for evolution of both levels, adding team spawnpoints, healthpacks and weapon pickups (right).
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
Evolved two-floor first person shooter level, in the Cube 2 environment.
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
The critical path of a player traversing a haunted mansion from a starting room to a final room (left image) is used as the objective of a level generation module but also as input to a sonification module which adds background music to each room (right image).
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
Marine sessile organisms generated by the Coralize tool: hard corals (left), soft corals (top right) and sponges (bottom right).
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
One of the possible paths between Alan Turing and Nikola Tesla, discovered via the DBpedia crawler. Each of the elements on the path is transformed into a game asset (a non-player character, a location, or a clue) that the player can interact with in the search for Nicola Tesla.
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
Best evolved MiniDungeons levels when maximizing the utility of a monster killer persona and a treasure collector persona (left) and when maximizing the uncertainty in utilities of these personas (right).
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
Strategy game map sketches evolved via NEA 2 using visual impression for niching (top row), via restart-ES with CMA-ES restart criteria (middle row), and via novelty search based on visual impression distance (bottom row).
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
Map sketches for different game genres (top) and the complete maps they generate (bottom). The map sketches were evolved using heuristics of balance, area control and exploration.
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
User interface for ranking maps according to preference. Rank-based interactive evolution is then applied to create new, personalized content.
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
Progressive complexification of generated spaceships trained with new features in every iteration.
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
Map sketches optimized for one objective: resource safety, safe area, exploration, resource safety balance, safe area balance, exploration balance (from left to right).
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
Different methods for calculating aesthetic metrics on the balance (first and second images), alignment (third image) and containment (fourth image) of spaceship hulls.
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
Evolving spaceships performing simulations which evaluate their movement (left) and survival (right).
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