Level Generation with Constrained Expressive Range

This research introduces a systematic approach to procedural content generation by utilizing expressive range analysis as a conceptual space for guiding level design. The primary thesis posits that by applying quality diversity principles to a constraint-based generator, developers can move beyond random generation to systematically explore and fill underrepresented regions within a defined metric space. This method enhances the diversity of generated content while providing a clearer understanding of a generator's specific capabilities and limitations.

The study utilizes a constraint-based generator, Sturgeon, to create Super Mario Bros. levels based on a corpus of 2,302 segments extracted from the Video Game Level Corpus. The methodology involves defining a two-dimensional expressive range based on density and difficulty metrics. Researchers implemented three distinct pattern templates—ring, block2, and nbr-plus—to constrain the generation process. The system employs a prioritized random selection strategy to target underrepresented cells, allocating 12 hours of generation time per template to compare performance metrics, including success rates, solve times, and a quantitative measure of level interestingness based on path length and jump frequency.

Key findings indicate a clear trade-off between structural constraint and generation efficiency. Highly constrained templates, such as the ring pattern, produced more structured levels but faced higher failure rates and longer solve times. Conversely, less restrictive templates like nbr-plus achieved significantly faster generation speeds but struggled to produce playable, interesting levels without additional guidance. The systematic traversal approach demonstrated superior coverage of the expressive range compared to purely random generation, confirming that targeted exploration effectively uncovers unique design variations that might otherwise remain inaccessible. The study concludes that this controlled, constraint-based exploration is a viable strategy for curating diverse training datasets and refining generative models.