Halina & Guzdial: Generating Levels as a "Cake of Time" — Fukai Reads

TL;DR

In most automatic level-generation methods, a game level is treated like a still image. Yet the essence of a game is that it changes over time: the player moves, boxes get pushed, the state shifts moment by moment. In this paper Emily Halina and Matthew Guzdial (University of Alberta, Canada) propose a new representation that treats a level as a stack of board states sliced by time. They call it the "cake" representation, because the stacked slices resemble a cake.

On top of this representation runs a generation method called PRP (Playtrace Reconstructive Partitioning), which reassembles levels from recorded play traces. It produces a level and its solution simultaneously. Compared against six existing methods in Sokoban, it kept playability at 100% while also achieving high diversity, and did so without any external solvability check or reward function. Embedding the dynamic information into the representation itself is what pays off, as I read it.

Introduction

Today I introduce "Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning" by Emily Halina and Matthew Guzdial. Both are with the Department of Computing Science and Amii (Alberta Machine Intelligence Institute) at the University of Alberta. The paper is an arXiv preprint posted on July 13, 2026 (arXiv:2607.12097), and at the same time an accepted paper at the peer-reviewed conference FDG 2026 (Foundations of Digital Games, held in Copenhagen in August), with a DOI assigned. So it is not a pre-review draft but a formally published paper.

Guzdial has long worked in procedural content generation (PCG, generating content by algorithm rather than by hand). This paper is the kind of work that lays down a new foundational tool, and its focus is less a flashy generation demo than a rethinking of how a level should be held by a computer in the first place.

I chose it today because it is directly useful for anyone making Sokoban-like puzzles, as we do at Puzzlebyrinth. From a handful of levels on hand, you can produce many new levels fast, each guaranteed to be playable. I want to convey how that machinery works without you having to open the paper.

Background

Past level representations came in many forms: tiles (a grid of cells), graphs, images, and memory. But as the authors frame it, all of these treat a level as static, a single frozen state. Games, however, move. Unless dynamic information is supplied from outside, you cannot guarantee that a generated level is actually playable (solvable). That is the starting problem.

There have been tricks to add dynamic information before. In the well-known Super Mario dataset (VGLC), the player's path is overlaid on the board as a separate token. But because this is a two-dimensional representation, it cannot capture the true path when the player crosses the same cell many times. Others use hand-authored constraints, or fold a solver into a reward (in reinforcement-learning approaches), but all of these merely approximate the dynamic information outside the representation.

This "bolt-on" approach creates the burden of rewriting design information by hand for each new game domain. If one could close the very gap between static representation and dynamic gameplay, the same machinery could serve both level generation and automated play, and designers could more easily bring it into their own games. That is the aim of this study.

Approach

Start with the central cake representation. The authors define a level as a solid formed by stacking the board (an n by m grid of cells) at each time step, for k steps. Each "slice" records the full state at that instant, and the stack becomes the flow of time itself. One assumption is the Markov property (the property that the next state is determined by the current state alone). Without it, dynamic information cannot be sealed into the representation.

The crux of the cake representation is the "temporal entity": each distinct object that persists across time steps, tracked separately. In Sokoban these are the player, each individual box, and the walls. A box turns into a "solved box" when placed on a goal, and reverts to a box if pushed off. Who is where at which moment, and what they transformed into, is held wholesale inside the representation. Similar spacetime representations exist in prior work (Vandara et al.), but tracking entities individually is what the authors say makes the cake representation new.

PRP runs on top of this representation. Its inspiration is BSP (Binary Space Partitioning, an existing method that fills a new level with fragments of existing ones by recursively splitting space). PRP performs this along the axis of time. It takes two inputs: a partial specification of the output (elements you want fixed in advance; it may be empty) and a set of source levels with their play traces. From these it fits elements one at a time, assembling the level and its solution simultaneously.

The fitting uses two pieces of domain knowledge. One is the Selection Policy, which decides the order in which entity types are placed. In Sokoban the most dynamic entity, the player, goes first, then boxes, then the rest. The other is MatchesAt, which judges whether an element can sit at a given time and place. For Sokoban the authors imposed three rules: only one player at any time; player, box, and wall never share a cell; nothing goes out of bounds. The core algorithm is domain-independent; per domain you only need this policy, this matching, and pre/post-processing.

Findings

Look at the Sokoban comparison (Table 1 in the paper). PRP reached 100% playability, 0.00% duplicates, 50.86% tile diversity, 1.924 unique solutions, and 0.534 unique signatures. What stands out is that it achieved this without hand-writing any information about Sokoban's dynamics. The dynamics arise naturally from the representation, the selection policy, and the matching function.

The six baselines were Path of Destruction (PoD), Sturgeon-MKIII, Sturgeon-ST, the Turtle and Wide variants of PCGRL, and an LSTM (a neural network with a memory unit). PoD and the two Sturgeon variants also reach 100% playability, but that is because they force playability through an external solvability check or constraints. The reinforcement-learning PCGRL sits at 86.40% and 86.60%, and the LSTM at 73.4% (on average more than a quarter of its levels are unplayable). PRP, as I read it, matched the best without such external crutches.

