PaperlayerView exact revision on arXiv

Source-linked AI summary

Syntactic Segmentation and Collage Generation for Videogame Levels with Perceptual Distance

Ross Mawhorter, Matthew Guzdial

arXiv:2610.38987v1cs.AI

TL;DR

Procedural level design often relies on hand-authored chunks or constraints, while existing tile-based approaches can miss longer-range dependencies. This paper uses perceptual distance and hierarchical clustering to segment existing designs, then demonstrates a proof-of-concept collage generator; its segmentations cover StarCraft and Super Metroid, but gameplay properties of generated levels are unchecked.

  • Problem

    Procedural level generators often require hand-authored chunks or rules, and tile-based methods can miss longer-range dependencies.

    Source: Introduction · p. 1

  • Method

    The paper defines perceptual distance from scaled isovist information and uses it in Perceptual Distance Segmentation, a hierarchical clustering algorithm for level designs.

    Source: Introduction · p. 1

  • Results

    PDS produced high-level segmentations of StarCraft and Super Metroid designs, and at B = 3, 21% of border pairs were compatible in the Big Pink collage example.

    Source: Collage Generation Results · p. 7, Conclusion · p. 9

  • Takeaways & Limitations

    The segmentations provide a basis for a proof-of-concept generator that remixes existing level designs using automatically identified segments.

    Source: Conclusion · p. 9

    PDS uses visibility even though 2D game graphics and gameplay do not depend on it, and the collage generator does not check gameplay properties of its outputs.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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.

Introduction

The paper addresses the hand-authoring involved in procedural level design by introducing perceptual-distance segmentation for existing 2D designs. It proposes using the resulting segments for graph abstraction and collage-based generation.

Introduction

  • The value of a segmentation depends on its purpose; for StarCraft tactical analysis, clusters and their edges represent map regions and choke points useful for unit movement.The paper distinguishes this tactical purpose from segmentation for higher-level design structure.Source: Introduction · p. 1
  • Tile-based generators can capture short-range relationships but often miss longer-range dependencies, leading existing approaches to rely on hand-authored constraints or rules.The paper does not apply its approach to this task.Source: Introduction · p. 1
  • The method can automatically create a graph abstraction from an existing tile representation, unlike approaches that rely on hand-authored rules or example graphs.Source: Introduction · p. 1
  • The paper explores using automatically identified segments as components for collage-based procedural level generation.Its contributions include a basic algorithm that remixes existing content and an example application to Super Metroid.Source: Introduction · p. 1
  • Perceptual Distance Segmentation uses a perceptual-distance metric in a hierarchical clustering algorithm to segment 2D level designs.The paper introduces perceptual distance based on scaled isovist information.Source: Introduction · p. 1

Background

The background connects videogame level analysis to architectural space-analysis techniques and prior segmentation approaches. It also frames automatic segmentation as a way to identify chunks for collage-based generation.

Background

  • Architectural analysis techniques have been applied to videogames, including Lynch-inspired descriptions of open-world games and isovist measures correlated with human evaluations of Minecraft settlements.Source: Background · p. 2

Level Segmentation

  • BWTA and PDS both identify and merge regions before finding boundaries, but use different criteria; tactical choke-point detail can be unsuitable for a high-level design structure.A small solid island may matter for arranging units but need not define a separate design region.Source: Level Segmentation · p. 2

Isovist Analysis and Space Syntax

  • Isovist analysis studies how visible points change with position; prior partitions include convex and axial maps, while some partition schemes are too restrictive for discontinuous spaces that may need slightly concave regions.Source: Isovist Analysis and Space Syntax · p. 2
  • An isovist-cover method can produce overlapping segments that do not cover the space, while Zhao et al.'s visibility-and-travel-distance metric trades off those criteria with λ.At small λ, travel distance can needlessly separate large convex rooms; at large λ, the method shares theoretical problems with other isovist-based methods.Source: Isovist Analysis and Space Syntax · p. 2

Collage Generation

  • Collage-based generation pastes segments from a pre-existing library, but commonly requires authors to create those chunks; this work explores identifying them automatically from existing designs.Source: Collage Generation · pp. 2–3

Perceptual Segmentation

The paper segments spaces by clustering locations with similar visibility, using perceptual distance to measure how much an observation distinguishes where it came from. It finds flux minima as candidate room centers, clusters them hierarchically, and assigns remaining points to the nearest cluster.

Perceptual Segmentation

  • Grid points are hierarchically clustered by visibility similarity, reflecting that points in a convex room are mutually visible and room-like regions approximate that pattern.Source: Perceptual Segmentation · p. 3

Perceptual Distance

  • Perceptual distance measures information about an observer gained from the visible boundary point, approximated by segment probabilities proportional to angular area.Source: Perceptual Distance · p. 3

Properties of Perceptual Distance

Perceptual Fields and Perceptual Flux

Level Segmentation with Perceptual Distance

Perceptual Segmentation Experiments

The experiments tune a shared perceptual-distance threshold, compare PDS with BWTA on StarCraft maps, and apply PDS to Super Metroid rooms. Ablations examine two design choices.

Threshold Selection

  • 0.59 bits was used across evaluations after the chosen Hallway and Ring segmentations required thresholds of 0.56 and 0.59 bits, respectively.The authors describe threshold choice as more art than science and report that values between 0.5 and 0.6 bits tend to work across domains.Source: Threshold Selection · p. 5

Comparison to Prior Work on Starcraft

  • The StarCraft comparison used 24 of 48 BWTA maps and discretized, downsampled map data; the authors call it an imperfect comparison.The BWTA output images were larger than the underlying maps, motivating downsampling.Source: Comparison to Prior Work on Starcraft · p. 5
  • 86% of points agree with their assigned cluster in the PDS–BWTA comparisons, although some maps differ sharply.Longinus has the sample’s highest agreement score (0.96), while Andromeda 1.0 has the lowest (0.71).Source: Figure 3 · p. 5, Figure 4 · p. 5, Table 1 · p. 6

