Die Klasse Zelle ist ein JButton der abhängig vom Zustand einer Position eine bestimmte Farbe annimmt. In der main() Methode werden die verschiedenen Menüpunkte implementiert um den JButton zu testen. Rechts ist ein Beispiel zu sehen. Jede Zelle hat einen Zeiger auf eine Position. In der Klasse Zeiger werden alle graphischen Aspekte implementiert. In der Klasse Position wird die Logik zum Darstellen einer Position implementiert. Die Zellen werden in der nächsten Stufe zu einem Feld zusammengefaßt aus dem ein Labyrinth gebaut wird. Die Klasse Position hat hierzu eine x und y Koordinate da sie später in einem Feld zu Lösen des Labyrinths verwendet wird. Implementieren Sie die Klassen im Paket s2.backtrack.

 

Quellcode der Klasse Zelle

package s2.backtrack;
 
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JCheckBoxMenuItem;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;

/**
*
* @author s@scalingbits.com
* @version 1.0
*/
public class Zelle extends JButton{
   /**
  * Die Zelle ist im Editiermodus und erlaubt Änderungen zwischen
  * Wand und Leer.
  * Alle Objekte teilen sich diese Eigenschaft
  */
  public static boolean editierbar = false;
  public static Position start;
  public static Position ziel;
  /**
  * Die x,y Position
  */
  public Position p;

   public static Icon leerIcon;
   public static Icon wandIcon;
   public static Icon kruemelIcon;
   public static Icon startIcon;
   public static Icon zielIcon;
   public static Icon loesungIcon;
   public static int xRaster=20;
   public static int yRaster=20;

   /**
   *
   * @param pp eine Position im Feld
   */
   public Zelle (Position pp) {
      // Hier kodieren
   }

   /**
   * Update des graphischen Objekts falls sich die Position verändert hat
   * Es wird die Farbe und der Tooltip neu gesetzt
   */
   public void update() {
      // Hier kodieren
   }

   /**
   * Erzeugt eine Ikone in der richtigen Größe und Farbe
   * @param farbe Farbe der Ikone
   * @return die erzeugte Ikone
   */
   public static ImageIcon erzeugeIcon(Color farbe) {
      BufferedImage img =
      new BufferedImage(xRaster, yRaster, BufferedImage.TYPE_4BYTE_ABGR);
      Graphics2D g = img.createGraphics();
      g.setColor(farbe);
      g.fillRect(0, 0, xRaster-1, yRaster-1);
      g.dispose();
      return new ImageIcon(img);
   }

   /**
   * Erzeugt ein Fenster mit einem einzelnen Button zum Testen der Funktionen
   * dieser Klasse
   * @param args Eingabeparameter werden nicht gelesen
   */
   public static void main(String[] args) {
   // Implementieren Sie alles was zum testen des JButtons benötigt wird.

   } // Ende Methode main
} // Ende Klasse Zelle

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java

Hilfe! Wie packe ich das an?

Hier ein paar Tips wie man dieses Problem in kleineren Schritten lösen kann...

Wichtig: Immer ein lauffähiges Programm behalten!

1. Erzeugen Sie die Klasse Zelle als Spezialierung von JButton. Sie wird sich erstmal wie ein normaler JButton verhalten...
2. Schreiben Sie ein Hauptprogramm (main() Routine):
   1. Legen Sie ein JFrame an
   2. Erzeugen Sie ein Objekt vom Typ Zelle. Geben Sie dem Button einen Namen
   3. Fügen Sie den Button zum JFrame hinzu
   4. Fügen Sie notwendigen Code zum JFrame hinzu (Größe, Schließen beim Verlassen etc.)
   5. Testen Sie alles. Ein Fenster mit einem JButton erscheint
3. Fügen Sie ein Menü mit einer Leiste hinzu
   1. Aktionen benötigen Sie erstmal keine
   2. Testen Sie alles
4. Die update() Methode
   1. Sie wird verwendet wenn sich der Zustand einer Position ändert. Die Zelle muß dann eine neue Graphik anzeigen
   2. Man liest den Zustand aus und nutzt setIcon() um neue Ikone mit anderer Farbe anzulegen
   3. Ein neuer Tooltip ist dann auch nötig (Methode setToolTipText() )
   4. Die Methode update() kann man natürlich auch im Konstruktor verwenden. Hier muß die Farbe auch gesetzt werden.
