Search-Based Procedural Content Generation: A Taxonomy and Survey
Open accessThe DOI matches its Crossref record; 79 of the 80 references it cites were found in a registry or an index.
Abstract
The focus of this survey is on research in applying evolutionary and other metaheuristic search algorithms to automatically generating content for games, both digital and nondigital (such as board games). The term search-based procedural content generation is proposed as the name for this emerging field, which at present is growing quickly. A taxonomy for procedural content generation is devised, centering on what kind of content is generated, how the content is represented and how the quality/fitness of the content is evaluated; search-based procedural content generation in particular is situated within this taxonomy. This article also contains a survey of all published papers known to the authors in which game content is generated through search or optimisation, and ends with an overview of important open research problems.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Kennedy, J., & Eberhart, R. (2002) · Proceedings of ICNN'95 - International Conference on Neural Networks · doi:10.1109/icnn.1995.488968 · Cited by 58,192
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Multi-Objective Optimization Using Evolutionary Algorithms
Deb, K., & Kalyanmoy, D. (2001) · Andalas University Repository (Andalas University) · Cited by 17,323
(2019) · Handbook of Machine Learning · doi:10.1142/9789811205675_0004 · Cited by 6,270
Evolving Neural Networks through Augmenting Topologies
Stanley, K. O., & Miikkulainen, R. (2002) · Evolutionary Computation · doi:10.1162/106365602320169811 · Cited by 3,258
Self-citationSMS-EMOA: Multiobjective selection based on dominated hypervolume
Beume, N., Naujoks, B., & Emmerich, M. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2006.08.008 · Cited by 2,048
Mathematical models for cellular interactions in development I. Filaments with one-sided inputs
Lindenmayer, A. (1968) · Journal of Theoretical Biology · doi:10.1016/0022-5193(68)90079-9 · Cited by 1,620
Search‐based software test data generation: a survey
McMinn, P. (2004) · Software Testing, Verification and Reliability · doi:10.1002/stvr.294 · Cited by 1,368
Takagi, H. (2001) · Proceedings of the IEEE · doi:10.1109/5.949485 · Cited by 1,327
Procedural modeling of buildings
Müller, P., Wonka, P., Haegler, S., Ulmer, A., & Van Gool, L. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141931 · Cited by 950
Search-based software engineering
Harman, M., & Jones, B. F. (2001) · Information and Software Technology · doi:10.1016/s0950-5849(01)00189-6 · Cited by 914
Computer rendering of stochastic models
Fournier, A., Fussell, D., & Carpenter, L. (1982) · Communications of the ACM · doi:10.1145/358523.358553 · Cited by 826
Artificial evolution for computer graphics
Sims, K. (1991) · Proceedings of the 18th annual conference on Computer graphics and interactive techniques · doi:10.1145/122718.122752 · Cited by 741 · cited 1×
“Similarly, generate-and-test methods such as evolutionary algorithms are widely used for PCG in nongame domains, for example in the generation of procedural art; the evaluation function for this very subjective content may be a human observer who specifies which individuals survive each generation [16], [17] or a full…”
MethodCompositional pattern producing networks: A novel abstraction of development
Stanley, K. O. (2007) · Genetic Programming and Evolvable Machines · doi:10.1007/s10710-007-9028-8 · Cited by 713
Self-citationTexturing and modeling: a procedural approach
(1995) · Choice Reviews Online · doi:10.5860/choice.32-5129 · Cited by 659
Representations for Genetic and Evolutionary Algorithms
(2006) · Springer eBooks · doi:10.1007/3-540-32444-5 · Cited by 470
Experience-Driven Procedural Content Generation
Yannakakis, G. N., & Togelius, J. (2011) · IEEE Transactions on Affective Computing · doi:10.1109/t-affc.2011.6 · Cited by 470
Self-citationArtificial evolution for computer graphics
Sims, K. (1991) · ACM SIGGRAPH Computer Graphics · doi:10.1145/127719.122752 · Cited by 435
A Taxonomy for Artificial Embryogeny
Stanley, K. O., & Miikkulainen, R. (2003) · Artificial Life · doi:10.1162/106454603322221487 · Cited by 425
Self-citationFaçade: An Experiment in Building a Fully-Realized Interactive Drama
Mateas, M., & Stern, A. (2003) · Cited by 420
Rabin, S. (2003) · Cited by 405
Ludologists love stories, too: notes from a debate that never took place
Frasca, G. (2003) · DiGRA Digital Library · doi:10.26503/dl.v2003i1.64 · Cited by 382
Three ways to grow designs: a comparison of embryogenies for an evolutionary design problem
Bentley, P. J., & Kumar, S. (1999) · UCL Discovery (University College London) · Cited by 289
Towards automatic personalised content creation for racing games
Togelius, J., De Nardi, R., & Lucas, S. M. (2007) · 2007 IEEE Symposium on Computational Intelligence and Games · doi:10.1109/cig.2007.368106 · Cited by 283
Self-citationRepresentations for Genetic and Evolutionary Algorithms
Rothlauf, F. (2006) · Representations for Genetic and Evolutionary Algorithms · doi:10.1007/3-540-32444-5_2 · Cited by 257
An experiment in automatic game design
Togelius, J., & Schmidhuber, J. (2008) · 2008 IEEE Symposium On Computational Intelligence and Games · doi:10.1109/cig.2008.5035629 · Cited by 246
Self-citationGraphical applications of L-systems
Prusinkiewicz, P. (1986) · doi:10.20380/gi1986.44 · Cited by 236
The definition and rendering of terrain maps
Miller, G. S. P. (1986) · ACM SIGGRAPH Computer Graphics · doi:10.1145/15886.15890 · Cited by 234
Modeling Player Experience for Content Creation
Pedersen, C., Togelius, J., & Yannakakis, G. N. (2010) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2010.2043950 · Cited by 231
Self-citationBourg, D. M., & Seemann, G. (2004) · Cited by 218
Analyzing the expressive range of a level generator
Smith, G., & Whitehead, J. (2010) · Proceedings of the 2010 Workshop on Procedural Content Generation in Games · doi:10.1145/1814256.1814260 · Cited by 204 · cited 1×
“However, it is also important to assess other properties of content generators, such as characterizingtheirexpressiverange:thevariationinthecontent generatedabyaspecificcontentgenerator[ 78 ].Conversely, it is important to analyze the range of domains for which a particular content generator can be effective.”
BackgroundPicbreeder: evolving pictures collaboratively online
Secretan, J., Beato, N., D Ambrosio, D. B., Rodriguez, A., Campbell, A., & Stanley, K. O. (2008) · Proceedings of the SIGCHI Conference on Human Factors in Computing Systems · doi:10.1145/1357054.1357328 · Cited by 192
Self-citationA connection between partial symmetry and inverse procedural modeling
Bokeloh, M., Wand, M., & Seidel, H.-P. (2010) · ACM Transactions on Graphics · doi:10.1145/1778765.1778841 · Cited by 177
The advantages of generative grammatical encodings for physical design
Hornby, G. S., & Pollack, J. B. (2002) · Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546) · doi:10.1109/cec.2001.934446 · Cited by 176
Automatic Content Generation in the Galactic Arms Race Video Game
Hastings, E. J., Guha, R. K., & Stanley, K. O. (2009) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2009.2038365 · Cited by 173
Self-citationModeling player experience in Super Mario Bros
Pedersen, C., Togelius, J., & Yannakakis, G. N. (2009) · 2009 IEEE Symposium on Computational Intelligence and Games · doi:10.1109/cig.2009.5286482 · Cited by 166
Self-citation(1983) · Elsevier eBooks · doi:10.1016/b978-0-408-01302-4.50005-7 · Cited by 156
Search-Based Procedural Content Generation
Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12239-2_15 · Cited by 156
Self-citationKimbrough, S. O., Koehler, G. J., Lu, M., & Wood, D. H. (2008) · European Journal of Operational Research · doi:10.1016/j.ejor.2007.06.028 · Cited by 145
The 2010 Mario AI Championship: Level Generation Track
Shaker, N., Togelius, J., Yannakakis, G. N., Weber, B. G., Shimizu, T., Hashiyama, T., Sorenson, N., Pasquier, P., Mawhorter, P. A., Takahashi, G., et al. (2011) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2011.2166267 · Cited by 143
Self-citationEvolving content in the Galactic Arms Race video game
Hastings, E. J., Guha, R. K., & Stanley, K. O. (2009) · 2009 IEEE Symposium on Computational Intelligence and Games · doi:10.1109/cig.2009.5286468 · Cited by 142
Self-citationCellular automata for real-time generation of infinite cave levels
Johnson, L., Yannakakis, G. N., & Togelius, J. (2010) · Proceedings of the 2010 Workshop on Procedural Content Generation in Games · doi:10.1145/1814256.1814266 · Cited by 137
Self-citationEvolutionary computation and games
Lucas, S. M., & Kendall, G. (2006) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2006.1597057 · Cited by 133
Towards affective camera control in games
Yannakakis, G. N., Martínez, H. P., & Jhala, A. H. (2010) · User Modeling and User-Adapted Interaction · doi:10.1007/s11257-010-9078-0 · Cited by 128
Self-citationTowards a Generic Framework for Automated Video Game Level Creation
Sorenson, N., & Pasquier, P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12239-2_14 · Cited by 110
Towards multiobjective procedural map generation
Togelius, J., Preuss, M., & Yannakakis, G. N. (2010) · Proceedings of the 2010 Workshop on Procedural Content Generation in Games · doi:10.1145/1814256.1814259 · Cited by 110
Self-citationMultiobjective exploration of the StarCraft map space
Togelius, J., Preuss, M., Beume, N., Wessing, S., Hagelback, J., & Yannakakis, G. N. (2010) · Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games · doi:10.1109/itw.2010.5593346 · Cited by 108
Self-citationExploratory modeling with collaborative design spaces
Talton, J. O., Gibson, D., Yang, L., Hanrahan, P., & Koltun, V. (2009) · ACM Transactions on Graphics · doi:10.1145/1618452.1618513 · Cited by 106
Machado, P., & Cardoso, A. (1998) · Lecture notes in computer science · doi:10.1007/10692710_23 · Cited by 106
Variations Forever: Flexibly generating rulesets from a sculptable design space of mini-games
Smith, A. M., & Mateas, M. (2010) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/itw.2010.5593343 · Cited by 105
An affectively driven planner for synthetic characters
Aylett, R. S., Dias, J., & Paiva, A. (2006) · Cited by 99
Making Racing Fun Through Player Modeling and Track Evolution
Togelius, J., Nardi, R. D., & Lucas, S. M. (2006) · CogPrints (University of Southampton) · Cited by 98
Self-citationControlled Procedural Terrain Generation Using Software Agents
Doran, J., & Parberry, I. (2010) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2010.2049020 · Cited by 98
Automatic generation and evaluation of recombination games
Browne, C. (2008) · Cited by 92
Self-citationA computational model of narrative generation for suspense
Cheong, Y.-G. (2006) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 81
Automatic Design of Balanced Board Games
Hom, V., & Marks, J. (2007) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v3i1.18777 · Cited by 79
Computational Intelligence in Games
Baba, N. (2001) · Studies in fuzziness and soft computing · doi:10.1007/978-3-7908-1833-8 · Cited by 77
Integrating procedural generation and manual editing of virtual worlds
Smelik, R., Tutenel, T., de Kraker, K. J., & Bidarra, R. (2010) · Proceedings of the 2010 Workshop on Procedural Content Generation in Games · doi:10.1145/1814256.1814258 · Cited by 76
A connection between partial symmetry and inverse procedural modeling
Bokeloh, M., Wand, M., & Seidel, H. (2010) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/1833349.1778841 · Cited by 70
Declarative optimization-based drama management in interactive fiction
Nelson, M. J., Mateas, M., Roberts, D. L., & Isbell, C. L. (2006) · IEEE Computer Graphics and Applications · doi:10.1109/mcg.2006.55 · Cited by 60
Ebert, D. S., Musgrave, F. K., Peachey, D., Perlin, K., & Worley, S. (2011) · Cited by 58
Automatic generation of game elements via evolution
Ashlock, D. (2010) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/itw.2010.5593341 · Cited by 49
How to model and augment player satisfaction : a review
Yannakakis, G. N. (2008) · OAR@UM (University of Malta) · Cited by 49
Self-citationEvolution of Artificial Terrains for Video Games Based on Accessibility
Frade, M., de Vega, F. F., & Cotta, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12239-2_10 · Cited by 48
Beyond the cybernetic jam fantasy: the continuator
Pachet, F. (2004) · IEEE Computer Graphics and Applications · doi:10.1109/mcg.2004.1255806 · Cited by 47
Polymorph: A Model for Dynamic Level Generation
Jennings-Teats, M., Smith, G., & Wardrip-Fruin, N. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v6i1.12417 · Cited by 36
SWAP ADJACENT GEMS TO MAKE SETS OF THREE: A HISTORY OF MATCHING TILE GAMES
Juul, J. (2007) · Artifact · doi:10.1080/17493460601173366 · Cited by 34
NEAT Particles: Design, Representation, and Animation of Particle System Effects
Hastings, E. J., Guha, R. K., & Stanley, K. O. (2007) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/cig.2007.368092 · Cited by 33
Self-citationEvolving A Diverse Collection of Robot Path Planning Problems
Ashlock, D., Manikas, T. W., & Ashenayi, K. (2006) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2006.1688530 · Cited by 27
Evolution of L-systems for Compact Virtual Landscape Generation
Ashlock, D., Gent, S. P., & Bryden, K. M. (2005) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2005.1555041 · Cited by 25
Story Planning with Vignettes: Toward Overcoming the Content Production Bottleneck
Riedl, M. O., & Sugandh, N. (2006) · Lecture notes in computer science · doi:10.1007/978-3-540-89454-4_23 · Cited by 25
Evolving 3D Buildings for the Prototype Video Game Subversion
Martin, A., Lim, A., Colton, S., & Browne, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12239-2_12 · Cited by 24
Self-citationCombining local and global optimisation for virtual camera control
Burelli, P., & Yannakakis, G. N. (2010) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/itw.2010.5593328 · Cited by 17
Self-citationRelevant Information as a formalised approach to evaluate game mechanics
Salge, C., & Mahlmann, T. (2010) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/itw.2010.5593344 · Cited by 16
Toward proccedural decorative ornamentation in games
Whitehead, J. (2010) · doi:10.1145/1814256.1814265 · Cited by 16
Evolutionary Algorithm for Generation of Entertaining Shinro Logic Puzzles
Oranchak, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12239-2_19 · Cited by 15
Authoring an Interactive Narrative with Declarative Optimization-Based Drama Management
Nelson, M., Ashmore, C., & Mateas, M. (2006) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v2i1.18761 · Cited by 13
Interactive genetic engineering of evolved video game content
Hastings, E. J., & Stanley, K. O. (2010) · doi:10.1145/1814256.1814264 · Cited by 12
Self-citationGlobal Search for Occlusion Minimization in Virtual Camera Control
Burelli, P., & Yannakakis, G. N. (2010) · IT University Of Copenhagen (IT University of Copenhagen) · Cited by 3
Self-citation
Research works printed but not linked: 9
- golding, 2010, Building blocks: Artist driven procedural buildings, Proc Present Game Develop Conf
- compton, 2010, Remarks during a panel session at the FDG workshop on PCG
- mallett, 1998, Zillions of Games
- wardrip-fruin, 2009, Expressive Process
- togelius, 2010, Proc EvoAppl, 6024
- olsen, 2004, Realtime procedural terrain generation
- kernighan, 1999, The Practice of Programming
- smelik, 2010, Proc Found Digit Games
- miikkulainen, 2006, Computational Intelligence Principles and Practice
Cited by
Gatt, A., & Krahmer, E. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5477 · Cited by 776
“…a few endeavours to enhance the variety of linguistic expressions used in virtual environments (e.g., Orkin & Roy, 2007), nlg technology is relatively unrepresented in research on games, despite significant progress on dynamic content generation in game environments (e.g., Togelius et al., 2011).”
BackgroundDesigning neural networks through neuroevolution
Stanley, K. O., Clune, J., Lehman, J., & Miikkulainen, R. (2019) · Nature Machine Intelligence · doi:10.1038/s42256-018-0006-z · Cited by 689
Self-citationExperience-Driven Procedural Content Generation
Yannakakis, G. N., & Togelius, J. (2011) · IEEE Transactions on Affective Computing · doi:10.1109/t-affc.2011.6 · Cited by 470
Self-citationProcedural Content Generation via Machine Learning (PCGML)
Summerville, A., Snodgrass, S., Guzdial, M., Holmgard, C., Hoover, A. K., Isaksen, A., Nealen, A., & Togelius, J. (2018) · IEEE Transactions on Games · doi:10.1109/tg.2018.2846639 · Cited by 425
Self-citationEvolving mario levels in the latent space of a deep convolutional generative adversarial network
Volz, V., Schrum, J., Liu, J., Lucas, S. M., Smith, A., & Risi, S. (2018) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3205455.3205517 · Cited by 239
Metadata
- Authors
- Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C.
- Affiliations
- IT University of Copenhagen (DK)
- University of Central Florida (US)
- Imperial College London (GB)
- Venue
- IEEE Transactions on Computational Intelligence and AI in Games
- Published
- 2011-09
- Volume
- 3
- Issue
- 3
- Pages
- 172-186
- ISSN
- 1943-068X (ISSN-L)
- 1943-0698
- OpenAlex
- W2168115594
- Cited by
- 706
- References
- 80
- Citations by year
- 2026: 38 · 2025: 44 · 2024: 49 · 2023: 28 · 2022: 37 · 2021: 40 · 2020: 66 · 2019: 64 · 2018: 45 · 2017: 48 · 2016: 61 · 2015: 47 · 2014: 63 · 2013: 39 · 2012: 32
- FWCI
- 40.87
- Type
- journal article
- Language
- en
- Open access
- Locations
- IEEE Transactions on Computational Intelligence and AI in Games (publishedVersion)
- Journal of International Crisis and Risk Communication Research (submittedVersion)
- Funders
- Engineering and Physical Sciences Research Council (EP/I001964/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Social Sciences › Sociology and Political Science › Digital Games and Media
- Keywords
- procedural content generation, evolutionary algorithms, metaheuristic search, game content generation, game design, board games
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.