Erstellen eines prozeduralen Puzzle-Generators

Dieser Beitrag beschreibt den Levelgenerator für mein Linjat- Puzzlespiel. Ein Beitrag kann ohne Vorbereitung gelesen werden, aber es ist einfacher zu assimilieren, wenn Sie in mehreren Levels spielen. Ich habe den Quellcode auf github gepostet . Alles, was im Artikel besprochen wird, befindet sich in der src/main.cc

Beispiel für einen Postplan:

• Linjat ist ein Logikspiel, bei dem Sie alle Zahlen und Punkte im Raster mit Linien schließen müssen.
• Die Rätsel werden prozedural mit einer Kombination aus Solver, Generator und Optimierer generiert.
• Solver versucht, die Rätsel so zu lösen, wie es eine Person tun würde, und weist jedem Rätsel eine Bewertung von Interesse zu.
• Der Puzzle-Generator ist so konzipiert, dass ein Teil des Puzzles (Nummer) leicht geändert werden kann und gleichzeitig alle anderen Teile (Punkte) geändert werden, sodass das Puzzle lösbar bleibt.
• Der Puzzle-Optimierer löst wiederholt die Level und generiert neue Variationen aus den derzeit interessantesten.

Die Regeln

Um zu verstehen, wie der Levelgenerator funktioniert, müssen Sie leider die Spielregeln verstehen. Zum Glück sind sie sehr einfach. Das Puzzle besteht aus einem Gitter mit leeren Quadraten, Zahlen und Punkten. Ein Beispiel:


Das Ziel des Spielers ist es, unter drei Bedingungen eine vertikale oder horizontale Linie durch jede der Zahlen zu ziehen:

• Eine Linie durch eine Zahl muss dieselbe Länge wie die Zahl haben.
• Linien können sich nicht schneiden.
• Alle Punkte müssen mit Linien geschlossen werden.

Beispiellösung:


Hurra! Das Spieldesign ist fertig, die Benutzeroberfläche ist implementiert, und jetzt müssen nur noch mehrere hundert gute Rätsel gefunden werden. Und für solche Spiele ist es normalerweise nicht sinnvoll, solche Rätsel manuell zu erstellen. Dies ist ein Computerjob.

Anforderungen

Was macht das Puzzle für dieses Spiel gut? Ich neige dazu zu glauben, dass Puzzlespiele in zwei Kategorien unterteilt werden können. Es gibt Spiele, in denen Sie einen komplexen Zustandsraum von Anfang bis Ende erkunden (z. B. Sokoban oder Rush Hour ) und in denen möglicherweise nicht klar ist, welche Zustände im Spiel vorhanden sind. Und es gibt Spiele, in denen alle Zustände von Anfang an bekannt sind, und wir gestalten den Zustandsraum schrittweise so, dass unnötige (z. B. Sudoku oder Picross ) eliminiert werden. Mein Spiel fällt definitiv in die zweite Kategorie.

Spieler haben sehr unterschiedliche Anforderungen an diese verschiedenen Arten von Rätseln. Im zweiten Fall erwarten sie, dass das Rätsel nur durch Abzug gelöst werden kann und dass sie niemals zurückgehen / raten / versuchen und irren müssen ^{[0] [1]} .

Es reicht nicht aus zu wissen, ob ein Rätsel nur durch Logik gelöst werden kann. Außerdem müssen wir irgendwie verstehen, wie gut die erstellten Rätsel sind. Andernfalls sind die meisten Ebenen nur triviale Schlacken. Im Idealfall kann dieses Prinzip auch verwendet werden, um eine reibungslose Fortschrittskurve zu erstellen, sodass die Level im Verlauf des Spiels allmählich schwieriger werden.

Löser

Der erste Schritt zur Erfüllung dieser Anforderungen besteht darin, einen für diesen Zweck optimierten Spiellöser zu erstellen. Mit dem Backtracking-Solver können Sie schnell und genau feststellen, ob das Puzzle lösbar ist. Darüber hinaus kann es geändert werden, um festzustellen, ob die Lösung eindeutig ist. Aber er kann keine Vorstellung davon geben, wie kompliziert das Rätsel wirklich ist, weil die Leute sie anders lösen. Solver muss menschliches Verhalten imitieren.