5. Konstruktor für Zelle:
   1. Setzen Sie den Namen des JButtons im Konstruktor des JButtons (-> super )
   2. Erzeugen Sie einen Konstruktor ohne Parameter
   3. Passen Sie den Aufruf im Hauptprogramm an.
   4. Testen Sie alles
6. Umbauen von einem JButton mit Text zu einem JButton mit Farbe
   1. Legen Sie die Konstanten für die Größe der Ikone an (x,y und bitte static, sie gilt für alle Buttons)
   2. Legen Sie einen Zeiger auf eine Ikone Ihrer Wahl an (z.Bsp. Start = rot). Sie ist statisch und final, Eine Methode zum Erzeugen von Ikonen ist vorgegeben.
   3. Kopieren Sie sich die Methode zum Erzeugen von Ikonen in die Klasse
   4. Erweitern Sie den Konstruktor
      1. Erzeugen Sie eine rote Ikone wenn nötig (Factory-pattern! Suchen Sie auf dem Webserver nach Factory wenn notwendig )
      2. Löschen Sie den super Aufruf mit Namen
      3. Setzen Sie die Ikone (Das findet man mit Google "java API 11 JButton)
   5. Testen Sie Ihren roten Button
7. Bunte Buttons Infrastruktur:
   1. Wiederholen Sie alles was Sie für rote Ikonen gemacht haben für die anderen Farben ...
      1. Sie benötigen Farben für: Start, Ziel, Leere Kachel, Wand, Krümmel, Lösung)
      2. Macht man am besten in der Methode update()
   2. Testen: Codieren Sie eine andere Farbe für Ihren Button in dem Sie der Position einen anderen Status geben
8. Vorbereiten des Farbenwechseln beim Klicken
   1. Schreiben Sie einen Actionlister für einen Buttonklick
   2. Am besten im Konstruktor implementieren . Jeder Button soll automatisch einen besitzen.
   3. Schreiben Sie beim Buttonclick etwas auf die Konsole
   4. Testen des Buttonclicks!
   5. Nicht vergessen: Löschen Sie die Konsolenausgabe wieder
9. Implementieren Sie Klasse Position
   1. Minimalanforderungen:
      1. x,y Attribut und Farbe (entweder enum oder Konstante für jede Farbe)
      2. Konstruktor
   2. Der Rest der Klasse ist mechanisch. Sie machen das jetzt oder wenn Sie es später benötigen...
10. Ändern des Konstruktors der Klasse Zelle
    1. Akzeptieren Sie eine Position
    2. Merken Sie sich die Position...
    3. Passen Sie das Hauptprogramm an
       1. Erzeugen Sie zuerst eine Position
       2. und dann einen JButton mit Ihr
    4. Testen Sie alles (keine optische Verbesserung)
11. Implementieren Sie einen "Tooltip"
    1. Im Konstruktor von Zelle
    2. Lesen Sie die x,y Koordinate und den Zustand aus
       1. am besten jetzt eine Methode toString() in Position implementieren und verwenden
    3. Testen Sie Ihre Anwendung mit dem Tooltip
12. Farbwechsel des Buttons
    1. Verbessern Sie den ActionListener Ihres JButton (er ist irgendwo im Konstruktor...)
    2. Lesen Sie den Zustand ihrer "Position" aus und wechseln Sie ihn (setIcon() )
    3. Testen Sie Ihren JButton
13. Implementieren Sie die Tests der anderen Farben und den Editierschutz
    1. Verwenden Sie die Klasse JCheckBoxMenuItem im Menü.
    2. Verwenden Sie eine statische Variable für den Editierschutz. Man soll entweder alle Felder editieren können oder keines.
    3. Sie benötigen ActionListener die auf die anderen Farben wechseln...
    4. Sie benötigen einen ActionListener der die Editierbarkeit checkt und die statische Variable wechselt
       1. Blocken Sie die Editierbarkeit im ActionListener der die Farbe von leer auf Wand wechselt...
    5. Testen Sie alles!

In der zweiten Phase werden viele Zellen mit JButtons zu einem Feld zusammengefaßt.

