PaperlayerView exact revision on arXiv

Source-linked AI summary

Procedural Content Generation through Quality Diversity

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

arXiv:1907.04053v1cs.NEcs.AI

TL;DR

PCG seeks content that is both high-quality and varied, while many existing methods face a trade-off between these goals. This paper presents quality-diversity algorithms and surveys their applications to games. Across the reviewed work, these methods can produce large sets of diverse, high-quality content in one run, with uses including designer feedback and mixed-initiative tools.

  • Problem

    PCG must balance playable, high-quality content with variation, while many methods trade off quality and diversity and subjective, multifaceted objectives are difficult to formalize.

    Source: §I · p. 1, B. Fitness-Free Search · p. 3

  • Method

    The paper distinguishes QD as a search strategy for PCG that rewards divergence while controlling quality through constraints or local competition, and surveys its components and game applications.

    Source: §I · p. 1

  • Results

    Across recent game applications, PCG-QD can produce large sets of diverse, high-quality content in one run.

    Source: §VI · p. 7

  • Takeaways & Limitations

    Such outputs are useful as explainable designer feedback, in mixed-initiative tools, and for expressivity analysis.

    Source: §VI · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

PCG must produce content that is both high-quality and varied, but many methods trade these goals off. The paper presents quality-diversity as a search strategy for procedural content generation and describes behavioral distance as one way to measure diversity.

I. INTRODUCTION

  • PCG content must be playable and entertaining while also varying enough to avoid player fatigue; value and novelty are both criteria for creative artifacts.The introduction argues that traditional PCG commonly targets value but not novelty or broader content diversity.Source: §I · p. 1
  • PCG methods often trade off quality and diversity, while the paper argues that recent search methods can emphasize both simultaneously.It proposes this as a way to expand what PCG can do in games.Source: §I · p. 1

II. QUALITY DIVERSITY APPROACHES

  • QD rewards divergence through novelty, surprise, or curiosity while using localized convergence to retain quality.The approach is presented as distinct from search that directly rewards problem objectives.Source: §II · p. 2

A. Divergence Components

  • Divergence components maintain and reward diversity in the population.The section introduces several ways to achieve this in current QD algorithms.Source: A. Divergence Components · p. 2

1) Behavior Space Distance:

  • Behavior-space distance measures how different an individual is from others, using the current population, past archive, predicted population, or areas explored during its lifetime as reference.Unlike niching, divergence is assessed in behavioral rather than genotypic space.Source: 1) Behavior Space Distance · p. 2

2) Behavior Space Partitioning:

QD algorithms can preserve diversity by partitioning behavior space, with partition granularity under designer control. They support quality through local competition or constraints on candidate solutions.

2) Behavior Space Partitioning:

  • Partitioning behavior space into discretized dimensions lets designers control the granularity of the represented space.Cells group individuals with specified behaviors; partitions can be uniform or based on the population distribution.Source: 2) Behavior Space Partitioning · p. 2

B. Quality Components

  • Current QD algorithms use different strategies to push evolutionary search toward higher-quality candidate solutions.Source: B. Quality Components · p. 2

1) Local Competition:

  • Local competition improves quality by comparing a candidate with others in its niche, defined using a distance metric or shared partition cell.Source: 1) Local Competition · p. 2

2) Constraints:

  • Hard constraints divide candidates into feasible and infeasible groups; prior work differs on whether infeasible candidates also retain diversity.Some approaches ignore infeasible individuals’ diversity, while others maintain it regardless of constraint satisfaction.Source: 2) Constraints · p. 2

C. Algorithms

The section surveys QD algorithms used in previous work, including methods not yet applied to games. It describes MAP-Elites and variants that alter selection or behavior-space partitioning.

C. Algorithms

  • The section reviews QD algorithms from prior work, including algorithms that have not been applied to games.Source: C. Algorithms · p. 2

1) MAP-Elites (ME):

  • MAP-Elites [12] partitions behavior space and keeps the best individual in each cell, iteratively selecting stored solutions to produce and evaluate offspring.A candidate replaces the cell’s current elite only if its performance is better; the process continues for a set number of evaluations or until desired grid coverage.Source: 1) MAP-Elites (ME) · p. 2

2) MAP-Elites with Novelty Search (ME-NOV):

  • MAP-Elites with Novelty Search selects elites for reproduction in proportion to novelty and stores offspring in a novelty archive.The behavioral distance used for novelty can bias exploration; variants combine feature maps or search novelty orthogonal to partition features.Source: 2) MAP-Elites with Novelty Search… · p. 2

3) MAP-Elites with Sliding Boundaries (MESB):

4) Constrained Novelty Search (CNS):