Wie löst eine Person dieses Rätsel? Hier sind einige offensichtliche Schritte, die das In-Game-Tutorial lehrt:

• Wenn ein Punkt nur von einer Zahl aus erreicht werden kann, müssen Sie zum Schließen eines Punktes eine Linie von dieser Zahl ziehen. In diesem Beispiel kann der Punkt nur von den drei, nicht aber von den vier erreicht werden:
  
  
  
  
  Und das führt zu dieser Situation:
  
  
  
• Wenn die Linie nicht in eine Richtung passt, muss sie in eine andere Richtung gelegt werden. Im obigen Beispiel können die vier nicht mehr vertikal positioniert werden, sodass wir wissen, dass sie horizontal sind:
  
  
  
• Wenn bekannt ist, dass sich die Linie der Länge X an einer bestimmten Position (vertikal / horizontal) befinden muss und nicht genügend Leerraum vorhanden ist, um eine Linie von X leeren Zellen auf beiden Seiten zu platzieren, müssen Sie mehrere Quadrate in der Mitte abdecken. Wenn die vier in dem oben gezeigten Beispiel drei wären, würden wir nicht wissen, ob sie sich ganz nach rechts oder links erstrecken. Aber wir würden wissen, dass die Linie zwei mittlere Quadrate abdecken sollte:
  
  
  

Ähnliche Überlegungen sind die Grundlage des Spiels. Der Spieler sucht nach Möglichkeiten, eine kleine Linie zu strecken, und untersucht dann das Feld erneut, da er Informationen erhalten kann, um eine weitere logische Schlussfolgerung zu ziehen. Das Erstellen eines Lösers, der diesen Regeln folgt, reicht aus, um festzustellen, ob eine Person das Rätsel lösen kann, ohne zurückzukehren.

Dies sagt jedoch nichts über die Komplexität oder Interessantheit des Levels aus. Neben der Lösbarkeit müssen wir auch die Komplexität quantifizieren.

Eine offensichtliche erste Idee für die Bewertungsfunktion: Je mehr Züge Sie benötigen, um das Rätsel zu lösen, desto schwieriger wird es. Dies ist wahrscheinlich eine gute Metrik in anderen Spielen, aber meine ist höchstwahrscheinlich wichtiger als die Anzahl der erlaubten Züge, die ein Spieler hat. Wenn ein Spieler 10 logische Schlussfolgerungen ziehen kann, wird er höchstwahrscheinlich sehr schnell eine davon finden. Wenn es nur einen richtigen Zug gibt, dauert es länger.

Das heißt, in erster Näherung muss der Entscheidungsbaum tief und eng sein: Es gibt eine lange Abhängigkeit der Bewegungen von Anfang bis Ende, und zu jedem Zeitpunkt gibt es nur wenige Möglichkeiten, die Kette nach oben zu bewegen ^[2] .

Wie bestimmen wir die Breite und Tiefe eines Baumes? Eine einzige Lösung für das Rätsel und die Bewertung des erstellten Baums gibt keine genaue Antwort. Die genaue Reihenfolge, in der Bewegungen ausgeführt werden, wirkt sich auf die Form des Baums aus. Wir müssen alle möglichen Lösungen in Betracht ziehen und damit so etwas wie eine Optimierung für die besten und schlechtesten Fälle durchführen. Ich bin mit der Technik der groben Suche nach Suchgraphen in Puzzlespielen vertraut, aber für dieses Projekt wollte ich einen One-Pass-Solver erstellen und keine erschöpfende Suche. Aufgrund der Optimierungsphase habe ich versucht sicherzustellen, dass die Laufzeit des Solvers nicht in Sekunden, sondern in Millisekunden gemessen wurde.

