Xu & Verbrugge: „Richtung der Schwerkraft" und „Zeit" als Koordinaten der Levelgenerierung — gelesen von Fukai

Zusammenfassung in einem Absatz

Automatische Levelgenerierung war lange „Terrainarbeit": Wände, Böden und Gänge werden angeordnet, und erst danach werden Mechaniken wie „Schwerkraft kann umgekehrt werden" oder „die Plattform bewegt sich" nachträglich geprüft. Kaijie Xu und Clark Verbrugge von der McGill University haben diese Reihenfolge umgedreht: Ihr Vorschlag ist, die Mechanik selbst zur Koordinate zu erheben und sie zusammen mit dem Terrain zu durchsuchen.

Das Framework heißt HDPCG (High-Dimensional Procedural Content Generation, hochdimensionale prozedurale Inhaltsgenerierung). Zu den Rasterkoordinaten (x, y) wird etwa „auf welcher Ebene man sich gerade befindet" oder „welche Sekunde es gerade ist" hinzugefügt, wodurch ein großer Graph entsteht. Führt man auf diesem Graphen eine gewöhnliche Pfadsuche durch, lässt sich eine Anforderung wie „ein Pfad mit genau drei Schwerkraftumkehrungen" bereits während der Generierung erfüllen — nicht erst durch nachträgliche Prüfung.

Ich habe die auf arXiv hinterlegte Version gelesen. Ein Beitrag mit demselben Titel ist in den Proceedings der FDG 2026 (21. Foundations of Digital Games) erschienen — die Forschung hat die Begutachtung durchlaufen.

Über diesen Beitrag

Der Titel lautet „High Dimensional Procedural Content Generation". Die Autoren, Kaijie Xu und Clark Verbrugge, gehören beide der McGill University in Montreal, Kanada, an.

Ich habe die arXiv-Version gelesen, auf deren Seitenrand „arXiv:2602.18943v1 [cs.AI] 21 Feb 2026" gedruckt ist — ein am 21. Februar 2026 eingereichtes Preprint (ein vor der Begutachtung veröffentlichtes Manuskript). Ein Beitrag mit demselben Titel ist jedoch mit DOI in den Proceedings der FDG 2026 erschienen, die vom 10. bis 13. August an der Royal Danish Academy in Kopenhagen stattfand. Das heißt, die Begutachtung wurde durchlaufen. Ich weise darauf hin, dass die folgenden Zahlen aus der arXiv-Version stammen und sich im Detail von der endgültigen Fassung der Proceedings unterscheiden können.

Ich habe diesen Beitrag heute ausgewählt, weil es sich, von einer Puzzle-Website aus gesehen, um eine seltene Art von Forschung handelt, die sich „direkt umsetzen" lässt. Schwerkraftumkehr, Wechsel zwischen Parallelwelten, Plattformen, die man durch Anhalten der Zeit passiert — all das sind zentrale Verben des Puzzle-Plattformers, die diese Seite bereits unter Das Verb, die Schwerkraft umzudrehen behandelt hat. Diese Forschung treibt die Frage über „kann man generieren" hinaus bis zu „kann man nach Bestellung generieren".VVVVVV (Terry Cavanagh, 2010), Steam-Storeseite. Ein Knopfdruck genügt, um die Schwerkraft oben/unten zu vertauschen. Der Beitrag nennt dieses Spiel als Vorbild für seine Unity-Nachbildung.

Was bisher bekannt war

PCG (Procedural Content Generation, automatische Inhaltsgenerierung) bezeichnet die Technik, Level und Assets maschinell erzeugen zu lassen. Jahrzehntelang erforscht, ist der Teil, der Terrain erzeugt, inzwischen recht ausgereift. Nach Aussage der Autoren bleibt die Formulierung der Levelgenerierung dennoch „largely geometry-first" (überwiegend geometrieorientiert).

Wie wurden Mechaniken bisher behandelt? Der Beitrag ordnet ein, dass zeitabhängige Bewegung, diskrete Interaktionsregeln und andere Zustände als das Terrain nicht direkt im Generator dargestellt, sondern als simulationsbasierte Zielfunktionen oder Nachbearbeitungs-Heuristiken eingespeist wurden. Die Reihenfolge lautet: erst bauen, dann spielen lassen, bei Misserfolg Punkte abziehen.