What about diversity? PRP's 50.86% tile diversity is high, but the authors caution that higher is not necessarily better (too high may mean noisy levels). Its 1.924 unique solutions is close to the human levels' 2.083 (the highest, Sturgeon-MKIII's 2.138, benefits from an 8 by 8 board, one size larger). On unique signatures (a metric that normalizes solutions by rotation and flip and reduces them to just the directions boxes are pushed), no generator reaches the human 0.917. PCGRL comes closest, but the authors carefully note this may reflect its reward function biasing toward longer solutions.

The ablation study over partial specifications (an experiment that removes or changes elements to check their effect, Table 2) is also interesting. The empty "dataset" setting was most diverse (1.924 unique solutions, 0.534 signatures, 1000 levels in about 24.8 seconds). The "path" setting, given a player path, dropped somewhat (1.347/0.264), and the "border" setting, boxing levels in with walls, dropped sharply (0.257/0.094, 27.60% duplicates). The tighter the constraint, the lower the diversity, but the greater the designer's control, a two-sided relationship. The authors state plainly that they "make no claim that PRP is superior" and that they run no statistical analysis, since the metrics are simple sums and they lack access to the original generated levels.

Use cases

If you are building a Sokoban-like puzzle, this is immediately usable. Feed it a handful of levels (the paper uses 12 hand-made 7 by 7 levels) and their solutions, and it will emit 1000 new levels, each guaranteed playable, in about 25 seconds. You need neither a solver in the generation loop to check solvability nor hand-written constraints. Because the level and its solution are generated together, the output is, in principle, always solvable.

Second, you get designer control through partial specification. Want levels that pass along a particular play path? Hand it the path (the path setting). Want levels always boxed in by walls? Hand it a wall frame (the border setting). Diversity drops, but you can guarantee the intended structure or solution line. This suits a daily-puzzle operation that wants consistent difficulty or skeleton, and fits well with co-creative tools (tools where a human and an AI build levels together).

Third, a "difficulty knob" via clever post-processing. The cake representation holds the entire course through to the solved state. The authors normally take the first slice (the initial state) in post-processing, but note that taking a partially solved slice instead auto-produces a "slightly easier version" of the same level. This connects to mechanically mass-producing tutorial or gradual on-ramp levels.

Fourth, porting across genres. The paper also generates meaningfully different levels from a single source level in the co-op game OvercookedAI and in SkeleWalker (a Sokoban variant the authors built, where a skeleton leads dogs to bones). When you want environments to train or evaluate reinforcement-learning agents, or to prototype a new mechanic, you can run it with minimal effort by writing just the selection policy and matching function. It suits small-studio prototyping too.

Limitations

Start with what the authors themselves acknowledge. Rigorous evaluation is limited to a single domain, Sokoban, and the two case studies (OvercookedAI and SkeleWalker) lack robust evaluation. They also run no statistical analysis (because the metrics are sums and they cannot access the baselines' original levels). And the tighter the partial specification, the more "trivial box-less levels" appear and the more regenerations are needed (about 140 for empty, 230 for a path, 430 for a wall frame). The method requires play-trace data and a per-domain selection policy and matching function.

From here on are points I (Fukai) noticed on reading. PRP essentially recombines existing play traces into new levels. That means the novelty of the generated dynamics is bounded by the range of dynamics present in the source levels. A genuinely novel gimmick lying outside the 12 teaching levels will not spring from this machinery. The quality and breadth of the source corpus, I read, becomes the ceiling of the output.

One more point I, Fukai, want to flag: playability is a different thing from being fun or being appropriately difficult. The paper shows that solvable levels can be produced fast and in bulk, but whether they make good puzzles has not passed a human playtest. That the unique signatures fall short of the human levels may suggest the generated levels are structurally a bit shallow, which I read cautiously, within the bounds of what the authors do not assert.

Fukai's reading

This is my (Fukai's) interpretation. I want to place this work in the lineage of "fix the representation first" PCG. Rather than pasting playability on afterward via constraints or rewards, it folds the dimension of time into the object itself. In the vocabulary of design criticism, this is closer to automating the recombination of the solution space (how a level is solved) than of the tile space. Since I hold that a puzzle is, in the end, the design of the process by which it is solved, treating level and solution together as a single cake seems, as I read it, to place the abstraction in the right spot.

Closing

For those who want to go deeper, here is a map. The basis of this paper's evaluation is Zakaria et al.'s survey of PCGML (machine-learning-based generation) for Sokoban, from which many of the comparison metrics and baselines come. The closest prior work is Vandara et al.'s Sturgeon-ST (a constraint-based method that treats a level and its solution as spacetime blocks); reading it against the cake representation, contrasting whether entities are tracked individually, deepens understanding.

As the origin of the framework for making levels with reinforcement learning, reading Khalifa et al.'s PCGRL alongside gives you a picture of how the field has handled "playability." If you want to peek at the implementation, the fastest route is the authors' public project repository, which contains the Sokoban source levels and their cake representations. The next time you build a puzzle by hand, this idea of a "time-folded representation" will surely become one tool in your box.

Sources

Papers and related materials referenced in this article:

・Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning (Halina & Guzdial, 2026, arXiv:2607.12097 / FDG '26, DOI: 10.1145/3815598.3815619)

・Project repository (emily-halina/PRP-Sokoban, Sokoban source levels and cake representations)

・Related: PCGRL: Procedural Content Generation via Reinforcement Learning (Khalifa et al., 2020) / Zakaria et al.'s PCGML survey for Sokoban (2022), Vandara et al.'s Sturgeon-ST (2025)