Ich habe mich dagegen entschieden. Stattdessen macht mein Löser nicht jeweils einen Zug, sondern löst das Rätsel in Schichten: Wenn er einen Zustand annimmt, findet er alle gültigen Züge, die ausgeführt werden können. Wendet dann alle diese Züge gleichzeitig an und beginnt in einem neuen Zustand von vorne. Die Anzahl der Ebenen und die maximale Anzahl der auf einer Ebene gefundenen Bewegungen werden dann als ungefähre Werte für die Tiefe und Breite des gesamten Suchbaums verwendet.

Hier erfahren Sie, wie Sie eines der schwierigen Rätsel mit diesem Modell lösen können. Gepunktete Linien sind Linien, die auf dieser Schicht des Lösers gestreckt sind. Durchgezogene Linien sind solche, die sich nicht geändert haben. Die grünen Linien haben die richtige Länge, die roten sind noch nicht vollständig.


Das nächste Problem ist, dass alle vom Spieler ausgeführten Züge gleich sind. Was wir am Anfang dieses Abschnitts aufgelistet haben, ist nur gesunder Menschenverstand. Hier ist ein Beispiel für eine komplexere Abzugsregel, deren Suche etwas mehr Nachdenken erfordert. Betrachten Sie das folgende Feld:


Die Punkte in C und D können nur von den fünf und den mittleren vier abgedeckt werden (und keine einzige Zahl kann beide Punkte gleichzeitig abdecken). Dies bedeutet, dass die vier in der Mitte einen der beiden Punkte abdecken sollten und daher nicht zur Abdeckung von A verwendet werden können. Daher sollte der Punkt A die vier in der unteren linken Ecke schließen.

Offensichtlich wäre es dumm, diese Argumentationskette als gleichbedeutend mit der einfachen Schlussfolgerung zu betrachten, dass "dieser Punkt nur von dieser Zahl aus erreicht werden kann". Ist es möglich, diesen komplexeren Regeln in der Bewertungsfunktion mehr Gewicht zu verleihen? Leider ist dies in einem schichtbasierten Löser nicht möglich, da nicht garantiert wird, dass eine Lösung zu den niedrigsten Kosten gefunden wird. Dies ist nicht nur ein theoretisches Problem - in der Praxis kommt es häufig vor, dass ein Teil des Feldes entweder durch ein einzelnes komplexes Argument oder durch eine Kette viel einfacherer Schritte gelöst werden kann. Tatsächlich findet ein schichtbasierter Löser den kürzesten und nicht den kostengünstigsten Weg, und dies kann nicht in der Bewertungsfunktion widergespiegelt werden.

Als Ergebnis kam ich zu dieser Entscheidung: Ich habe den Löser so geändert, dass jede Ebene nur aus einer Art von Argumentation bestand. Der Algorithmus umgeht die Argumentationsregeln in einer ungefähren Reihenfolge der Komplexität. Wenn die Regel einige Züge findet, werden sie angewendet, und die Iteration endet, und die nächste Iteration beginnt die Liste von Anfang an.

Anschließend wird der Entscheidung eine Bewertung zugewiesen: Jeder Schicht werden Kosten zugewiesen, die auf einer darin verwendeten Regel basieren. Dies garantiert immer noch nicht, dass die Lösung am kostengünstigsten ist. Wenn die Gewichte jedoch richtig ausgewählt werden, findet der Algorithmus zumindest keine kostspielige Lösung, wenn es eine billige gibt.

Darüber hinaus ist es sehr ähnlich, wie Menschen Rätsel lösen. Sie versuchen zunächst, einfache Lösungen zu finden, und beginnen nur dann, ihr Gehirn aktiv zu bewegen, wenn es keine einfachen Bewegungen gibt.

Generator

Im vorherigen Abschnitt wurde festgestellt, ob ein bestimmtes Niveau gut oder schlecht war. Aber nur das ist nicht genug, wir müssen immer noch irgendwie Level generieren, damit der Solver sie auswerten kann. Es ist sehr unwahrscheinlich, dass eine zufällig erzeugte Welt lösbar ist, ganz zu schweigen von interessant.