Layout Nutzen Sie einen Layoutmanager mit dem Sie Oben das Feld darstellen können und unten die Statusinformationen. Was bietet sich hier an? Welcher Layoutmanager bietet sich für das Feld an? Unten sollen Sie zwei Komponenten implementieren, einen Text und einen variablen Text. Welcher Layoutmanager bietet sich hier an? Komponenten Welche Komponenten benötigen Sie? Pull-down Menü Implementieren Sie das Pull-down Menü. Das Feld soll editierbar sein oder schreibgeschützt. Welche Komponente bietet sich hier an? Implementieren Sie eine Textausgabe für Weg finden, Oeffnen, Speichern. Diese Funktionen werden in späteren Phasen implementiert. Implementieren Sie Editieren, Loeschen, Beenden.

GUI mit ausgeklapptem Menü

 

Klasse Backtrack

Zur Klasse Backtrack gibt es einige Entwurfsüberlegungen. Die Klasse soll in den nächsten Stufen in der Lage sein das Laden und Speichern von Dateien zu unterstützen. Sie soll es auch erlauben, dass die Suchalgorithmen eingebunden werden.

Dies kann man erreichen in dem man alle Aktionen des Pull-Down Menüs als eigene Methoden implementiert. Jede zukünftige Phase wird aus dieser Klasse spezialisert. Durch überschreiben der Methoden kann man in zukünftigen Phasen die Aktionen ändern, ohne das man die alte Implementierung ändern muss.
Die Methoden für spätere Phasen machen nur ein Update im Textfeld. So kann man sehen, dass sie aufgerufen werden.

Dadurch kann man auf den Code der vorhergehenden Klasse zurückgreifen und muss den Code nicht replizieren.

Hierzu muss man das GUI in einer Instanz von Backtrack implementieren. Das GUI der vorhergehenden Phase wurde als statische Methode in Zelle implementiert. Dies ist hier nicht geschickt.

Um das Editieren zur ermöglichlichen muß der Benutzer einen aus mehreren Zuständen auswählen. Dies kann man mit der Klasse javax.swing.JCheckBoxMenuItem erreichen.

Klasse Labyrinth

Die Klasse Labyrinth dient zum Darstellen und Speichern des Labyrinths. Sie enthält keine Aspekte der Benutzeroberfläche. Das Labyrinth wird von Backtrack benutzt um die entsprechenden graphischen Elemente korrekt anzuzeigen.

Da das GUI immer etwas sinnvolles anzeigen soll, wird ein Labyrinth nach dem Laden immer in das Labyrinth umkopiert welches zur Anzeige benutzt wird. Jeder JButton (Zelle) hat einen Zeiger auf eine Position. Würde man den neuen Zustand nicht in ein Objekt der Klasse Position umkopieren müsste man alle Zeiger der Zellenobjekte auf die neuen Objekte des Labyrinths ändern.

Die Klasse Labyrinth hat deshalb zwei Konstruktoren

• einen Copy-Konstruktor: ein existierendes Feld wird als Vorlage verwendet.
• einen Konstruktor mit den Dimensionen und der Start und Ziel-Position: Ein Ausgangszustand
  • Hier ist es wichtig die Koordinaten der Start- und Ziel Objekte zu nutzen und die dazu passenden Objekte im Feld zu identifizieren.

Die Methode update() kopiert ein existierendes Labyrinth in ein anderes um.

getPos(x,y) ist eine Bequemlichkeitsmethode die in den späteren Phasen beim Suchen helfen wird.

UML

Die Klasse Labyrinth wird alle Information enthalten die gespeichert werden: Labyrinth Position  Die Klasse Labyrinth enthält Zeiger auf den Start und das Ziel des Labyrinths. Diese beiden Objekte müssen Teile des Feldes sein welches angezeigt wird! Die Klassen die zum GUI gehören sind: Backtrack Zelle sie werden nicht gespeichert.

 Speicherstruktur

Im Speicher gibt es Objekte die mit der Hilfe von Swing das GUI repräsentieren. Das ist eine Instanz von Ariadne und das Feld der Buttons vom Typ Zelle. Der Zustand der Zellen holen sich die graphischen Objekt aus der Instanz des Labyrinths und dem Feld der Positionen. Später wird der nicht grafische Zustand vom Backtrackingalgorithmus und von den Methoden zum Speichern und Laden verwendet. Die Idee, hier ist, mir Hilfe einer Kopiermethode und eines Copykonstruktors jeweils eine Kopie anzulegen die dann für den entsprechenden Zweck verwendet wird. Die Objekte die den Status des GUI repräsentieren sind getrennt vom GUI.

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java
• Klasse Labyrinth.java
• Klasse Backtrack.java

