cs.AIOct 28, 2026
SaveSyntactic Segmentation and Collage Generation for Videogame Levels with Perceptual Distance
Organizations: University of Alberta 116 Street and 85th Avenue Edmonton, AB T6G 2R3
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.
| Metric | Value |
|---|---|
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 ( 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