Search-Based Procedural Content Generation: A Taxonomy and Survey
---
paper_title: Texturing and Modeling: A Procedural Approach

paper_content:

From the Publisher: ::: This the classic text/tutorial/reference introducing and defining the procedural approach to texturing and modeling and computer graphics in general. This Second Edition is completely revised and updated to the current computer graphics marketplace. It contains a toolbox of procedures upon which programmers can build a library of textures and objects, and includes extensive explanations of how these functions work and how to design new functions. New chapters include: Cellular Texture Generation, Volumetric Cloud Modeling with Implicit Functions, Interacting with Virtual Actors, and Rendering with Adaptive Level of Detail.
---
paper_title: Computational intelligence in games

paper_content:

This invention relates to the stoichiometric condensation of substituted phenylacetonitriles with dibasic carboxylic anhydrides. The resulting cyano-keto-acids are obtained in good yield and can be used to prepare biologically active 2-aryl-1,3-cyclohexanediones without elaborate purification.
---
paper_title: Integrating procedural generation and manual editing of virtual worlds

paper_content:

Because of the increasing detail and size of virtual worlds, designers are more and more urged to consider employing procedural methods to alleviate part of their modeling work. However, such methods are often unintuitive to use, difficult to integrate, and provide little user control, making their application far from straightforward. In our declarative modeling approach, designers are provided with a more productive and simplified virtual world modeling workflow that matches better with their iterative way of working. Using interactive procedural sketching, they can quickly layout a virtual world, while having proper user control at the level of large terrain features. However, in practice, designers require a finer level of control. Integrating procedural techniques with manual editing in an iterative modeling workflow is an important topic that has remained relatively unaddressed until now. This paper identifies challenges of this integration and discusses approaches to combine these methods in such a way that designers can freely mix them, while the virtual world model is kept consistent during all modifications. We conclude that overcoming the challenges mentioned, for example in a declarative modeling context, is instrumental to achieve the much desired adoption of procedural modeling in mainstream virtual world modeling.
---
paper_title: AI for Game Developers

paper_content:

Advances in 3D visualization and physics-based simulation technology make it possible for game developers to create compelling, visually immersive gaming environments that were only dreamed of years ago. But today's game players have grown in sophistication along with the games they play. It's no longer enough to wow your players with dazzling graphics; the next step in creating even more immersive games is improved artificial intelligence, or AI. Fortunately, advanced AI game techniques are within the grasp of every game developer--not just those who dedicate their careers to AI. If you're new to game programming or if you're an experienced game programmer who needs to get up to speed quickly on AI techniques, you'll find AI for Game Developers to be the perfect starting point for understanding and applying AI techniques to your games. Written for the novice AI programmer, AI for Game Developers introduces you to techniques such as finite state machines, fuzzy logic, neural networks, and many others, in straightforward, easy-to-understand language, supported with code samples throughout the entire book (written in C/C++). From basic techniques such as chasing and evading, pattern movement, and flocking to genetic algorithms, the book presents a mix of deterministic (traditional) and non-deterministic (newer) AI techniques aimed squarely at beginners AI developers. Other topics covered in the book include: Potential function based movements: a technique that handles chasing, evading swarming, and collision avoidance simultaneouslyBasic pathfinding and waypoints, including an entire chapter devoted to the A* pathfinding algorithmAI scriptingRule-based AI: learn about variants other than fuzzy logic and finite state machinesBasic probabilityBayesian techniques Unlike other books on the subject, AI for Game Developers doesn't attempt to cover every aspect of game AI, but to provide you with usable, advanced techniques you can apply to your games right now. If you've wanted to use AI to extend the play-life of your games, make them more challenging, and most importantly, make them more fun, then this book is for you.
---
paper_title: Automatic generation and evaluation of recombination games

paper_content:

Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.
---
paper_title: Automatic generation and evaluation of recombination games

paper_content:

Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.
---
paper_title: Picbreeder: evolving pictures collaboratively online

paper_content:

Picbreeder is an online service that allows users to collaboratively evolve images. Like in other Interactive Evolutionary Computation (IEC) programs, users evolve images on Picbreeder by selecting ones that appeal to them to produce a new generation. However, Picbreeder also offers an online community in which to share these images, and most importantly, the ability to continue evolving others' images. Through this process of branching from other images, and through continually increasing image complexity made possible by the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, evolved images proliferate unlike in any other current IEC systems. Participation requires no explicit talent from the users, thereby opening Picbreeder to the entire Internet community. This paper details how Picbreeder encourages innovation, featuring images that were collaboratively evolved.
---
paper_title: Artificial evolution for computer graphics

paper_content:

This paper describes how evolutionary techniques of variation and selection can be used to create complex simulated structures, textures, and motions for use in computer graphics and animation. Interactive selection, based on visual perception of procedurally generated results, allows the user to direct simulated evolutions in preferred directions. Several examples using these methods have been implemented and are described. 3D plant structures are grown using fixed sets of genetic parameters. Images, solid textures, and animations are created using mutating symbolic lisp expressions. Genotypes consisting of symbolic expressions are presented as an attempt to surpass the limitations of fixed-length genotypes with predefined expression rules. It is proposed that artificial evolution has potential as a powerful tool for achieving flexible complexity with a minimum of user input and knowledge of details.
---
paper_title: The definition and rendering of terrain maps

paper_content:

This paper examines three methods, two existing and one new, for the generation of fractals based on recursive subdivision. Both existing methods are found to have defects, which are not present in the new method. A parallel processing algorithm is proposed for the rendering of height fields which is exact and distributes the load evenly between the processors. A method is described for the 'fan-tracing' of height fields to allow the realistic simulation of water reflections.
---
paper_title: Particle swarm optimization

paper_content:

