Xu & Verbrugge: Turning gravity and time into coordinates of the level generator — Fukai Reads

TL;DR

Automated level generation has long been treated as the job of shaping terrain. You lay out walls, floors and corridors, and only afterwards do you check whether mechanics such as gravity inversion or moving platforms actually work. Kaijie Xu and Clark Verbrugge of McGill University turn that order around. Their proposal is to promote the mechanic itself to a coordinate axis and search for it together with the geometry.

The framework is called HDPCG, High-Dimensional Procedural Content Generation. You build a larger graph in which the grid coordinates (x, y) are joined by something like "which layer am I on" or "what second is it". Run ordinary path search over that graph and a request such as "a route that flips gravity exactly three times" is satisfied during generation rather than judged after the fact.

I read the version posted on arXiv. A paper with the same title appears in the proceedings of FDG 2026, the 21st International Conference on the Foundations of Digital Games, so this is peer-reviewed work.

About this paper

The title is "High Dimensional Procedural Content Generation". The authors are Kaijie Xu and Clark Verbrugge, both at McGill University in Montreal, Canada.

What I read is the arXiv version, stamped down the left margin as "arXiv:2602.18943v1 [cs.AI] 21 Feb 2026". That is a preprint, a manuscript posted before peer review, submitted on 21 February 2026. However, a paper with the same title appears with a DOI in the proceedings of FDG 2026, held 10-13 August at the Royal Danish Academy in Copenhagen. So the work has been peer-reviewed. I should note only that the figures below come from the arXiv version and may differ in detail from the camera-ready one.

I picked this paper today because, unusually for a puzzle site, it is the kind of research you can implement directly. Gravity inversion, switching between parallel worlds, platforms you cross while time is held still. These are the working verbs of the puzzle platformer, and we have written about one of them before as the verb of flipping gravity. What this study pushes towards is not "can we generate it" but "can we generate it to order".From the Steam store page for VVVVVV (Terry Cavanagh, 2010). One button swaps which way is down. The paper names this game as the model for one of its Unity case studies.

What was already known

PCG, procedural content generation, means getting a machine to build levels and assets. It has been studied for decades and the terrain-shaping part has become rather good. In the authors' phrasing, the dominant formulations for level generation nonetheless remain "largely geometry-first".

So how have mechanics been handled? The paper's account is that things like time-dependent traversal, discrete interaction rules and extra non-spatial state have been injected via simulation-based objective functions or post-processing heuristics rather than being represented natively in the generator. Build it, play it, dock points if it fails.

That order has a weakness. Simulation, the authors write, typically enforces such requirements only indirectly, which makes it harder to target specific mechanism-level structure during generation. If you want a level with exactly three gravity flips, you end up generating at random, counting, and throwing away.

So what is missing is not another algorithm but the representation itself: a general, extensible representation and problem formulation for complex, mechanism-rich PCG.

How they approached it

The idea is surprisingly plain. Give the cells attributes and write the world state as cells over an expanded state space. A path-finding program can then reason about geometry and dynamics inside a single graph. The graph gets bigger; the search itself does not change.(Diagram) On the left, an (x, y) grid of geometry alone. On the right, one layer axis has been added, and only the switch nodes join the two copies. The same search now doubles as verification of the mechanic.

The first axis is Space (Direction-Space). A discrete layer dimension is added to the geometry, and reachability is validated across the four coordinates (x, y, z, layer). Gravity inversion and parallel-world switching then become the same event: you took one edge that crossed layers. Mechanics that used to be special cases fall into a single shape.

The second axis is Time (Direction-Time). Here the paper uses a time-expanded graph: copy the map once per tick and join the copies with edges that advance the clock. Player actions are written as three kinds of transition - wait, walk and ride - with occupancy checks for whether a cell is currently blocked, and constraints such as being able to board a moving platform only at its endpoints.

