Xu et al.: „Mechanismen" des Spiels als Koordinaten aufwerten, um lösbare Level automatisch zu generieren — Fukai liest

Kurzzusammenfassung (TL;DR)

Die meisten PCG-Techniken zur automatischen Generierung von Spielleveln erstellen zunächst nur die Geländeform und überprüfen Mechanismen wie Sprung-Timing oder Gravitationsumkehrung erst nachgelagert. Dieser Artikel kehrt diese Reihenfolge um und schlägt „HDPCG (High-Dimensional PCG)" vor — ein Rahmen, der die Mechanismen selbst als Koordinate zusammen mit dem Terrain entwirft. Durch Pfadsuche auf einem erweiterten Graphen, der den Positionen die Achsen „Schicht" und „Zeit" hinzufügt, wird die Lösbarkeit des Levels während der Generierung garantiert. Die Autoren reproduzierten Gravitationsumkehrungs- und Bewegungsplatten-Level mit Lösungspfaden in Unity.

Einleitung

Dieser Artikel behandelt „High-Dimensional Procedural Content Generation" von Kaijie Xu und Clark Verbrugge von der McGill University (Montreal, Kanada). Es handelt sich um ein am 21. Februar 2026 auf arXiv eingereichtes Preprint (arXiv:2602.18943, Bereich cs.HC; formales Peer-Review nicht bestätigt). Der Artikel ist derzeit nur auf arXiv verfügbar, ohne etablierte Zitierungen — ein neues Werk, das noch nicht breit diskutiert wurde.

Ich habe diesen Artikel heute gewählt, weil er direkt meinem Kriterium „ist es nah an der Implementierung?" entspricht. PCG-Artikel bleiben oft theoretisch, aber dieser behandelt konkrete Mechanismen wie Gravitationsumkehrung und bewegliche Böden und reproduziert die generierten Level bis zu einer spielbaren Form in Unity.

Hintergrund

Die Forschung zur automatischen Level-Generierung konzentrierte sich lange auf die „Geländeform". Zeitabhängige Mechanismen oder diskrete Regelinteraktionen wurden typischerweise nach der Generierung durch Simulation oder Nachverarbeitung überprüft — was die Autoren als „geometry-first (Terrain zuerst)" bezeichnen.

Diese Reihenfolge hat eine Schwäche: Bei Levels, in denen Terrain und Mechanismen eng verknüpft sind, führt das Vorausfestlegen der Form und nachträgliches Hinzufügen von Mechanismen leicht zu unlösbaren Levels. Das von den Autoren identifizierte Problem ist das Fehlen einer „allgemeinen und erweiterbaren Darstellung" für Mechanismen direkt im Generator. Die Lösbarkeit während der Generierung zu garantieren, nicht danach — das ist der Ausgangspunkt dieses Artikels.

Ansatz (Methode)

Kurz gesagt: die Idee der Autoren ist es, „Mechanismen als Koordinaten aufzuwerten". Normalerweise werden Felder nur durch Position (x, y, z) gedacht, aber in HDPCG werden zusätzliche Achsen wie „Schicht" oder „Zeit" hinzugefügt. Jedes Feld enthält nicht nur „wo", sondern auch „welche Schicht / welche Sekunde". Die Autoren nennen dies einen „dimensional erweiterten Graphen (Dimensional-Expanded Graph)".

Auf diesem erweiterten Graphen wird die Lösbarkeit eines Levels zu einem einfachen Suchproblem: Kann man vom Start zum Ziel einen Pfad ziehen? Die Autoren verwenden A*, Breitensuche und dynamische Programmierung, um während der Generierung einen Lösungspfad zu finden. Wenn kein Pfad gefunden wird, ist das Level ungültig und die Parameter werden neu abgetastet — „Lösbarkeit" ist als unveränderliche Vorbedingung eingebaut.

Der Gesamtablauf ist in vier Schritte vereinheitlicht: (1) einen groben Skelettspfad ziehen; (2) um das Skelett herum Korridore, Schichtwechselpunkte, bewegliche Böden usw. ergänzen; (3) durch Pfadsuche auf dem erweiterten Graphen verifizieren; (4) das Level mit Metriken bewerten und Parameter bei Bedarf per genetischem Algorithmus neu erkunden.

Die Konkretisierung geht in zwei Richtungen. Die „räumliche Richtung" fügt Schichten zur Position hinzu für VVVVVV-artige Gravitationsumkehrungen, mit drei Methoden: NNB, NP-A*, PF-A*. Die „zeitliche Richtung" fügt Zeit zur Position hinzu für periodisch bewegliche Böden, mit statischem Skelett, TEG-A* und TEG-DP.

Befunde

Für die räumliche Richtung: Bei der Kontrollierbarkeit des minimalen Abstands der Wechselpunkte ist PF-A* nahezu perfekt. Der mittlere absolute Fehler (MAE) zur Zielgröße liegt für alle Größen bei ~0,00, verglichen mit ~0,09 für NP-A* und ~0,28–0,33 für NNB (Table 3). Beim Gesamtqualitätsscore gewinnt NP-A* bei kleiner/mittlerer Größe, PF-A* kehrt sich bei großer Größe um.