A concept for the optimization of nonlinear functions using particle swarm methodology is introduced. The evolution of several paradigms is outlined, and an implementation of one of the paradigms is discussed. Benchmark testing of the paradigm is described, and applications, including nonlinear function optimization and neural network training, are proposed. The relationships between particle swarm optimization and both artificial life and genetic algorithms are described.
---
paper_title: Optimization by simulated annealing

paper_content:

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.
---
paper_title: Search based software engineering

paper_content:

This paper was written to accompany the author’s keynote talk for the Workshop on Computational Science in Software Engineering held in conjunction with International Conference in Computational Science 2006 in Reading, UK. The paper explains how software engineering activities can be viewed as a search for solutions that balance many competing constraints to achieve an optimal or near optimal result. ::: ::: The aim of Search Based Software Engineering (SBSE) research is to move software engineering problems from human-based search to machine-based search, using a variety of techniques from the metaheuristic search, operations research and evolutionary computation paradigms. As a result, human effort moves up the abstraction chain to focus on guiding the automated search, rather than performing it. The paper briefly describes the search based approach, providing pointers to the literature.
---
paper_title: Variations Forever: Flexibly generating rulesets from a sculptable design space of mini-games

paper_content:

Variations Forever is a novel game in which the player explores a vast design space of mini-games. In this paper, we present the procedural content generation research which makes the automatic generation of suitable game rulesets possible. Our generator, operating in the domain of code-like game content exploits answer-set programming as a means to declaratively represent a generative space as distinct from the domain-independent solvers which we use to enumerate it. Our generative spaces are powerfully sculptable using concise, declarative rules, allowing us to embed significant design knowledge into our ruleset generator as an important step towards a more serious automation of whole game design process.
---
paper_title: Representations for Genetic and Evolutionary Algorithms

paper_content:

From the Publisher: ::: In the field of genetic and evolutionary algorithms (GEAs), much theory and empirical study has been heaped upon operators and test problems, but problem representation has often been taken as given. This monograph breaks with this tradition and studies a number of critical elements of a theory of representations for GEAs and applies them to the empirical study of various important idealized test functions and problems of commercial import. The book considers basic concepts of representations, such as redundancy, scaling and locality and describes how GEAs'performance is influenced. Using the developed theory representations can be analyzed and designed in a theory-guided manner. The theoretical concepts are used as examples for efficiently solving integer optimization problems and network design problems. The results show that proper representations are crucial for GEAs'success.
---
paper_title: Evolving A Diverse Collection of Robot Path Planning Problems

paper_content:

This study presents an evolutionary computation system that can generate grid robot path planning problems. An evolvable cellular representation that specifies how to build a PPP is used. Also presented is a technique for taxonomizing path planning problems so that the vast number of problems that can be generated with the evolutionary computation system can be subsequently winnowed into a collection of substantially different problems of specified size. In this study the most difficult path planning problems, according to three different criteria, are evolved and those results are used to demonstrated the taxonomic technique. The hardness criteria are (i) the minimum number of turns a robot must make, (ii) the minimum number of forward moves it must make, and (iii) the sum of these quantities. A dynamic programming algorithm is used to compute these quantities for a given path planning program. The technique can be generalized to find cases of a specified hardness. The size of the board and maximum number of obstacles used are transparently specifiable.
---
paper_title: Three Ways to Grow Designs: A Comparison of Embryogenies for an Evolutionary Design Problem

paper_content:

This paper explores the use of growth processes, or embryogenies, to map genotypes to phenotypes within evolutionary systems. Following a summary of the significant features of embryogenies, the three main types of embryogenies in Evolutionary Computation are then identified and explained: external, explicit and implicit. An experimental comparison between these three different embryogenies and an evolutionary algorithm with no embryogeny is performed. The problem set to the four evolutionary systems is to evolve tessellating tiles. In order to assess the scalability of the embryogenies, the problem is increased in difficulty by enlarging the size of tiles to be evolved. The results are surprising, with the implicit embryogeny outperforming all other techniques by showing no significant increase in the size of the genotypes or decrease in accuracy of evolution as the scale of the problem is increased.
---
paper_title: A Taxonomy for Artificial Embryogeny

paper_content:

A major challenge for evolutionary computation is to evolve phenotypes such as neural networks, sensory systems, or motor controllers at the same level of complexity as found in biological organisms. In order to meet this challenge, many researchers are proposing indirect encodings, that is, evolutionary mechanisms where the same genes are used multiple times in the process of building a phenotype. Such gene reuse allows compact representations of very complex phenotypes. Development is a natural choice for implementing indirect encodings, if only because nature itself uses this very process. Motivated by the development of embryos in nature, we define artificial embryogeny (AE) as the subdiscipline of evolutionary computation (EC) in which phenotypes undergo a developmental phase. An increasing number of AE systems are currently being developed, and a need has arisen for a principled approach to comparing and contrasting, and ultimately building, such systems. Thus, in this paper, we develop a principled taxonomy for AE. This taxonomy provides a unified context for long-term research in AE, so that implementation decisions can be compared and contrasted along known dimensions in the design space of embryogenic systems. It also allows predicting how the settings of various AE parameters affect the capacity to efficiently evolve complex phenotypes.
---
paper_title: Compositional pattern producing networks: A novel abstraction of development

paper_content:

Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike currently accepted abstractions such as iterative rewrite systems and cellular growth simulations, CPPNs map to the phenotype without local interaction, that is, each individual component of the phenotype is determined independently of every other component. Results produced with CPPNs through interactive evolution of two-dimensional images show that such an encoding can nevertheless produce structural motifs often attributed to more conventional developmental abstractions, suggesting that local interaction may not be essential to the desirable properties of natural encoding in the way that is usually assumed.
---
paper_title: Evolving Neural Networks through Augmenting Topologies

paper_content:

An important question in neuroevolution is how to gain an advantage from evolving neural network topologies along with weights. We present a method, NeuroEvolution of Augmenting Topologies (NEAT), which outperforms the best fixed-topology method on a challenging benchmark reinforcement learning task. We claim that the increased efficiency is due to (1) employing a principled method of crossover of different topologies, (2) protecting structural innovation using speciation, and (3) incrementally growing from minimal structure. We test this claim through a series of ablation studies that demonstrate that each component is necessary to the system as a whole and to each other. What results is significantly faster learning. NEAT is also an important contribution to GAs because it shows how it is possible for evolution to both optimize and complexify solutions simultaneously, offering the possibility of evolving increasingly complex solutions over generations, and strengthening the analogy with biological evolution.
---
paper_title: Experience-Driven Procedural Content Generation

paper_content:

Procedural content generation is an increasingly important area of technology within modern human-computer interaction with direct applications in digital games, the semantic web, and interface, media and software design. The personalization of experience via the modeling of the user, coupled with the appropriate adjustment of the content according to user needs and preferences are important steps towards effective and meaningful content generation. This paper introduces a framework for procedural content generation driven by computational models of user experience we name Experience-Driven Procedural Content Generation. While the framework is generic and applicable to various subareas of human computer interaction, we employ games as an indicative example of content-intensive software that enables rich forms of interaction.
---
paper_title: Integrating procedural generation and manual editing of virtual worlds

paper_content:

Because of the increasing detail and size of virtual worlds, designers are more and more urged to consider employing procedural methods to alleviate part of their modeling work. However, such methods are often unintuitive to use, difficult to integrate, and provide little user control, making their application far from straightforward. In our declarative modeling approach, designers are provided with a more productive and simplified virtual world modeling workflow that matches better with their iterative way of working. Using interactive procedural sketching, they can quickly layout a virtual world, while having proper user control at the level of large terrain features. However, in practice, designers require a finer level of control. Integrating procedural techniques with manual editing in an iterative modeling workflow is an important topic that has remained relatively unaddressed until now. This paper identifies challenges of this integration and discusses approaches to combine these methods in such a way that designers can freely mix them, while the virtual world model is kept consistent during all modifications. We conclude that overcoming the challenges mentioned, for example in a declarative modeling context, is instrumental to achieve the much desired adoption of procedural modeling in mainstream virtual world modeling.
---
paper_title: How to model and augment player satisfaction: a review.

paper_content:

This is a review on approaches for modeling satisfaction perceived by users interacting with entertainment systems. Experimental studies with adult and children users of games (screen-based and physical-interactive) are outlined and the most promising approaches for augmenting player satisfaction while the game is played (i.e. in real-time) are discussed.
---
paper_title: Automatic Content Generation in the Galactic Arms Race Video Game

paper_content:

Simulation and game content includes the levels, models, textures, items, and other objects encountered and possessed by players during the game. In most modern video games and in simulation software, the set of content shipped with the product is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly and automatically renewed, players would remain engaged longer. This paper introduces two novel technologies that take steps toward achieving this ambition: 1) a new algorithm called content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) is introduced that automatically generates graphical and game content while the game is played, based on the past preferences of the players, and 2) Galactic Arms Race (GAR), a multiplayer video game, is constructed to demonstrate automatic content generation in a real online gaming platform. In GAR, which is available to the public and playable online, players pilot space ships and fight enemies to acquire unique particle system weapons that are automatically evolved by the cgNEAT algorithm. A study of the behavior and results from over 1000 registered online players shows that cgNEAT indeed enables players to discover a wide variety of appealing content that is not only novel, but also based on and extended from previous content that they preferred in the past. Thus, GAR is the first demonstration of evolutionary content generation in an online multiplayer game. The implication is that with cgNEAT it is now possible to create applications that generate their own content to satisfy users, potentially reducing the cost of content creation and increasing entertainment value from single-player to massively multiplayer online games (MMOGs) with a constant stream of evolving content.
---
paper_title: Evolving content in the Galactic Arms Race video game

paper_content:

Video game content includes the levels, models, items, weapons, and other objects encountered and wielded by players during the game. In most modern video games, the set of content shipped with the game is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly renewed, players would remain engaged longer in the evolving stream of novel content. To realize this ambition, this paper introduces the content-generating NeuroEvolution of Augmenting Topolo- gies (cgNEAT) algorithm, which automatically evolves game content based on player preferences, as the game is played. To demonstrate this approach, the Galactic Arms Race (GAR) video game is also introduced. In GAR, players pilot space ships and fight enemies to acquire unique particle system weapons that are evolved by the game. As shown in this paper, players can discover a wide variety of content that is not only novel, but also based on and extended from previous content that they preferred in the past. The implication is that it is now possible to create games that generate their own content to satisfy players, potentially significantly reducing the cost of content creation and increasing the replay value of games.
---
paper_title: The advantages of generative grammatical encodings for physical design

paper_content:

One of the applications of evolutionary algorithms is the automatic creation of designs. For evolutionary techniques to scale to the complexities necessary for actual engineering problems, it has been argued that generative systems, where the genotype is an algorithm for constructing the final design, should be used as the encoding. We describe a system for creating generative specifications by combining Lindenmayer systems with evolutionary algorithms, and we apply it to the problem of generating table designs. Designs evolved by our system reach an order of magnitude more parts than previous generative systems. Comparing it against a non-generative encoding, we find that the generative system produces designs with higher fitness and is faster than the non-generative system. Finally, we demonstrate the ability of our system to go from design to manufacture by constructing evolved table designs using rapid prototyping equipment.
---
paper_title: Modeling player experience in Super Mario Bros

paper_content:

This paper investigates the relationship between level design parameters of platform games, individual playing characteristics and player experience. The investigated design parameters relate to the placement and sizes of gaps in the level and the existence of direction changes; components of player experience include fun, frustration and challenge. A neural network model that maps between level design parameters, playing behavior characteristics and player reported emotions is trained using evolutionary preference learning and data from 480 platform game sessions. Results show that challenge and frustration can be predicted with a high accuracy (77.77% and 88.66% respectively) via a simple single-neuron model whereas model accuracy for fun (69.18%) suggests the use of more complex non-linear approximators for this emotion. The paper concludes with a discussion on how the obtained models can be utilized to automatically generate game levels which will enhance player experience.
---
paper_title: Automatic generation of game elements via evolution

paper_content:

This study presents a system for automatically producing puzzles for use in game design. The system incorporates an evolutionary algorithm that optimizes the puzzle to a specified level of difficulty. The fitness function uses dynamic programming to compute the minimum number of moves required to solve a puzzle. Two types of puzzle are explored, one is a maze based on chess pieces and the other uses colors as related by the color wheel to create an implicit maze. The evolutionary algorithm is able to produce a wide variety of puzzles at specified levels of difficulty. The algorithm can thus be used to provides a library for game design or for variable game content. The technique is flexible and can be generalized to puzzles of remarkable complexity by simply upgrading the dynamic programming algorithm used in the fitness function. It is found that puzzles requiring a maximum number of moves to solve are, potentially, less difficult because such puzzles present the player with few choices. This problem is addressed by modifying the algorithm to search for puzzles with a smaller minimum number of moves required, leaving more room in the puzzle for choice and its attendant confusion.
---
paper_title: Variations Forever: Flexibly generating rulesets from a sculptable design space of mini-games

paper_content:

Variations Forever is a novel game in which the player explores a vast design space of mini-games. In this paper, we present the procedural content generation research which makes the automatic generation of suitable game rulesets possible. Our generator, operating in the domain of code-like game content exploits answer-set programming as a means to declaratively represent a generative space as distinct from the domain-independent solvers which we use to enumerate it. Our generative spaces are powerfully sculptable using concise, declarative rules, allowing us to embed significant design knowledge into our ruleset generator as an important step towards a more serious automation of whole game design process.
---
paper_title: Automatic generation and evaluation of recombination games

paper_content:

Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.
---
paper_title: Relevant Information as a formalised approach to evaluate game mechanics

paper_content:

We present a new approach to use adaptive AI and Information Theory to aid the evaluation of game mechanics. Being able to evaluate the core game mechanics early during production is useful to improve the quality of a game, and ultimately, player satisfaction. A current problem with automated game evaluation via AI is to define measurable parameters that correlate to the quality of the game mechanics. We apply the Information Theory based concept of “Relevant Information” to this problem and argue that there is a relation between enjoyment related game-play properties and Relevant Information for an AI playing the game. We also demonstrate, with a simple game implementation, a.) how an adaptive AI can be used to approximate the Relevant Information, b.) how those measurable numerical values relate to certain game design flaws c.) how this knowledge can be used to improve the game.
---
paper_title: Towards a generic framework for automated video game level creation

paper_content:

This paper presents a generative system for the automatic creation of video game levels. Our approach is novel in that it allows high-level design goals to be expressed in a top-down manner, while existing bottom-up techniques do not. We use the FI-2Pop genetic algorithm as a natural way to express both constraints and optimization goals for potential level designs. We develop a genetic encoding technique specific to level design, which proves to be extremely flexible. Example levels are generated for two different genres of game, demonstrating the system’s broad applicability.
---
paper_title: Introducing a Feasible-Infeasible Two-Population (FI-2Pop) Genetic Algorithm for Constrained Optimization: Distance Tracing and No Free Lunch

paper_content:

We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se.
---
paper_title: Polymorph: a model for dynamic level generation

paper_content:

Players begin games at different skill levels and develop their skill at different rates—so that even the best-designed games are uninterestingly easy for some players and frustratingly difficult for others. A proposed answer to this challenge is Dynamic Difficulty Adjustment (DDA), a general category of approaches that alter games during play, in response to player performance. However, nearly all these techniques are focused on basic parameter tweaking, while the difficulty of many games is connected to aspects that are more challenging to adjust dynamically, such as level design. Further, most DDA techniques are based on designer intuition, which may not reflect actual play patterns. Responding to these challenges, we have created Polymorph, which employs techniques from level generation and machine learning to understand level difficulty and player skill, dynamically constructing levels for a 2D platformer game with continually-appropriate challenge. We present the results of the user study on which Polymorph's model of level difficulty is based, as well as a discussion of the unique features of the model. We believe Polymorph creates a play experience that is unique because the changes are both personalized and structural, while also providing an example of a new application of machine learning to aid game design.
---
paper_title: Automatic design of balanced board games

paper_content:

AI techniques are already widely used in game software to provide computer-controlled opponents for human players. However, game design is a more-challenging problem than game play. Designers typically expend great effort to ensure that their games are balanced and challenging. Dynamic game-balancing techniques have been developed to modify a game-engine's parameters in response to user play. In this paper we describe a first attempt at using AI techniques to design balanced board games like checkers and Go by modifying the rules of the game, not just the rule parameters. Our approach involves the use of a commercial general game-playing (GGP) engine that plays according to rules that are specified in a general game-definition language. We use a genetic algorithm (GA) to search the space of game rules, looking for turn-based board games that are well balanced, i.e., those that the GGP engine in self-play finds equally hard to win from either side and rarely draws. The GA finds better games than a random-search strategy that uses equivalent computational effort.
---
paper_title: An experiment in automatic game design

paper_content:

This paper presents a first attempt at evolving the rules for a game. In contrast to almost every other paper that applies computational intelligence techniques to games, we are not generating behaviours, strategies or environments for any particular game; we are starting without a game and generating the game itself. We explain the rationale for doing this and survey the theories of entertainment and curiosity that underly our fitness function, and present the details of a simple proof-of-concept experiment.
---
paper_title: Evolutionary Algorithm for Generation of Entertaining Shinro Logic Puzzles

