Kar: Laufzeitprüfung generierten Levels auf Begehbarkeit — Fukai liest

TL;DR (Zusammenfassung in einem Absatz)

Was ich heute vorstelle, ist ein Artikel darüber, wie man in Echtzeit — ohne das Spiel zu unterbrechen — prüft, ob von PCG (Procedural Content Generation, algorithmisch statt manuell generierte Level und Terrain) erzeugte Level wirklich bis zum Ende begehbar sind. Der Autor trennt Generierung und Validierung nicht in zwei separate Schritte, sondern lässt sie in derselben Spielschleife koexistieren.

Das System heißt Momentum. In einem Endless Runner laufen zwei autonome Agenten knapp vor dem Spieler her und prüfen im Voraus, ob der kommende Weg blockiert ist oder ob Hindernisse unpassierbar platziert wurden. Wird ein Problem entdeckt, wird es protokolliert; je nach Konfiguration können Hindernisse automatisch entfernt werden.

Die Schlussfolgerung vorweg: Der Artikel illustriert eine Designphilosophie, bei der 'Generierung sofort Validierung bedeutet' statt 'Validierung nach der Generierung', gestützt auf eine strukturelle Schätzung aus dem Code. Es geht nicht um eine Studie mit echten Spielern, sondern um eine formale Herleitung dessen, was das System konstruktiv garantieren kann.

Einleitung

Der Autor ist Rishabh Kar vom Informatik-Department des King’s College London. Der Artikel erscheint als arXiv-Preprint (arXiv:2605.01783v1, eingereicht am 3. Mai 2026, cs.AI) und hat noch kein Peer Review durchlaufen. Er ist also als ‘frisch eingereicht, noch nicht breit diskutiert’ zu lesen.

Warum dieser Artikel heute? Ich lese jeden Morgen die arXiv-Neueinreichungen, aber die meisten PCG-Artikel drehen sich um ‘wie man abwechslungsreichere und interessantere Level generiert’. Dieser weicht einen Schritt ab und stellt eine schlichte, aber praktische Frage direkt: ‘Wie stellt man sicher, dass das generierte Level nicht kaputt ist?’ Für jemanden, der wirklich ein Spiel ausliefern muss, ist das oft die dringlichere Frage.

Was mich ebenfalls anzieht: Das System ist als laufendes Spiel in Unity (weit verbreitete Spielengine) implementiert, mit Werkzeugen wie NavMesh (kommt gleich — die begehbare Fläche für die Wegfindung) und Raycast, die Entwickler in realen Projekten direkt einsetzen können.

Hintergrund

PCG begann in frühen Spielen wie Rogue als Methode, mit begrenztem Speicher große Welten zu erzeugen. Heute generiert es automatisch Terrain, Level, Vegetation und Wetter und trägt Spiele wie Minecraft oder No Man’s Sky, in denen ‘jede Welt anders ist’. Der Autor baut auf dieser Geschichte auf und betont die Schwäche von PCG.

Diese Schwäche: Automatische Generierung garantiert weder, dass ‘es visuell stimmt’, noch dass ‘es wirklich spielbar ist’. Ein Algorithmus kann ein Hindernis so platzieren, dass es den Weg versperrt, oder einen Abschnitt erzeugen, der schlicht unpassierbar ist. Und weil Zufall im Spiel ist, braucht man zum Reproduzieren exakt den damaligen Seed (Ausgangswert des Zufallsgenerators) und die Parameter — das Debugging ist schwierig.

Daher muss Generierung von Validierung begleitet werden — das ist der Ausgangspunkt. Traditionelle Validierungsansätze sind entweder eine statische Prüfung nach Abschluss der Generierung oder ein automatischer Agent, der das Level durchspielt. Aber in einem Endless Runner werden Level kontinuierlich während des Spielens generiert. Es gibt keine Gelegenheit, ‘alles nachträglich zu validieren’. Darin liegt die Motivation für die Echtzeit-Validierung dieses Artikels.

Ansatz / Methode

Die Methode des Autors in einfachen Worten. Momentum ist ein 3D-Endless-Runner, bei dem der Boden aus Kacheln fester Länge (96 Meter im Artikel) besteht, die vorwärts aneinandergereiht werden. Die Hindernisplatzierung nutzt nicht Wave Function Collapse (WFC — Methode, die Kandidaten jedes Feldes unter Berücksichtigung der Nachbarkompatibilität schrittweise festlegt) vollständig, sondern nur dessen Idee vereinfacht: Querreihen in Felder aufteilen, Hindernisse platzieren und dabei Überdichtung verhindern, und mit einem dedizierten Pufferparameter immer befahrbare Spuren freihalten.

