Sokoban Spiel: Boxen automatisch verschieben

Question

Ich habe bereits eine Funktionalität implementiert, wenn Keeper automatisch mit Breite ersten Suchalgorithmus bewegt. Jetzt möchte ich, dass die Boxen automatisch verschoben werden (wenn der Halter die Box von der Quelle zum Ziel bewegen kann, ohne eine andere Box zu verschieben). Wie mache ich es? Ich habe versucht, BFS zu modifizieren, noch nicht erfolgreich.

UPDATE: Ich brauche das Rätsel nicht zu lösen. Stattdessen möchte ich eine praktische Benutzeroberfläche entwickeln, wenn Benutzer Boxen mit ihrer Maus bewegen können. Dazu brauche ich etwas Algo, mit dem sich die Bewegungssequenz berechnen lässt. Aber es geht nur darum, einzelne Boxen zu bewegen und wenn nur keine anderen Boxen bewegt werden sollten, um dies zu tun.

Answer 1

Verwenden Sie die erste Breitensuche wie zuvor (oder A *, falls Sie dies bevorzugen), suchen Sie jedoch die entsprechende Gruppe von Zuständen.

Wenn Sie einen Pfad für den Keeper suchen, entsprechen die Zustände den Quadraten im Raster. Aber wenn Sie nach einem Weg für den Torwart suchen, einen Block zu bewegen, entsprechen die Zustände Paare der Quadrate im Raster (eins für den Halter, eins für den Block).

Hier ist das kleinste nicht-triviale Beispiel. Angenommen, wir haben eine Sokoban Ebene mit Quadraten markiert, wie folgt:

Das Raster der Halter enthält, und einen Block.Der Staatsraum besteht aus Paaren von Quadraten, die vom Keeper und vom Block besetzt sind. Es gibt 56 solcher Zustände, die im folgenden Diagramm als kleine Kreise gezeichnet sind.

Die Linien zeigen mögliche Übergänge in diesem Zustandsraum. Die dünnen Linien entsprechen den Bewegungen des Bewahrers (und sind bidirektional). Die dicken Linien entsprechen dem Schieben des Blocks (daher nur in eine Richtung gehen). Es ist dieser Staat Raum, den Sie suchen müssen.

Zum Beispiel, wenn der Block 7 und der Halter 8 beginnt, dann kann der Halter um den Block zu 8 Drücken durch den roten Pfad im Zustandsraum folgt:

Man beachte, dass entlang diesen Weg durchläuft der Block die Positionen 7-6-5-6-7-8. Sie hätten diesen Weg nicht finden können, wenn Sie nur Positionen für den Block in Betracht ziehen, da der Block zweimal die Positionen 6 und 7 durchläuft.

Answer 2

Von Wikipedia - Sokoban:

Sokoban mit der Theorie der Rechenkomplexität werden kann untersucht. Das Problem der Lösung von Sokoban-Puzzles hat sich als NP-schwer erwiesen. 3 Dies ist auch interessant für künstliche Intelligenz Forscher, weil die Lösung von Sokoban mit der Entwicklung eines Roboter, der Kisten in einem Lagerhaus bewegt, verglichen werden kann. Weitere Arbeiten haben gezeigt, dass das Lösen von Sokoban-Problemen auch PSPACE-vollständig ist. [4]

Sokoban ist nicht nur wegen seines Verzweigungsfaktors schwierig ( vergleichbar mit Schach), sondern auch seine enorme Suchbaumtiefe; einige Ebenen erfordern mehr als 1000 "schiebt". Erfahrene menschliche Spieler verlassen sich hauptsächlich auf Heuristiken ; Sie sind in der Regel in der Lage, vergebliche oder redundante Spiellinien schnell zu verwerfen und Muster und Unterziele zu erkennen, drastische Verringerung der Menge der Suche.

Einige Sokoban-Rätsel können durch die Verwendung eines Single-Agent-Suchalgorithmus, wie IDA *, verstärkt durch mehrere Techniken automatisch gelöst werden, die Verwendung von domänenspezifischen Wissen zu machen. [5] Dies ist die Methode, die von Rolling Stone verwendet wird, einem Sokoban Solver, der von der University of Alberta GAMES Group entwickelt wurde. Die komplexeren Sokoban-Stufen sind jedoch selbst für die besten automatisierten Löser unerreichbar.

Möchten Sie das wissen?

Übrigens ist NP-hard das Lösen von Sokoban-Puzzles in einer nachweisbar optimalen Weise, was bedeutet, dass ein $1,000,000 prize auf Sie wartet, wenn Sie herausfinden, wie es geht.