Hilfe! Wie packe ich das an?

Hier ein paar Tips wie man dieses Problem in kleineren Schritten lösen kann...

Wichtig: Immer ein lauffähiges Programm behalten!

1. Implementieren Sie die Klasse Labyrinth
   1. Erzeugen Sie im Konstruktor ein zweidimensionales Feld von Position
   2. Der graphische Teil der Anwendung soll auf eigenen Datenstrukturen arbeiten. Deshalb benötigen Sie
      1. Eine Updatemethode: Der Zustand einer Vorlage wird in in ein Labyrinth kopiert
      2. Einen Copy-Konstruktur
      3. Die Klasse Position sollte eine ähnliche Infrastruktur haben
   3. Start und Ziel: Können theoretisch aus Objekten bestehen, die nicht zum aktuellen Labyrinth gehören (Gefahr von Inkonsistenzen!)
      1. Lesen Sie das Start- und Ziel-objekt im Konstruktor nur
         1. Ziegen Sie mit Ihren internen Zeigern auf die äquivalenten Objekte im Labyrinth.
         2. Setzen Sie deren Zustand.
            1. Equals- und Update-Methoden in Position sind hier sehr nützlich
   4. Setzen Sie beim Anlegen des Feldes alle Positionen auf eine leere Position (ausgenommen Start und Ziel)
   5. Testen ist schwierig: Mut zur Lücke...
2. Design Ihres GUIs (Klasse Backtrack)
   1. Bauen Sie Ihr GUI im Konstruktor der Klasse
   2. Legen Sie ein JFrame an
      1. Beenden Sie die Anwendung beim Schliessen des Fenster
   3. Nutzen Sie ein Borderlayout als Hauptstruktur
      1. Im Süden implementieren Sie ein JPanel mit z.Bsp. ein Flowlayout
         1. Ein JLabel links
         2. Ein JTextField rechts
            1. Nur lesbar
            2. Merken Sie sich den Zeiger auf das Textfeld als Attribut in Ihrer Hauptklasse.
               1. ActionListener in inneren Klassen müssen hier den Zustand dokumentieren
      2. Im Zentrum wird ein neues JPanel mit Gridlayout angelegt
         1. Die Dimension muss zum Labyrinth passen
         2. Legen Sie ein Labyrinth an.
         3. Legen Sie zu jedem Feld im Labyrinth eine Zelle an und stecken Sie die Zellen in das JPanel mit Gridlayout
         4. Speichern Sie sich einen Zeiger auf das Anzeigelabyrinth in einem Attribut der äusseren Klasse
3. Implementieren Sie das Hauptprogramm
   1. Legen Sie ein Objekt Ihrer Klasse an
   2. Implementieren und benutzen Sie eine Methode anzeigen()
      1. Die Methode "packt" das JFrame und zeigt es an
      2. Man muss später Spezialisierungen der Klasse mit dem spezifisichen Konstruktor in zukünftigen main() Methoden erzeugen. Dies Methode kann man dann wiederverwenden...
   3. Testen Sie alles!
4. Implementieren Sie das Menü mit allen Einträgen. Diese Klasse wir noch spezialisiert. Esa erspart später Schreibarbeit
   1. Schreiben Sie hierfür eine eigene Methode
   2. Rufen Sie die Methode aus dem Hauptprgramm auf
5. Behandlung der Aktionen (siehe Screenshot)
   1. Viele Behandlungen werden erst später benötigt. Implementieren nur eine Kontrollausgabe auf der Konsole
   2. Vorgehen:
      1. Die Klasse Backtrack wird in späteren Phasen spezialisiert
      2. Schreiben Sie für jede Aktion eine Methode die einen Zeiger auf die graphische Komponente entgegen nimmt.
      3. Diese Methoden werden später überschrieben!
      4. In der Methode wird ein ActionListener angelegt und registriert
   3. Jetzt zu implementierende Behandlungen
      1. Beenden der Anwendung
      2. Schützen der Anwendung vor Editierversuchen
      3. Löschen des Labyrinths
   4. Testen, testen, testen
