Sokoban Solver, Tipps [geschlossen]

Begriffe

Feld - der Level, der ganze Spielbereich des aktuellen Spiels.

position - eine Phase, die im Feld eingerichtet wird.

Endposition - eine Position, in der keine Abzweigung möglich ist - entweder das Ziel oder ein Deadlock .

Box - wie Kiste.

Theorie

Nur ein bisschen Logik - es scheint offensichtlich, aber wir werden es im Implementierungsteil verwenden.

Also - über jedes Spiel von Sokoban können wir sagen, dass es eines davon ist:

• lösbar, ungelöst - bei der Lösung von
• lösbar, gelöst - das Ziel
• unlösbar, ungelöst - wenn unsere Implementierung keine Ergebnisse liefert und es keine weiteren Moves / Kombinationen von Moves mehr gibt

Jetzt - ein Sokoban-Spiel besteht aus Wendungen, die sind:

• Züge - Der Charakter kann sich in einem Bereich bewegen, der durch Wände und / oder Kästchen definiert ist. Dieser Bereich ist jedoch kleiner oder gleich (wenn man die Wände nicht zählt und keine Kästchen) für den gesamten Spielbereich macht das Bewegen des Charakters um das Feld keinen Unterschied außer score, was für die tatsächliche Lösung irrelevant ist - lasst es uns jetzt ignorieren
• schiebt - das Drücken der Kästchen ist viel wichtiger und kann möglicherweise zu unserem Ziel führen - das Feld zu lösen - indem wir die Kästchen auf ihre jeweiligen Ziele schieben

Eine Box kann sein:

• In-Ziel - diese Box muss höchstwahrscheinlich nicht verschoben werden, und einige Regeln können verhindern, dass sich eine Box bei einer Zielposition bewegt (sehr ungewöhnlich)
• drückbar - in 1 bis 4 Richtungen
• nicht dehnbar, nicht am Ziel
  • durch 2 Wände blockiert - die aktuelle Position ist unlösbar egal was
  • andere - wir werden später zu dieser Kiste kommen - denn jetzt steht uns eine Kiste im Weg

Prozess

Dies ist der Schritt-für-Schritt-Prozess, den wir zum Lösen verwenden werden (Definitionen darunter):

1. bevölkert possibleTurns _n mit jedem direkt zugänglichen Push (drückbar oder im Ziel) an der aktuellen Position, mit dem Spieler an der aktuellen Position
2. nimm das erste Element in possibleTurns _n , entferne es und führe es aus
3. sehen ob die aktuelle Position:
   1. ist endgültig - Ziel - gelöst, tue nichts
   2. ist final - Deadlock - dieser Turn führte zu einem Deadlock, bevölkere ihn nicht mehr, gehe zurück zu 2. Schritt, n bleibt gleich
   3. ist nicht final - inkrementieren Sie n und füllen Sie possibleTurns _n mit möglichen Drehungen in dieser Position

Definitionen:

possibleTurns _x - ein zweidimensionales Array oder ein Array von Arrays - das x definiert die "Tiefe" der Kurven

n - am Anfang ist Null, wird in der Ausführung des obigen Algorithmus erhöht

Tipps

Schließlich - der obige Prozess wird Sie mit einer Kombination von Wendungen verlassen, die zu einer gelösten Position führen werden. Das letzte, was zu tun ist, ist einen Algorithmus wie A * zu verwenden, um den kürzesten Weg zwischen diesen Drehungen / Stößen zu bestimmen, um die Geschwindigkeit zu maximieren und um die Anzahl der Spielumdrehungen zu minimieren.