CEC 2012
0 likes188 views
This summarizes six approaches to procedural terrain generation using evolutionary algorithms. It finds that while each approach has advantages, future work needs better genotype representations that allow varied, detailed, and controllable terrain for different applications. Fitness functions must effectively evaluate playability, believability, and aesthetics. A standardized metric is also needed to evaluate algorithm performance for games.
CEC 2012
- 1. A SURVEY OF PROCEDURAL TERRAIN GENERATION TECHNIQUES USING EVOLUTIONARY ALGORITHMS William Raffe, Fabio Zambetta, Xiaodong Li RMIT University, Australia {william.raffe , fabio.zambetta , xiaodong.li} @rmit.edu.au Summary Approach Fitness Evaluation Refinement Variety Control Game Integration Ideal Use Procedurally generated terrains have been successfully used in numerous applications over the last three decades. They are predominantly utilized in media applications, such as video games, animations, and simulations, where they Simulated natural terrain. Could be used in games such as flight Ong et al. Compared to example terrains. High Low Medium Low are used either as designer aids, to provide expansive virtual environments to navigate, or to provide a believable simulators that need large, natural terrain. backdrop to an existing scene. Ashlock et al. Compared to idealized terrain. Medium Low Medium Low Where single feature terrains and fractal terrains are applicable. Recently, the use of Evolutionary Algorithms (EA) during the procedural terrain generation process has been proposed Simulation applications. and is now a growing field. The use of EA allows for more control to be exerted on the terrain generation process. Most Evolutionary art where a single screen capture is more desirable then Walsh and Gade Interactive evolution. High Low High Low existing procedural terrain generation systems are designed for a specific application, however the inclusion of EA has a playable game. the potential result in algorithms that can produce not only a higher variety of terrains but also terrains that can be Interactive evolution. Accessibility metric. Early approaches for evolutionary art or games with eccentric terrain. Frade et al. Medium High Low Medium sculpted at a finer resolution. Obstacle length metric. Later approaches for games that require predominately flat terrain. This poster displays the six primary approaches that have been published thus far. A summary of the EA structure used Multiobjective evolution for base and Real-time strategy games that use player bases and collectable Togelius et al. High Medium Low High in each is provided as well as an accompanying image from the respective papers. A table of comparisons is also resource distances and asymmetry of terrain. resources. provided, analyzing each technique with the specific purpose of generating terrain to be used in video games. Raffe et al. Two-levelled interactive evolution. High Medium High Medium As a development aid for game maps of all sizes. Conclusions Each one of the approaches shown here has its own advantages and disadvantages and each of them provides new ideas and highlights new challenges to overcome. By reviewing them it has been shown that the focus of this research Acknowledgments field in the future needs to be directed towards: Finding a robust genotype representation. A superior genotype should allow for a variety of terrains to be generated All images belong to their respective authors and those included in the conference so that it can be used for multiple applications, allow for a high level of refinement to produce detailed terrain, and proceedings are done so with consent of the primary author of each paper. provide enough control such that terrain can be created to meet a users requirements. Finding strong fitness evaluation methods that can be used to score each candidate for the purposes of playability in video games, believability in animations and simulations, and aesthetics in art. Investigating and agreeing upon a standardised metric that can be used to evaluate the performance of these types of evolutionary procedural terrain generation algorithms. Authors: J. Togelius, M. Preuss, G. Yannakakis Sample Paper: Towards multiobjective procedural map generation Genotype: Each mountain created by a Gaussian curve on a height-map. Each peak/ridge has 5 parameter values: 2 for standard deviation of a Gaussian distribution, 2 for the (x,y) coordinates of a mountain peak, and 1 Authors: W. Raffe, F. Zambetta, X. Li for the height of the peak. Player bases and game resources have similar coordinate parameters. Sample Paper: Evolving patch-based games for use in video games Fitness Evaluation: Multiobjective evaluation of fitness measures that ensure dispersal of player bases on the Genotype: NxN grid of identifiers. Each identifier is associated with a unique, pre-made patch of height-map terrain, fair access to game resources from each base, and traversable paths between bases. Authors: P. Walsh, P. Gade terrain data. Parent Selection: Fittest candidate always chosen as parents. Sample Paper: Terrain generation using an interactive genetic algorithm Fitness Evaluation: Interactive evolution. Seeding: None (random generation of initial population). Genotype: Parameter values in the form of 8-bit strings. Parameters include feature scale, spikiness, water Parent Selection: Parents chosen solely through interactive evolution. Crossover: Simulated binary crossover. level, sun angle, and cloud coverage. Seeding: Pre-made terrains are provided to program which are decomposed into smaller patches of height-map Mutation: Probability based mutation of terrain parameters and base/resource coordinates. Fitness Evaluation: Interactive evolution. data and given unique identifiers. These are also used as the initial population. Parent Selection: Tournament Selection with higher probability given to candidates that the user selected Crossover: Uniform crossover - Each patch identifier of each parent has a probability of appearing in a child. through Interactive Evolution. Mutation: Each patch identifier in a new child given a probability to mutate. A randomly selected patch replaces Seeding: A base terrain is provided and parameter changes applied to it to create candidates. the existing patch. Crossover: One-point Crossover of two parents. Mutation: Flipping a single bit in one or more of a childs 8-bit parameter strings. Authors: D. Ashlock, S. Gent, K. Bryden Authors: M. Frade, F. F. de Vega, C. Cotta Sample Paper: Evolution of l-systems for compact virtual landscape generation Authors: T. Ong, R. Saunders, J. Keyser, J. Leggett Sample Paper: Evolution of artificial terrains for video games based on obstacles edge length Genotype: 1) A list of L-system symbol replacement rules. Each symbol is replaced by 4 others in a replacement Sample Paper: Terrain generation using genetic algorithms Genotype: A tree of numerical and trigonometric operators with noise functions as terminal functions (leaf and therefore grows two dimensionally. 2) A list of displacement values for each symbol in the grammar that is Genotype: List of transform operations for control points on a height-map. Operations include translate, rotate, nodes). Resulting program is applied to each height-map vertex coordinate to get a height value. used to convert the L-System into height-map data. and raise/lower. Fitness Evaluation: Interactive evolution. Accessibility measure. Obstacle length measure. Fitness Evaluation: A similarity measure between a candidate and an idealized target terrain. Fitness Evaluation: Similarity measure between a candidate and the initial population. Parent Selection: Size 7 Tournament Selection. Parent Selection: Size 7 Tournament Selection. Replaces the least fit candidates. Parent Selection: Not stated. Seeding: None (random generation of initial population). Seeding: None (Random generation of initial population). Seeding: Initial population made of sample terrains from geospatial height-map data. Crossover: Sub-tree crossover A random node from each parent is chosen and their respective sub-trees are Crossover: Two-point crossover for both genotypes. Crossover: One-point crossover of the operator lists of two parents. swapped. Mutation: Change one symbol replacement rule in a candidate by randomly changing the resulting symbol. Mutation: Add or change a transform operation of a candidate. Mutation: Addition or substitution of a tree node. Removal of a tree node and its sub-tree. Change one displacement value in a candidate by stochastic stepping. RESEARCH POSTER PRESENTATION DESIGN 息 2012 www.PosterPresentations.com