High Dimensional Procedural Content Generation

Kaijie Xu; Clark Verbrugge

cs.AIFeb 21, 2026

High Dimensional Procedural Content Generation

Authors: Kaijie Xu, Clark Verbrugge

Organizations: McGill University Montreal, Quebec, Canada

Abstract

Procedural content generation (PCG) has made substantial progress in shaping static 2D/3D geometry, while most methods treat gameplay mechanics as auxiliary and optimize only over space. We argue that this limits controllability and expressivity, and formally introduce High-Dimensional PCG (HDPCG): a framework that elevates non-geometric gameplay dimensions to first-class coordinates of a joint state space. We instantiate HDPCG along two concrete directions. Direction-Space augments geometry with a discrete layer dimension and validates reachability in 4D (x,y,z,l), enabling unified treatment of 2.5D/3.5D mechanics such as gravity inversion and parallel-world switching. Direction-Time augments geometry with temporal dynamics via time-expanded graphs, capturing action semantics and conflict rules. For each direction, we present three general, practicable algorithms with a shared pipeline of abstract skeleton generation, controlled grounding, high-dimensional validation, and multi-metric evaluation. Large-scale experiments across diverse settings validate the integrity of our problem formulation and the effectiveness of our methods on playability, structure, style, robustness, and efficiency. Beyond quantitative results, Unity-based case studies recreate playable scenarios that accord with our metrics. We hope HDPCG encourages a shift in PCG toward general representations and the generation of gameplay-relevant dimensions beyond geometry, paving the way for controllable, verifiable, and extensible level generation.

Figures & tables

Scale	Grid	Seeds	GA (pop $\times$ gens)	$K$	$D_{1}/D_{2}$	$\boldsymbol{\lambda}$	Targets	Sweep	Validation settings
Small	$30^{3}$	$80$	$40\times 30$	10	$2/4$	1	$\rho{=}2.0{/}100,\ s_{\min}{=}5$	$\rho\!\in\!\{1,3,5\},\ s_{\min}\!\in\!\{3,5,7\}$	band, $p{=}0.01$ , $r_{\text{band}}{=}1$ ; ARR- $k{=}10$ ; stab: pairs $=12$ , $\|x\!-\!y\|_{1}\!\geq\!20$
Medium	$50^{3}$	$40$	$20\times 20$	15	$3/6$	1	$\rho{=}2.0{/}100,\ s_{\min}{=}5$	$\rho\!\in\!\{2,4\},\ s_{\min}\!\in\!\{4,6\}$	band, $p{=}0.01$ , $r_{\text{band}}{=}1$ ; ARR- $k{=}10$ ; stab: pairs $=10$ , $\|x\!-\!y\|_{1}\!\geq\!25$
Large	$100^{3}$	$20$	$10\times 10$	30	$4/8$	2	$\rho{=}2.0{/}100,\ s_{\min}{=}5$	(no full sweep)	global, $p{=}0.005$ , $r_{\text{band}}{=}1$ ; ARR- $k{=}8$ ; stab: pairs $=12$ , $\|x\!-\!y\|_{1}\!\geq\!30$

Table 1. Large-Scale Experimental Settings for Space Direction. Targets use density per 100 path cells;

\lambda

is the layer-switch cost.

Scale	Grid & Horizon	Seeds	GA (pop $\times$ gens)	Plats/Obs	Min spans (P/O)	Sweep	Options
Small	$30{\times}15;\ T_{\max}{=}200$	$12$	$20{\times}20$	$4/4$	$4/3$	$r\in\{0.30,0.40\},\ d_{\min}\in\{10,12\}$	allow-ride, TTC on
Medium	$50{\times}25;\ T_{\max}{=}300$	$8$	$20{\times}20$	$5/5$	$5/4$	$r\in\{0.25,0.35\},\ d_{\min}\in\{12,15\}$	allow-ride, TTC on
Large	$80{\times}40;\ T_{\max}{=}500$	$4$	$20{\times}20$	$8/8$	$6/5$	$r\in\{0.30,0.40\},\ d_{\min}\in\{15,18\}$	allow-ride, TTC on

Table 2. Large-Scale Experimental Settings for the Time Direction. Each scale runs all methods in single and GA modes.