paper_content:

A Shinro puzzle is a type of deductive reasoning puzzle that originated in Japanese periodicals. To solve the puzzle, one must locate twelve hidden stones on an 8x8 grid using only clues in the form of stone counts per row and column, and arrows placed in the grid that point to some of the hidden stones. Construction of these puzzles by hand is tedious. We explore the use of a simple genetic algorithm that automates construction of Shinro puzzles with desirable qualities which improve their entertainment value.
---
paper_title: Making racing fun through player modeling and track evolution

paper_content:

This paper addresses the problem of automatically constructing tracks tailor-made to maximize the enjoyment of individual players in a simple car racing game. To this end, some approaches to player modeling are investigated, and a method of using evolutionary algorithms to construct racing tracks is presented. A simple player-dependent metric of entertainment is proposed and used as the fitness function when evolving tracks. We conclude that accurate player modeling poses some significant challenges, but track evolution works well given the right track representation.
---
paper_title: Evolution of L-systems for compact virtual landscape generation

paper_content:

An L-system or Lindenmayer system consists of a grammar and an interpreter. The grammar contains an axiom, usually a short string, that the grammar expands into a long, complex string. The interpreter then renders the string into an object. A midpoint L-system is a generalization of L-systems to two-dimensional arrays of characters inspired by midpoint displacement fractals. This study presents a system for simultaneously evolving the rules and interpreter for a midpoint L-system that encodes a desired landscape. Unlike a midpoint displacement fractal a midpoint L-system is deterministic and can be evolved to yield fixed, complex shapes. The fractal character of a midpoint L-system permits the storage of a large complex virtual landscape in a small data object. The level of detail rendered by an L-system can be changed rapidly and, with a fast graphics engine, dynamically. This study introduces midpoint L-systems, gives techniques for evolving them, and demonstrates those techniques on trial landscapes that resemble hills and craters. The application of this work is for virtual reality where midpoint L-systems allow a designer to select from many rugged versions of a landscape without requiring vast amounts of storage or machine time to render them.
---
paper_title: Computer rendering of stochastic models

paper_content:

A recurrent problem in generating realistic pictures by computers is to represent natural irregular objects and phenomena without undue time or space overhead. We develop a new and powerful solution to this computer graphics problem by modeling objects as sample paths of stochastic processes. Of particular interest are those stochastic processes which previously have been found to be useful models of the natural phenomena to be represented. One such model applicable to the representation of terrains, known as “fractional Brownian motion,” has been developed by Mandelbrot. The value of a new approach to object modeling in computer graphics depends largely on the efficiency of the techniques used to implement the model. We introduce a new algorithm that computes a realistic, visually satisfactory approximation to fractional Brownian motion in faster time than with exact calculations. A major advantage of this technique is that it allows us to compute the surface to arbitrary levels of details without increasing the database. Thus objects with complex appearances can be displayed from a very small database. The character of the surface can be controlled by merely modifying a few parameters. A similar change allows complex motion to be created inexpensively.
---
paper_title: Towards multiobjective procedural map generation

paper_content:

A search-based procedural content generation (SBPCG) algorithm for strategy game maps is proposed. Two representations for strategy game maps are devised, along with a number of objectives relating to predicted player experience. A multiobjective evolutionary algorithm is used for searching the space of maps for candidates that satisfy pairs of these objectives. As the objectives are inherently partially conflicting, the algorithm generates Pareto fronts showing how these objectives can be balanced. Such fronts are argued to be a valuable tool for designers looking to balance various design needs. Choosing appropriate points (manually or automatically) on the Pareto fronts, maps can be found that exhibit good map design according to specified criteria, and could either be used directly in e.g. an RTS game or form the basis for further human design.
---
paper_title: Integrating procedural generation and manual editing of virtual worlds

paper_content:

Because of the increasing detail and size of virtual worlds, designers are more and more urged to consider employing procedural methods to alleviate part of their modeling work. However, such methods are often unintuitive to use, difficult to integrate, and provide little user control, making their application far from straightforward. In our declarative modeling approach, designers are provided with a more productive and simplified virtual world modeling workflow that matches better with their iterative way of working. Using interactive procedural sketching, they can quickly layout a virtual world, while having proper user control at the level of large terrain features. However, in practice, designers require a finer level of control. Integrating procedural techniques with manual editing in an iterative modeling workflow is an important topic that has remained relatively unaddressed until now. This paper identifies challenges of this integration and discusses approaches to combine these methods in such a way that designers can freely mix them, while the virtual world model is kept consistent during all modifications. We conclude that overcoming the challenges mentioned, for example in a declarative modeling context, is instrumental to achieve the much desired adoption of procedural modeling in mainstream virtual world modeling.
---
paper_title: Compositional pattern producing networks: A novel abstraction of development

paper_content:

Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike currently accepted abstractions such as iterative rewrite systems and cellular growth simulations, CPPNs map to the phenotype without local interaction, that is, each individual component of the phenotype is determined independently of every other component. Results produced with CPPNs through interactive evolution of two-dimensional images show that such an encoding can nevertheless produce structural motifs often attributed to more conventional developmental abstractions, suggesting that local interaction may not be essential to the desirable properties of natural encoding in the way that is usually assumed.
---
paper_title: SMS-EMOA: Multiobjective selection based on dominated hypervolume

paper_content:

Abstract The hypervolume measure (or S metric) is a frequently applied quality measure for comparing the results of evolutionary multiobjective optimisation algorithms (EMOA). The new idea is to aim explicitly for the maximisation of the dominated hypervolume within the optimisation process. A steady-state EMOA is proposed that features a selection operator based on the hypervolume measure combined with the concept of non-dominated sorting. The algorithm’s population evolves to a well-distributed set of solutions, thereby focussing on interesting regions of the Pareto front. The performance of the devised S metric selection EMOA ( SMS-EMOA ) is compared to state-of-the-art methods on two- and three-objective benchmark suites as well as on aeronautical real-world applications.
---
paper_title: Evolution of artificial terrains for video games based on accessibility

