Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning
arXiv:2607.12097 · doi:10.1145/3815598.3815619
The paper proposes a new "cake" representation that captures the dynamic, time‑based nature of video game levels and introduces a Playtrace Reconstructive Partitioning method to generate valid, diverse Sokoban levels using this representation.
Abstract
Video games are a dynamic medium experienced over time. While there are many Procedural Content Generation (PCG) approaches for generating video game levels, they often use representations that abstract away this dynamic nature. In this paper, we introduce a novel, domain-independent ``cake'' representation for game levels over time which implicitly encodes dynamic information. We present a novel level generation approach Playtrace Reconstructive Partitioning (PRP) specifically developed for this cake representation. We compare against six state-of-the-art PCG approaches in the game domain of \textit{Sokoban}, and find that our approach can generate valid levels without sacrificing solution diversity. We believe our cake representation more neatly encodes the implicit dynamic nature of games compared to existing representations, which allows for our domain-agnostic level generation algorithm PRP.
11 pages, 5 figures, ACM Conference on the Foundations of Digital Games