Diese Reihenfolge hat eine Schwäche. Die Autoren schreiben, dass „die Simulation Anforderungen nur indirekt erzwingt", weshalb es schwierig wird, während der Generierung gezielt eine bestimmte mechaniklastige Levelstruktur anzusteuern. Will man „ein Level mit drei Schwerkraftumkehrungen" erzeugen, bleibt nur, per Zufall zu bauen, zu zählen und zu verwerfen — wieder und wieder.

Ausgangspunkt ist daher, dass nicht ein einzelner Algorithmus fehlt, sondern die Repräsentation selbst. Nötig ist eine allgemeine, erweiterbare Repräsentation samt Problemstellung für mechanikreiche Level.

Wie das Problem gelöst wurde

Die Idee ist erstaunlich einfach. Man stattet die Rasterzellen mit „Attributen" aus und schreibt den Weltzustand als Zelle in einem erweiterten Zustandsraum. Damit kann das Pfadsuchprogramm Terrain und Mechanik gemeinsam in einem einzigen Graphen betrachten. Nur der Graph wird größer — die Art der Suche ändert sich nicht.

一つ目の軸は空間(Direction-Space)である。地形に「層」という飛び飛びの次元を足し、(x, y, z, 層)という4つの座標で到達できるかどうかを検証する。こうすると、重力の反転も、並行世界の切り替えも、「層をまたぐ辺を1本通った」という同じ出来事として扱える。バラバラだった仕掛けが一つの型に収まる。

Die erste Achse ist der Raum (Direction-Space). Dem Terrain wird eine diskrete Dimension namens „Ebene" hinzugefügt, und die Erreichbarkeit wird mit den vier Koordinaten (x, y, z, Ebene) geprüft. So lassen sich Schwerkraftumkehr und Wechsel zwischen Parallelwelten als dasselbe Ereignis behandeln: „eine ebenenübergreifende Kante wurde durchlaufen". Bisher disparate Mechaniken passen in eine einzige Form.

Die zweite Achse ist die Zeit (Direction-Time). Hier kommt ein zeitexpandierter Graph zum Einsatz (time-expanded graph: dieselbe Karte wird für jeden Zeitschritt dupliziert und durch Kanten verbunden, die den Zeitverlauf darstellen). Die Aktionen der Spielerin werden als drei Übergangsarten geschrieben — „warten", „gehen", „aufsteigen" —, mit Einschränkungen wie der Prüfung, ob die Zelle gerade belegt ist, oder dass man bewegliche Plattformen nur an den Endpunkten betreten oder verlassen kann.

Beide Achsen durchlaufen dieselbe vierstufige Pipeline: zuerst ein grobes Grundgerüst erzeugen, dann kontrolliert ins Terrain umsetzen, auf dem hochdimensionalen Graphen auf Gültigkeit prüfen und schließlich mit mehreren Kennzahlen bewerten. Auf der Raumseite stehen drei Verfahren bereit: Naive Noise Baseline (NNB), das nur mit i.i.d.-Rauschen (unabhängig und identisch verteilt) erzeugt; Naive Penalty A* (NP-A*), das um bereits durchlaufene Stellen Abstoßung legt, um zu streuen; und Potential Field A* (PF-A*), das Umschaltpunkte direkt mit Anziehungs- und Abstoßungsfeldern anvisiert.

Auch auf der Zeitseite gibt es drei Verfahren: Static Backbone Baseline, das zunächst mit 2D/3D-A* ein Grundgerüst zieht und danach periodische Plattformen und Hindernisse per Breitensuche auf Gültigkeit prüft; TEG-A*, mit einem leichten Bitmasken-Gedächtnis; und TEG-DP, ein dynamisches Programmierverfahren, das auf einem geschichteten, gerichteten azyklischen Graphen vorwärts löst.

Ergebnisse

