Xu et al.: Promoting Game Mechanics to Coordinates to Generate Solvable Levels — Fukai Reads

TL;DR

Most procedural content generation (PCG) for game levels builds the geometry first and only checks mechanics — jump timing, gravity flips, and the like — afterward. This paper reverses that order, proposing High-Dimensional PCG (HDPCG), a framework that designs the mechanics together with the geometry by treating each mechanic as an extra coordinate. By running pathfinding on an expanded graph that adds axes such as 'layer' or 'time' to position, solvability is guaranteed during generation rather than checked later. The authors auto-generate gravity-flip and moving-platform levels complete with a guaranteed solution path, and reproduce them as actually playable scenes in Unity.

Introduction

Today I am reading 'High-Dimensional Procedural Content Generation' by Kaijie Xu and Clark Verbrugge of McGill University (Montreal, Canada). It is a preprint submitted to arXiv on February 21, 2026 (paper ID arXiv:2602.18943) — a preprint being a submitted manuscript that, as far as I can confirm, has not yet formally cleared peer review (expert review). The text is formatted in the style of a games-research conference, but as far as I can verify it currently exists only on arXiv. Its citation count has not yet built up either, so let me note up front that this is fresh work, not yet widely discussed.

I chose this as today's piece because it lands squarely on my criterion of 'is it close to implementation.' PCG (Procedural Content Generation, the technology for automatically building game geometry and levels) papers tend to stay theoretical, but this one takes concrete mechanics — gravity inversion, moving platforms — as its subject, and even brings the generated levels all the way down to playable scenes in Unity. It read as a 'something makers can use directly' paper, the kind I could work through with a hot, strong drip coffee, marking up the printed PDF with colored pens.

Background

Let me first set the stage. Level-generation research has long centered on 'the shape of the geometry.' There are many methods for producing 2D tile maps and good-looking 3D spaces, but mechanics — time-dependent traversal, rule-bound discrete interactions, non-spatial state (e.g., 'which world am I currently in') — have mostly been reconciled after generation, via simulation or post-processing. The authors call this approach 'geometry-first.'

This ordering has a weakness. For levels where geometry and mechanics are tightly intertwined — say, 'this platform can only be boarded after three seconds' or 'this wall is passable in another world' — deciding the shape first and adding mechanics later tends to mass-produce levels that simply cannot be solved (cannot be cleared). What the authors take issue with is the absence of a 'general, extensible representation' that expresses mechanics head-on inside the generator. They want to guarantee solvability while building, rather than verify it afterward — and that is the paper's starting point.

Approach (Method)

In a phrase, the authors' idea is to 'promote mechanics to coordinates.' Normally a cell is described by position (x, y, z) alone, but HDPCG adds extra axes such as 'layer' or 'time.' Each cell then carries not only 'where am I' but also 'which layer am I on / what time-step is it now.' The authors call this a 'Dimensional-Expanded Graph' (a path network with extra axes woven into position). The special case with time as the axis is the long-known 'time-expanded graph' (a method that duplicates the map at each time-step and connects them).