Die entscheidende Validierung übernehmen zwei Agenten. Der erste ist ein in der Luft fahrender Luftscanner, der Raycast (Technik, die eine unsichtbare Linie in die Szene schickt und die erste getroffene Fläche meldet), Volumen-Sweep (prüft, ob ein kastenförmiger 3D-Bereich einen Festkörper schneidet) und einen Filter, der nur die Hindernisschicht sieht, kombiniert, um geometrisch zu prüfen, ob der kommende Korridor frei ist. Der zweite ist ein am Boden laufender Lauf-Agent, der aus Sicht des NavMesh (die vom Motor für die Wegfindung vorbereitete begehbare Fläche) prüft, ob derselbe Abschnitt wirklich durchquerbar ist.

Das Entscheidende: Beide Augenpaare prüfen unterschiedliche Eigenschaften. Der Luftagent prüft, ob der Raum physisch frei ist, der Bodenagent, ob der Weg als Pfad tatsächlich begehbar ist. Wird eine Blockierung entdeckt, protokolliert das System Details zum Hindernis, Spielerzustand, Generierungsparameter und das verursachende Objekt in einem Bericht (PDF-Export möglich). Je nach Konfiguration kann der Luftscanner das Hindernis entfernen, bevor der Spieler ankommt.

Der NavMesh wird asynchron kontinuierlich auf 600 Meter vor und 50 Meter hinter dem Spieler neu berechnet (rebaked), um mit der rollenden Welt synchron zu bleiben. Um mögliche kurzfristige Lücken im Boden zu überbrücken, sind bis zu 9 Wiederbelebungen (Respawns) pro Partie erlaubt. All diese Details dokumentiert der Artikel anhand des Codes.

Erkenntnisse

Zunächst muss klargestellt werden, was die ‘Ergebnisse’ dieses Artikels bezeichnen. Der Autor hat keine groß angelegte Spielerstudie durchgeführt — er schätzt das Systemverhalten aus dem Code selbst und aus First Principles (formale Herleitung von Grundannahmen). Die Auswertung folgt der Klassifikation von Cook et al. in vier Achsen: Spielbarkeit (playability), Diversität (diversity), Kontrollierbarkeit (controllability) und Performance.

Zur Kontrollierbarkeit macht der Autor eine bemerkenswerte Beobachtung: Selbst wenn man den Schieberegler für die Hindernisdichte auf Maximum stellt, erreicht die tatsächlich platzierte Anzahl viel früher als erwartet eine Obergrenze. Der Grund: Die Constraints für das Freihalten von Spuren und das Füllen der Nachbarn greifen vorrangig. Der Autor beschreibt dies als strukturelle Obergrenze, nicht parametrisch. Mit anderen Worten: Der Dichte-Schieberegler hat konstruktiv eine unüberwindbare Decke.

Zur Performance schätzt der Autor, dass der Aufwand für einen Agenten, einen Abschnitt zu prüfen, eine kleine Konstante bleibt, die mit der Laufstrecke nicht wächst, weil die Prüfung durch ganzzahlige Kachelnummern geteilt und die teuren Volumen-Sweeps über viele Rayprüfungen geglättet werden. Der Autor setzt das in Bezug zu Unitys Frame-Budget: 16,66 ms bei 60 fps, 33,33 ms bei 30 fps.

Zur Validierungsabdeckung hält der Autor fest, dass Luft- und Bodenagent unterschiedliche Fehlerarten fangen, sodass das Kombinieren beider Berichte systemisch eine höhere Abdeckung liefert als jeder allein. Der Blockierungsgrad wird als Anteil der geprüften Abschnitte, die blockiert waren, quantifiziert. Besonders hervorzuheben: Die erste Forschungsfrage (RQ1) — ‘reduziert Validierung Blockierungen im Vergleich zu keiner Validierung’ — wird als Hypothese formuliert, nicht als gemessenes Ergebnis.

Einsatzmöglichkeiten

Konkret: Wie kann ein Spieleentwickler diesen Artikel nutzen? Erstens: Wenn Sie PCG für einen Endless Runner oder ein Hypercasual-Spiel bauen, können Sie dieses Design direkt übernehmen — geben Sie die Idee ‘erst generieren, dann separat validieren’ auf und fügen Sie unmittelbar nach der Generierung eine Begehbarkeitsprufung ein. Das Einrichten eines Sicherheitsnetzes — Blockierungen entfernen, bevor der Spieler ankommt — ist direkt anwendbar.

Zweitens: Wenn Sie ein Sokoban-like (Schiebepuzzle) oder ein Rogue-lite (automatisch generiertes Dungeon) bauen, können Sie die Idee eines vorauseilenden Agenten, der Erreichbarkeit prüft, übertragen — ersetzen Sie Raycast durch einen Suchloser (einen Mechanismus, der durch echte Suche feststellt, ob eine Lösung existiert). Der Kern dieses Artikels ist weniger die konkrete Methode als das Designmuster ‘Generierung und Validierung in derselben Schleife’, das genreübergreifend übertragbar ist.