The section presents constrained and local-competition QD variants that combine feasibility or quality objectives with novelty or surprise. Their designs differ in how infeasible candidates are handled and how diversity is measured.

4) Constrained Novelty Search (CNS):

  • Constrained Novelty Search combines FI-2Pop with novelty search, evolving feasible individuals for novelty and infeasible ones toward feasibility or novelty.Offspring migrate between populations according to feasibility, which the passage says increases the chance of finding stepping stones toward multiple high-quality solutions.Source: 4) Constrained Novelty Search (CNS) · p. 2

5) Constrained Surprise Search (CSS):

  • Constrained Surprise Search, uses surprise for feasible individuals and evolves infeasible individuals to minimize their distance from feasibility.It applies unexpectedness rather than novelty as the diversity measure for feasible individuals in FI-2Pop.Source: 5) Constrained Surprise Search (CSS) · p. 3

6) Constrained MAP-Elites (CME):

  • Constrained MAP-Elites, maintains feasible and infeasible populations in each archive cell, optimizing fitness for the former and feasibility distance for the latter.Source: 6) Constrained MAP-Elites (CME) · p. 3

7) Novelty Search with Local Competition (NS-LC):

  • NS-LC combines novelty with local competition, which rewards individuals that outperform their K nearest neighbors.The local objective creates selection pressure across the search space by comparing nearby individuals in the generation and novelty archive.Source: 7) Novelty Search with Local… · p. 3

8) Surprise Search with Local Competition (SS-LC):

  • SS-LC uses surprise rather than novelty as one objective and local competition as another; surprise measures deviation from predictions of past generations.The passage notes that combining surprise, novelty, and local competition can perform well in highly deceptive domains.Source: 8) Surprise Search with Local… · p. 3

III. WHY QUALITY DIVERSITY?

The paper presents PCG-QD as search-based PCG that can generate many high-quality, behaviorally diverse artifacts in one run. It argues that QD also supports multifaceted game objectives and makes generator expressivity visible during search.

A. Generative Efficiency

  • One QD run can produce a large corpus of high-quality, behaviorally diverse content, avoiding repeated generation and post-generation quality and diversity assessment.This can be computationally heavy, but is useful when a broad variety of content is needed.Source: A. Generative Efficiency · p. 3

B. Fitness-Free Search

  • QD can address subjective, multifaceted game objectives by considering multiple dimensions and using local rather than global fitness competition.The resulting visualizations can highlight potential biases in the chosen fitness function.Source: B. Fitness-Free Search · p. 3

C. Online Expressivity Analysis

  • QD diversity components analyze expressivity during evolution, while behavioral-distance search targets under-explored niches.The artifacts needed for expressivity analysis can also be produced in one run.Source: C. Online Expressivity Analysis · pp. 3–4
  • The Mario-scenes heatmap uses six binary mechanics features; dependent behavior characterizations leave some search-space regions without generated levels.For example, killing an enemy requires jumping in Super Mario Bros.Source: C. Online Expressivity Analysis · p. 4, Figure 1 · p. 4

D. Human-Machine Co-Creation

QD can support co-creative design by providing varied, high-quality suggestions as developers revise priorities. Feature maps and lineage visualizations can help designers understand, group, and select generated artifacts.

D. Human-Machine Co-Creation

  • When game priorities change, QD lets designers adjust quality criteria and behavioral characterizations while receiving diverse, high-quality suggestions.The paper presents this as a way to support mixed-initiative content design and foster user creativity.Source: D. Human-Machine Co-Creation · p. 4

E. Explainability

  • MAP-Elites feature maps can help developers explore and understand generator output, while lineage visualizations show artifact origins and shared ancestors.These views can help designers group individuals and select artifacts with desired features.Source: E. Explainability · p. 4

IV. CASES OF QUALITY DIVERSITY IN PCG

The surveyed cases apply quality-diversity methods to varied game content, using different algorithm components, quality criteria, and behavior characterizations. Examples include generating image and object collections with MAP-Elites and playable bullet-hell scripts with constrained MAP-Elites.

IV. CASES OF QUALITY DIVERSITY IN PCG

  • Table I organizes PCG-QD cases by algorithm, components, quality and diversity characterizations, and artifact type.Its component codes are behavior-space distance, partitioning, local competition, and constraints.Source: §IV · p. 4, Table I · p. 5

A. Generation of 2D and 3D Objects

  • MAP-Elites uses a DNN’s 1000 image-classification classes as search-space bins and optimizes each bin for classification confidence when generating 2D images or 3D objects.Source: A. Generation of 2D and 3D Objects · p. 4

B. Generation of Bullet Hell Scripts

  • Constrained MAP-Elites evolves playable bullet-hell scripts, using agent entropy, agent risk, and bullet distribution as feature-map dimensions.An A* algorithm checks playability.Source: B. Generation of Bullet Hell Scripts · p. 5