Both axes run through a shared four-stage pipeline: generate an abstract skeleton, ground it under control, validate in the high-dimensional graph, and evaluate against multiple metrics. The Space side offers three methods. The Naive Noise Baseline (NNB) simply uses i.i.d. noise fields. Naive Penalty A* (NP-A*) plans between waypoints with repulsive kernels around carved segments. Potential Field A* (PF-A*) aims explicitly at the switch coordinates with attractive and repulsive potential fields.

The Time side also offers three. The Static Backbone Baseline draws a spatial backbone with 2D/3D A*, instantiates periodic platforms and obstacles, then validates feasibility with breadth-first search. TEG-A* searches a cyclic time-expanded graph with lightweight bitmask memory. TEG-DP is forward dynamic programming over a layered directed acyclic graph.

What they found

The clearest numbers on the Space side concern whether you get what you ordered. For switch spacing, the mean absolute error against the target is given in Table 3 as 0.002 / 0.000 / 0.000 for PF-A* at the small, medium and large scales. NP-A* gives 0.091 / 0.093 / 0.097 and the unguided NNB gives 0.288 / 0.284 / 0.326. A method that aims at the switch points honours a spacing request almost exactly.

Switch density is less tidy. In the same Table 3, PF-A* records 2.247 / 2.078 / 1.343 and NP-A* records 2.217 / 1.366 / 2.554; the two trade places depending on scale. NNB, though, sits at 9.410 / 8.738 / 10.978, an order of magnitude away. That guidance helps is clear; which guidance is stronger depends on the size of the map.

For robustness the paper measures ARR, alternative route robustness. Single-run means are 0.338 / 0.319 / 0.530 for PF-A*, 0.156 / 0.215 / 0.360 for NP-A*, and 0.037 / 0.042 / 0.057 for NNB across the three scales. Against the unguided baseline, PF-A* leaves roughly nine to ten times as many alternative routes standing. In other words, fewer dead ends.

Speed is practical too. Table 4 puts a single PF-A* run at 0.138 ± 0.060 seconds at the small scale, 0.663 ± 0.278 at medium and 4.119 ± 1.136 at large. A few seconds per level. More than enough for a nightly batch.

On the Time side the experimental scale is stated plainly. Table 2 gives small as a 30x15 grid with a time limit of 200 and 12 seeds, medium as 50x25 with a limit of 300 and 8 seeds, and large as 80x40 with a limit of 500 and 4 seeds. Table 6's weighted score for single runs at the large scale is 7.81 ± 1.77 for the Static Backbone, 13.30 ± 3.51 for TEG-A* and 20.35 ± 9.58 for TEG-DP, at 0.31 ± 0.20, 0.25 ± 0.18 and 6.42 ± 0.68 seconds respectively.

