cs.AIOct 28, 2026

Syntactic Segmentation and Collage Generation for Videogame Levels with Perceptual Distance

Authors: Ross Mawhorter, Matthew Guzdial

Organizations: University of Alberta 116 Street and 85th Avenue Edmonton, AB T6G 2R3

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

In procedural videogame level design, many existing techniques combine hand-authored level chunks. Some existing analysis techniques also rely on a higher-level graph structure which abstracts the level design. In this paper, we explore techniques for computing both of these things automatically from an existing design. We introduce the concept of perceptual distance, based on analysis techniques from the architecture subfield of Space Syntax. We use this perceptual distance to segment level designs with hierarchical clustering. We compare with past work on StarCraft analysis, show results on rooms from Super Metroid, and also demonstrate a proof-of-concept level generation algorithm based on this segmentation method.

Figures & tables

Figure 1: The pipeline for computing the Perceptual Distance Segmentation shown on “Bubble Mountain” from Super Metroid . We begin by computing the probability of observing (angular area of) each visible surface (orange) from each point. The figure shows an example for a single point. Second, we use the Jensen-Shannon divergence of these probabilities to compute an approximate rate of change at each interior point (perceptual flux). We then find the minima of this field, and cluster the minima hierarchically based on the perceptual distance. Finally, the non-minima points are assigned to the cluster that they are closest to (in terms of perceptual distance).
Figure 2: Left: Three scaled versions of the same figure, clustered with perceptual distance. The threshold of 0.56 bits is the lowest threshold that does not separate either hallway at the two larger scales. Right: a room with an interior obstacle which is clustered with perceptual distance into a single cluster. The threshold of 0.59 bits is the lowest threshold that does not separate this room into multiple clusters.
Figure 3: Clusterings for the StarCraft map Longinus. Longinus is the map from our sample with the highest cluster agreement score (0.96). Red shaded regions indicate cluster disagreement. The primary difference is that BWTA creates an additional cluster near the center. BWTA does not split the small top-right spur into multiple segments
Figure 4: Clusterings for the StarCraft map Andromeda 1.0. Andromeda 1.0 is the map from our sample with the lowest cluster agreement score (0.71). Red shaded regions indicate cluster disagreement. PDS creates a large central cluster, whereas BWTA breaks this central cluster into smaller parts.
MetricValue
A(PDS,BWTA)A(\mathrm{PDS},\mathrm{BWTA})0.83±0.100.83\pm 0.10
A(BWTA,PDS)A(\mathrm{BWTA},\mathrm{PDS})0.88±0.030.88\pm 0.03
S(PDS,BWTA)S(\mathrm{PDS},\mathrm{BWTA})0.86±0.050.86\pm 0.05
S(Random,BWTA)S(\mathrm{Random},\mathrm{BWTA})0.17±0.060.17\pm 0.06
Table 1: Average cluster agreement values with standard deviation comparing PDS with BTWA segmentations. The Random entry compares BWTA to random segmentations to obtain a baseline. Overall the segmentation agreement scores are high ( 86%86\% of points agree with their assigned cluster).
Figure 5: Detail from the generated clustering for the “Green Hill Zone” (room 0x79E52 ).
Figure 6: Detail from the generated clustering for “Big Pink” (room 0x79D19 ).
Figure 7: Detail from the generated clustering for “Bubble Mountain” (room 0x7ACB3 ).
Figure 8: Example collage border match. Overlap (good) refers to locations where the inner and outer borders of the two rooms overlap. Disagreement (bad) refers to locations where one room has a solid tile and the other has an air tile (or vice versa). Underlap (bad) is the set of locations of either border that are not covered by the other room. Border tiles are the remaining additional borders of the current collage. The border in the top left is due to hidden tiles: the ceiling there looks solid but does not have collision.
Figure 9: Randomly-selected generated collage outputs from “Big Pink” (seeds 343, 344, 345, and 346). Sub-rooms are color-coded based on the segmentation from Figure 6 . Red dots indicate remaining unfilled borders. Each generated output uses a badness threshold of 3 and adds up to 10 rooms. In the bottom right (seed 346), an awkward placement ends the generation at only 6 rooms: there are no valid matches for the remaining border.
Figure 10: Randomly-selected generated collage outputs from “Green Brinstar Entrance” (room 0x79AD9 ) (seeds 343 and 344). Seed 343 is disconnected because one of the identified clusters was disconnected.
Figure 11: A long hallway segmented with two different methods. In IJI, clusters below size 6 are also merged and the threshold value of 0.4 is chosen manually by the authors for best results. For PDS, the threshold value of 0.59 is the same as our other domains. While the PD segmentation splits the hallway in two and does have some intrusion of the rooms into the hallway, the IJI segmentation also has some segments within a room due to the sudden increase in the area of the isovist once the hallway is visible.
Figure 12: The Long Hallway Problem. Moving from the red point (inside the hallway) to the green point (inside the room) allows a viewer to see the two interior corners of the room which were previously invisible. Moving from the blue point (inside the room) to the green point allows the viewer to see the hallway. If the hallway is sufficiently long, interior visibility approaches will treat the blue point as more dissimilar from the green point than the red point even though the green and blue points are both in the same room.
More in this topic

Procedural Content Generation

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

See all 67 papers

Explore similar work

CardsList
Jul 13, 2026

Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning

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.

Emily Halina, Matthew Guzdial

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

Procedural Content Generation
AskPDF
Feb 21, 2026

High Dimensional Procedural Content Generation

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.

Kaijie Xu, Clark Verbrugge

McGill University Montreal, Quebec, Canada

Procedural Content Generation
AskPDF
Mar 16, 2026

GameUIAgent: An LLM-Powered Framework for Automated Game UI Design with Structured Intermediate Representation

Game UI design requires consistent visual assets across rarity tiers yet remains a predominantly manual process. We present GameUIAgent, an LLM-powered agentic framework that translates natural language descriptions into editable Figma designs via a Design Spec JSON intermediate representation. A six-stage neuro-symbolic pipeline combines LLM generation, deterministic post-processing, and a Vision-Language Model (VLM)-guided Reflection Controller (RC) for iterative self-correction with guaranteed non-regressive quality. Evaluated across 110 test cases, three LLMs, and three UI templates, cross-model analysis establishes a game-domain failure taxonomy (rarity-dependent degradation; visual emptiness) and uncovers two key empirical findings. A Quality Ceiling Effect (Pearson r=-0.96, p<0.01) suggests that RC improvement is bounded by headroom below a quality threshold -- a visual-domain counterpart to test-time compute scaling laws. A Rendering-Evaluation Fidelity Principle reveals that partial rendering enhancements paradoxically degrade VLM evaluation by amplifying structural defects. Together, these results establish foundational principles for LLM-driven visual generation agents in game production.

Wei Zeng, Fengwei An, Zhen Liu +1

School of Microelectronics, Southern University of Science and Technology (SUSTech), Shenzhen, China · Zhongguancun Academy, Beijing, China · School of Marxism, Tsinghua University, Beijing, China

Vision-Language AgentsLLM Agent Self-Improvement
AskPDF