On this expanded graph, whether a level is solvable becomes the simple search question 'can a path be drawn from start to goal.' The authors use A* (a search that uses an estimate to the goal to find shortest paths efficiently), breadth-first search, and dynamic programming (building the global optimum from the answers to small subproblems) to find one solution path during generation. If no path can be drawn, the level is discarded as invalid, or its parameters are resampled and retried. In other words, 'being solvable' is built in as a precondition of generation (in the authors' words, a first-class invariant — a condition held from the start).

The whole is unified into a four-stage flow. First (1) draw a rough skeleton path; then (2) flesh out attributes and rules around that skeleton — corridors, rooms, layer-switch sites, moving platforms; then (3) validate via pathfinding on the expanded graph that it is truly traversable; and finally (4) evaluate the resulting level with metrics and, if needed, re-search the parameters with a genetic algorithm (an optimization that selects good individuals and mutates them slightly across generations). Handling both space and time within this same four-stage frame is the backbone of the paper.

The instantiation goes in two directions. The 'Space direction' adds layers to position and handles gravity inversion like VVVVVV and parallel-world switching like Dishonored 2 and Titanfall 2. It has three methods of increasing control strength: a nearly unguided naive noise baseline (NNB), NP-A* which applies a 'dispersion' that pushes later paths away from earlier ones, and PF-A* which explicitly targets the coordinates of switch sites. The 'Time direction' adds time to position and handles periodically moving platforms and enemies, again with three methods: a naive static backbone, a simplified TEG-A*, and the flagship TEG-DP (a dynamic-programming version).

Findings

Let us look at the results. In the Space direction, PF-A* was near-perfect at hitting the 'minimum spacing' of switch sites as targeted (spacing controllability). Its mean absolute error (MAE, the average gap between target and actual) against the target was about 0.00 from small to large scale, versus about 0.09 for NP-A* and a larger 0.28–0.33 for the unguided NNB (the paper's Table 3). For density control too, at large scale PF-A* was more accurate at about 1.34 error versus NP-A*'s about 2.55. On the composite quality score, NP-A* wins at small/medium scale (168.9 vs. 137.6 in the small-scale GA), while PF-A* overtakes at large scale (412.3 vs. 400.0 in GA). The authors report that NNB's score collapses badly at large scale (minus 327.5 single-run).

For robustness — whether, after injecting small obstacle noise into a level, an alternate path can still be found — only PF-A* (single-run) showed any success rate (0.217±0.40 at large scale; the others near zero). The authors read this as 'PF-A*'s regularity in spacing translating into easier local re-planning.' They caution, however, that maximizing the quality score with the genetic algorithm prunes the slack detours and makes layouts more brittle. As for speed, single-run PF-A* takes 0.138s at small and 4.1s at large scale, but running the GA takes close to 500s at large scale (Table 4).

In the Time direction, the composite-score ranking was largely consistent as TEG-DP > TEG-A* > static backbone. The authors state that even after multiple-comparison correction (the Holm-Bonferroni method), this difference was statistically significant in most conditions except the small- and medium-scale single runs. And in both directions, they ran the generated levels in Unity and confirmed that gravity inversion, the time-switch lens, and moving-platform timing play out exactly as the computed solution dictates. Their claim is that they reproduced 'the mechanics and all,' not just 'matching geometry.'

Where It Is Useful

So how can someone building games or puzzles use this? Let me give concrete examples. First, if you are building a gravity-flip platformer like VVVVVV, just turning two knobs — 'switch frequency (density)' and 'minimum spacing between switch sites' — lets you carve out sections of rapid consecutive flips that test dexterity versus sections of leisurely progress, all with a guarantee of solvability. The fact that you do not need to hand-stitch the geometry is what pays off.

Second, if you are building a time-shift puzzle that 'switches between past and present to progress,' like Dishonored 2 or Titanfall 2, the same density/spacing knobs now control the 'spacing of time jumps.' You can author rapid multi-hop sequences distinctly from slow, set-piece contrivances. Third, for a moving-platform timing action like Super Mario 3D World, giving the 'fraction of time spent riding platforms (ride ratio)' and the 'minimum spacing between events' as targets lets the designer dictate the rhythm of wait, walk, and ride.

More generally, I read the paper's sweet spot as 'level blockout (rough drafting).' You can mass-produce skeletons that each secure one solvable path, then divide labor by having humans season them by hand on top. For those who confirm whether a puzzle has a solution using constraint satisfaction or a SAT solver (a tool that mechanically decides whether a satisfying solution exists), the shift from 'inspecting for a solution afterward' to 'generating with a solution already in hand' should port directly into their own pipeline.

Limitations

The limitations are clear too. First, the ones the authors themselves acknowledge. The ideal Time-direction search (full TEG-A*) requires the state to carry 'interaction memory' of which platforms and endpoints have already been used, which causes a combinatorial explosion and, they report, timed out even at the smallest scale. They therefore compromise with a simplified version, leaving a performance gap between the static backbone and the flagship DP. They have also not yet incorporated PCGML (learning level tendencies with machine learning) or reinforcement learning; they evaluate each mechanic axis separately and have not validated composite levels mixing layers and time at once; and robustness stops at post-generation inspection and is not folded into the optimization. Decisively, the authors explicitly state that there is no user study with human participants, so evidence of 'fun' is future work.

What I (Fukai) add here are two points. One is that what the method guarantees is that 'one solution path exists,' not the experience of the level as a whole. The authors admit that 'unintended shortcuts can emerge after widening corridors,' but conversely, this reads as: whether the generated single path truly carries the designer's intended rhythm wavers depending on how the metrics are weighted. The other is that evaluation is largely confined to automated metrics and replay footage. Even if spacing and density are hit accurately, how that feels to a person as 'challenge' or 'unfairness' lies outside this paper's reach — a point the authors themselves concede.

Fukai's Reading

From here is my (Fukai's) reading. I want to place this work within PCG's historical shift of gravity 'from geometry to mechanics.' Level generation so far has asked 'what shape,' verifying solvability afterward. HDPCG shifts that question toward 'what network of state transitions,' building solvability into the premise of design. In the vocabulary of design criticism, I can frame this as an attempt to externalize and automate, as graph search, the reachability reading — 'with this mechanic, I should be able to move like so here' — that level designers do implicitly in their heads. In seating 'the path one can move along' rather than the shape as a first-class citizen, I sense the breadth of this paper's reach — and this section alone is my interpretation.

Closing

Finally, let me hand over a map. Those who want to go deeper can read this paper's foundations — Seth Cooper and colleagues' Sturgeon series (generating a level and its solution path simultaneously via constraint satisfaction) and Kaylah Facey and Seth Cooper's space-time WaveFunctionCollapse (level generation with time added as an axis) — to see the map of the 'generate-with-a-solution-in-hand' lineage. Conversely, if you are interested in the connection to PCGML or reinforcement learning that this paper has not yet touched, starting from Julian Togelius and colleagues' textbook-style PCG work should give you a three-dimensional sense of where this paper left blanks.

References

Papers and related material referenced in this article:

・High-Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, 2026, arXiv preprint arXiv:2602.18943, submitted 2026-02-21)

・HTML version of the paper (full text, figures, experimental settings)

・Related: Seth Cooper & Mahsa Bazzaz, Sturgeon-MKIV: constraint-based level and playthrough generation with graph label rewrite rules (AIIDE 2024) — the lineage of generating level and solution together via constraint satisfaction

・Related: Kaylah Facey & Seth Cooper, Toward space-time WaveFunctionCollapse for level and solution generation (AIIDE 2024) — level generation with time added as an axis

Note: All figures are based on the paper's text and Tables 3 / 4. The citation count has not yet built up; this is work prior to wide discussion.