Die Hauptidee (keineswegs neu) ist die alternative Verwendung von Solver und Generator. Beginnen wir mit einem Rätsel, das wahrscheinlich unlösbar ist: Platzieren Sie einfach zwei bis fünf Zahlen in zufälligen Quadraten der Zelle:


Solver funktioniert, bis es sich weiterentwickeln kann:


Anschließend fügt der Generator dem Puzzle weitere Informationen in Form eines Punkts hinzu. Anschließend wird die Ausführung des Lösers fortgesetzt.


In diesem Fall reicht der dem Löser hinzugefügte Punkt für die weitere Entwicklung nicht aus. Dann fügt der Generator weiterhin neue Punkte hinzu, bis er den Löser erfüllt:


Und dann setzt der Löser seine übliche Arbeit fort:


Dieser Vorgang wird entweder fortgesetzt, bis das Rätsel gelöst ist oder bis weitere Informationen hinzugefügt werden müssen (z. B. wenn jede Zelle, die über die Nummer erreichbar ist, bereits einen Punkt enthält).

Diese Methode funktioniert nur, wenn die hinzugefügten neuen Informationen keine der zuvor gemachten Schlussfolgerungen falsch machen können. Dies wäre beim Hinzufügen von Zahlen zum Raster schwierig ^[3] . Das Hinzufügen neuer Punkte zum Feld hat jedoch diese Eigenschaft. Zumindest für die Argumentationsregeln, die ich in diesem Programm verwende.

Wo soll der Algorithmus Punkte hinzufügen? Am Ende habe ich beschlossen, sie dem leeren Raum hinzuzufügen, der im Ausgangszustand mit so vielen Zeilen wie möglich geschlossen werden kann, damit jeder Punkt so wenig Informationen wie möglich preisgibt. Ich habe nicht versucht, den Punkt an der Stelle zu platzieren, an der er nützlich wäre, um das Rätsel zu lösen, wenn der Löser stecken bleibt. Dies erzeugt einen sehr praktischen Effekt: Die meisten Punkte am Anfang des Puzzles scheinen völlig nutzlos zu sein, was das Puzzle schwieriger macht als es wirklich ist. Wenn all dies eine Menge offensichtlicher Bewegungen ist, die ein Spieler machen kann, aber aus irgendeinem Grund funktioniert keiner von ihnen nicht richtig. Als Ergebnis stellte sich heraus, dass sich der Puzzle-Generator ein bisschen wie ein Schwein verhält.

Dieser Prozess erstellt nicht immer eine Lösung, ist jedoch recht schnell (ca. 50 bis 100 Millisekunden). Um ein Level zu generieren, können Sie es einfach mehrmals wiederholen. Leider schafft er normalerweise mittelmäßige Rätsel. Von Anfang an gibt es zu viele offensichtliche Bewegungen, das Feld füllt sich sehr schnell und der Entscheidungsbaum ist eher flach.

Optimierer

Der oben beschriebene Prozess erzeugte mittelmäßige Rätsel. In der letzten Phase verwende ich diese Ebenen als Grundlage für den Optimierungsprozess. Es funktioniert wie folgt.

Der Optimierer erstellt einen Pool mit bis zu 10 Puzzle-Optionen. Der Pool wird mit einem neu generierten zufälligen Puzzle initialisiert. Bei jeder Iteration wählt der Optimierer ein Puzzle aus dem Pool aus und führt seine Mutation durch.

Die Mutation löscht alle Punkte und ändert dann die Zahlen geringfügig (d. H. Verringert / erhöht den Wert einer zufällig ausgewählten Zahl oder verschiebt die Zahl in eine andere Zelle im Gitter). Sie können mehrere Mutationen gleichzeitig auf das Feld anwenden. Anschließend führen wir den Solver im speziellen Level-Generierungsmodus aus, der im vorherigen Abschnitt beschrieben wurde. Er fügt dem Puzzle genügend Punkte hinzu, damit es wieder lösbar wird.