Results on Super Metroid

  • PDS splits Green Hill Zone side passages at bottlenecks, resolves Big Pink’s ambiguous space with concave rooms, and detects Bubble Mountain structures at multiple scales.The selected Super Metroid rooms are parsed using Layer 1 tiles; slopes and other partially solid tiles are treated as empty.Source: Results on Super Metroid · p. 6
  • PDS segmentations are only one interpretation and may not align with human intuition, yet the examples show reasonable interpretations with one hyperparameter choice.Source: Results on Super Metroid · pp. 6–7

Ablations

  • On Bubble Mountain, No Minima and Smaller Surfaces produced agreement scores of 0.93 and 0.96 with PDS; No Minima was over 10× slower.These initial ablation results cover one example and support the authors’ algorithm design choices.Source: Ablations · p. 7

Collage Generation using Perceptual Distance

The collage generator builds new layouts by attaching segments from a PDS segmentation wherever their borders match. On “Big Pink,” the outputs varied in shape and branching, though some placements left graphical mismatches or unfilled borders.

Collage Generation using Perceptual Distance

  • PDS segments a level first, then the generator repeatedly attaches a remaining segment matching an existing border until segments run out, the target is reached, or no match remains.After each placement, borders are recomputed because it can create a new border shape for later matches.Source: Collage Generation using Perceptual… · p. 7
  • Only borders facing in opposite directions are compatible; border matching seeks overlapping interior and exterior faces while avoiding tile disagreement and underlap.Placement conflicts with already placed rooms can also create tile disagreements and unintended entrances.Source: Collage Generation using Perceptual… · p. 7
  • Raising the badness threshold permits more placements but can also produce awkward layouts or empty spaces that no existing segment can fill.Badness counts placement violations, including tile disagreement, underlap, and conflicts with placed rooms.Source: Collage Generation using Perceptual… · p. 7

Collage Generation Results

  • At B = 3, 21% of border pairs are compatible (40% at B = 18), while generated “Big Pink” remixes vary in shape and internal branching.“Big Pink” contains 34 segments and 73 borders; its average interior border size is 2.4±1.5 tiles.Source: Collage Generation Results · p. 7
  • The generated outputs include neighboring tiles that do not match graphically because the algorithm pastes segments without retiling them.The authors identify WFC as a possible fit for retiling, but do not apply it here.Source: Collage Generation Results · p. 7
  • The example outputs look navigable, but the authors do not evaluate their gameplay properties.The collage algorithm is presented as a proof of concept.Source: Collage Generation Results · p. 7
  • Some generated borders remain graphically disconnected, but the examples attribute these cases to destructible blocks or tiles without collision.Some outputs also stop before the requested room count when no valid match remains for a border.Source: Collage Generation Results · p. 8, Figure 9 · p. 8

Discussion

The discussion contrasts PDS with visibility-based alternatives, then describes constraints on its use and possible extensions. In particular, PDS avoids the long-hallway issue of interior-visibility methods, but its runtime and 2D visibility basis limit its current scope.

Alternative Approaches

  • Unlike interior-point visibility methods, PDS considers visible surfaces and scales their importance by distance, avoiding the long-hallway case where points in one room can appear more dissimilar than a hallway point.The Jaccard-based isovist method illustrates this problem; other interior-visibility methods are described as sharing it.Source: Alternative Approaches · p. 8, Figure 12 · p. 9, Figure 11 · p. 9
  • Leiden segmentation of the visibility graph can identify two rooms linked by a hallway, but its resolution setting varies across room regions, making large varied rooms difficult to handle.The approach treats locations as graph points and mutual visibility as unweighted edges.Source: Alternative Approaches · pp. 8–9

Limitations

  • PDS relies on visibility even though 2D game graphics and gameplay do not depend on that notion; the authors suggest trajectory bottlenecks as a possible alternative with full game-dynamics knowledge.Its runtime is O(s^6), with StarCraft segmentation averaging 2.4±0.8 hours per map and Super Metroid examples finishing in under four minutes.Source: Limitations · p. 9
  • Without algorithm improvements, PDS would be difficult to apply at larger scales or in three dimensions.Almost all (84%) of the StarCraft runtime is spent computing surface probabilities.Source: Limitations · p. 9
  • The collage generator is a proof of concept: it does not check gameplay properties, usually leaves borders unfilled, and does not deliberately create the cycles common in original designs.Some rooms also yield unsatisfactory outputs because segmentation identified disconnected segments or borders with only one valid match.Source: Figure 10 · p. 8, Limitations · p. 9

Future Work

  • Perceptual distance could extend to 3D by discretizing surfaces into triangles and treating each triangle’s angular area as a probability distribution.The same segmentation algorithm could then be used to analyze 3D structures.Source: Future Work · p. 9
  • A room that curves smoothly without a clear edge, such as an S-shaped room, may be split into multiple segments; clustering based on edge perceptual flux could potentially keep it together.Source: Future Work · p. 9
  • Perceptual flux could also guide a generator to match a specified flux distribution, following the building-design idea attributed to Benedikt.Source: Future Work · p. 9

Conclusion

The paper applies architectural analysis techniques to create Perceptual Distance Segmentation for 2D maps, then uses the resulting segmentations to support a proof-of-concept collage generator that remixes existing levels.

Conclusion

  • PDS summarizes high-level structure in StarCraft and Super Metroid level designs and provides the basis for a collage generator that remixes an existing design from a single input.The paper frames this as one step toward understanding level-design patterns at multiple scales.Source: Conclusion · p. 9
Loading 2610.38987v1…