Auf der Raumseite ist die klarste Zahl die zur „Bestellungstreue". Beim Fehler zum Ziel-Umschaltintervall (MAE, mittlerer absoluter Fehler) liefert Tabelle 3 für PF-A* bei kleiner, mittlerer und großer Skalierung: 0,002 / 0,000 / 0,000. NP-A*: 0,091 / 0,093 / 0,097. Das ungesteuerte NNB: 0,288 / 0,284 / 0,326. Gezielt platzierende Verfahren halten die Intervall-Bestellung nahezu perfekt ein.

Bei der Umschaltdichte sieht es weniger sauber aus. In derselben Tabelle 3 erreicht PF-A* 2,247 / 2,078 / 1,343, NP-A* 2,217 / 1,366 / 2,554 — die beiden Verfahren gewinnen und verlieren je nach Skalierung gegeneinander. NNB liegt jedoch bei 9,410 / 8,738 / 10,978, eine ganze Größenordnung darüber. Man kann lesen: „Steuerung wirkt" ist eindeutig, aber „welche Steuerung stärker ist" hängt von der Skalierung ab.

Als Robustheitskennzahl misst der Beitrag ARR (alternative route robustness, Bestand alternativer Routen). Im Durchschnitt einzelner Durchläufe erreicht PF-A* bei kleiner, mittlerer und großer Skalierung 0,338 / 0,319 / 0,530, NP-A* 0,156 / 0,215 / 0,360, NNB 0,037 / 0,042 / 0,057. Im Vergleich zur ungesteuerten Variante bleiben bei PF-A* etwa 9- bis 10-mal so viele alternative Routen erhalten — es entstehen also nicht überall Sackgassen.

Auch die Geschwindigkeit liegt im praktikablen Bereich. Laut Tabelle 4 dauert ein einzelner Durchlauf von PF-A* bei kleiner Skalierung 0,138 ± 0,060 Sekunden, bei mittlerer 0,663 ± 0,278 Sekunden und selbst bei großer Skalierung 4,119 ± 1,136 Sekunden. Wenige Sekunden für ein Level — für einen täglichen Batch mehr als ausreichend.

Auf der Zeitseite sind die Versuchsgrößen klar angegeben. Tabelle 2: klein = 30×15 Zellen, Zeitobergrenze 200, 12 Zufallssamen; mittel = 50×25, Obergrenze 300, 8 Samen; groß = 80×40, Obergrenze 500, 4 Samen. Der Gesamtscore aus Tabelle 6 (einzelner Durchlauf) bei großer Skalierung: Static Backbone 7,81 ± 1,77, TEG-A* 13,30 ± 3,51, TEG-DP 20,35 ± 9,58. Benötigte Zeit: 0,31 ± 0,20 s / 0,25 ± 0,18 s / 6,42 ± 0,68 s.

Tabelle 5 zeigt, dass TEG-DP TEG-A* signifikant übertrifft — „in allen Fällen außer zwei Einstellungen (kleine Skalierung einzeln, mittlere Skalierung einzeln)" — mit einer Effektgröße (Cliffs Delta), die als „large" berichtet wird. Ein vertrautes Ergebnismuster: je sorgfältiger gelöst wird, desto besser, aber auch desto langsamer.

Wie Entwicklerinnen es nutzen können

Erstens. Wer ein Schwerkraftumkehr-Puzzle baut, kann „Anzahl der Umschaltungen" und „Umschaltintervall" als Bestellung übergeben. Dieser Beitrag zeigt, dass eine Intervall-Bestellung mit nahezu null Fehler eingehalten werden kann. Eine Schwierigkeitskurve wie „am Anfang weite Intervalle, gegen Ende enger" lässt sich in Worten festlegen und direkt als Parameter des Generators verwenden — Generieren, Zählen, Verwerfen entfällt.

