Procedural Constraint-based Generation for Game Development

  • Tristan Smith

Student thesis: Doctoral ThesisDoctor of Engineering (EngD)


Game designers produce structured content for games that is informed by both hard gameplay requirements and design desiderata they must track and fulfil. Procedural content generation techniques can help, but are often inflexible, unwieldy or opaque; it can be difficult to make precise alterations or predict the effect of individual changes. We contribute a novel combination of approaches and develop the ‘encode, evaluate, explore’ paradigm as a method for defining
and then refining generators’ output. We build on design space sculpting literature to directly describe a desired generation domain, and integrate a quantitative visualisation approach to inform designers’ alteration decisions. We use declarative constraint satisfaction, in the form of answer set solving, to directly describe a space of possible outputs in terms of the characteristics
of desirable solutions.
We present applications of the initial ‘encode’ portion of the approach in two different domains, that represent interesting structured generation problems and are informed by industry needs. First an adaptable, parameterisable solution for automated generation (and re-generation) of varied and increasingly-demanding combat sequences for action/combat games, by composing fitting selections of enemies under provided constraints. Also, a tool for complex level layout specifications for action-adventure games, drawing on playability constraints that include structural and temporal ‘lock-and-key’ dependencies from dungeon generation literature. We implement the ‘evaluate’ phase via quantitative expressive range analysis, and show accessible visual characterisations of the output space of the latter generator system that facilitate visualisation of both iterations that ‘explore’ the formulation and also comparisons with the outputs of another generator.
By applying the methodological cycle of encode, evaluate, explore, we improve on existing approaches in two relevant domains. This dissertation shows that declarative constraint-based generation combined with clear visualisations and fast iteration provides game developers a novel, effective approach to produce structured content, and suggests multiple avenues of further research.
Date of Award28 Jun 2023
Original languageEnglish
Awarding Institution
  • University of Bath
SponsorsNinja Theory Ltd
SupervisorJulian Padget (Supervisor) & Philip Willis (Supervisor)

Cite this