paper_content:

Diverse methods have been developed to generate terrains under constraints to control terrain features, but most of them use strict restrictions. However, there are situations were more flexible restrictions are sufficient, such as ensuring that terrains have enough accessible area, which is an important trait for video games. The Genetic Terrain Program technique, based on genetic programming, was used to automatically evolve Terrain Programs (TPs - which are able to generate terrains procedurally) for the desired accessibility parameters. Results showed that the accessibility parameters have negligible influence on the evolutionary system and that the terminal set has a major role on the terrain look. TPs produced this way are already being used on Chapas video game.
---
paper_title: Multiobjective exploration of the StarCraft map space

paper_content:

This paper presents a search-based method for generating maps for the popular real-time strategy (RTS) game StarCraft. We devise a representation of StarCraft maps suitable for evolutionary search, along with a set of fitness functions based on predicted entertainment value of those maps, as derived from theories of player experience. A multiobjective evolutionary algorithm is then used to evolve complete StarCraft maps based on the representation and selected fitness functions. The output of this algorithm is a Pareto front approximation visualizing the tradeoff between the several fitness functions used, and where each point on the front represents a viable map. We argue that this method is useful for both automatic and machine-assisted map generation, and in particular that the Pareto fronts are excellent design support tools for human map designers.
---
paper_title: Façade: An Experiment in Building a Fully-Realized Interactive Drama

paper_content:

Contemporary games are making significant strides towards offering complex, immersive experiences for players. We can now explore sprawling 3D virtual environments populated by beautifully rendered characters and objects with autonomous behavior, engage in highly visceral action-oriented experiences offering a variety of missions with multiple solutions, and interact in ever-expanding online worlds teeming with physically customizable player avatars.
---
paper_title: Ludologists love stories, too: notes from a debate that never took place

paper_content:

During the last few years, a debate took place within the game scholars community. A debate that, it seems, opposed two groups: ludologists and narratologists. Ludologists are supposed to focus on game mechanics and reject any room in the field for analyzing games as narrative, while narratologists argue that games are closely connected to stories. This article aims at showing that this description of the participants is erroneous. What is more, this debate as presented never really took place because it was cluttered with a series of misunderstandings and misconceptions that need to be clarified if we want to seriously discuss the role of narrative in videogames.
---
paper_title: An affectively driven planner for synthetic characters

paper_content:

This paper discusses the requirements of planning for believable synthetic characters and examines the relationship between appraisal and planning as components of an affective agent architecture. It discusses an implementation in the synthetic characters of the FearNot! anti-bullying education demonstrator and how far this provides an adequate mechanism for believable behaviour.
---
paper_title: SWAP ADJACENT GEMS TO MAKE SETS OF THREE: A HISTORY OF MATCHING TILE GAMES

paper_content:

Abstract From sales figures and interviews, we know that many people outside the typical video game audience play small downloadable video games like Zuma, Diner Dash, or Bejeweled. Such small video games are known as casual games, and have unsuspectedly become a major industry during the last few years. However, video game studies have so far mostly focused on foundational issues (“what is a game”) and on AAA games, big games purchased in stores. In this article, I try to remedy the situation by examining the historical development of the casual game sub-genre of matching tile games, to see how their game design has evolved over time, and to discuss the opposing perspectives that players and developers have on video game history,
---
paper_title: Authoring an Interactive Narrative with Declarative Optimization-Based Drama Management ∗

paper_content:

Drama managers reconfigure a game in reaction to a player's actions. In declarative optimization-based drama management (DODM), a game's story is abstracted as a sequence of plot points; possible drama manager interventions are abstracted as a set of DM actions. The author defines an function evaluating story quality, and some optimization method (currently reinforcement learning) chooses DM actions so as to maximize expected story quality according to that evaluation function. While previous work has developed this approach at a technical level and discussed its potential applications, no work to date has used DODM to write real games. We report on our experiences designing a game in the Neverwinter Nights engine, entitled The Guilty, in which we use DODM to create a dynamic plot that in a previous design iteration we had found difficult to create with other techniques.
---
paper_title: Procedural modeling of buildings

paper_content:

CGA shape, a novel shape grammar for the procedural modeling of CG architecture, produces building shells with high visual quality and geometric detail. It produces extensive architectural models for computer games and movies, at low cost. Context sensitive shape rules allow the user to specify interactions between the entities of the hierarchical shape descriptions. Selected examples demonstrate solutions to previously unsolved modeling problems, especially to consistent mass modeling with volumetric shapes of arbitrary orientation. CGA shape is shown to efficiently generate massive urban models with unprecedented level of detail, with the virtual rebuilding of the archaeological site of Pompeii as a case in point.
---
paper_title: Automatic Content Generation in the Galactic Arms Race Video Game

paper_content:

Simulation and game content includes the levels, models, textures, items, and other objects encountered and possessed by players during the game. In most modern video games and in simulation software, the set of content shipped with the product is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly and automatically renewed, players would remain engaged longer. This paper introduces two novel technologies that take steps toward achieving this ambition: 1) a new algorithm called content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) is introduced that automatically generates graphical and game content while the game is played, based on the past preferences of the players, and 2) Galactic Arms Race (GAR), a multiplayer video game, is constructed to demonstrate automatic content generation in a real online gaming platform. In GAR, which is available to the public and playable online, players pilot space ships and fight enemies to acquire unique particle system weapons that are automatically evolved by the cgNEAT algorithm. A study of the behavior and results from over 1000 registered online players shows that cgNEAT indeed enables players to discover a wide variety of appealing content that is not only novel, but also based on and extended from previous content that they preferred in the past. Thus, GAR is the first demonstration of evolutionary content generation in an online multiplayer game. The implication is that with cgNEAT it is now possible to create applications that generate their own content to satisfy users, potentially reducing the cost of content creation and increasing entertainment value from single-player to massively multiplayer online games (MMOGs) with a constant stream of evolving content.
---
paper_title: Interactive genetic engineering of evolved video game content