Zweitens. Für eine Stage mit beweglichen Plattformen lässt sich mit dem zeitexpandierten Graphen das Verhältnis von „Warten" zu „Fahren" gestalten. Der Anteil der Zeit, in der die Spielerin stillsteht, der Anteil auf der Plattform, das Kontaktintervall — diese Kennzahlen stehen nebeneinander, sodass sich das „Gefühl des Wartenmüssens" wie ein Regler behandeln lässt. Die Tempoabstimmung wird zu einer zahlenmäßigen Bestellung statt einer Gefühlssache.Contrast (Compulsion Games, 2013), Steam-Storeseite. Man wechselt zwischen einer dreidimensionalen Welt und einer an Wände geworfenen Schattenwelt. Hier als anschauliches Beispiel für das Verb „Ebene wechseln" angeführt (kein im Beitrag behandeltes Spiel).

Drittens. Auch für alle nützlich, die nicht generieren. Man muss nur ein von Hand gebautes Level auf diesen erweiterten Graphen legen. Ob es einen „Schleichweg zum Ziel ohne Schwerkraftumkehr" gibt, lässt sich klären, indem man die Pfadsuche mit verbotenen ebenenübergreifenden Kanten laufen lässt. Man muss nicht den gesamten Generator einführen, sondern kann nur den Prüfer herauslösen.

Viertens. Ein Störungstest als Qualitätsschranke. Der Beitrag misst Robustheit, indem nach der Generierung kleine Störungen eingeführt werden und geprüft wird, ob sich neu bauen lässt. Dasselbe lässt sich im Betrieb nutzen: Bei einem täglichen Puzzle könnte man vor der Veröffentlichung „eine Plattform um ein Feld verschieben" oder „um einen Takt verzögern" ausprobieren und Spielfelder, deren Lösung dabei zerbricht, nicht ausliefern. Der Gedanke: eine Kennzahl wie ARR als Freigabekriterium zu nutzen.

Fünftens, als Warnhinweis. „Bestellungstreue" und „unterhaltsam" sind zwei verschiedene Dinge. Alle Kennzahlen dieses Beitrags messen Ersteres. Wer einen Generator einführt, sollte auch bei durchweg grünen Kennzahlen nicht auf Playtests verzichten.

Grenzen

Die Autoren nennen fünf Grenzen. Erstens muss das ideale TEG-A* auf der Zeitseite den Zustand mit Gedächtnis und Belohnung aufblähen, um „sinnvolle, sich nicht wiederholende Kontakte" zu fördern, was zu einer Zustandsexplosion führt. In der Praxis wird daher eine vereinfachte Version verwendet, die zwar handlicher ist, aber weniger Kraft hat, Interaktionen strikt zu formen — das lasse, so die Autoren, eine Lücke zwischen der Static-Baseline und DP.

Zweitens werden nur konstruktive, suchbasierte Verfahren behandelt; PCGML (PCG mittels maschinellem Lernen) oder Reinforcement Learning (ein Rahmen, in dem durch Versuch und Irrtum Handlungen mit höherer Belohnung gelernt werden), die in diesem hochdimensionalen Zustandsraum Vorwissen oder Wertfunktionen lernen könnten, sind noch nicht integriert. Drittens werden die Mechanik-Achsen einzeln getrennt bewertet; Erfolg und Skalierungsverhalten beim Mischen mehrerer Mechaniken in einem gemeinsamen Zustandsraum sind unbewertet. Viertens wird Robustheit nur nachträglich durch Störung gemessen und fließt nicht in die Fitness eines genetischen Algorithmus ein (das würde wiederholtes Neubauen erfordern und die Kosten stark erhöhen).

Und der fünfte Punkt wiegt am schwersten. Die Autoren schreiben ausdrücklich „we have not conducted user studies" (es wurden keine Nutzerstudien durchgeführt): Spielbarkeit und Tempo werden zwar durch Kennzahlen und Replays gestützt, doch ein formaler Beleg für den Spielspaß bleibt zukünftige Arbeit, wie sie einräumen.