Danach starten wir den Solver erneut, diesmal im normalen Modus. Während dieses Laufs überwacht der Löser a) die Tiefe des Entscheidungsbaums, b) die Häufigkeit des Bedarfs an verschiedenen Arten von Regeln, c) die Breite des Entscheidungsbaums zu verschiedenen Zeitpunkten. Das Puzzle wird anhand der oben beschriebenen Kriterien bewertet. Die Bewertungsfunktion bevorzugt tiefe und enge Lösungen, und die zunehmende Komplexität erhöht auch das Gewicht von Rätseln, bei denen komplexere Argumentationsregeln erforderlich sind.

Dann wird dem Pool ein neues Puzzle hinzugefügt. Wenn der Pool mehr als 10 Rätsel enthält, wird das Schlimmste verworfen.

Dieser Vorgang wird mehrmals wiederholt (ungefähr 10.000 bis 50000 Iterationen haben mich gekostet). Danach wird die am höchsten bewertete Version des Puzzles in der Puzzle-Level-Datenbank gespeichert. So sieht der Fortschritt des besten Puzzles in einem Optimierungslauf aus:


Ich habe versucht, die Optimierung auf andere Weise zu strukturieren. In einer Version wurde simuliertes Tempern verwendet, andere waren genetische Algorithmen mit verschiedenen Überkreuzungsoperationen. Keine der Lösungen war so gut wie ein naiver Algorithmus mit einem Pool von Optionen, die wieder nach oben gehen.

Einzigartige Einzellösung

Wenn ein Puzzle eine einzigartige, einzigartige Lösung hat, entsteht eine interessante Schwierigkeit. Ist es möglich, dem Spieler zu erlauben, anzunehmen, dass es eine Lösung gibt, und daraus Schlussfolgerungen zu ziehen? Wäre es fair, wenn der Puzzle-Generator dem Spieler dies vorschlagen würde?

In einem Beitrag auf HackerNews sagte ich, dass es vier Möglichkeiten gibt, sich dieser Situation zu nähern:

• Erklären Sie die Eindeutigkeit der Lösung von Anfang an und zwingen Sie den Generator, Ebenen zu erstellen, die diese Art von Argumentation erfordern. Dies ist eine schlechte Entscheidung, da dies das Verständnis der Regeln erschwert. Und normalerweise sind dies die Details, die die Leute vergessen.
• Garantieren Sie nicht die Einzigartigkeit einer Entscheidung: Treffen Sie möglicherweise viele Entscheidungen und treffen Sie alle. Tatsächlich löst dies das Problem nicht, sondern schiebt es weg.
• Nehmen Sie einfach an, dass dies ein sehr seltenes Ereignis ist, das in der Praxis nicht wichtig ist. (Dies ist die Lösung, die bei der ersten Implementierung verwendet wurde.)
• Ändern Sie den Puzzle-Generator so, dass keine Puzzles generiert werden, bei denen die Kenntnis der Einzigartigkeit der Lösung hilfreich wäre. (Wahrscheinlich die richtige Lösung, erfordert aber zusätzliche Arbeit.)

Anfangs habe ich mich für die letztere Option entschieden, und das war ein schrecklicher Fehler. Es stellte sich heraus, dass ich nur einen Weg berücksichtigt habe, auf dem die Einzigartigkeit der Lösung zu Informationslecks führte, und dies ist tatsächlich ziemlich selten. Aber es gibt noch andere; Einer von ihnen war tatsächlich auf jeder von mir generierten Ebene präsent und führte oft dazu, dass die Lösung trivial wurde. Daher habe ich im Mai 2019 den Hard- und den Expertenmodus mit der dritten Option geändert.

Der nervigste Fall ist eine Zwei mit einer gestrichelten Linie in diesem Feld:


Warum kann ein schlauer Spieler eine solche Schlussfolgerung ziehen? Eine Zwei kann jedes der vier benachbarten Felder bedecken. Keiner von ihnen hat Punkte, daher müssen sie nicht durch eine Linie abgedeckt werden. Und das Quadrat darunter hat keine Überlagerungen mit anderen Zahlen. Wenn es eine einzige Lösung gibt, sollte dies der Fall sein, wenn andere Zahlen die verbleibenden drei Quadrate abdecken und die beiden das Quadrat darunter schließen.

