Mein Sohn spielt zur Zeit sehr gerne folgendes Spiel (irl, nicht online): https://www.smartgames.eu/uk/try-smartgames-online/one-player-games/jumpin
Ziel ist es, einen Generator für solche Puzzles zu programmieren, inklusive Lösungen.
Ein UI zum Spielen ist dann noch ein netter Bonus.
Grundidee: Man speichert Spielzustände (Positionen aller Objekte) und generiert daraus neue.
Am Ende dieses Algorithmus enthält $E$ alle möglichen von der Startposition aus erreichbaren Positionen.
Je nachdem, wie das hinzufügen und entfernen von Elementen in $T$ gehandhabt wird, erhält man gleich auch noch alle kürzeste Spielzüge, um auf die Ausgangsposition zurückzukommen. Wird nämlich $T$ als Warteschlange gehandhabt (immer das älteste Element wird entfernt). Zusätzlich kann zu jeder Position gespeichert werden, von welcher Position diese erreicht wurde.
Im Algorithmus muss sehr oft überprüft werden, ob eine Position schon einmal erreicht wurde oder nicht. Nicht nur ist diese Überprüfung in der innersten Schlaufe, auch ist zu erwarten, dass es schnell sehr viele mögliche Positionen gibt, mit denen zu vergleichen ist. Es lohnt sich also darüber nachzudenken, wie eine solche Überprüfung möglichst effizient passieren kann.
Die fixen Pilze müssen nicht in jeder Position gespeichert werden, es reicht die variablen Dinge (Hasen und Füchse) zu speichern.
Dazu kann entweder das ganze Raster oder nur die Koordinaten der beweglichen Dinge gespeichert werden.
Raster:
. H . P . P . F P . . . F . . f f . H . H . . . .
Hier steht '.' für ein leeres Feld, 'H' für Hase und 'f' und 'F' für die Position der Füchse. Das sind je vier Möglichkeiten, die in 2 Bits codiert werden können, d.h. das ganze Feld kann in 50 Bits codiert werden, was in JavaScript noch als Ganzzahl in einen Float passt (53 Bits, siehe https://www.tutorialspoint.com/what-is-javascript-s-highest-integer-value-that-a-number-can-go-to-without-losing-precision#:~:text=The%20value%20of%20the%20MAX,as%20specified%20in%20IEEE%20754.)
Man könnte auch die Füchse noch zusammenfassen und das Feld als eine Zahl im Dreiersystem auffassen, was dann in $\lceil \log_2\left(3^{25}\right) \rceil = 40$ Bits passt.
Eine andere Variante wäre die Koordinaten der Figuren zu speichern (bis zu 4 Hasen und 2 Füchse). Bei 25 Feldern, nummeriert von 0-24 werden also 5 Bits pro Figur benötigt, d.h. maximal 30 Bits. Um eine eindeutige Codierung zu erreichen, werden die Hasen nach aufsteigenden Feldnummern sortiert abgespeichert (und dann ebenso die Füchse). Für die Füchse würde sogar eine Koordinate reichen (die andere ist schliesslich fix), wobei die Positionen nur von 0-3 gehen, d.h. für die Füchse reichen schon je 2 Bits, was die Anzahl Bits auf total 24 Bits reduziert.
$2^{24} \approx 1.8*10^7$, was eher wenig ist. Damit liesse sich eine Menge von Positionen als Bitstring mit $2^{24}$ Bits schreiben, was im Speicher $2^{21} Bytes (2MB) belegt, was sicherlich kein Problem ist.
Damit lassen sich Positionen in konstanter Zeit markieren und abfragen, besser geht's nicht. Konkret lässt sich das mit einem Uint8Array umsetzen.
Für grössere Felder werden mehr Bits pro Position benötigt und ein Bit-Array ist nicht mehr praktikabel.
Werden alle besuchten Positionsnummern als Zahl oder String in einem Array gespeichert, ist die Überprüfung, ob eine Position schon vorhanden ist sehr ineffizient, weil mit allen Positionen verglichen werden muss. Man könnte das Array sortieren und dann einen binary search darauf machen. Allerdings ist das Sortieren sehr aufwendig. Selbst das Einfügen in ein sortieres Array ist aufwendig, weil etwa die Hälfte aller Element umplatziert werden müssen.
Eine Möglichkeit besteht darin, die Zahlen «halbsortiert» in einem Binary Heap, (Binärer Heap) zu speichern. Damit lassen sich alle Operationen in $\log(n)$ durchführen.
Verfolgen Sie die komplette Entwicklung des Programm mit Erklärungen:
git clone https://github.com/techlabksbg/gumpine.git
Einen gegebenen Tag (z.B. v0) kann man wie folgt aus-checken und daran in einem eigenen Branch (z.B. dev) weiterarbeiten:
git fetch --all --tags git checkout tags/v0 git switch -c dev
Fix, Ausgabe eines Spielfelds.Moving für bewegliche Teile des Spielfelds. explore: Sämtliche erreichbare Spielpositionen ab einer Startposition generieren.explore.explore-Funktion, die zu unnötigen Fuchs-Bewegungen am Ende einer Lösung geführt hat (obwohl die Hasen schon in den Löchern waren).makePuzzle-Funktion als Generator-Funktion, Serialisierung der Fix- und Moving-Instanzen (wird für die Dekodierung der Lösungen benötigt).fuchsPlaetze-Funktion liefert nur noch nötige Platzierungen, nicht mehr alle. Damit muss nicht mehrmals das gleiche Puzzle gelöst werden.toMiniObj() etc. für Fix und Moving: Schlankere Codierung, so dass alle Puzzles gespeichert werden können.