6. Feiern: Sie haben die nächste Stufe geschafft.

Klasse BacktrackIO

Diese Klasse wird aus Backtrack spezialisiert. Sie nutzt die gesamte Infrastruktur. Sie überschreibt

• speichernLabyrinth() 
• ladenLabryrinth()
• main(String[] args): Sie müssen hier eine Instanz von BacktrackIO anlegen und anzeigen

Da man hier mit Verzeichnissen im Dateiverwaltungssystem arbeiten muss, sollte man die folgenden GUI Klassen verwenden:

• javax.swing.JFileChooser
• javax.swing.filechooser.FileSystemView

Man kann Sie wie folgt einsetzen um den Zugriff auf eine Datei zu bekommen:

File selectedFile;
JFileChooser jfc
  = new JFileChooser(FileSystemView.getFileSystemView().getHomeDirectory());
int returnValue = jfc.showSaveDialog(null);
if (returnValue == JFileChooser.APPROVE_OPTION) {
   selectedFile = jfc.getSelectedFile();
   System.out.println(selectedFile.getAbsolutePath());
   // Ab hier mit der Datei arbeiten...
}

Beispiel JFileChooser

Damit erhalten Sie, abhängig von Ihrer Plattform, einen Auswahldialog im Home-Verzeichniss Ihres Benutzers.

 

UML

Speicherstruktur

Zum Speichern und Laden eines Labyrinths wird eine Kopie der Daten angelegt die zum visualieren angelegt werden.

 

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java
• Klasse Labyrinth.java
• Klasse Backtrack.java
• Klasse BacktrackIO.java

Hilfe! Wie packe ich das an?

1. Erzeugen Sie eine spezialisierte Klasse BacktrackIO
2. Kopieren Sie sich das Hauptprogramm der Oberklasse
   1. Anpassung: Erzeugen Sie ein Objekt der aktuellen Klasse
   2. Testen: Läuft alles wie zuvor?
3. Nutzen Sie die Serialisierung
   1. Die Klassen Labyrinth und Position müssen die entsprechende Schnittstelle implementieren
4. Überschreiben Sie die Methode zum Speichern
   1. Nutzen Sie Klasse JFileChooser zum Selektieren der Datei
   2. Holen Sie sich von der Klasse JFileChooser das Ergebnis (Eine Instanz der Klasse File)
   3. Spicken Sie doch einfach (Im ersten Semester wurde bei den Schnittstellen ein sehr ähnliches Beispiel diskutiert)
   4. Schreiben Sie Labyrinth, Start und Ziel als Datei
      1. Verketten Sie FileOutputStream mit ObjectOutputStream
      2. Schreiben Sie Ihre GUI Datenstruktur des Layrinths in die Datei
   5. Behandeln Sie alle Ausnahmen wie benötigt...
   6. Testen: Wurde die Datei geschrieben?
5. Vorbereiten zum Laden
   1. Schreiben Sie eine Methode die alle JButtons updated. Nach dem Laden müssen neue Zustände angezeigt werden
6. Überschreiben Sie die Methode zum Laden
   1. Nutzen Sie den JFileChooser zur Identifikation der Datei
   2. Laden Sie die Datei. Sie haben nun einen Zeiger auf ein neues Labyrinth
   3. Machen Sie Ihr Labyrinth editierbar
   4. Nutzen Sie die Methode update() und Ihr GUI Labyrinth mit dem eingelesen Labyrinth zu überschreiben
   5. Machen Sie ein Update auf allen Zellen
   6. Testen

 

Klasse BacktrackSuche

Diese Klasse wird aus BacktrackIO spezialiert. Sie nutzt die gesamte Infrastruktur. Sie überschreibt

• loesungFinden() 
• main(String[] args): Sie müssen hier eine Instanz von BacktrackSuche anlegen und anzeigen

Klasse Ariadne

In dieser Klasse wird die Suche implementiert.

Zuschauen beim Suchen...

Implementieren Sie eine Wartebedingung, dann können Sie Ihrem Algorithmus zuschauen.

Definieren Sie eine Variable mit Millisekunden Schlafzeit

public static final int WARTEN=10; //ms Schlafen vor dem nächsten Schritt

Lassen Sie den aktuellen Thread schlafen

