On Linking Level Segments
This addresses a specific issue for game designers in procedural content generation, offering a customizable solution to improve level creation, though it is incremental as it builds on existing segment-based methods.
The paper tackled the problem of concatenating level segments in procedural content generation, which often fails to produce completable levels and breaks in-game structures, by introducing a Markov chain and tree search algorithm that reliably finds links ensuring completability and structural integrity.
An increasingly common area of study in procedural content generation is the creation of level segments: short pieces that can be used to form larger levels. Previous work has used basic concatenation to form these larger levels. However, even if the segments themselves are completable and well-formed, concatenation can fail to produce levels that are completable and can cause broken in-game structures (e.g. malformed pipes in Mario). We show this with three tile-based games: a side-scrolling platformer, a vertical platformer, and a top-down roguelike. Additionally, we present a Markov chain and a tree search algorithm that finds a link between two level segments, which uses filters to ensure completability and unbroken in-game structures in the linked segments. We further show that these links work well for multi-segment levels. We find that this method reliably finds links between segments and is customizable to meet a designer's needs.