JumpIN Knobelspiel

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.

• Start in Endposition $f$.
• Initialisieren zwei Mengen: Erledigt $E=\{\}$, und zu Bearbeiten (todo) $T=\{f\}$.
• So lange $T$ nicht leer ist:
  • Entferne eine Position $p$ aus $T$.
  • Füge $p$ der Menge $E$ hinzu.
  • Für alle Nachbarpositionen $n$ von $p$:
    • Wenn $n$ weder in $T$ noch in $E$:
      • Füge $n$ zu $T$ hinzu.

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:

• https://fginfo.ksbg.ch/~ivo/videos/ffprog/gumpine/ oder via OneDrive
• Die Codes gibt es als git-Repo, für jeden einzeln Video gibt es einen Tag, dem man auch einzeln auschecken kann. https://github.com/techlabksbg/gumpine

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

• v0: «Einrichtung» von NodeJS, package.json, die fixen Teile eines Spielfelds als Klasse Fix, Ausgabe eines Spielfelds.
  • Wie bringt man emojis in die git-bash? Vieleicht so: https://www.reddit.com/r/git/comments/ih4frz/how_to_get_emojis_in_git_bash_prompt_on_windows/
• v1: Klasse Moving für bewegliche Teile des Spielfelds.
• v2: Codierung und Dekodierung der beweglichen Teile als Zahl.
• v3: Generierung aller möglichen Hasenzüge als Generator-Funktion.
• v4: Generierung aller möglichen Fuchszüge als Generator-Funktion.
• v5: explore: Sämtliche erreichbare Spielpositionen ab einer Startposition generieren.
• v6: Aufräumen (aka refactoring) der Funktion explore.
• v7: Generator aller möglichen Hasen-Endposition.
• v8: Generator aller möglichen Pilzposition als rekursive Funktion (sollte zwar besser iterativ als Generatorfunktion gemacht werden).
• v9: Erste Generierung von puzzles (inkl. Lösungen). Noch ohne Füchse.
• v10: Generator aller möglichen Platzierunge für die Füchse (muss dann später überarbeitet werden, weil gar nicht alle Positionen benötig werden).
• v11: Kleiner bugfix in der 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).
• v12: makePuzzle-Funktion als Generator-Funktion, Serialisierung der Fix- und Moving-Instanzen (wird für die Dekodierung der Lösungen benötigt).
• v13: fuchsPlaetze-Funktion liefert nur noch nötige Platzierungen, nicht mehr alle. Damit muss nicht mehrmals das gleiche Puzzle gelöst werden.
• v14: toMiniObj() etc. für Fix und Moving: Schlankere Codierung, so dass alle Puzzles gespeichert werden können.
• v15: Parallelisierter Puzzle-Generator mit Threads.
• v16: Puzzles in eine JSON-Datei speichern.
• v17: Alle puzzles generiert.
• v18: Triviale Puzzle gefiltert.
• v19: Full width Canvas. (Start der GUI-Programmierung)
• v20: Koordinatensystem (0,0) bis (4,4)
• v21: Maus und Touch Interaktion (langes Video, viel Debugging)