Figure 1. Space quality. S/M: NP-A* $>$ PF-A* $>$ NNB; L: PF-A* $>$ NP-A* $\gg$ NNB. GA boosts all methods; PF-A* best at L.

	S		M		L
Method	Den.	Sp.	Den.	Sp.	Den.	Sp.
PF-A*	2.247	0.002	2.078	0.000	1.343	0.000
NP-A*	2.217	0.091	1.366	0.093	2.554	0.097
NNB	9.410	0.288	8.738	0.284	10.978	0.326

Table 3. Controllability summary (MAE

\downarrow

). Mean absolute error between target and achieved Density / Spacing aggregated per scale (S/M/L). Best per column is bold . Counts (runs aggregated per scale): S:

1080

; M:

240

; L:

30

Figure 2. Controllability-density. PF-A* tracks density targets with lowest MAE at L and competitive at S/M; NP-A* exhibits mild systematic overshoot; NNB is insensitive to targets.

Figure 3. Controllability-spacing. PF-A* $\approx$ perfect across scales; NP-A* slightly lower; NNB drops with higher targets.

Method (mode)	S	M	L
PF-A* (single)	$0.138\pm 0.060$	$0.663\pm 0.278$	$4.119\pm 1.136$
NP-A* (single)	$0.248\pm 0.094$	$0.982\pm 0.419$	$3.542\pm 0.915$
NNB (single)	$\mathbf{0.070\pm 0.032}$	$\mathbf{0.366\pm 0.173}$	$\mathbf{3.163\pm 1.597}$
PF-A* (GA)	$35.888\pm 6.045$	$186.431\pm 26.924$	$500.064\pm 37.407$
NP-A* (GA)	$43.172\pm 7.086$	$153.150\pm 9.749$	$\mathbf{199.189\pm 9.823}$
NNB (GA)	$\mathbf{25.368\pm 4.292}$	$\mathbf{119.232\pm 15.990}$	$411.569\pm 44.407$

Table 4. Runtime (seconds; lower is better; Mean

\pm

std.)

Figure 4. 2D combined-geometry view (Space). Blue/red cells are free only on $L_{0}/L_{1}$ ; green are free on both (switch pockets); grey are blocked on both. Start/end are overlaid. This top-down grid visualization corresponds to our 2.5D Space (gravity-shift) instantiation. The corridor layout and pocket placement obey the target density / spacing used in Sec. 5.1 .

Figure 5. 3D combined-path view (Space). Blue/red points are free voxels on $L_{0}/L_{1}$ ; purple diamonds are planned switch nodes on the successful route. Alternation frequency matches the requested spacing.

Figure 6. Time (scores). Weighted score distributions across scales and modes. The ordering is consistent: TEG-DP $>$ TEG-A* $>$ Static, and GA pushes medians higher, especially at Scale L.

Figure 7. Unity snapshot (2.5D gravity inversion). Flipping gravity swaps the active walkable layer; corridors and apertures correspond one-to-one with Fig. 4 .

Figure 8. Unity snapshot (3.5D time-shift). The lens previews the alternate timeline; toggling swaps active/inactive layers. Planned switch points remain reachable post-toggle.

Figure 9. Time direction (Python view). Green: platform tracks; red: obstacle tracks; blue: validated player path (darker $\rightarrow$ later); purple: ride segments; black points: waits. Stars mark start/goal.

Figure 10. Time direction (Unity snapshot). The 3D platformer level instantiates the same moving platforms (green) / enemies (red) and reproduces the planned route (blue).

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 11. Robustness to micro-perturbations. PF-A* (single) attains the highest success on S/M/L; NP-A*/NNB are near zero. Error bars show across-seed std.

Figure 12. ARR distributions (by method and scale). PF-A* stochastically dominates NP-A* and NNB in single mode; GA narrows the gap on S/M and remains comparable on L.

Figure 13. Endpoint perturbations. Near-ceiling success ( $\approx 1.0$ ) for all methods and scales.

Figure 14. Cost increase under micro-perturbations. S/M: near-zero for all (except NP-A* at M); L: PF-A* accepts costlier detours while NP-A* stays conservative.