paper_content:

Procedural content generation techniques can increase re-playability and lower the burden on developers by satisfying players' demand for new content. However, procedural content also creates an opportunity for new kinds of player-driven content customization by giving players access to the parameterized content space. This paper presents such a technique that enables players to manually customize evolved content represented by artificial neural networks. In particular, particle system weapons evolved by the multiplayer space shooter called Galactic Arms Race (GAR) can be further "genetically engineered" by the players themselves in a new extension to the game called the Weapons Lab. Results are presented that demonstrate procedural weapons evolved by the game that are further customized by players in the Weapons Lab. The implication is that procedurally-generated content of many types can also be customized by players, adding a further dimension to its potential appeal.
---
paper_title: Combining local and global optimisation for virtual camera control

paper_content:

Controlling a virtual camera in 3D computer games is a complex task. The camera is required to react to dynamically changing environments and produce high quality visual results and smooth animations. This paper proposes an approach that combines local and global search to solve the virtual camera control problem. The automatic camera control problem is described and it is decomposed into sub-problems; then a hierarchical architecture that solves each sub-problem using the most appropriate optimisation technique is proposed. The approach is compared to pure local search solutions to showcase the advantages of the proposed architecture in terms of visual performance and robustness.
---
paper_title: Towards affective camera control in games

paper_content:

Information about interactive virtual environments, such as games, is perceived by users through a virtual camera. While most interactive applications let users control the camera, in complex navigation tasks within 3D environments users often get frustrated with the interaction. In this paper, we propose inclusion of camera control as a vital component of affective adaptive interaction in games. We investigate the impact of camera viewpoints on psychophysiology of players through preference surveys collected from a test game. Data is collected from players of a 3D prey/predator game in which player experience is directly linked to camera settings. Computational models of discrete affective states of fun, challenge, boredom, frustration, excitement, anxiety and relaxation are built on biosignal (heart rate, blood volume pulse and skin conductance) features to predict the pairwise self-reported emotional preferences of the players. For this purpose, automatic feature selection and neuro-evolutionary preference learning are combined providing highly accurate affective models. The performance of the artificial neural network models on unseen data reveals accuracies of above 80% for the majority of discrete affective states examined. The generality of the obtained models is tested in different test-bed game environments and the use of the generated models for creating adaptive affect-driven camera control in games is discussed.
---
paper_title: Evolving 3D buildings for the prototype video game Subversion

paper_content:

We investigate user-guided evolution for the development of virtual 3D building structures for the prototype (commercial) game Subversion, which is being developed by Introversion Software Ltd. Buildings are described in a custom plain-text markup language that can be parsed by Subversion’s procedural generation engine, which renders the 3D models on-screen. The building descriptions are amenable to random generation, crossover and mutation, which enabled us to implement and test a user-driven evolutionary approach to building generation. We performed some fundamental experimentation with ten participants to determine how visually similar child buildings are to their parents, when generated in differing ways. We hope to demonstrate the potential of user-guided evolution for content generation in games in general, as such tools require very little training, time or effort to be employed effectively.
---
paper_title: Evolving content in the Galactic Arms Race video game

paper_content:

Video game content includes the levels, models, items, weapons, and other objects encountered and wielded by players during the game. In most modern video games, the set of content shipped with the game is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly renewed, players would remain engaged longer in the evolving stream of novel content. To realize this ambition, this paper introduces the content-generating NeuroEvolution of Augmenting Topolo- gies (cgNEAT) algorithm, which automatically evolves game content based on player preferences, as the game is played. To demonstrate this approach, the Galactic Arms Race (GAR) video game is also introduced. In GAR, players pilot space ships and fight enemies to acquire unique particle system weapons that are evolved by the game. As shown in this paper, players can discover a wide variety of content that is not only novel, but also based on and extended from previous content that they preferred in the past. The implication is that it is now possible to create games that generate their own content to satisfy players, potentially significantly reducing the cost of content creation and increasing the replay value of games.
---
paper_title: NEAT Particles: Design, Representation, and Animation of Particle System Effects

paper_content:

Particle systems are a representation, computation, and rendering method for special effects such as fire, smoke, explosions, electricity, water, magic, and many other phenomena. This paper presents NEAT particles, a new design, representation, and animation method for particle systems tailored to real-time effects in video games and simulations. In NEAT particles, the neuroevolution of augmenting topologies (NEAT) method evolves artificial neural networks (ANN) that control the appearance and motion of particles. NEAT particles affords three primary advantages over traditional particle effect development methods. First, it decouples the creation of new particle effects from mathematics and programming, enabling users with little knowledge of either to produce complex effects. Second, it allows content designers to evolve a broader range of effects than typical development tools through a form of interactive evolutionary computation (IEC). And finally, it acts as a concept generator, allowing users to interactively explore the space of possible effects. In the future such a system may allow content to be evolved in the game itself, as it is played
---
paper_title: Exploratory modeling with collaborative design spaces

paper_content:

Enabling ordinary people to create high-quality 3D models is a long-standing problem in computer graphics. In this work, we draw from the literature on design and human cognition to better understand the design processes of novice and casual modelers, whose goals and motivations are often distinct from those of professional artists. The result is a method for creating exploratory modeling tools, which are appropriate for casual users who may lack rigidly-specified goals or operational knowledge of modeling techniques. ::: Our method is based on parametric design spaces, which are often high dimensional and contain wide quality variations. Our system estimates the distribution of good models in a space by tracking the modeling activity of a distributed community of users. These estimates drive intuitive modeling tools, creating a self-reinforcing system that becomes easier to use as more people participate. ::: We present empirical evidence that the tools developed with our method allow rapid creation of complex, high-quality 3D models by users with no specialized modeling skills or experience. We report analyses of usage patterns garnered throughout the year-long deployment of one such tool, and demonstrate the generality of the method by applying it to several design spaces.
---
paper_title: Automatic generation and evaluation of recombination games