Drittens: Das Design des Crash-Reports ist pragmatisch nützlich. Seed, Parameter, verursachendes Objekt und Spielerzustand auf einmal zu protokollieren, wenn eine Blockierung auftritt, ist direkt auf PCG-Bugs anwendbar, die wegen Zufälligkeit schwer zu reproduzieren sind.

Viertens: Der Befund, dass Kontroll-Schieberegler eine strukturelle Decke haben, ist eine Lehre für die Feinabstimmung. Wenn ein Dichteparameter trotz Erhöhung keine Wirkung zeigt, ist das vielleicht kein Bug, sondern das Ergebnis sich gegenseitig neutralisierender Constraints.

Grenzen

Ich unterscheide die vom Autor eingehäumten Grenzen und die, die mir beim Lesen aufgefallen sind. Erstens, das Wichtigste zum Verständnis des Rahmens: Die Zahlen stammen nicht aus einem menschlichen Experiment, sondern aus einer strukturellen Schätzung aus Code und First Principles (das ist keine Paraphrase — der Autor selbst schreibt im Abstract, dass er von First Principles ausgeht). Es gibt daher hier keine Messung der Art ‘Blockierungen sanken im realen Spiel um X %’.

Was Fukai hier betont, ist die enge Anwendungsbreite. Das Zielsystem ist ein Endless Runner mit konstantem Gefälle und fester Spuraufteilung. Um Geländeunebenheiten oder komplexere logische Lösbarkeit wie bei einem Puzzle zu behandeln, würden Raycast und NavMesh allein nicht ausreichen. Der Autor räumt selbst ein, WFC nur als Platzierungsidee zu verwenden, nicht als vollständigen Constraint-Löser.

Ein weiterer Punkt, der mir beim Lesen auffallt: Was der Artikel ‘Auswertung’ nennt, tendiert zur Erreichbarkeit (keine Blockierung) und berührt nicht die Erlebnisqualität — Spass, angemessener Schwierigkeitsgrad etc. Dass ein generiertes Level ‘nicht kaputt’ und ‘gut’ ist, sind zwei verschiedene Fragen; dieser Artikel löst die erste. Dass es sich noch um ein nicht begutachtetes Preprint ohne Zitierungen handelt, ist ebenfalls im Hinterkopf zu behalten.

Fukais Lektüre

Das ist meine Lektüre. Ich möchte diese Forschung in eine Bewegung einordnen, bei der sich das Interesse der PCG von ‘wie man reichhaltigeren Inhalt generiert’ zu ‘wie man dem Generierten vertrauen kann’ verschiebt. In der Sprache der Designkritik lässt sich das als Versuch lesen, einen Teil des Playtestings in dieselbe Zeitlinie wie die Generierung zu falten. Validierung nicht mehr als nachgelagerte Kontrollinstanz, sondern als ständige Komponente der Generierungsschleife — diese Haltung ist wichtiger als die technischen Details. Ob sie tatsächlich funktioniert, muss freilich irgendwann mit echten Menschen überprüft werden.

Schluss

Zum Abschluss eine Karte. Wer die PCG-Auswertung systematischer vertiefen möchte, kann parallel den Artikel von Cook, Withington und Tokarchuk über die Auswertung prozeduraler Level-Generierungssysteme lesen, auf den dieser Artikel aufbaut — sein Überblick über vier Achsen (spielbar, divers, kontrollierbar, performant) ist ein guter Referenzrahmen. Um die Grundlagen von WFC zu verstehen, ist der Artikel von Karth und Smith ‘WFC is Constraint Solving in the Wild’ ein guter Ausgangspunkt.

Die Idee, Generierung und Validierung in dieselbe Schleife zu packen, ist nicht auf Endless Runner beschränkt. Wenn man sie auf das bezieht, was man gerade baut, und sich fragt ‘kann ich im Moment der Generierung behaupten, es wird nicht kaputt sein?’ — dann zeigt sich der Geltungsbereich dieses Artikels. Heute Morgen habe ich mir das beim Trinken einer starken Kanne Filterkaffee wieder gefragt.

Referenzen

In diesem Artikel referenzierte Artikel und Ressourcen:

・Runtime Evaluation of Procedural Content Generation in an Endless Runner Game Using Autonomous Agents (Rishabh Kar, 2026, arXiv preprint arXiv:2605.01783)

・Verwandte Studie (Vier-Achsen-Rahmen für die Auswertung): On the Evaluation of Procedural Level Generation Systems — Cook, Withington & Tokarchuk (zitiert in den Referenzen dieses Artikels)

・Verwandte Studie (Einstiegspunkt zum Verständnis von WFC): WaveFunctionCollapse is Constraint Solving in the Wild — Karth & Smith, 2017 (zitiert in den Referenzen dieses Artikels)