public static final int WARTEN=1000; // ms Schlafen vor dem nächsten Schritt
try {
       Thread.sleep(WARTEN);
    } catch (InterruptedException ex) {
         System.out.println("Probleme mit Thread aufwachen");
    }

Das GUI muss jetzt noch wissen, dass sich etwas geändert hat. Deshalb benötigt man einen Zeiger auf das GUI. Das schafft eine Abhängigkeit vom GUI und ist nicht schön (muss aber sein).

Triggern Sie ein Update indem Sie das Labyrinth des GUIs erneuern und dann alle Buttons dazu zwingen den Zustand ihrer Zelle zu checken:

bt.laby.update(laby);
bt.updateButtons();

Die rekursive Suche

Es gibt einen Einstieg in die Suche ohne Parameter mit der Methode  suche(). Die rekursive Suche findet in einer überschriebenen Methode statt, die die Teilstrecke von einem Zwischenstart zu einem Zwischenziel sucht.

Alle Methoden arbeiten auf dem gleichen Labyrinth, dadurch kann man Stellen entdecken auf denen man schon mal war.

Eine separate Methode findeOptionen() checkt alle Nachbarpositionen und gibt eine Liste von Optionen zurück.
Optionen sind freie Felder. Keine Optionen sind die Wände und Felder die schon einmal betreten wurden.

UML

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java
• Klasse Labyrinth.java
• Klasse Backtrack.java
• Klasse BacktrackIO.java
• Klasse BacktrackSuche.java

Hilfe! Wie packe ich das an? Grundlegende Überlegungen Die Suche findet in einer eigenen Klasse statt. Man kann dann diese Klasse für das parallele Suchen verwenden Die Suche muss in einem eigenen Java-Thread laufen. Sie wird sonst das GUI blockieren und wir wollen den Fortschritt sehen. Das heißt, das GUI muss etwas während der Suche arbeiten können Mein Rechner wird zu schnell suchen. Ich muss meinen Tread nach jedem Schritt schlafen legen damit ich den Schritt sehen kann Mein Suchalgorithmus muß das GUI nachen jedem Schritt bitten den neuen Zustand anzuzeigen. Wir benötigen einen Zeiger auf das graphische Objekt um es den neuen Zustand malen zu lassen. Rekursion: Ich bestimme alle von meiner aktuellen Position erreichbaren Nachbarfelder. Ich nehme jedes Nachbarfeld als Startposition einer neuen Suche. Ich benutze immer das gleiche Ziel Habe ich das Ziel gefunden erzeuge ich eine Java-Liste, trage die Zielposition ein und gebe die Liste als Ergebnis zurück Hatte eine Suche meiner Nachbarfelder Erfolg, nehme ich die Ergebnisliste, setzte meine aktuelle Position vorne an und gebe die Liste als Ergebnis zurück

1. Erzeugen Sie eine spezialisierte Klasse BacktrackSuche aus der Klass BacktrackIO
2. Kopieren Sie sich das Hauptprogramm der Oberklasse
   1. Anpassung: Erzeugen Sie ein Objekt der aktuellen Klasse
   2. Testen: Läuft alles wie zuvor?
3. Überschreiben Sie die Methode loesungFinden()
   1. Implementieren Sie einen ActionListener der die Suche started
   2. Setzen Sie das Statusfeld. Das ist ein guter Test ob der Aktionlistener funktioniert.
