Programmierprojekt „Schiffe versenken“

Programmierprojekt „Schiffe versenken“
Prof. Dr. Christian Heinlein, Hochschule Aalen, Wintersemester 2015/2016
1 Einleitung
In diesem Dokument werden Details festgehalten, die in den wöchentlichen Besprechungen vereinbart
wurden und für alle Gruppen verbindlich sind.
Bei Bedarf wird das Dokument erweitert oder aktualisiert.
Die vorliegende Version ist vom 9. November 2015.
2 Spielregeln
Höhe h und Breite b des Spielfelds können vom Benutzer unabhängig voneinander zwischen 5 und 30
gewählt werden. Die Standard-Spielfeldgröße ist 10 × 10.
Schiffe dürfen sich weder an ihren Seiten noch an ihren Ecken berühren.
Schiffen dürfen auf den Rand- und Eckfeldern des Spielfelds plaziert werden.
Ein Schiff muss mindestens Länge 2 besitzen. Nach oben ist die Länge nur durch das Maximum von
Spielfeldhöhe und -breite beschränkt.
Wenn ein Spieler mit seinem Schuss ein Schiff getroffen oder versenkt hat, darf er weiterschießen.
Wenn er ins Wasser geschossen hat, darf anschließend der andere Spieler schießen.
3 Standardflotte
Beim Standardspiel 10 × 10 ist die Standardflotte 1 × 5 + 2 × 4 + 3 × 3 + 4 × 2, d. h. es gibt ein Schiff
der Länge 5, zwei Schiffe der Länge 4, drei Schiffe der Länge 3 und vier Schiffe der Länge 2. Die Gesamtlänge aller Schiffe ist in diesem Fall 30, d. h. die Schiffe belegen 30 % der Spielfeldfläche (Belegungsfaktor 30 %).
Bei anderen Spielfeldgrößen soll das Programm dem Benutzer eine ähnliche Standardflotte vorschlagen, z. B. 1 × s + 2 × (s − 1) + 3 × (s − 2) + . . . + (s − 1) × 2, d. h. ein Schiff der Länge s, zwei Schiffe der Länge s − 1, drei Schiffe der Länge s − 2 usw. und s − 1 Schiffe der Länge 2. Dabei wird s
(durch einfaches Ausprobieren) möglichst groß gewählt, ohne jedoch den Standardbelegungsfaktor
s−1
von 30 % zu überschreiten, d. h.
3
Σ k (s + 1 − k) ≤ 10 h b. Um dem Standardbelegungsfaktor mögk=1
lichst nahe zu kommen, können anschließend eventuell noch gezielt einzelne Schiffe hinzugefügt werden.
Der Benutzer kann die vorgeschlagene Flotte anschließend nach Belieben (im Rahmen der Regeln
von §2) verändern und dabei auch den Standardbelegungsfaktor von 30 % überschreiten.
1
4 Zufällige Plazierung von Schiffen durch einen Computergegner
Der folgende Algorithmus scheint für alle zulässigen Spielfeldgrößen und Flotten mit Belegungsfaktor bis zu 30 % problemlos zu funktionieren. Es wird daher empfohlen, diesen Algorithmus für die zufällige Plazierung von Schiffen durch einen Computergegner zu verwenden.
• Starte mit einem leeren Spielfeld und irgendeiner Flotte.
• Wähle aus den noch nicht plazierten Schiffen eines mit maximaler Länge.
• Bestimme die Menge aller für dieses Schiff möglichen Plazierungen
(jeweils bestehend aus Zeile, Spalte und Richtung).
• Solange diese Menge nicht leer ist:
Wähle zufällig eine der Plazierungen aus und plaziere das Schiff entsprechend im Spielfeld.
Entferne diese Plazierung aus der Menge.
Plaziere die verbleibenden Schiffe rekursiv nach demselben Verfahren.
Wenn dies gelingt, Ende (vorzeitiger Abbruch der Schleife).
Andernfalls entferne das zuvor plazierte Schiff wieder aus dem Spielfeld und setze die Schleife
fort.
• Wenn die Schleife nicht vorzeitig abgebrochen wurde, konnte man (in diesem Rekursionsschritt)
keine mögliche Plazierung finden.
Nur bei Belegungsfaktoren über 30 % darf ein Computergegner das Spiel „verweigern“ bzw. abbrechen.
5 Spielvarianten
Wenn ein Spieler allein gegen seinen Computer spielt, kann er als erstes die Spielfeldgröße und die
Flotte wählen (oder einfach die Standardeinstellungen übernehmen). Anschließend darf er den ersten
Schuss abfeuern.
Wenn zwei Spieler an zwei Computern gegeneinander spielen, spielt ein Computer die Rolle des
Servers und der andere die Rolle des Clients. Der Server wartet am Anfang auf eine Clientverbindung.
Der Client muss den Namen oder die IP-Adresse des Servers kennen, um eine Socketverbindung mit
ihm aufbauen zu können. Gruppe n verwendet hierbei als Portnummer standardmäßig 50000 + n. Damit Programme unterschiedlicher Gruppen gegeneinander spielen können, muss die Portnummer aber
vom Benutzer verändert werden können.
Der Spieler auf der Serverseite darf die Spielfeldgröße und die Flotte wählen (oder wiederum die
Standardeinstellungen übernehmen). Beides wird dann an den Client übermittelt (vgl. §6). Der Spieler
auf der Clientseite darf dann den ersten Schuss abfeuern.
Sowohl Server als auch Client können auf Wunsch ohne Beteiligung eines menschlichen Spielers arbeiten (Computergegner; der Fall „ein Spieler gegen einen anderen Computer“ fehlt auf den Folien
der Vorbesprechung, soll aber ebenfalls unterstützt werden). Der Server bestimmt dann zufällig eine
zulässige Spielfeldgröße und eine Flotte mit Belegungsfaktor von maximal 30 %.
Ein Computergegner plaziert seine Schiffe zufällig (vgl. §4) und feuert seine Schüsse nach einer einigermaßen sinnvollen Strategie ab. Er darf auf keinen Fall auf Felder schießen, die aufgrund der Plazierungsregeln für Schiffe (vgl. §2) und der bisherigen Antworten des Gegners garantiert keine Schiffe
enthalten können.
2
Um einen menschlichen Spieler zu unterstützen, sollen solche Felder in der Darstellung des gegnerischen Spielfelds automatisch als Wasser gekennzeichnet werden.
Ein Computergegner kann wahlweise mit oder ohne graphische Oberfläche ausgeführt werden. Im ersten Fall kann man den Verlauf des Spiels optisch verfolgen. Sinnvollerweise wird dann z. B. vor jedem Schuss eine (vom Benutzer einstellbare) künstliche Verzögerung eingebaut. Im zweiten Fall kann
der Spielverlauf zumindest auf der Konsole protokolliert werden.
6 Kommunikationsprotokoll
Die über das Netzwerk zwischen zwei Programmen ausgetauschten Nachrichten bestehen jeweils aus
einem Befehlswort (z. B. size oder ships) und zugehörigen Parameterwerten. Diese Bestandteile
sind durch jeweils ein Leerzeichen getrennt. Jede Nachricht endet mit einem Zeilentrenner. Die Parameterwerte sind nichtnegative ganze Zahlen, normalerweise im Wertebereich von int (d. h. zwischen
0 und 231 − 1), bei save und load im Wertebereich von long (d. h. zwischen 0 und 263 − 1).
Derartige Nachrichten können leicht durch Stringverkettung oder Verwendung von String.format
konstruiert werden. Der Empfänger kann sie mittels java.io.BufferedReader.readLine bequem lesen und z. B. mittels String.split in ihre Bestandteile zerlegen. Der Empfänger darf davon
ausgehen, dass der Sender nur syntaktisch und semantisch korrekte Nachrichten verschickt.
Folgende Nachrichten sind definiert (kursiv gesetzte Wörter sind Platzhalter für entsprechende Parameterwerte):
• size rows cols (z. B. size 10 20)
Damit teilt der Server dem Client zu Beginn eines Spiels mit, dass das Spielfeld aus rows Zeilen
und cols Spalten besteht.
• ships length ... (z. B. ships 5 4 4 3 3 3 2 2 2 2)
Damit teilt der Server dem Client anschließend mit, dass die Flotte aus Schiffen der Längen length
besteht. Die Längen müssen absteigend sortiert sein.
• shot row col (z. B. shot 3 4)
Damit teilt ein Programm dem anderen mit, dass sein Spieler einen Schuss auf Zeile row und Spalte
col abfeuert. Zeilen und Spalten werden jeweils ab 1 von oben nach unten bzw. von links nach
rechts gezählt.
• answer a (z. B. answer 1)
Damit teilt ein Programm dem anderen seine Antwort auf die vorhergehende shot-Nachricht mit.
answer 0 bedeutet Wasser, answer 1 bedeutet Treffer, answer 2 bedeutet Treffer-versenkt.
• save id (z. B. save 173586903851)
Damit teilt ein Programm dem anderen zu einem beliebigen Zeitpunkt mit, dass es den aktuellen
Spielstand speichern soll, wobei id zur späteren Identifikation dieses Spielstands dient. (Es kann
z. B. eine Zufallszahl oder die aktuelle Systemzeit in Millisekunden seit 01.01.1970 sein. Siehe
auch §7.) Anschließend kann das Spiel beendet oder auch weitergespielt werden.
• load id (z. B. load 173586903851)
Damit teilt der Server dem Client zu Beginn eines Spiels − anstelle von size und ships − mit,
dass er kein neues Spiel beginnen, sondern den Spielstand mit der angegebenen id laden soll.
Durch das Versenden bzw. Empfangen der answer-2-Nachricht für das letzte eigene bzw. gegnerische Schiff, können beide Seiten ohne eine zusätzliche Nachricht erkennen, wann ein Spiel erfolgreich beendet ist und wer gewonnen hat.
3
In diesem Zustand beenden beide Programme die Socketverbindung. Anschließend kann jedes Programm (wenn der Benutzer es möchte) erneut als Server auf eine Clientverbindung warten oder als
Client eine Serververbindung aufbauen, um ein neues Spiel zu beginnen (egal, ob das Programm zuvor Server oder Client war).
Wenn eines der Programme zu einem beliebigen anderen Zeitpunkt die Socketverbindung schließt,
liefert readLine beim anderen Programm null. Auf diese Weise kann ein Programm dem anderen
indirekt mitteilen, dass es das Spiel vorzeitig beenden möchte bzw. bereits beendet hat, z. B. wenn es
als Computergegner nicht in der Lage ist, die Schiffe zu plazieren oder wenn der Benutzer das Spiel
abbrechen möchte.
Die korrekte Nachrichtenabfolge für ein Spiel ist:
• Am Anfang
entweder size und ships
oder load
(jeweils vom Server zum Client).
• Anschließend beliebig oft
entweder shot (in der Richtung, die gemäß Spielregeln gerade erlaubt ist)
und answer (in der Gegenrichtung)
oder save (in beliebiger Richtung).
7 Speichern und Laden
Das Speichern des aktuellen Spielstands soll bei allen Spielen möglich sein, an denen mindestens ein
menschlicher Spieler beteiligt ist.
Wenn ein Spieler gegen seinen eigenen Computer spielt, kann dieser die gesamte Information, die für
eine spätere Fortsetzung des Spiels benötigt wird, in einer Datei speichern, deren Name vom Benutzer
− z. B. mittels JFileChooser − frei gewählt werden kann.
Wenn zwei Computer beteiligt sind, muss jedes Programm den ihm zur Verfügung stehenden Teil der
Information unabhängig vom anderen Programm in einer lokalen Datei speichern. Wenn der Spielstand später wieder geladen werden soll, müssen beide Programme die jeweils richtige lokale Datei
verwenden. Um diese möglichst eindeutig identifizieren zu können, besitzen die Nachrichten save
und load als Parameter jeweils eine möglichst eindeutige (und deshalb möglichst lange) Nummer id.
Damit gespeicherte Spielstände andererseits auch von Benutzern möglichst leicht wiedergefunden
werden können, soll zumindest ein Benutzer die Möglichkeit haben, den Dateinamen frei zu wählen.
Dies kann z. B. wie folgt realisiert werden:
• Der Benutzer, der den aktuellen Spielstand speichern will, kann seinen lokalen Dateinamen in einem JFileChooser-Dialog frei wählen.
• Sein Programm schickt eine save-Nachricht mit einer möglichst eindeutigen Nummer id an das
andere Programm.
• Das andere Programm verwendet diese Nummer als Dateiname.
• Um das Spiel wieder zu laden, muss der Spieler, der das Speichern initiiert hat, das Programm als
Server starten. Dann kann er, wieder in einem JFileChooser-Dialog, seine lokale Datei auswählen, die neben dem Spielstand auch die Nummer id enthält.
• Sein Programm schickt eine load-Nachricht mit dieser Nummer an das andere Programm.
4
• Das andere Programm verwendet diese Nummer wieder als Dateiname.
• Sollte die zugehörige Datei nicht mehr existieren, beendet das andere Programm die Verbindung.
5