C. Generation of Mario Scenes

The surveyed applications use quality-diversity to generate playable Mario scenes, high-performing Hearthstone decks with varied mana curves, and diverse level suggestions for a human designer.

C. Generation of Mario Scenes

  • Eight binary game-mechanic dimensions define a 256-cell map; constrained MAP-Elites filled 100 cells on average with playable Mario scenes spanning zero to all eight mechanics.The examples shown range from no mechanics fired to five.Source: C. Generation of Mario Scenes · p. 5

D. Generation of Hearthstone Decks

  • MAP-Elites with Sliding Boundaries searches for high-performing Hearthstone decks that vary in mana distribution, measuring fitness over 200 games and diversity by mana-curve average and variance.Fitness is the difference between players’ health.Source: D. Generation of Hearthstone Decks · p. 5

E. Generation of Map Sketches

  • Sentient Sketchbook uses constrained novelty search seeded by the designer’s sketch to suggest playable levels that differ in their tile layouts.Feasibility checks whether resources are reachable from every player’s base; diversity counts differing tiles.Source: E. Generation of Map Sketches · p. 5

F. Generation of Weapons

The applications use quality-diversity methods to produce feasible content with varied or surprising properties, from weapons and spaceships to Minecraft-like structures.

F. Generation of Weapons

  • Constrained surprise search generates usable, balanced weapons, rewarding feasible designs for unexpected gameplay behavior measured from simulated player death locations.Surprise compares observed death locations with a linear-regression prediction from heatmaps over the previous two generations.Source: F. Generation of Weapons · p. 6

G. Generation of Spaceships

  • DeLeNoX generates diverse feasible spaceships by alternating constrained novelty-search exploration with autoencoder-based compression into a latent behavior space.The next exploration phase uses that latent space as its behavior characterization.Source: G. Generation of Spaceships · p. 6

H. Generation of Minecraft-like Structures

  • Novelty search with local competition generates diverse Minecraft-like block structures, with complexity as quality and a binary per-location block vector as behavior characterization.The structures are evolved via artificial neural networks.Source: H. Generation of Minecraft-like… · p. 6

I. Generation of Dungeons

The paper surveys an interactive dungeon-design application, discusses motivations and patterns across PCG-QD cases, and identifies open directions spanning behavior characterization, game-agent analysis, and new content types.

I. Generation of Dungeons

  • An interactive constrained MAP-Elites variant in Evolutionary Dungeon Designer lets users choose two dimensions of interest and select favored solutions while evolving dungeons.The feasible population maximizes a weighted sum of inventory and spatial-pattern features; the infeasible population minimizes playability violations.Source: §I · p. 6

J. Discussion

  • Across surveyed cases, constrained optimization commonly ensures playability; identified motivations include rapid multiple suggestions, unexpected weapon uses, and expressivity analysis.The paper reports that explainability to designers was implicit in EDD, with no surveyed project explicitly targeting it.Source: J. Discussion · p. 6

V. OPEN PROBLEMS AND OUTLOOK

  • Behavior characterization remains a challenge: high dimensionality can hinder search, while fine partitions impede coverage and coarse partitions can hide solutions.The paper points to further work on high-dimensional states and suggests simulation surrogates from learned gameplay models to reduce evaluations.Source: §V · p. 7
  • QD-generated diverse, playable levels could help analyze agent behavior and test reinforcement-learning generality, including with levels agents cannot beat [46, 47].QD may also evolve diverse or mutually compatible agent groups for collaborative games and test content across play styles.Source: §V · p. 7
  • The surveyed work focuses mostly on levels and visuals; the paper calls for exploring rules, music, and other content facets with distinct quality and diversity challenges.For rules, playability may be easier to define than what makes a game good.Source: §V · p. 7

VI. CONCLUSION

The paper frames quality-diversity as a search strategy for procedural content generation, producing diverse, high-quality artifacts that can support designer feedback, mixed-initiative tools, and expressivity analysis.

VI. CONCLUSION

  • QD can produce diverse, high-quality content through controllable behavioral dimensions and constraints on playability and/or local competition.The paper describes PCG-QD as particularly efficient at producing many diverse artifacts in one run.Source: §VI · p. 7
  • Many diverse artifacts from one run can serve as explainable designer feedback, support mixed-initiative tools, or enable expressivity analysis.Source: §VI · p. 7
  • The paper identifies under-explored areas in QD algorithms and intended uses, and outlines future challenges for the field.Source: §VI · p. 7
  • The paper distinguishes QD as a search strategy for search-based procedural content generation.Source: §VI · p. 7
Loading 1907.04053v1…