Für die Robustheit (kann nach dem Einfügen zufälliger Hindernisse ein anderer Pfad gefunden werden) zeigt nur PF-A* (Einzelausführung) eine gewisse Erfolgsrate (0,217 ± 0,40 bei großer Größe). Für die Geschwindigkeit: PF-A* in Einzelausführung dauert 4,1 s bei großer Größe, mit genetischem Algorithmus steigt das auf ~500 s (Table 4).

Für die zeitliche Richtung ist die Reihenfolge der Gesamtscores durchgehend: TEG-DP > TEG-A* > statisches Skelett. In beiden Richtungen wurden die generierten Level in Unity ausgeführt, was bestätigt, dass Gravitationsumkehrungen und Timing der beweglichen Böden dem berechneten Lösungspfad entsprechend funktionieren.

Einsatzmöglichkeiten

Wie können Spiel- und Puzzle-Designer das nutzen? Erstens: Bei einem Plattformer mit Gravitationsumkehrung im VVVVVV-Stil reicht es, zwei Regler anzupassen — „Schaltfrequenz (Dichte)" und „minimaler Abstand der Schaltpunkte" — um Abschnitte mit schnellen aufeinanderfolgenden Umkehrungen und ruhigere Abschnitte zu gestalten, mit Lösbarkeitsgarantie.

Zweitens: Bei Zeitverschiebungs-Puzzles im Stil von Dishonored 2 / Titanfall 2 steuern dieselben Regler den „Rhythmus der Zeitsprünge". Drittens: Bei Bewegungsplatten-Actionspielen im Stil von Super Mario 3D World kann man durch Eingabe von „Überlappungsanteil (ride ratio)" und „minimalem Ereignisabstand" als Zielwerte den Warten/Gehen/Reiten-Rhythmus vom Designer aus vorgeben.

Allgemeiner gesehen sehe ich den Hauptnutzen dieses Artikels im „Level Blockout". Automatisch in Masse Skelette mit garantiertem Lösungspfad erzeugen, dann von Hand verfeinern — diese Arbeitsteilung wird möglich.

Grenzen

Die Grenzen sind klar. Die vollständige Version von TEG-A* erfordert das Speichern von „welche Böden und Endpunkte wurden bereits verwendet" im Zustand, was zu kombinatorischer Explosion führt und selbst bei kleinster Größe zu einem Timeout führt. PCGML und Reinforcement Learning sind noch nicht integriert, Mechanismen werden achsweise separat bewertet, Level die Schichten und Zeit kombinieren sind nicht getestet. Robustheit bleibt eine Post-Generierungs-Prüfung, die nicht in die Optimierung eingebettet werden kann. Und entscheidend: Es gibt keine Benutzerstudie — der Beweis für „Spaß" ist eine künftige Aufgabe.

Zwei Anmerkungen von Fukai. Erstens garantiert diese Methode, dass „ein Lösungspfad existiert", nicht die gesamte Level-Erfahrung — ob der einzelne generierte Pfad wirklich den vom Designer beabsichtigten Rhythmus trägt, hängt von den Metrik-Gewichtungen ab. Zweitens beschränkt sich die Bewertung auf automatische Metriken und Replays; selbst wenn Abstand und Dichte präzise getroffen werden, liegt die Frage, wie sich das als „Biss" für den Spieler anfühlt, außerhalb des Rahmens dieses Artikels.

Fukais Lektüre

Im Folgenden meine Lektüre als Fukai. Ich möchte diese Forschung in die Verlagerung des Schwerpunkts von PCG „vom Terrain zu den Mechanismen" einordnen. Bisherige Level-Generierung fragte „was ist die Form?" und Lösbarkeit wurde nachgelagert geprüft. HDPCG verschiebt diese Frage zu „was ist das Zustandsübergangsnetzwerk?" und bettet Lösbarkeit als Designprämisse ein. In der Sprache der Designkritik ist das nahe an dem Versuch, das Erreichbarkeitsdenken, das Level-Designer implizit in ihrem Kopf tun, zu externalisieren und zu automatisieren. „Begehbare Pfade" statt „Form" als erstklassige Entität — das ist meine persönliche Interpretation.

Schlusswort — Eine Karte zur verwandten Forschung

Abschließend eine Karte zur verwandten Forschung. Zur Vertiefung hilft es, zusammen mit der Sturgeon-Reihe von Seth Cooper et al. (gleichzeitige Generierung von Level und Lösungspfad durch Constraint-Satisfaction) und dem raum-zeitlichen WaveFunctionCollapse von Kaylah Facey und Seth Cooper (Level-Generierung mit Zeitachse) zu lesen, um die Genealogie „Generieren mit einer Lösung" zu sehen. Für die Verbindungen mit PCGML und Reinforcement Learning, die dieser Artikel noch nicht angeht, bietet der manuelle PCG-Ansatz von Julian Togelius et al. einen guten Einstieg.

Literaturverzeichnis

In diesem Artikel herangezogene Studien und Ressourcen:

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

・HTML-Version desselben Artikels

・Verwandte Forschung: Seth Cooper & Mahsa Bazzaz, Sturgeon-MKIV (AIIDE 2024)

・Verwandte Forschung: Kaylah Facey & Seth Cooper, Toward space-time WaveFunctionCollapse (AIIDE 2024)

※ Alle Zahlen basieren auf dem Text, Table 3 / Table 4 dieses Artikels. Keine Zitierungen — noch nicht breit diskutiertes neues Werk.