Table 5 reports that TEG-DP significantly outperforms TEG-A* in all but two settings - small/single and medium/single - with effect sizes (Cliff's delta) described as "large". Solve it more carefully and it gets better, at the cost of time: a familiar shape of result.

How makers can use this

First. If you are building a gravity-flip puzzle, you can pass the number of switches and the spacing between them as an order. What this paper shows is that a spacing request can be honoured at essentially zero error. You can decide a difficulty curve in words - wide gaps early, tighter later - and hand it straight to the generator as an argument. No more generate, count, discard.

Second. For moving-platform stages, a time-expanded graph lets you design the ratio of waiting to riding. The fraction of time the player stands still, the fraction spent on a platform, the interval between interactions: these all appear as metrics, so "how much am I being made to wait" becomes a dial. Pacing becomes a numeric request rather than a feeling.From the Steam store page for Contrast (Compulsion Games, 2013), where you move between a solid world and the shadow world cast on its walls. An easy illustration of the verb "switch layers"; it is not a game studied in the paper.

Third. You can use this without generating anything. Take a hand-made level and place it on the expanded graph. Whether there is a shortcut that reaches the goal without ever using gravity inversion is answered by running path search with cross-layer edges forbidden. The verifier can be carved out on its own; you do not have to adopt the whole generator.

Fourth. Perturbation testing as a quality gate. The paper measures robustness by nudging a finished level and seeing whether it can be replanned. The same trick works in operations. For a daily puzzle, try shifting a platform by one cell or delaying it by one tick before you ship, and hold back any board whose solution breaks. Treat something like ARR as a release check.

Fifth, as a caution. "As ordered" and "fun" are not the same thing. Every metric in this paper measures the former. When you adopt a generator, do not let a green dashboard talk you out of playtesting.

Limitations

The authors list five limitations. First, the ideal TEG-A* for Time requires state augmentation with interaction memory and rewards to drive meaningful, non-redundant contacts, and that causes state explosion. They therefore use a simplified variant that is tractable but less capable of strictly shaping interactions, which they say leaves a gap between the Static baseline and DP.

Second, the representation and solvers studied here are constructive and search-based; they do not yet integrate PCGML (procedural generation using machine learning) or reinforcement learning (a framework in which behaviour that earns more reward is learned through trial and error) that could learn priors or value functions over the high-dimensional state space. Third, each mechanic axis is evaluated separately, so multi-mechanic compositions in a single joint state space, and how they scale, remain untested. Fourth, robustness is evaluated post-hoc by replanning under micro-perturbations and is not part of the genetic-algorithm fitness, because multiple replanning rollouts would raise the cost sharply.

The fifth is the heaviest. The authors state plainly that "we have not conducted user studies"; playability and pacing are supported by metrics and replays, but formal evidence of fun is future work.

What I would add here concerns the comparison itself. The Space baseline, NNB, uses i.i.d. noise fields and index-based layer switching - essentially no guidance at all. Beating that by nine or ten times is, read honestly, a careful confirmation of the obvious: guided beats unguided. As far as I read, there is no table putting these methods head to head against existing PCG systems.

One more. TEG-DP takes 6.42 seconds for a single large run, and running a genetic algorithm on top changes the order of magnitude. That is fine for one puzzle a day. For generating levels on the fly during play, I read this paper as not yet being there.

How Fukai reads it

I want to place this study in the movement of level generation from map-making towards constraint satisfaction. In the vocabulary of design criticism, it is a piece of work that translates the placement of verbs - something a level designer does tacitly, in their head - into coordinates a search can walk. The moment gravity inversion is rewritten as an edge in a graph rather than an element of a picture, its spacing and its count become things you can order. What I find interesting is how little new algorithmic machinery this required. A* and dynamic programming, old tools both; only the way the board is written has changed. I read it as the classical lesson - change the representation and the problem gets easier - shown in the vocabulary of the puzzle platformer.

Closing

The paper also includes Unity demonstrations. On the Space side, a 2.5D gravity-inversion level and a 3.5D time-shift level in which you toggle between two time states to get past geometry and enemies; for the latter the authors name Dishonored 2's A Crack in the Slab and Titanfall 2's Effect and Cause as models. Of the first they write that the Unity level is generated directly from the planner - what you see is exactly what is playable. The conclusion sets out connecting these metrics to perceived pacing, challenge and enjoyment as future work.

For those who want to go deeper: reading this alongside work on how to evaluate generation at all - the effort to build a benchmark for PCG, for instance - gives you a map of what "good generation" is supposed to mean. On this site, the shelves for Magnetism & Gravity, Time Manipulation and Puzzle Platformer map directly onto the verbs this paper turned into coordinates. Looking at how real games have used those verbs, before you implement anything, is how you work out which numbers are worth ordering.

Sources

Papers and materials referenced in this article:

・High Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, McGill University, 2026, arXiv:2602.18943v1 [cs.AI], 21 Feb 2026)

・The same paper in the Proceedings of the 21st International Conference on the Foundations of Digital Games (FDG 2026), DOI 10.1145/3815598.3815606 (peer-reviewed version)

・FDG 2026 official site (10-13 August 2026, Royal Danish Academy, Copenhagen)

・Images from Steam store pages: VVVVVV (Terry Cavanagh, 2010) and Contrast (Compulsion Games, 2013). Neither game was studied in the paper; both appear as illustrations of the verbs involved.

・The diagram was made by Fukai (alphanumeric labels only).