4. Starten Sie die Suche in einem eigenen Thread, dann kann das GUI parallel arbeiten und Sie können die Suche beobachten
5. Implementieren Sie die Klasse Ariadne
   1. Sie können Sie auch Gretel nennen, Ariadne streut in meinem Beispiel Krümel...
   2. Variablen
      1. int zum Warten in Millisekunden, Ariadne düst sonst wie von der Hummel gestochen durch das Labyrinth und Sie können nicht sehen wie der Weg gefunden wird.
      2. Ein Zeiger auf ein Labyrinth: Die Klasse arbeitet rekursiv auf einem eigenen Labyrinth
      3. Ein Rückzeiger auf Backtrack: Hiermit können Sie das GUI nach jedem gestreuten Krümel um ein Update bitten. Dann können Sie Ariadne beim Krümelstreuen zuschauen. Das ist nicht elegant, weil damit Ariadne von dem GUI abhängt. Das ganze am besten protected, diese Klasse wird nochmals spezialisiert werden
   3. Einen Konstruktor
      1. Parameter: Das GUI (Javaklasse Backtrack) welches den Suchauftrag gibt. Man kann dann nach jedem Krümel ein Update machen und zuschauen
      2. Legen Sie sich ein neues Labyrinth an. Kopieren Sie sich das Labyrinth des GUIs!
   4. Hilfsmethode: findeOptionen() implementieren
      1. Geben Sie ein Set mit allen Optionen zurück.
      2. Testen Sie alle Punkte um den gegebenen Startpunkt. Vorsicht; Ihr Feld ist endlich, es kann Feldüberläufe geben.
      3. Tipp: Benutzen Sie die Methode Position.neuerWeg(), sie wird wahr wenn das entsprechende Feld keine Wand oder kein Krümel ist.
   5. Eine Methode suche()
      1. Diese Methode wird vom GUI aufgerufen
      2. Rückgabe: Eine Liste von Position mit dem Pfad zur Lösung
      3. Diese Methode nutzt den hardcodierten Start und Ziel des Labyrinths zum Aufruf der rekursiven Methode suche()
   6. Testen der Rekursion in Teilschrittem ist schwierig. Möglichkeiten sind:
      1. findeOptionen() mit Testfällen testen
      2. Abbruch der Rekursion testen: Start ist gleich Ziel
   7. Design der Rekursion...
      1. Diese Methode bekommt einen individuellen Start und ein individuelles Ziel. Diese Methode soll Teilaufgaben lösen!
      2. Streue erstmal einen Krümel. Gretel meint das ist immer eine gute Sache...
         1. Das ist die echte Arbeit zum Verkleinern unseres Problems bei der Rekursion
      3. Tue gutes und sprich darüber...
         1. Kopiere das Suchlabyrinth um in das GUI-Labyrinth (es hat jetzt einen neuen Krümel=
         2. Rufe in Backtrack die Methode updateButtons() auf 
         3. So kann man sehen was gerade passiert
      4. Diese Methode ruft eine Methode findeOptionen() auf
         1. Diese Methode liefert eine Liste von Optionen
         2. Optionen sind freie Felder: keine Wand, kein Krümel
            1. Liegt da ein Krümel, so waren wir schon mal da und haben den Weg gefunden (super) oder auch nicht (da müssen wir nicht weitersuchen)
         3. Ergebnis ist eine Menge von Positionen
      5. Die Rekursion:
         1. Arbeite alle Optionen ab
         2. Erstmal Pause...
            1. Lasse den Thread etwas schlafen, damit man das Herumirren im Labyrinth verfolgen kann.
         3. Hänsel möchte wissen ob wir schon da sind?
            1. Wenn der Start das Ziel ist haben wir die Lösung gefunden
               1. wir legen eine neue Liste an
            2. falls nicht rufen wir die Methode suche() rekursiv auf.
               1. Verwende die Option als Start
               2. Verwende das ursprüngliche Ziel
            3. Wir hängen die aktuelle Position als Lösung ein und
               1. und geben sie zurück
               2. Ende der Methode
         4. Merke dir die
            1. erste Liste (Heureka!)
            2. die kürzeste Liste (Hänsel läuft nicht gerne)
         5. Nach dem Abarbeiten aller Optionen:
            1. Nimm Lösungsliste (der Weg)
            2. Hänge vorne die Option and um den Lösungsweg zu verlängern
         6. Gib die Liste mit der gewünschten Lösung zurück
            1. Gibt es keine Lösung ist die Liste leer
            2. Die Länge der Liste ist die Länge des Pfades

 

Klasse BacktrackSucheParallel

Diese Klasse wird aus BacktrackSuche spezialiert. Sie nutzt die gesamte Infrastruktur. Sie überschreibt

• loesungFinden() 
• main(String[] args): Sie müssen hier eine Instanz von BacktrackSucheParallel anlegen und anzeigen

Klasse Ariadne4Parallel

Sie müssen hier einen Konstruktor implementieren, da die Oberklasse einen besitzt.

Das parallele Suche wird in der überschriebenen Methode suchen(von, nach) implementiert.

UML

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java
• Klasse Labyrinth.java
• Klasse Backtrack.java
• Klasse BacktrackIO.java
• Klasse BacktrackSuche.java
• Klasse BacktrackSucheParallel