Fukai weist hier auf den Vergleichspartner hin. Die Baseline NNB auf der Raumseite ist ein nahezu ungesteuertes Verfahren („i.i.d.-Rauschen und Ebenenwechsel in numerischer Reihenfolge"). Die Zahl „9- bis 10-mal besser" liest sich ehrlicherweise eher als sorgfältige Bestätigung der Selbstverständlichkeit, dass Steuerung besser ist als keine Steuerung. Eine Tabelle, die direkt mit bestehenden PCG-Verfahren vergleicht, habe ich in dem, was ich gelesen habe, nicht gefunden.

Noch ein Punkt: TEG-DP braucht bei großer Skalierung 6,42 Sekunden für einen einzelnen Durchlauf, aber sobald man es in einem genetischen Algorithmus laufen lässt, ändert sich die Größenordnung. Für einen Anwendungsfall wie ein tägliches Puzzle (eines pro Tag) ist das kein Problem, aber für eine Generierung während des Spiels selbst reicht der Stand dieses Beitrags meiner Lesart nach noch nicht aus.

Fukais Lesart

Ich möchte diese Forschung in die Bewegung einordnen, in der „Levelgenerierung vom Kartenzeichnen zur Constraint-Erfüllung umzieht". Im Vokabular der Designkritik ist das eine Arbeit, die die „Verbplatzierung", die Level-Designerinnen im Kopf implizit vornehmen, in durchsuchbare Koordinaten übersetzt. In dem Moment, in dem Schwerkraftumkehr nicht mehr als „Bildelement", sondern als „Kante im Graphen" geschrieben wird, werden sowohl Intervall als auch Anzahl bestellbar. Interessant ist, dass dafür kaum ein neuer Algorithmus erfunden wurde. Man behält die alten Werkzeuge A* und dynamische Programmierung bei und ändert nur, wie das Spielfeld geschrieben wird. Ich lese darin einen Beitrag, der die klassische Lehre — dass ein Wechsel der Repräsentation ein Problem leichter macht — im Vokabular des Puzzle-Plattformers zeigt.

Schluss

Der Beitrag enthält auch eine Demonstration in Unity. Auf der Raumseite ein 2,5D-Level mit Schwerkraftumkehr sowie ein 3,5D-Level, das zwischen zwei Zeitzuständen wechselt, um Terrain und Gegner zu durchqueren. Für Letzteres werden A Crack in the Slab aus Dishonored 2 und Effect and Cause aus Titanfall 2 als Vorbilder genannt. Die Autoren schreiben: „Was generiert wird, ist direkt ein Unity-Level; was man sieht, ist direkt spielbar." Im Fazit bleibt es zukünftige Arbeit, diese Kennzahlen mit gefühltem Tempo, Spielgefühl und Spaß zu verknüpfen.

Für alle, die tiefer einsteigen wollen: Liest man dazu Arbeiten aus derselben Konferenzreihe, die sich mit der Bewertung von PCG selbst befassen — etwa die Strömung, die einen PCG-Benchmark etablieren will (The Procedural Content Generation Benchmark) —, zeichnet sich eine Landkarte davon ab, „was eine gute Generierung ausmacht". Auf dieser Seite entsprechen die drei Rubriken Magnetismus & Schwerkraft, Zeitmanipulation und Puzzle-Plattformer genau den Verben, die dieser Beitrag zu Koordinaten gemacht hat. Vor der Umsetzung lohnt sich ein Blick darauf, wie bestehende Spiele diese Verben bereits genutzt haben — dann wird klarer, welche Zahlen man bestellen sollte.

Quellen

Für diesen Artikel herangezogene Beiträge und verwandte Materialien:

・High Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, McGill University, 2026, arXiv:2602.18943v1 [cs.AI], 21 Feb 2026)

・Derselbe Beitrag / Proceedings of the 21st International Conference on the Foundations of Digital Games (FDG 2026), DOI 10.1145/3815598.3815606 (begutachtete Fassung)

・Offizielle Website der FDG 2026 (10.–13. August 2026, Royal Danish Academy, Kopenhagen)

・Bilder im Artikel stammen von Steam-Storeseiten: VVVVVV (Terry Cavanagh, 2010) / Contrast (Compulsion Games, 2013). Keines der beiden war ein im Beitrag experimentell verwendetes Spiel; sie dienen nur als Beispiele für die Verben.

・Das Schema ist eine Eigenanfertigung von Fukai (nur alphanumerische Zeichen).