Constrained Optimization
Unlike other forms of art, games are bound by playability concerns. Game content is often divided between playable and unplayable. My research focuses on satisfying playability constraints either via objective-driven search or via novelty search.
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
Controllable Exploration of a Design Space via Interactive Quality Diversity
Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis
Behavioral space exploration for the baseline MAP-Elites (bottom row) and UC-ME, for the first 5 user selections. Their shared color scale (bottom) is the feasible quality. The top row shows coverage differences: red cells are discovered only by the baseline, blue cells are discovered only by UC-ME and gray cells are common.
Abstract: This paper introduces a user-driven evolutionary algorithm based on Quality Diversity (QD) search. During a design session, the user iteratively selects among presented alternatives and their selections affect the upcoming results. We implement a variation of the MAP-Elites algorithm where the presented alternatives are sampled from a small region (window) of the behavioral space. After a user selection, the window is centered on the selected individual’s behavior characterization, evolution selects parents from within this window to produce offspring, and new alternatives are sampled. Essentially we define an adaptive system of local QD search, where the user’s selections guide the search towards specific regions of the behavioral space. The system is tested on the generation of architectural layouts, a constrained optimization task, leveraging QD search through a two-archive approach.
in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 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
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
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
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
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
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
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
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
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
Sentient Sketchbook: Computer-Aided Game Level Authoring
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
User interface of Sentient Sketchbook, with the user working on the map sketch canvas (left) and the computer generating suggestions in real-time (far right).
Abstract: This paper introduces the Sentient Sketchbook, a tool which supports a designer in the creation of game levels. Using map sketches to alleviate designer effort, the tool automates playability checks and evaluations and visualizes significant gameplay properties. This paper also introduces constrained novelty search via a two-population paradigm for generating, in real-time, alternatives to the author's design and evaluates its potential against current approaches. The paper concludes with a small-scale user study in which industry experts interact with the Sentient Sketchbook to design game levels. Results demonstrate the tool's potential and provide directions for its improvement.
in Proceedings of the 8th Conference on the Foundations of Digital Games, 2013, pp. 213-220. 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
Adapting Models of Visual Aesthetics for Personalized Content Creation
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
User interface for interactively evolving spaceship hulls.
Abstract: This paper introduces a search-based approach to personalized content generation with respect to visual aesthetics. The approach is based on a two-step adaptation procedure where (1) the evaluation function that characterizes the content is adjusted to match the visual aesthetics of users and (2) the content itself is optimized based on the personalized evaluation function. To test the efficacy of the approach we design fitness functions based on universal properties of visual perception, inspired by psychological and neurobiological research. Using these visual properties we generate aesthetically pleasing 2D game spaceships via neuroevolutionary constrained optimization and evaluate the impact of the designed visual properties on the generated spaceships. The offline generated spaceships are used as the initial population of an interactive evolution experiment in which players are asked to choose spaceships according to their visual taste: the impact of the various visual properties is adjusted based on player preferences and new content is generated online based on the updated computational model of visual aesthetics of the player. Results are presented which show the potential of the approach in generating content which is based on subjective criteria of visual aesthetics.
IEEE Transactions on Computational Intelligence and AI in Games 4(3), 2012, pp. 213-228. 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