paper_content:

Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.
---
paper_title: Automatic design of balanced board games

paper_content:

AI techniques are already widely used in game software to provide computer-controlled opponents for human players. However, game design is a more-challenging problem than game play. Designers typically expend great effort to ensure that their games are balanced and challenging. Dynamic game-balancing techniques have been developed to modify a game-engine's parameters in response to user play. In this paper we describe a first attempt at using AI techniques to design balanced board games like checkers and Go by modifying the rules of the game, not just the rule parameters. Our approach involves the use of a commercial general game-playing (GGP) engine that plays according to rules that are specified in a general game-definition language. We use a genetic algorithm (GA) to search the space of game rules, looking for turn-based board games that are well balanced, i.e., those that the GGP engine in self-play finds equally hard to win from either side and rarely draws. The GA finds better games than a random-search strategy that uses equivalent computational effort.
---
paper_title: An experiment in automatic game design

paper_content:

This paper presents a first attempt at evolving the rules for a game. In contrast to almost every other paper that applies computational intelligence techniques to games, we are not generating behaviours, strategies or environments for any particular game; we are starting without a game and generating the game itself. We explain the rationale for doing this and survey the theories of entertainment and curiosity that underly our fitness function, and present the details of a simple proof-of-concept experiment.
---
paper_title: NEAT Particles: Design, Representation, and Animation of Particle System Effects

paper_content:

Particle systems are a representation, computation, and rendering method for special effects such as fire, smoke, explosions, electricity, water, magic, and many other phenomena. This paper presents NEAT particles, a new design, representation, and animation method for particle systems tailored to real-time effects in video games and simulations. In NEAT particles, the neuroevolution of augmenting topologies (NEAT) method evolves artificial neural networks (ANN) that control the appearance and motion of particles. NEAT particles affords three primary advantages over traditional particle effect development methods. First, it decouples the creation of new particle effects from mathematics and programming, enabling users with little knowledge of either to produce complex effects. Second, it allows content designers to evolve a broader range of effects than typical development tools through a form of interactive evolutionary computation (IEC). And finally, it acts as a concept generator, allowing users to interactively explore the space of possible effects. In the future such a system may allow content to be evolved in the game itself, as it is played
---
paper_title: Making racing fun through player modeling and track evolution

paper_content:

This paper addresses the problem of automatically constructing tracks tailor-made to maximize the enjoyment of individual players in a simple car racing game. To this end, some approaches to player modeling are investigated, and a method of using evolutionary algorithms to construct racing tracks is presented. A simple player-dependent metric of entertainment is proposed and used as the fitness function when evolving tracks. We conclude that accurate player modeling poses some significant challenges, but track evolution works well given the right track representation.
---
paper_title: Particle swarm optimization

paper_content:

A concept for the optimization of nonlinear functions using particle swarm methodology is introduced. The evolution of several paradigms is outlined, and an implementation of one of the paradigms is discussed. Benchmark testing of the paradigm is described, and applications, including nonlinear function optimization and neural network training, are proposed. The relationships between particle swarm optimization and both artificial life and genetic algorithms are described.
---
paper_title: Analyzing the Expressive Range of a Level Generator

paper_content:

This paper explores a method for analyzing the expressive range of a procedural level generator, and applies this method to Launchpad, a level generator for 2D platformers. Instead of focusing on the number of levels that can be created or the amount of time it takes to create them, we instead examine the variety of generated levels and the impact of changing input parameters. With the rise in the popularity of PCG, it is important to be able to fairly evaluate and compare different generation techniques within similar domains. We have found that such analysis can also expose unexpected biases in the generation algorithm and holes in the expressive range that drive future work.
---
paper_title: The 2010 Mario AI Championship: Level Generation Track

paper_content:

The Level Generation Competition, part of the IEEE Computational Intelligence Society (CIS)-sponsored 2010 Mario AI Championship, was to our knowledge the world's first procedural content generation competition. Competitors participated by submitting level generators - software that generates new levels for a version of Super Mario Bros tailored to individual players' playing style. This paper presents the rules of the competition, the software used, the scoring procedure, the submitted level generators, and the results of the competition. We also discuss what can be learned from this competition, both about organizing procedural content generation competitions and about automatically generating levels for platform games. The paper is coauthored by the organizers of the competition (the first three authors) and the competitors.
---

Title: Search-Based Procedural Content Generation: A Taxonomy and Survey

Section 1: INTRODUCTION
Description 1: Introduce the field of search-based procedural content generation, its importance, and the aim of the paper.

Section 2: DISSECTING PROCEDURAL CONTENT GENERATION
Description 2: Discuss distinctions and taxonomies within procedural content generation, setting a framework for search-based PCG.

Section 3: SEARCH-BASED PROCEDURAL CONTENT GENERATION
Description 3: Define search-based procedural content generation, detailing its methodology and situating it within the broader scope of PCG.

Section 4: SURVEY OF SEARCH-BASED PCG
Description 4: Survey published research on search-based PCG, categorizing works by the type of content generated and their methodologies.

Section 5: A Note on Chronology
Description 5: Trace the chronological development of search-based PCG, highlighting key early works and their influence on subsequent research.

Section 6: Summary
Description 6: Summarize the survey findings, identifying patterns and trends in the use of representations, evaluation functions, and content types.

Section 7: OUTLOOK
Description 7: Discuss research challenges and future directions in search-based procedural content generation, outlining potential areas for development and interdisciplinary collaboration.