Wie speichern wir das Schachbrett?

Oder müssen wir das Schachbrett überhaupt speichern?

An dieser Stelle kann man mindestens sagen: Zwei Wege führen zum Ziel. Auf den ersten Blick ist es nicht offensichtlich, welcher dieser beiden Wege besser ist. Es hängt auch (selten!) von euren User Stories ab.

Möglichkeit 1

Naheliegend wäre zunächst natürlich, eine 2D-Matrix mit den Figurobjekten an den entsprechenden Stellen zur Verwaltung des Spielbretts zu benutzen. Die Position einer Figur würde dann durch die Matrix gespeichert, eine Figur muss ihre Position selbst nicht kennen, sondern könnte das Backend jederzeit dannach fragen.

Möglichkeit 2

Denkt man darüber nach, ist ein Schachbrett nicht mehr als eine Menge Figuren. Eine Menge Figuren muss man jedoch nicht zwangsläufig in einer 2D-Matrix verwalten, in der die meisten Felder dann leer sind! dafür reicht ein einfaches Array oder eine Liste mit allen Figuren. Jede Figur speichert dann ihre Position einfach selbst. Wenn man zum Beispiel für die GUI dann doch noch eine Matrixdarstellung benötigt, lässt sich das Schachbrett als 2D-Array dann jederzeit schnell als "Wegwerfprodukt" aus den Figuren erzeugen, indem man einmal über die Figurenliste iteriert. Dafür wird nur eine einstellige Anzahl Codezeilen benötigt!

Entscheidungshilfe

Für Möglichkeit 1 ist mehr Arbeit mit 2D-Vektoren und Vektormultiplikation erforderlich. Habt ihr das Rechnen mit Vektoren und Matritzen bisher im Matheuntericht flüssig geübt? Berücksichtigt bei dieser Entscheidung auch User Stories aus späteren Sprints. Wollt ihr später einen vollständigen Schachfigurensatz implementieren, muss für jeden Zug einzeln geprüft werden, ob dadurch einer der Könige in Schach geraten könnte. Für diese Überprüfung benötigt man auf einer Matrix außerordentlich viel Aufwand!

Tipp des Autors

Entscheidet euch für Möglichkeit 2. Geht ihr anders vor, werdet ihr viel Zeit verlieren, was eurem Product Owner nicht gefallen wird.

Aufgabe 1

Falls ihr euch trotzdem nicht entscheiden könnt, oder nachvollziehen wollt, warum obiger Tipp gegeben wird: Wie würdet ihr die Überprüfung der Könige auf Schach jeweils für beide Wege durchführen? Skizziert jeweils grob einen Algorithmus.

Aufgabe 2

Betrachtet eure beiden Skizzen. Welcher Algorithmus ist fehleranfälliger in der Programmierung und komplexer?

Hinweis

Falls ihr nicht direkt auf die Lösung kommt, stellt euch vor ihr würdet ein 3D-Schach implementieren. Wie würde die Komplexität und Fehleranfälligkeit eurer beiden Algorithmen dafür aussehen?

Auflösung

Der erste Weg wirkt auf den ersten Blick einfacher. Auf den zweiten Blick KANN er kompliziert werden. 2D-Arrays benötigen für viele Operationen doppelt verschachtelte Schleifen, diese sind fehleranfälliger und verursachen (unter Umständen) hohe Laufzeiten. Muss für jede Figur auf dem Spielbrett jeweils jede andere geprüft werden, ergeben sich vier oder mehr verschachtelte Schleifen (wie zum Beispiel bei der Prüfung, ob der eigene König in Schach geraten könnte). In diesem Fall ist ein 1D-Figurenarray einfacher. Wenn man (z.B. für die spätere Ausgabe) dennoch ein 2D-Array braucht, dauert das Erstellen des 2D-Arrays nur einen einzigen Schleifendurchlauf durch das Figurenarray.

Beispiel: In einer vollständigen Schach-Implementierung muss für jeden eingegebenen Zug geprüft werden, ob der eigene König dadurch möglicherweise ins Schach gerät, da der Zug in diesem Fall unzulässig wäre. Außerdem muss geprüft werden, ob der gegnerische König ins Schachmatt gerät, da dann das Spiel zu Ende wäre. Für diese Überprüfung müssen alle Figuren auf dem Schachbrett auf ihren möglichen Weg zu den Königen hin überprüft werden. Sind die Figuren in einer 2D-Schachbrett-Matrix gespeichert, muss allein für die Figurensuche über eine doppelt verschachtelte Schleife iteriert werden. Für die Überprüfung auf Schach/Schachmatt ergeben sich mehrere ineinander verschachtelte Exemplare solcher doppelt verschachtelten Schleifen.

Für 3D-Schach würde die Lage noch bedeutend unübersichtlicher, ein 3D-Array müsste mit drei mal drei verschachtelten Schleifen überprüft werden.

Aufgabe 3

Euer Klassendiagramm beinhaltet vielleicht bereits eine Klassen/Objektvariable für das Schachbrett oder den Figurenspeicher. Passt euer Klassendiagramm gegebenenfalls an eure jetzige Entscheidung an.