Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning

# Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning
Source: [https://arxiv.org/html/2607.12097](https://arxiv.org/html/2607.12097)
Emily HalinaDepartment of Computing Science, Alberta Machine Intelligence Institute \(Amii\), University of AlbertaEdmontonAlbertaCanada[ehalina@ualberta\.ca](https://arxiv.org/html/2607.12097v1/mailto:[email protected])Matthew GuzdialDepartment of Computing Science, Alberta Machine Intelligence Institute \(Amii\), University of AlbertaEdmontonAlbertaCanada[guzdial@ualberta\.ca](https://arxiv.org/html/2607.12097v1/mailto:[email protected])

\(2026\)

###### 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 ofSokoban, 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\.

PRP, playtrace reconstructive partitioning, cake representation, procedural content generation, level generation, Sokoban

††journalyear:2026††copyright:cc††conference:Foundations of Digital Games; August 10–13, 2026; Copenhagen, Denmark††booktitle:Foundations of Digital Games \(FDG ’26\), August 10–13, 2026, Copenhagen, Denmark††doi:10\.1145/3815598\.3815619††isbn:979\-8\-4007\-2495\-4/2026/08††isbn:978\-1\-4503\-XXXX\-X/2018/06††ccs:Computing methodologies Artificial intelligence††ccs:Computing methodologies Knowledge representation and reasoning## 1\.Introduction

Since the beginning of technical games research, there has been a question of how to represent video game levels\. Common solutions include tile and graph\-based representations\(Summervilleet al\.,[2016](https://arxiv.org/html/2607.12097#bib.bib25)\), memory\(Mawhorteret al\.,[2021](https://arxiv.org/html/2607.12097#bib.bib13)\), and images\(Snodgrass,[2018](https://arxiv.org/html/2607.12097#bib.bib14); Mirgati and Guzdial,[2023](https://arxiv.org/html/2607.12097#bib.bib15)\)\. All of these representations share a similarity: they treat levels as if they are static\. However, one of the fundamental features of video games is that they are dynamic: entities move and transform over time according to player input\. This means without an external source of dynamic information, it is impossible to guarantee that new levels have desired qualities, such as playability\.

There have been many prior approaches for addressing the discrepancy between static level representation and dynamic gameplay\. In the commonly used tile representation ofSuper Mario Bros\.from the Video Game Level Corpus \(VGLC\)\(Summervilleet al\.,[2016](https://arxiv.org/html/2607.12097#bib.bib25)\)the player path is encoded as a separate token onto an existing tile representation\(Summerville and Mateas,[2016](https://arxiv.org/html/2607.12097#bib.bib16)\)\. While this can help bias a generator towards playability, this representation is limited by its two\-dimensional nature\. For example, if the player backtracks to the same tile multiple times, it becomes impossible to represent the true path\. We can also encode dynamic information through hand\-authored or learned constraint information\(Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17); Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\), or by including an automated solver in a reward or evaluation function\(Khalifaet al\.,[2020](https://arxiv.org/html/2607.12097#bib.bib24)\)\. However, this does not change the level representation, instead approximating this dynamic information elsewhere in the generation process\. These approaches require the manual encoding of design information into constraints or functions, which could be burdensome or time\-consuming for developers, particularly for a new game domain\. If we could better address the discrepancy between existing static level representations and the true dynamic gameplay of video games, we could potentially improve generalizability across tasks such as level generation and automated game playing\. This could aid game designers aiming to implement these systems in their own games\.

In this paper, we formally define thecakerepresentation for representing levels over time, naturally encoding dynamic gameplay information\. A cake represents a playtrace of a level as a series ofkkdiscrete timesteps, where the global game state is recorded at each timestep\. These “slices” of game state represent the level over time, hence cake\. While similar temporal representations appear in prior work\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\), the cake representation is distinct in that each “temporal entity” is tracked separately over time, allowing for the automated encoding of game mechanics without separate hand\-authoring\. To showcase the strengths of the cake representation, we introduce a new method for level generation,Playtrace Reconstructive Partitioning\(PRP\) which takes advantage of the cake representation to generate valid levels\. Inspired by Tree\-based Reconstructive Partitioning\(Halina and Guzdial,[2023](https://arxiv.org/html/2607.12097#bib.bib20)\), PRP works by performing an adapted binary space partitioning across time over the cake representation, matching dynamic entities to generate both a level and its solution simultaneously\. We compare against six state\-of\-the\-art level generation approaches forSokoban, and find that PRP performed equivalently or better than these baselines in terms of playability and solution diversity without explicitly encoded constraints or reward signals\.

The contributions of this paper are as follows:

1. \(1\)The cake representation, a novel representation for game levels as slices of game state over time\.
2. \(2\)PRP, an algorithm which uses the cake representation to generate valid levels and their solutions simultaneously\.
3. \(3\)An evaluation of PRP in the game domain ofSokobanagainst six state\-of\-the\-art baselines\.
4. \(4\)An ablation study of PRP over different possible inputs, representing different potential levels of designer control\.
5. \(5\)Two case studies, one in an existing domain \(OvercookedAI\) and one in a novel game domain \(SkeleWalker\)\.

## 2\.Related Work

In this section, we discuss work on representing levels, and overview PCG approaches applied toSokoban, our evaluation domain\.

### 2\.1\.Level Representation

There exist many static level representations, including tiles\(Summervilleet al\.,[2016](https://arxiv.org/html/2607.12097#bib.bib25)\), graphs\(Kimet al\.,[2019](https://arxiv.org/html/2607.12097#bib.bib37)\), images\(Mirgati and Guzdial,[2023](https://arxiv.org/html/2607.12097#bib.bib15)\), and memory\(Mawhorteret al\.,[2021](https://arxiv.org/html/2607.12097#bib.bib13)\)\. Several of these representations explicitly encode dynamic information via affordances\. For example, the VGLC includes a “breakable” affordance which encodes the notion that a tile can break as inSuper Mario Bros\.\(Summervilleet al\.,[2016](https://arxiv.org/html/2607.12097#bib.bib25)\)\. Other approaches rely on the representation itself, as in tile embeddings\(Jadhav and Guzdial,[2021](https://arxiv.org/html/2607.12097#bib.bib33)\)and memory\-based representations\(Mawhorteret al\.,[2021](https://arxiv.org/html/2607.12097#bib.bib13)\)\. Still others use external rules or functions which act on the representation but are not encoded within it, such as constraints or re\-write rules\(Cooper,[2023](https://arxiv.org/html/2607.12097#bib.bib22)\)\. However, generally the level representation does not include sufficient information to fully encode a potential playthrough\.

Some prior level generation work has attempted to use videos as training data for machine learning\-based approaches in an attempt to encode dynamic information about the game state\(Guzdial and Riedl,[2016](https://arxiv.org/html/2607.12097#bib.bib44); Mirgati and Guzdial,[2023](https://arxiv.org/html/2607.12097#bib.bib15)\)\. However, these approaches do not generally consider dynamic information, instead representing each frame individually as an image\. World models, learned representations of an existing environment, implicitly encode level representation as pathways through the learned latent space\(Ha and Schmidhuber,[2018](https://arxiv.org/html/2607.12097#bib.bib35)\)\. While this representation is dynamic, there is no way at present to disentangle the level information from the representation of the game itself\.

A notable exception to the static representations discussed above is the representation defined by[Vandaraet al\.](https://arxiv.org/html/2607.12097#bib.bib43)in their work on Spacetime Level Generation using Sturgeon, an existing family of constraint\-based level generation approaches \(Sturgeon\-ST\)\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\. Vandara et al\. proposed a modification to Sturgeon over three\-dimensional space\-time blocks encoded as two\-dimensional film strips that represent a level and its solution over time\. They do not formally define their film strip representation, so we cannot clearly differentiate it from our cake representation \(defined below\)\. However, we note that their implementation does not track temporal entities, which form the bedrock of our representation\. Another major difference comes from the generation approach, which only considers local temporal constraints, meaning it can fail to respect global temporal constraints like there only being a single player entity\. Vandara et al\. addressed this through the addition of hand\-authored constraints for the first frame of generated gameplay\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\. As Sturgeon\-ST is the most similar prior approach we include it as a baseline in our evaluation\.

![Refer to caption](https://arxiv.org/html/2607.12097v1/x1.png)Figure 1\.Visualization of the PRP level generation pipeline\. As input the system requires a partial specification alongside a corpus of one or more source levels\. After processing the input into our cake representation, we perform PRP to assemble the output cake, then perform postprocessing to retrieve the output level\.Sokobangraphics by Kenney\.
### 2\.2\.PCG forSokoban

Sokobanis a well\-explored game domain for level generation\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. We identify two categories of prior approaches: those reliant on training data, and approaches reliant on human\-authored functions or other external information\. Our approach falls into the former category, as we draw the majority of the information required to generate levels from the cake representations derived from example playtraces of human\-authored levels\.

Level generation approaches that use training data fall under the category of PCG via Machine Learning \(PCGML\)\(Summervilleet al\.,[2018](https://arxiv.org/html/2607.12097#bib.bib30)\)\. Numerous PCGML approaches have been applied toSokoban\(Earleet al\.,[2021](https://arxiv.org/html/2607.12097#bib.bib39); Siperet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib21)\)\. A subset of these approaches are neural network\-based level generation approaches, which use various neural network architectures to model the level generation process\(Sulemanet al\.,[2017](https://arxiv.org/html/2607.12097#bib.bib40)\)\. Zakaria et al\.’s survey paper on PCGML forSokobanlevel generation is a foundational work comparing many of these existing approaches\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. As such, our evaluation is largely informed by their work\.

While some neural network\-based approaches have found success inSokoban, the domain can prove challenging without additional external information due to its strict global coherency constraints\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. We believe that our cake representation may be helpful to these approaches, as the representation contains more information on a game’s dynamics\. As a point of comparison, we use multiple neural network based approaches as baselines, including Path of Destruction\(Siperet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib21)\)and Long Short\-Term Memory Recurrent Neural Networks \(LSTM\)\(Sulemanet al\.,[2017](https://arxiv.org/html/2607.12097#bib.bib40)\)\.

The second category of approaches do not require training data for generation\. Instead, these approaches rely on human\-authored external signals such as functions or constraints\. For example, search\-based PCG approaches use a human\-authored fitness function to generate levels and have been applied toSokoban\(Schaa and Barriga,[2021](https://arxiv.org/html/2607.12097#bib.bib41)\)\. However, these approaches can suffer from slow inference speeds and convergence issues\. A natural extension of search\-based methods is the PCG via Reinforcement Learning \(PCGRL\) approach, in which an agent trains to make iterative changes to a level guided by an authored reward function\(Khalifaet al\.,[2020](https://arxiv.org/html/2607.12097#bib.bib24)\)\. While this approach requires a domain\-specific hand authored reward function to guide the training process, Zakaria et al\. found it to be highly performant in theSokobandomain\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. As such, we include two top performing PCGRL settings as baselines\.

Constraint\-based methods use authored constraints or re\-write rules to generate levels\(Beukmanet al\.,[2023](https://arxiv.org/html/2607.12097#bib.bib42); Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17)\)\. While these approaches can guarantee global coherency by enforcing playability constraints, these constraints require expert domain knowledge to author\. In comparison, our approach requires relatively little hand\-authored information outside of processing to the cake representation\. We use the constraint\-based method Sturgeon\-MKIII as a baseline\(Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17)\), as it is a modern example of a constraint\-based method\.

## 3\.System Overview

In this section, we discuss our cake representation and Playtrace Reconstructive Partitioning \(PRP\)\. Figure[1](https://arxiv.org/html/2607.12097#S2.F1)depicts a visualization of the PRP level generation pipeline based on existing level data, usingSokobanfor ease of visualization\. As input, the generation process requires two sources of dynamic information\. The first is a corpus of source levels with corresponding playtrace data from which to draw temporal entities\. The second is a partial specification for the output level, which may be empty\. Both inputs are processed intocakerepresentations that encode the complete state of the level at every timestep as slices over time\. We note that in practice, the source levels may be processed into the cake representation and stored, particularly in domains where the processing may be computationally expensive\. PRP takes these cake representations as input, and matches objects from the source levels into a partially specified output via a Binary Space Partitioning \(BSP\) over time\. BSP is an existing level generation approach that partitions spaces from existing levels to fill in sections of a new level\(Snodgrass,[2019](https://arxiv.org/html/2607.12097#bib.bib47); Halina and Guzdial,[2023](https://arxiv.org/html/2607.12097#bib.bib20)\)\. PRP yields an output cake which is processed into the final output level via a domain\-specific post\-processing step\.

### 3\.1\.Input & Requirements

Our generation pipeline requires two sources of dynamic information: a partial specification of the output level, and a corpus of one or more source levels with playtrace information\. The partial specification partially specifies the output level, constraining our pattern\-matching process\. This partial specification can include an arbitrary amount of detail to allow for flexible designer control of the output levels\. For example, a valid partial specification could be a player path or entities defining structure such as walls\. The corpus of source levels provides the temporal entities used by PRP to fill in the partial specification of the output level\. For each source level in the corpus, PRP requires a playtrace of said level which the algorithm uses to inform its generation\. We make a number of assumptions, outlined in the next subsection, based on this playtrace which makes PRP a domain\-agnostic level generation algorithm\. We argue that this allows PRP to better support designers of a novel game\.

### 3\.2\.Cake Representation

![Refer to caption](https://arxiv.org/html/2607.12097v1/x2.png)Figure 2\.A visualized segment of a cake representation of a playtrace for a human\-authored level\. Note that the cake representation for this paper uses a character\-based tile format\. Each game state is separated by a delimiter token to denote beginning and end points\.Figure[2](https://arxiv.org/html/2607.12097#S3.F2)depicts a segment of a cake representation for an exampleSokobanlevel playtrace\. We define a cake representation for a given game level as ak×n×mk\\times n\\times mtensor representing a Markovian sequence ofn×mn\\times mgame states overkktimesteps\. Within the cake representation, we define temporal entities as distinct entities of a typeTTwhich persist between timesteps\. For example, a temporal entity inSokobancould be the player, or an individual box, with their types being player and box respectively\. We note that in some cases, like the walls inSokoban, it may be useful to consider a temporal entity that takes up more than one spatial position\.

Our representation makes three assumptions\. The first is that the sequence of states is Markovian, meaning that each state contains all the information necessary to predict the next state independently\. This is necessary, as otherwise the representation would not encode the dynamic information of the game\. The second is that the representation must delineate between types of temporal entities over time\. The token\-based encoding of a game level mostly covers this assumption, and is a standard approach for most data\-based level generation\. The third is that it must track temporal entities over time, meaning we can tell when an entity has moved to a different location or transformed from one type to another\. For example, inSokobanwe have a box type which transforms into a solved box when placed on a goal\. Notably, a solved box can transform back into a box if pushed from its current position, which is required for certain solutions\. This third assumption encodes domain\-specific knowledge, but this knowledge can be learned\(Guzdialet al\.,[2017](https://arxiv.org/html/2607.12097#bib.bib46)\)\.

### 3\.3\.Playtrace Reconstructive Partitioning

Input:

kp×np×mpk\_\{p\}\\times n\_\{p\}\\times m\_\{p\}partial specification cake

PP, set of source cakes

SS
initialize output

OOas empty

kp×np×mpk\_\{p\}\\times n\_\{p\}\\times m\_\{p\}tensor

for**temporal entity*​p∈P\\textup\{temporal entity \}p\\in P*do

populate

OOwith

pp
end for

for*typeT∈ST\\in Sin order ofSelectionPolicy\(\)*do

for*temporal entitys∈Ss\\in Sof typeTT*do

matches=

\{\}\\\{\\\}
for*pos=\(z,x,y\)∈O=\(z,x,y\)\\in O*do

if*MatchesAt\(ss, pos\)*then

addpostomatches

end if

end for

if*matches≠\\neq\{\}\\\{\\\}*then

pos

←\\leftarrowsample frommatches

populate

OOwith

ssatpos

end if

end for

end for

Return:output cake

OO

Algorithm 1Playtrace Reconstructive PartitioningAlgorithm 1 describes Playtrace Reconstructive Partitioning \(PRP\)\. This algorithm relies on two sources of domain knowledge, encoded by the Selection Policy and MatchesAt functions, which we describe in detail below\. The algorithm takes in two sources of input: a partial specification processed into the cake representationPP, and a set of cake representations of source levelsSSfrom which to draw temporal entities\. To begin, we initialize the output as specified by the dimensions and content of the partial specification cake\. This process involves creating an emptykp×np×mpk\_\{p\}\\times n\_\{p\}\\times m\_\{p\}tensorOO, then populating the tensor with each of the temporal entities present in the partial specification\. If the partial specification is empty, the dimensions ofOOare determined by temporal entity selection\.

The first piece of domain knowledge required by PRP takes the form of the Selection Policy function, which returns an ordering over the types of temporal entities present in a cake representation\. This is domain\-specific as a particular set of types are only shared by a particular game domain\. For example, forSokobanwe have the player, the boxes, solved boxes, goals, walls, and empty tiles\. We note that this ordering could be arbitrary but in practice it makes sense to place the types that most constrain the output earlier in this ordering\. In particular, inSokobanwe used an ordering of players, boxes, and then all other types tied for third\.

We iterate through the typesTTof temporal entities based on the Selection Policy\. For each typeTT, we then iterate through all temporal entitiesssof typeTTinSS\. For each temporal entitysswe attempt to match it toOOusing the MatchesAt function\. This is a domain\-specific matching function, which indicates if a temporal entityssfromSScan exist in a particular position in time inOO\. These represent global coherency constraints, similar to the ones used by Sturgeon\-ST\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\. For each temporal entityss, if it matches with the current output cakeOOwe add it to a set of matches on a per\-entity basis\. If there are multiple matches we uniformly sample from them to place the entityssin the output cakeOOat a particular position in time\. The process continues until we run out of temporal entities to add and types of temporal entities\. There is one special case in this function, which is that if a temporal entityssis stationary spatially throughout all timesteps and occupies multiple positions, we run BSP on it, allowing us to break the temporal entity apart along the space axes if necessary for matching\.

As a practical example inSokoban, consider a case with a partial specification of just a player path\. From there, the algorithm would attempt to add other players to the output CakeOOand fail due to the MatchesAt global constraint of a single player\. Next, it would attempt to add in as many boxes as possible, where the boxes’ paths \(their temporal information\) matches with the player path\. In other words, the player could have pushed these boxes by walking along the provided player path\. From there, all other entities are added until the output cake has an entity in each position\. After this process, we return the output cake, a representation that captures both the generated level and an associated playtrace\.

There is one additional case not covered by the above pseudocode, which is that the generation process can fail\. Failure in this case means an output cake that includes null tokens, i\.e\., not all positions have been filled with temporal entities\. For example, this can happen in the case when a selected player path does not match with any other information fromSS\. As the null token is domain\-agnostic, this failure check is also domain\-agnostic, though additional failure cases may be added based on a domain\.

### 3\.4\.Postprocessing Output Cake

After PRP completes we have an output cake containingkkframes of level information across time\. To transform this representation into the final level we could simply take the first slice of the cake, which represents the initial state of the generated level\. In the case of this paper, we perform this simple post\-processing step\. However, there are many other possible ways to use the additional information in the cake representation when constructing the final output level\. For example, in a game likeSokoban, we could automatically take the level at a later, partially solved state, and return this as an “easier” version of the same level\.

### 3\.5\.SokobanImplementation

This subsection outlines the details and justifications of our design choices for the pre\-processing and post\-processing steps of ourSokobanPRP implementation, as well as the three aspects of domain\-specific knowledge: the cake representation processing, the Selection Policy, and the MatchesAt function\.

For pre\-processing, as theSokobaninput levels were already on a tile\-based grid, we were able to perform a one\-to\-one transfer of each tile type to a text representation\. This text representation directly maps each tile type to a specific text character\. We used an existing dataset of twelve7×77\\times 7human authored source levels for our approach which has been used in prior work for evaluating existing PCG approaches forSokoban\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. We ran a breadth\-first search solver to collect playtrace information, represented in the form of a series of inputs\. Notably, this solver isnota required component of PRP, and was simply used to find the shortest possible solution for eachSokobanlevel\. PRP can generate levels with playtraces from arbitrary sources, such as human playthrough data\. We demonstrate this in our case studies below\. We used the shortest possible solution to avoid biasing the generator to create more complex levels through using longer than necessary input paths, and to reduce computation time when solving each level\.

We processed the playtraces into the cake representation by a custom implementation ofSokoban’s logic, with each player move representing a new slice in each cake\. The text\-based representation of each source level, alongside their corresponding cake representations, can be found in the project’s Github repository111https://github\.com/emily\-halina/PRP\-Sokoban\. For post\-processing, we took the first slice of each output cake created by PRP if it contained boxes\. If it did not contain boxes, we considered the level trivial and discarded it\.

For the Selection Policy for temporal entities we order in terms of dynamism\. InSokoban, the player is inherently the most dynamic entity, as it moves each timestep, and as such we order the player type first\. The next most dynamic entity type is the box, which we order second, followed by all non\-moving entities\.

For the MatchesAt function, we specified three constraints\. The first was that only one player token was allowed at any given timestep\. The second is that no player, box, or wall could occupy the same space at the same timestep\. The third is that no part of the temporal entity went out\-of\-bounds of the dimensions of the output cakeOO\.

When performing generation forSokoban, we discarded trivial generated levels which contained no boxes\. We chose to consider these levels as failed generations as they are by default solved\. We report approximate generation times and failure rates in the Ablation subsection of the Evaluation section\.

## 4\.Evaluation

In this section we overview the evaluation of PRP in the domain ofSokoban\. To evaluate our approach, we compared against six baselines\. These baselines were Path of Destruction \(PoD\)\(Siperet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib21)\), Sturgeon\-MKIII\(Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17)\), Sturgeon\-ST\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\), two PCGRL implementations\(Khalifaet al\.,[2020](https://arxiv.org/html/2607.12097#bib.bib24)\), and an LSTM\-based recurrent neural network approach\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. The implementation details and parameters for each baseline are covered in the Baselines subsection\.

The majority of our evaluation is based on Zakaria et al\.’s survey paper on deep learning approaches forSokoban\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. We chose to base our evaluation on this work as it represents the most up\-to\-date and rigorous study of level generation approaches forSokoban\. As such, we report results directly from their paper for the PCGRL and LSTM approaches, and adapt their metrics for comparison purposes\. To supplement these results, we draw directly on corpora of levels from prior work for PoD and Sturgeon, which are approaches not evaluated by Zakaria et al\. We chose to use existing corpora rather than re\-implementing these approaches and regenerating populations of levels to maintain consistency on which future work can build\. We ran Sturgeon\-ST with minor implementation adjustments on our training levels as the original Sturgeon\-ST only gave the outputs for a single Sokoban training level\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\.

Alongside our baseline evaluation, we wanted to evaluate the effects of changing the partial specification provided to our approach\. We therefore identified three partial specifications and performed an ablation study over them\.

### 4\.1\.Baselines

#### 4\.1\.1\.Path of Destruction \(PoD\)

Path of Destruction \(PoD\) is a level generation approach that iteratively translates random noise into a playable level in a process similar to diffusion models\(Siperet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib21)\)\. At each timestep, a repair network takes the current tile position and level state and returns an edit to make at the given position\. The current tile position is then updated, whether at random or sequentially, and the process repeats\. This repair network is trained by iteratively “destroying” solvable levels, hence the name\. We sampled 1000 generated levels from an existing corpus of solvable PoD generated levels provided by the authors of\(Siperet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib21)\), since the loop in theory does not end until the level is solvable\. The levels in the corpus were generated with an observation and goal size of five\. PoD does not directly encode any dynamic information in its model, but this implementation had an additional external check for solvability before generation ended, representing a distinct way of authoring dynamic information into the generation process\.

#### 4\.1\.2\.Sturgeon\-MKIII

Sturgeon is a group of level generation approaches designed to enable constraint\-based level generation\(Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17)\)\. In particular, Sturgeon\-MKIII generates both a level and a playtrace simultaneously through tile re\-write rules and constraints\. These tile re\-write rules are a hand\-authored representation of the game’s dynamics\. Thus this baseline represents an alternative way of representing dynamic information in the level generation process\. We sampled 1000 generatedSokobanlevels from the “solvable” section of the Generated Game Level Corpus \(GGLC\)\(Bazzaz and Cooper,[2025](https://arxiv.org/html/2607.12097#bib.bib23)\), which were generated with these tile\-rewrite rules\(Cooper,[2023](https://arxiv.org/html/2607.12097#bib.bib22)\)\. These levels were generated with solvability as a constraint, and each level contains two boxes and two goals\. Notably, these levels had a size of8×88\\times 8rather than the7×77\\times 7of the other approaches\. While this limitation may lead to a slight difference in the number of unique solutions present in each level, this is strictly an advantage for Sturgeon in terms of population diversity\. This is because there are more possible levels in an8×88\\times 8grid\.

#### 4\.1\.3\.Sturgeon Spacetime \(Sturgeon\-ST\)

Sturgeon\-ST is a level generation approach which modifies Sturgeon to act over three\-dimensional space\-time blocks encoded as two\-dimensional film strips\(Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\. As Sturgeon supports global constraints, Stugeon\-ST introduces additional hand\-authored constraints to allow for more controllability\. Because the implementation of Sturgeon\-ST we had access to could only take in a single level as input at a time, we generated 84 levels from each training level to get as close to 1000 as possible, yielding 1008 generated levels\. For each generated level, we specified that there can be only one player token in the first frame to ensure playability, and that the number of boxes in the first frame must equal the number of boxes found in the respective training level\. This constraint was a necessary addition, as without it the approach generated levels without any boxes\. We also specified each level to have a maximum solution length of 20, though notably this was an upper bound, and some generated levels had shorter solutions\. We chose this solution length as it was the solution length used in the author’sSokobancase study, and represented an upper bound on the solution lengths present in the training data\. We included Sturgeon\-ST as it is the most related prior work, similarly defining levels over time, but reliant on Sturgeon for generation and with additional authored global constraints\.

#### 4\.1\.4\.PCG via Reinforcement Learning \(PCGRL\)

PCG via Reinforcement Learning \(PCGRL\) is a level generation approach that models the generation process as a Markov Decision Process \(MDP\), then attempts to learn an agent to solve the MDP\. The goal of the learned agent is to maximize the sum of expected rewards while interacting in the environment\. The reward of a given level state is in part based on the level’s path length and solvability, which is assessed by an external BFS solver\. Thus this represents another distinct approach for representing dynamic information, not explicitly in the level generation process but while training the level generator\.

For PCGRL, we directly report the results from\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)for comparison, which evaluated 10000 generated levels for each PCGRL condition\. In particular, we selected two conditions to report: Turtle and Wide\. The difference between the two conditions is the form of the observation and action set for the agent\. In the Turtle condition, the agent has a position in the level, and take actions to move locations orthogonally or edit the tile at its specified location\. In the Wide condition, the agent can edit any tile freely, and takes actions in the form of \(position, tile to edit\)\. We chose these conditions as they performed best in terms of diversity and playability among the PCGRL conditions reported by Zakaria et al\.\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\.

#### 4\.1\.5\.Long Short\-Term Memory \(LSTM\)

Long Short\-Term Memory Recurrent Neural Networks \(LSTM\) are a type of neural network applied to level generation\. On a high level, LSTMs applied to level generation work by generating tiles sequentially, commonly in a “snake”\-like pattern\(Summerville and Mateas,[2016](https://arxiv.org/html/2607.12097#bib.bib16)\)\. As the name suggests, the defining characteristic of LSTMs is the memory unit, which holds pieces of input in memory for a learned amount of time\. This helps LSTMs generate content with sequential structure, such as game levels\.

For the LSTM generator, as with the PCGRL approaches, we directly report the results from\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)over 10000 generated levels\. In particular, we report on the condition which includes sampling level conditions from a Gaussian Mixture Model \(GMM\)\. We chose to report this condition as it performed best among the LSTM variants evaluated by Zakaria et al\. In their implementation, the network had two LSTM layers with a hidden size of 128 each, and a fully connected layer for output\. For more details regarding the implementation of the network and the GMM condition sampling, see Zakaria et al\.’s paper\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\. We included an LSTM as it represents a common PCGML approach that does not encode any dynamic information\.

Table 1\.Comparison of PRP against our baseline approaches across our metrics\. We group the approaches in terms of the original Human training levels, the approaches where we collected the metrics ourselves, the reported metrics, and our own approach\. We normalize the unique solutions and signatures based on the number of levels generated by each approach\. The highest values in each column are bolded, excluding the human dataset results\. Baseline values taken from\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)are denoted by †\. \(∼\\sim\) denotes the approach was run using a stochastic policy\. The LSTM values are averaged across five training runs\.Table 2\.Ablation study of PRP conditions based on altering the input partial specification\. The highest values in each column are bolded\.

### 4\.2\.Metrics

To evaluate the performance of each generator we aimed to examine two aspects of a level’s quality: playability and diversity\. Notably, these metrics were adapted from\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)to ensure consistency between their results and ours, though some had to be reimplemented according to the descriptions in their paper\.

We define playability as the level being possible to complete, i\.e\., there is some sequence of inputs such that the level reaches a solved state \(all boxes are solved boxes\)\. To measure playability, we implemented a Breadth\-First Search \(BFS\) solver which exhaustively visited every unique state of each level until all solutions were found\. Notably, this solver was only used for computing the evaluation metrics,notas part of the PRP level generation pipeline\. We consider a level playable if the solver finds at least one solution\. We consider a solution unique if every state encountered along the path to the solution was also unique, discounting solutions which include cycles of states\. The solver logged each encountered solution in order of length, which we use for our diversity metrics\.

![Refer to caption](https://arxiv.org/html/2607.12097v1/x3.png)Figure 3\.Three randomly selected generated PRP levels from each condition\.Diversity refers to both the aesthetic differences between levels in a population, as well as the differences between their solutions\. To capture both of these aspects of diversity, we used four different metrics\. The first isDuplicates, which simply counts the duplicate levels found within a population\. This metric identifies the rate at which a generator produces unique levels\. The second isTile Diversity, which measures the percentage of tiles which differ within the population of levels on average\. We measure this percentage by calculating the Hamming distance, or edit\-distance between each unique pair of levels in the population\. The third isUnique Solutions, which measures the rate of unique solutions found within a population, which we divided by the total number of levels in each population\. This gives a cursory measure of how “unique” generated levels are compared to one another, but is an imperfect way of measuring uniqueness on its own\. An example of a potential problem with measuring solution diversity using only the unique solution count is that two solutions can take very different paths, but ultimately end up pushing the boxes in the same directions to solve the level\. To get around this issue, we include our last metricUnique Signatures, in which solutions are generalized into a rotation and flip invariant representation which condenses the solution path to only the directions in which boxes are pushed\. For more details on the implementation of unique signatures and the justification behind using this metric, see Zakaria et al\.’s paper\(Zakariaet al\.,[2022](https://arxiv.org/html/2607.12097#bib.bib18)\)\.

### 4\.3\.Ablation

We wanted to investigate the effects of varying the partial specification as a source of input for our approach\. Intuitively, varying the partial specification could drastically change the population of output levels, allowing for greater designer control\. However, it could come at the cost of decreasing level diversity or impacting playability\. As such, we performed an ablation study across three settings for PRP\. A visual example of each of the three settings can be found in Figure[3](https://arxiv.org/html/2607.12097#S4.F3)\.

The first of these settings was thedatasetsetting, in which the provided partial specification was left empty\. In this case, PRP draws all temporal entities in each output level from the dataset, hence the name\. We performed generation 1000 times as specified in the System Overview section, giving us a total of 1000 generated levels\. This generation process took 24\.804 seconds, averaging out to roughly 0\.025 seconds to generate a single level, with approximately 140 re\-generations required due to trivial generations\.

The second setting was thepathsetting, in which we used a player path as the partial specification\. These player paths ranged in length between ten and twenty inputs which were selected uniformly at random without regard for repeats or cycles\. Specifically, we generated ten randomized paths of each path length between ten and twenty, and generated ten levels based on each of those paths, giving us a total of 1000 generated levels\. This process took 16\.812 seconds, averaging out to roughly 0\.017 seconds on average to generate a single level, with approximately 230 re\-generations required due to trivial generations\. This is slightly faster than the dataset condition, as we do not need to iterate through all of the potential player entities to populate into the level, and can just use the provided path\.

The third setting was thebordersetting, in which we populated the partial specification with a border of wall tokens surrounding the level at each timestep\. This allowed for the exclusive generation of boxed in levels\. Notably, not all of the levels in the human authored dataset we used for generation follow this pattern\. We performed generation 1000 times, giving us a total of 1000 generated levels\. This process took 31\.241 seconds, averaging out to roughly 0\.031 seconds per generated level, with approximately 430 re\-generations required due to trivial generations\. This is slightly slower than the dataset condition, as some of the levels in the dataset have entities which go outside the bounds of the added border walls, leading to more cases which require rerunning the algorithm\. Notably, the number of trivial generations increased as the partial specification became more constrained\. This could be potentially circumvented with a more robust generation strategy, but for simplicity we chose to simply regenerate in this paper\.

As discussed further in the Results section, we found that the dataset setting was the most effective of the three at generating a diverse population of levels\. As such, we present a comparison of that dataset setting against our baselines, and provide the results of the other two settings as an ablation\.

## 5\.Results

![Refer to caption](https://arxiv.org/html/2607.12097v1/overcooked.png)Figure 4\.OvercookedAIlevels generated with PRP\. Source level is a human\-authored level used as the sole entry in the dataset\.![Refer to caption](https://arxiv.org/html/2607.12097v1/skeleton.png)Figure 5\.SkeleWalkerlevels generated with PRP\. Source level is a human\-authored level used as the sole entry in the dataset\. Labels under generated levels denote additional settings used in generation\.Table[1](https://arxiv.org/html/2607.12097#S4.T1)depicts the comparison of the populations of generated levels as captured by our metrics\. PRP achieves 100% playability without hand\-authored information aboutSokoban’s dynamics\. PoD, Sturgeon\-MKIII, and Sturgeon\-ST also achieve 100% playability, which is intuitive as each approach requires the output level to be playable via an external check or global constraints\. PCGRL has no such hard requirement and still manages to perform reasonably well in playability, as the approach is guided by a reward function which has multiple hand\-authored checks for playability encoded into it\(Khalifaet al\.,[2020](https://arxiv.org/html/2607.12097#bib.bib24)\)\. The LSTM has no explicit or implicit guidance towards playability, and performs worse on the metric as a result, with over a quarter of the approach’s generated levels being unplayable on average\. This demonstrates that any of the common associated approaches for encoding solvability information can be effective in level generation forSokoban\. However, we specifically identify that PRP accomplishes this without any of these prior common approaches, simply via the cake representation, selection policy, and matching function\.

All of the approaches excluding PoD and Sturgeon\-ST exhibited very few or no duplicate levels within the generated set\. We hypothesize that PoD’s high number of duplicates comes from a convergence towards a singular playable level, which could guide the generation process down the same path of edits multiple times\. Similarly, the additional constraints implemented for Sturgeon\-ST’s generation process may be causing the approach to have a smaller possibility space for generation, leading to some duplicate generated levels\.

PRP exhibited a high level of tile diversity while also retaining a similar amount of unique solutions and signatures to the best performing baselines\. Notably, higher tile diversity is not necessarily always desirable, as a high percentage of tile diversity may indicate the population of levels is noisy\. This is observable when considering the tile diversity of the human dataset, which is lower than PRP, PCGRL Turtle, or the LSTM due to the consistent presence of certain level features such as border walls\.

Sturgeon outperforms PRP in unique solution count, but both are similar to the human dataset\. We remind the reader that the Sturgeon levels were8×88\\times 8, which could be a contributing factor\. In terms of unique signatures, all the generated approaches fall short in comparison to the human\-authored levels\. PCGRL performs the closest, but we anticipate this may have been due to its reward function biasing the generator towards levels with longer solutions, increasing the chance of more unique signatures\. Despite no hand\-authored factor explicitly biasing it towards unique signatures, PRP still performs similarly to PCGRL, especially in comparison to the other baselines\.

We do not provide statistical analysis of our results, as they were not appropriate for these metrics, which are simply sums\. We also lack access to the original generated levels from Zakaria et al\.’s paper, making statistical analysis impossible for those populations of levels\. While we do not make any claims that PRP is superior to the existing baseline approaches, it is notable that our approach is able to even perform comparably without the use of external hand\-authored signals encoding dynamic information\. Instead, we are able to draw all of the dynamic information from the cake representation, selection policy, and matching function\.

Table[2](https://arxiv.org/html/2607.12097#S4.T2)depicts the results of our ablation study across our partial specification settings\. Overall, the dataset condition in which the partial specification was empty was most effective in terms of solution and signature diversity\. We hypothesize the decrease in diversity within the other two conditions is due to the constraining nature of a partial specification\. Even by just providing a path or a ring of walls to surround a level, we are drastically reducing the possibility space of potentially generatable levels\. With this in mind, the decreased diversity of levels in the path setting and especially the border setting could be seen as indicating a high degree of controllability\. Guaranteeing existing structure or a specific solution path may be desirable in many applications, such as in co\-creative tools\(Guzdialet al\.,[2018](https://arxiv.org/html/2607.12097#bib.bib45)\)\.

## 6\.Case Studies

To showcase the generalizability of PRP, we present two additional case studies in two separate game domains\. While we do not provide robust evaluations for these case studies, they instead represent PRP’s applicability as a generation approach to multiple domains with minimal domain\-specific changes\. The two domains wereOvercookedAI, an existing grid\-world domain commonly used in reinforcement learning research\(Carrollet al\.,[2019](https://arxiv.org/html/2607.12097#bib.bib29)\), andSkeleWalker, a proof of concept domain we authored\. These domains showcase PRP’s applicability to domains with more complex entities and rules, and PRP’s potential usefulness as part of the design process respectively\.

### 6\.1\.OvercookedAI

OvercookedAI222https://github\.com/HumanCompatibleAI/overcooked\_aiis a simplification of the gameOvercooked\. InOverCookedAI, two chefs, controlled by humans or AI agents, work together to prepare meals\. A defining feature of the environment is the complexity of the paths required to achieve reward\. Agents must go through several steps to cook various recipes before delivering food to a serving location\. In particular, agents must collect onions, place them on the stove, wait for the onions to cook, collect a plate, place the cooked onion on the plate, then deliver them to the serving location\. There is additional complexity added with the multiplayer aspect of the environment\. Players can pass objects over walls to each other, which is sometimes required to achieve reward in human\-authored levels\. As such, it is challenging to generate valid environments forOvercookedAIwhich are non\-trivial and distinct from existing training data\(Rocha and Prada,[2025](https://arxiv.org/html/2607.12097#bib.bib27)\)\.

Figure[4](https://arxiv.org/html/2607.12097#S5.F4)depicts three randomly selected generated levels based on a single input level and playtrace, which contains movement information for both players\. Our procedure for generating these levels was similar to ourSokobanimplementation, with some tweaks based on the domain\. As inSokoban,OvercookedAIis on a grid, so we perform a similar tile to character conversion to process the levels to and from the cake representation\. For the PRP selection policy, we first considered the two player paths\. We then consider all other objects simultaneously, which are implicitly restricted by the places where the player paths interacted with each object in the cake representation\. The matching function was implemented similarly toSokoban, allowing only two player paths and for entities to not overlap on the same timestep\. After generation is complete, we perform the same simple preprocessing as inSokoban, taking the first slice of the output cake as the output level\.

As shown in Figure[4](https://arxiv.org/html/2607.12097#S5.F4), PRP generated meaningfully distinct, playable environments from a single example\. In the source level, the two players are separated by serving plates and must work independently\. However, in the presented generated environments, there are examples where the two players are together or with different objects separating the players\. This leads to different optimal solutions and potential strategies, which could be beneficial for the training and evaluation of reinforcement learning agents in the domain\(Ruhdorferet al\.,[2024](https://arxiv.org/html/2607.12097#bib.bib26); Fontaineet al\.,[2021](https://arxiv.org/html/2607.12097#bib.bib28)\)\. However we note in all cases the original player paths are still valid solutions\. While we do not present a robust evaluation of PRP in this domain, it is a promising showcase of the generalizability of our approach to more complex domains\.

### 6\.2\.SkeleWalker

SkeleWalkeris a test domain we designed to learn more about the generalizability of the cake representation and PRP, as a variant ofSokoban\. In the game, the player controls a skeleton tasked with the goal of walking each dog to a stationary bone, as opposed to how the player pushes boxes into goals inSokoban\. If the skeleton is adjacent to any one dog, the dog begins to follow the skeleton, tracing its path with every movement action\. If the skeleton is ever followed by more than one dog, the skeleton gets eaten, and the game is considered lost\. The game is considered won when all dogs are occupied by a bone\.

We designedSkeleWalkerto test the PRP algorithm in a unique domain, and to see how well the approach would generalize with as few changes as possible from theSokobanimplementation\. AsSkeleWalkeris also a grid\-based game with similar rules and entities toSokoban, we used the exact same selection policy and representation, with dogs in place of boxes, and attempted to generate levels just as inSokoban\. However, we found that PRP was exactly replicating the dog placements found in the original levels with only translational variations\. We hypothesize this is due to the more constrained nature of the paths inSkeleWalker, as the player needs to walk directly over each goal rather than just pushing a box to it and the gameplay has additional constraints around relative placements of dogs\. In other words, there were fewer valid levels that could be output following the PRP assumptions for this domain with a single source level\. To get around this, we implemented a weighted path augmented similar to the one found in the “path” setting of our ablation test where we provided a player path as a partial specification\. In particular, this weighted path was generated such that at each timestep, the path had a 50% chance to continue in its current direction, and a 50% chance to pick a new direction\. This choice was made given the nature of the paths required to make uniqueSkeleWalkerlevels, and gives some insight into the PRP algorithm: not all input playtraces are necessarily good for generating a variety of levels, particularly when working from a single example\. Further, we introduced path rotation for the dog paths in the MatchesAt function, which acted as a direct transformation to the pool of possible temporal entities able to be matched to a given player path\.

Figure[5](https://arxiv.org/html/2607.12097#S5.F5)depicts three generatedSkeleWalkerlevels with varying conditions, as well as the source level they were based on\. Notably, while the positions of the dogs relative to the bones are the same across levels, each level has a different optimal solution path due to the initial position of the player\. We hypothesize that with more input levels, we would see a larger variety in potential level possibilities, as we found in theSokobandomain\. In particular, levels with shorter temporal entity paths in theory create a higher amount of possible variety in output levels, as there are simply more places in time and space where entities can be placed relative to other entities already present in the output cake\. Notably, the cake representation was not changed betweenSokobanandSkeleWalker, despite encoding a completely different set of mechanics\. The only changes that were made between the two domains were to the PRP settings previously discussed\. We feel these adaptations required to make the algorithm perform in theSkeleWalkerdomain highlight the strengths and weaknesses of PRP, and showcases the versatility of the cake representation\.

## 7\.Discussion

In this section, we discuss the limitations of the cake representation, PRP, and our evaluation\. We also discuss future avenues for exploration for the cake representation and PRP\.

### 7\.1\.Limitations

One limitation of the cake representation is the requirement of domain\-specific processing from and to the initial game’s representation\. This requirement is shared with similar text\-based tile representations\(Summervilleet al\.,[2016](https://arxiv.org/html/2607.12097#bib.bib25)\)\. Sometimes this required information may involve the game’s dynamics, meaning the processing must have additional dynamic information about a game’s systems\. However, this is a trade\-off in terms of where the domain\-specific information is encoded\. By only requiring domain\-specific information during processing to and from the cake representation, we argue that this allows algorithms that use the cake representation to be more domain\-independent\. Notably in all three domains presented in this paper, the base PRP algorithm did not change\.

Another limitation is that the conversion from the original game’s representation to the cake representation may be lossy\. The amount of information lost in the conversion is dependent on the chosen representation for each level slice in the cake representation\. For example, inSuper Mario Bros\., Mario’s movement is not bound by the tile grid of blocks that make up the level geometry\. As such, potentially important information could be lost when converting the gameplay into a cake\-style representation using a tile grid\. This could be possible to avoid with tweaks to how information for each slice of cake is represented, such as appending Mario’s relative x and y position to each cake slice rather than representing him as a single token\. However, this requires additional insight into the game’s dynamics, and an approach using this adjusted representation would also need to be updated on a per\-game basis\. As such, we present a more traditional tile\-based representation in this paper for simplicity, and leave further adaptation to future work\.

A limitation of our evaluation is the use of some existing results and generated level corpora rather than reimplementing and regenerating new populations of levels for all baselines\. While we acknowledge this limitation, this paper is not intended to be a broad evaluation in the domain ofSokoban\. Rather, we showcase a new generation approach using our cake representation and intend to show it can perform comparably to other existing approaches using additional hand\-authored information\.

### 7\.2\.Future Work

There are a number of future research avenues for both the cake representation and PRP\.

For the cake representation, one could try this representation with existing level generation approaches\. Constraint\-based systems such as Sturgeon or WFC are a natural fit for the cake representation\(Cooper,[2022](https://arxiv.org/html/2607.12097#bib.bib17); Vandaraet al\.,[2025](https://arxiv.org/html/2607.12097#bib.bib43)\)\. As presented in this paper, the cake representation is extendable to other 2D grid\-based games\. In terms of changing the representation, there is a valuable extension of the cake representation to environments which are not grid based, such as 3D games\. This could involve taking a similar approach of representing the level state over time in slices, but the representation of each level slice would need to change\. Possible solutions could be polygon\-based or graph\-based representations of these levels\.

For the PRP approach, there are a number of potential application domains\. PRP could be applicable to many reinforcement learning tasks, in which agents are trained to accomplish a goal based on their interactions with an environment\. PRP is especially suitable to these tasks, as we can generate many variations of levels based on an agent’s playtrace that are consistently valid\. These generated levels could be useful in the training process, as well as to evaluate the behaviour of existing agents\. We also imagine PRP could serve as the basis for co\-creative game design tools\. As an example of a potential tool, designers could create a partial specification with an editor, then browse levels generated by PRP in a search\-based format, picking and choosing the levels they like best\.

We have preliminary results of the application of PRP to the 3D grid\-based domainMinecraftusing an altered representation to allow for the encoding of multiple playthroughs with branching edits\. We intend to present these results in future work\.

## 8\.Conclusions

In this paper, we introduced the cake representation, a novel structure for representing game levels over time\. We introduced PRP, a generation approach designed to use the cake representation, and found that PRP performed comparably to state\-of\-the\-art baselines with additional human\-authored information in the domain ofSokoban\. We consider the cake representation a promising step toward addressing the issue of dynamics in level representation, and hope it can prove useful for future technical games research\.

###### Acknowledgements\.

This work was funded by the Canada CIFAR AI Chairs Program\. We acknowledge the support of the Alberta Machine Intelligence Institute \(Amii\)\. The authors would like to thank Kaylah Facey and Seth Cooper for helpful discussions\.

## References

- M\. Bazzaz and S\. Cooper \(2025\)Analysis of robustness of a large game corpus\.InProceedings of the 20th International Conference on the Foundations of Digital Games,pp\. 1–9\.Cited by:[§4\.1\.2](https://arxiv.org/html/2607.12097#S4.SS1.SSS2.p1.3)\.
- M\. Beukman, B\. Ingram, I\. Liu, and B\. Rosman \(2023\)Hierarchical wavefunction collapse\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.19,pp\. 23–33\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p5.1)\.
- M\. Carroll, R\. Shah, M\. K\. Ho, T\. Griffiths, S\. Seshia, P\. Abbeel, and A\. Dragan \(2019\)On the utility of learning about humans for human\-ai coordination\.Advances in neural information processing systems32\.Cited by:[§6](https://arxiv.org/html/2607.12097#S6.p1.1)\.
- S\. Cooper \(2022\)Sturgeon: tile\-based procedural level generation via learned and designed constraints\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.18,pp\. 26–36\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p5.1),[§4\.1\.2](https://arxiv.org/html/2607.12097#S4.SS1.SSS2.p1.3),[§4](https://arxiv.org/html/2607.12097#S4.p1.1),[§7\.2](https://arxiv.org/html/2607.12097#S7.SS2.p2.1)\.
- S\. Cooper \(2023\)Sturgeon\-mkiii: simultaneous level and example playthrough generation via constraint satisfaction with tile rewrite rules\.InProceedings of the 18th International Conference on the Foundations of Digital Games,pp\. 1–9\.Cited by:[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1),[§4\.1\.2](https://arxiv.org/html/2607.12097#S4.SS1.SSS2.p1.3)\.
- S\. Earle, M\. Edwards, A\. Khalifa, P\. Bontrager, and J\. Togelius \(2021\)Learning controllable content generators\.In2021 IEEE Conference on Games \(CoG\),pp\. 1–9\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p2.1)\.
- M\. C\. Fontaine, Y\. Hsu, Y\. Zhang, B\. Tjanaka, and S\. Nikolaidis \(2021\)On the importance of environments in human\-robot coordination\.arXiv preprint arXiv:2106\.10853\.Cited by:[§6\.1](https://arxiv.org/html/2607.12097#S6.SS1.p3.1)\.
- M\. Guzdial, B\. Li, and M\. O\. Riedl \(2017\)Game engine learning from video\.\.InIJCAI,pp\. 3707–3713\.Cited by:[§3\.2](https://arxiv.org/html/2607.12097#S3.SS2.p2.1)\.
- M\. Guzdial, N\. Liao, and M\. Riedl \(2018\)Co\-creative level design via machine learning\.arXiv preprint arXiv:1809\.09420\.Cited by:[§5](https://arxiv.org/html/2607.12097#S5.p6.1)\.
- M\. Guzdial and M\. Riedl \(2016\)Game level generation from gameplay videos\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.12,pp\. 44–50\.Cited by:[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p2.1)\.
- D\. Ha and J\. Schmidhuber \(2018\)World models\.arXiv preprint arXiv:1803\.10122\.Cited by:[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p2.1)\.
- E\. Halina and M\. Guzdial \(2023\)Tree\-based reconstructive partitioning: a novel low\-data level generation approach\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.19,pp\. 244–254\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p3.1),[§3](https://arxiv.org/html/2607.12097#S3.p1.1)\.
- M\. Jadhav and M\. Guzdial \(2021\)Tile embedding: a general representation for level generation\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.17,pp\. 34–41\.Cited by:[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1)\.
- A\. Khalifa, P\. Bontrager, S\. Earle, and J\. Togelius \(2020\)Pcgrl: procedural content generation via reinforcement learning\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.16,pp\. 95–101\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p4.1),[§4](https://arxiv.org/html/2607.12097#S4.p1.1),[§5](https://arxiv.org/html/2607.12097#S5.p1.1)\.
- H\. Kim, S\. Lee, H\. Lee, T\. Hahn, and S\. Kang \(2019\)Automatic generation of game content using a graph\-based wave function collapse algorithm\.In2019 IEEE conference on games \(CoG\),pp\. 1–4\.Cited by:[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1)\.
- R\. Mawhorter, B\. Aytemiz, I\. Karth, and A\. Smith \(2021\)Content reinjection for super metroid\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.17,pp\. 172–178\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1)\.
- N\. Mirgati and M\. Guzdial \(2023\)Joint level generation and translation using gameplay videos\.In2023 IEEE Conference on Games \(CoG\),pp\. 1–10\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p2.1)\.
- J\. B\. Rocha and R\. Prada \(2025\)Procedural content generation for cooperative games\-a systematic review\.IEEE Transactions on Games\.Cited by:[§6\.1](https://arxiv.org/html/2607.12097#S6.SS1.p1.1)\.
- C\. Ruhdorfer, M\. Bortoletto, A\. Penzkofer, and A\. Bulling \(2024\)The overcooked generalisation challenge\.arXiv preprint arXiv:2406\.17949\.Cited by:[§6\.1](https://arxiv.org/html/2607.12097#S6.SS1.p3.1)\.
- H\. Schaa and N\. A\. Barriga \(2021\)Generating entertaining human\-like sokoban initial states\.In2021 40th International Conference of the Chilean Computer Science Society \(SCCC\),pp\. 1–6\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p4.1)\.
- M\. Siper, A\. Khalifa, and J\. Togelius \(2022\)Path of destruction: learning an iterative level generator using a small dataset\.In2022 IEEE Symposium Series on Computational Intelligence \(SSCI\),pp\. 337–343\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p3.1),[§4\.1\.1](https://arxiv.org/html/2607.12097#S4.SS1.SSS1.p1.1),[§4](https://arxiv.org/html/2607.12097#S4.p1.1)\.
- S\. Snodgrass \(2018\)Towards automatic extraction of tile types from level images\.\.InAIIDE Workshops,Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p1.1)\.
- S\. Snodgrass \(2019\)Levels from sketches with example\-driven binary space partition\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.15,pp\. 73–79\.Cited by:[§3](https://arxiv.org/html/2607.12097#S3.p1.1)\.
- M\. Suleman, F\. H\. Syed, T\. Q\. Syed, S\. Arfeen, S\. I\. Behlim, and B\. Mirza \(2017\)Generation of sokoban stages using recurrent neural networks\.International Journal of Advanced Computer Science and Applications8\(3\)\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p3.1)\.
- A\. J\. Summerville, S\. Snodgrass, M\. Mateas, and S\. Ontanón \(2016\)The vglc: the video game level corpus\.arXiv preprint arXiv:1606\.07487\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p1.1),[§1](https://arxiv.org/html/2607.12097#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p1.1),[§7\.1](https://arxiv.org/html/2607.12097#S7.SS1.p1.1)\.
- A\. Summerville and M\. Mateas \(2016\)Super mario as a string: platformer level generation via lstms\.pp\.\.External Links:[Document](https://dx.doi.org/10.26503/dl.v2016i1.752)Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p2.1),[§4\.1\.5](https://arxiv.org/html/2607.12097#S4.SS1.SSS5.p1.1)\.
- A\. Summerville, S\. Snodgrass, M\. Guzdial, C\. Holmgård, A\. K\. Hoover, A\. Isaksen, A\. Nealen, and J\. Togelius \(2018\)Procedural content generation via machine learning \(pcgml\)\.IEEE Transactions on Games10\(3\),pp\. 257–270\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p2.1)\.
- A\. Vandara, K\. Facey, and S\. Cooper \(2025\)Spacetime level generation and editing with constraints from examples\.InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,Vol\.21,pp\. 142–152\.Cited by:[§1](https://arxiv.org/html/2607.12097#S1.p2.1),[§1](https://arxiv.org/html/2607.12097#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.12097#S2.SS1.p3.1),[§3\.3](https://arxiv.org/html/2607.12097#S3.SS3.p3.15),[§4\.1\.3](https://arxiv.org/html/2607.12097#S4.SS1.SSS3.p1.1),[§4](https://arxiv.org/html/2607.12097#S4.p1.1),[§4](https://arxiv.org/html/2607.12097#S4.p2.1),[§7\.2](https://arxiv.org/html/2607.12097#S7.SS2.p2.1)\.
- Y\. Zakaria, M\. Fayek, and M\. Hadhoud \(2022\)Procedural level generation for sokoban via deep learning: an experimental study\.IEEE Transactions on Games15\(1\),pp\. 108–120\.Cited by:[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p3.1),[§2\.2](https://arxiv.org/html/2607.12097#S2.SS2.p4.1),[§3\.5](https://arxiv.org/html/2607.12097#S3.SS5.p2.1),[§4\.1\.4](https://arxiv.org/html/2607.12097#S4.SS1.SSS4.p2.1),[§4\.1\.5](https://arxiv.org/html/2607.12097#S4.SS1.SSS5.p2.1),[§4\.2](https://arxiv.org/html/2607.12097#S4.SS2.p1.1),[§4\.2](https://arxiv.org/html/2607.12097#S4.SS2.p3.1),[Table 1](https://arxiv.org/html/2607.12097#S4.T1),[§4](https://arxiv.org/html/2607.12097#S4.p1.1),[§4](https://arxiv.org/html/2607.12097#S4.p2.1)\.