Die Lösung besteht darin, beim Erkennen solcher Fälle einige weitere Punkte hinzuzufügen:


Ein weiterer häufiger Fall ist ein Strich mit einer gepunkteten Linie in diesem Feld:


Die Quadrate links und oben sind nicht unterschiedlich. Keiner von ihnen hat einen Punkt und keiner kann von einer anderen Nummer aus erreicht werden. Jede Lösung, bei der eine Zwei das obere Quadrat bedeckt, hat eine entsprechende Lösung, bei der das linke Quadrat geschlossen wird und umgekehrt. Wenn es eine einzige einzigartige Lösung gäbe, könnte dies nicht sein, und die Zwei hätte das untere Quadrat bedecken sollen.

Ich habe mich für diese Art von Fall entschieden: "Wenn es weh tut, berühren Sie es nicht." Solver hat diese Regel frühzeitig in der Prioritätenliste angewendet und solchen Bewegungen ein solches negatives Gewicht zugewiesen. Rätsel mit dieser Funktion werden normalerweise vom Optimierer verworfen, und die wenigen verbleibenden Rätsel werden in der Phase der endgültigen Auswahl der Ebenen für das veröffentlichte Spiel verworfen.

Dies ist keine vollständige Liste. Während des Spieltests mit einer absichtlichen Suche nach Fehlern habe ich viele andere Regeln für eindeutige Lösungen gefunden. Aber die meisten von ihnen schienen selten zu sein und sie waren genug zu finden, so dass sie das Spiel nicht wesentlich vereinfachten. Wenn jemand das Rätsel mit solchen Überlegungen löst, werde ich es ihnen nicht vorwerfen.

Fazit

Ursprünglich wurde das Spiel als Experiment zur prozeduralen Generierung von Rätseln entwickelt. Das Design und der Generator des Spiels gingen Hand in Hand, so dass es schwierig ist, die Techniken selbst direkt auf andere Spiele anzuwenden.

Die Frage, auf die ich keine Antwort habe: Hat sich die Investition solcher Bemühungen in die Verfahrensgenerierung gerechtfertigt?Das Feedback der Spieler zum Leveldesign war sehr kontrovers. In positiven Kommentaren wurde normalerweise gesagt, dass in Rätseln immer ein kniffliger Trick zu spüren ist. In den meisten negativen Bewertungen haben sie mir geschrieben, dass dem Spiel ein Gradient der Komplexität fehlt.

Ich habe noch ein paar Rätsel in den Kinderschuhen und ich mochte den Generator so sehr, dass ich höchstwahrscheinlich einen ähnlichen prozeduralen Ansatz für sie verwende. Ich werde nur eines ändern: Ich werde von Anfang an aktive Spieltests mit der Suche nach Fehlern durchführen.

Anmerkungen

[0] Oder zumindest schien es mir. Aber als ich die Spieler live beobachtete, machte fast die Hälfte von ihnen nur Vermutungen und durchlief sie dann. Na ja.

[1] Leser meines Artikels sollten auch den Artikel Minesweeper lösen und verbessern Magnus Hoff lesen .

[2] Ich werde klarstellen, dass die Tiefe / Enge eines Baumes eine Metrik ist, die ich für mein Spiel und nicht für alle anderen Rätsel als wichtig erachtet habe. Zum Beispiel gibt es ein gutes Argument dafür, dass das Rush Hour-Puzzle interessant ist, wenn es mehrere Möglichkeiten hat, fast, aber nicht genau dieselbe Länge zu lösen. Aber es ist passiert, weil Rush Hour ein Spiel ist, um die kürzeste Lösung zu finden, und nicht irgendeine Lösung.

[3] Ohne Hinzufügen von Einheiten. In der ersten Version des Puzzles gab es keine Punkte, und der Generator sollte bei Bedarf Einheiten hinzufügen. Aber das schien zu restriktiv.