Constrained level generation through grammar-based evolutionary algorithms

Jose M. Font, Roberto Izquierdo, Daniel Manrique, Julian Togelius

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    This paper introduces an evolutionary method for generating levels for adventure games, combining speed, guaranteed solvability of levels and authorial control. For this purpose, a new graph-based two-phase level encoding scheme is developed. This method encodes the structure of the level as well as its contents into two abstraction layers: the higher level defines an abstract representation of the game level and the distribution of its content among different inter-connected game zones. The lower level describes the content of each game zone as a set of graphs containing rooms, doors, monsters, keys and treasure chests. Using this representation, game worlds are encoded as individuals in an evolutionary algorithm and evolved according to an evaluation function meant to approximate the entertainment provided by the game level. The algorithm is implemented into a design tool that can be used by game designers to specify several constraints of the worlds to be generated. This tool could be used to facilitate the design of game levels, for example to make professional-level content production possible for non-experts.

    Original languageEnglish (US)
    Title of host publicationApplications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings
    EditorsPaolo Burelli, Giovanni Squillero
    PublisherSpringer Verlag
    Number of pages16
    ISBN (Print)9783319312033
    StatePublished - 2016
    Event19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016 - Porto, Portugal
    Duration: Mar 30 2016Apr 1 2016

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016


    • Evolutionary computation
    • Genetic programming
    • Procedural content generation

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Constrained level generation through grammar-based evolutionary algorithms'. Together they form a unique fingerprint.

    Cite this