Figure 15. Switch Pattern Compliance (SPC). GA tightens patterns and ranks PF-A* highest on M; single-mode shows NP-A* higher on S/M and PF-A* catching up on L.

Figure 16. Switch Exit Freedom (SEF). NNB has higher local exit openness but without gains in controllability or robustness.

Figure 17. Layer balance. No contradicting imbalance; GA generally narrows dispersion.

Figure 18. Pareto: length vs. coverage. PF-A* lies on a strong frontier; NP-A* reaches extreme coverage with longer paths; NNB is dominated.

Scale	Mode	Comparison	Cliff’s $\delta$ (mag.)	$p_{\mathrm{adj}}$
S	Single	Static vs. TEG-A*	$-0.997$ ( large )	$<\!0.001$
S	Single	TEG-A* vs. TEG-DP	$0.236$ ( small )	$0.372$
S	GA	Static vs. TEG-A*	$-0.979$ ( large )	$<\!0.001$
S	GA	TEG-A* vs. TEG-DP	$-1.000$ ( large )	$<\!0.001$
M	Single	Static vs. TEG-A*	$-0.992$ ( large )	$<\!0.001$
M	Single	TEG-A* vs. TEG-DP	$-0.250$ ( small )	$0.854$

Appendix

Table 5. Time direction: nonparametric significance and effect sizes. Two-sided Mann–Whitney U with Holm–Bonferroni correction across key metrics; entries report Cliff’s

\delta

(magnitude) and adjusted

p

-values (

p_{\mathrm{adj}}

Scale	Method	Mode	Runtime (s)		Score
S	Static Backbone	Single	0.19 $\,\pm\,$	0.17	8.22 $\,\pm\,$	2.65
S	Static Backbone	GA	34.39 $\,\pm\,$	5.75	13.56 $\,\pm\,$	1.68
S	TEG-A*	Single	0.17 $\,\pm\,$	0.22	9.19 $\,\pm\,$	6.09
S	TEG-A*	GA	15.79 $\,\pm\,$	2.39	22.27 $\,\pm\,$	2.42
S	TEG-DP	Single	1.62 $\,\pm\,$	0.16	9.19 $\,\pm\,$	7.32
S	TEG-DP	GA	159.23 $\,\pm\,$	14.77	26.10 $\,\pm\,$	9.31

Appendix

Table 6. Time direction: runtime and weighted score across scale/method/mode (mean

\pm

std).

Figure 19. Efficiency summary across methods, scales, and modes.

Procedural Content Generation

Procedural content generation creates game levels, 3D worlds, assets, stories, and simulation environments through algorithms and learned models.

See all 66 papers

Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning
Jul 13, 2026Emily Halina, Matthew GuzdialProcedural Content Generation
Department of Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta
Runtime Evaluation of Procedural Content Generation in an Endless Runner Game Using Autonomous Agents
May 3, 2026Rishabh KarGenerative Modeling Procedural Content Generation
Department of Informatics King’s College London London, United Kingdom
Learning Local Constraints for Reinforcement-Learned Content Generators
May 13, 2026Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis +1Constrained Generative Modeling Constrained RL
Institute of Digital Games, Msida, Malta · Game Innovation Lab, New York, New York, USA

Jul 13, 2026J/K move · Enter open · S save

Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning

Emily Halina, Matthew Guzdial

Department of Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta

Procedural Content Generation

Open paper AskPDF arXiv

Video games are a dynamic medium experienced over time. While there are many Procedural Content Generation (PCG) approaches for generating video game levels, they often use representations that abstract away this dynamic nature. In this paper, we introduce a novel, domain-independent ``cake'' representation for game levels over time which implicitly encodes dynamic information. We present a novel level generation approach Playtrace Reconstructive Partitioning (PRP) specifically developed for this cake representation. We compare against six state-of-the-art PCG approaches in the game domain of Sokoban, and find that our approach can generate valid levels without sacrificing solution diversity. We believe our cake representation more neatly encodes the implicit dynamic nature of games compared to existing representations, which allows for our domain-agnostic level generation algorithm PRP.

Abstract

Procedural Content Generation

Explore similar work

Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning

Runtime Evaluation of Procedural Content Generation in an Endless Runner Game Using Autonomous Agents

Learning Local Constraints for Reinforcement-Learned Content Generators