Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:lee:start [2023/10/18 13:52] – Martin Pabst
+++ graphen:breitensuche:lee:start [2023/10/23 09:24] (aktuell) – Martin Pabst
@@ Zeile 1: / Zeile 1: @@
 ====== Exkurs zu Game Development: Lee's Algorithm ======
-{{ :graphen:breitensuche:lee:pasted:20231018-153354.png }}
+{{ :graphen:breitensuche:lee:pasted:20231018-153354.png?500 }}
-Ausgangsproblem: Eine Figur (z.B. die Biene im Bild) soll auf kürzestem Weg zu einem Ziel (im Beispiel: der Edelstein) kommen, dabei aber Hindernissen (hier: die grauen Wände) ausweichen. Die Hindernisse können dabei ein beliebig komplexes Labyrinth bilden, so dass die Problemstellung nicht so trivial ist, wie sie auf den ersten Blick erscheint. Wir können sie aber lösen, indem wir das Spielfeld als Graph interpretieren. Dazu zerlegen wir es in lauter gleich große Quadrate ("Kacheln"), die entweder ganz aus Mauerwerk oder ganz aus betretbarem Boden bestehen:
+Ausgangsproblem: Eine Figur (z.B. die Biene im Bild) soll auf kürzestem Weg zu einem Ziel (im Beispiel: der Edelstein) kommen, dabei aber Hindernissen (hier: die grauen Wände) ausweichen. Die Hindernisse können dabei ein beliebig komplexes Labyrinth bilden, so dass die Problemstellung nicht so trivial ist, wie sie auf den ersten Blick erscheint. Wir können sie aber lösen, indem wir das Spielfeld als Graph interpretieren. Dazu zerlegen wir es in lauter gleich große Quadrate ("Kacheln"), die entweder ganz aus Mauerwerk oder ganz aus betretbarem Boden bestehen. Jede Kachel ist ein Knoten im Graphen:
+{{ :graphen:breitensuche:lee:pasted:20231023-091958.png?500 }}
+Die schwarzen Striche sind die Kanten des Graphen. Ausgehend von dem Knoten, an dem sich der Diamant befindet, traversieren wir den Graphen mittels Breitensuche solange, bis wir bei der Biene angelangt sind. Bei jedem Knoten speichern wir dabei, wie viele Schritte der Breitensuche wir bereits durchgeführt haben.
+{{ :graphen:breitensuche:lee:pasted:20231023-092529.png?500 }}
+Jetzt muss die Biene nur noch in absteigender Reihenfolge den Zahlen folgen um zum Diamanten zu finden.
+<WRAP center round tip 80%>
+Haben Sie gestutzt, als Sie gelesen haben, dass wir die Breitensuche beim Diamanten und nicht bei der Biene beginnen? Welches Problem würde entstehen, wenn wir bei der Biene beginnen?
+</WRAP>
+<HTML>
+<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Lee1'}">
+<script type="text/plain" title="Level.java">
+new World(1600, 640);
+new Level();
+class Level extends Actor {
+   Block[][] felder;
+   Figur biene;
+   Figur diamant;
+   int spaltenAnzahl;
+   int zeilenAnzahl;
+   int t = 0;
+   Level() {
+      levelAufbauen();
+      diamant = new Figur(23, 1, 186);
+      biene = new Figur(5, 3, 264);
+      felderBewerten();
+   }
+   /**
+    * Die Methode felderBewerten() wird vom Programm zu Beginn aufgerufen. Sie soll
+    * via felder[spalte][zeile].setEntfernung(int e) in jedem Feld die Entfernung
+    * zum Diamanten speichern.
+    *    *
+    * istWand(spalte, zeile) gibt genau dann true zurück, wenn das Feld an der Position eine Wand ist.
+    * biene.geheZu(spalte, zeile) verschiebt die Biene an die angegebene Position
+    * biene.spalte, biene.zeile, diamant.spalte und diamant.zeile geben Ihnen die Positionen von Biene/Diamant
+    * felder[spalte][zeile].setEntfernung(int e) können Sie benutzen, um jedem Feld einen Wert zuzuweisen.
+    *
+    */
+   void felderBewerten() {
+      for (int spalte = 0; spalte < spaltenAnzahl; spalte++) {
+         for (int zeile = 0; zeile < zeilenAnzahl; zeile++) {
+            felder[spalte][zeile].setEntfernung(-1);  // -1 bedeutet: noch nicht besucht
+         }
+      }
+      // Breitensuche vom Feld des Diamanten aus
+      LinkedList<Block> warteschlange = new LinkedList<Block>();
+      Block aktuellesFeld = felder[diamant.spalte][diamant.zeile];
+      warteschlange.addLast(felder[diamant.spalte][diamant.zeile]);
+      aktuellesFeld.setEntfernung(0);
+      while (!warteschlange.isEmpty()) {
+         aktuellesFeld = warteschlange.removeFirst();
+         int aktuelleEntfernung = aktuellesFeld.getEntfernung();
+         // linkes Nachbarfeld:
+         if(aktuellesFeld.spalte > 1) {
+            Block linkerNachbar = felder[aktuellesFeld.spalte - 1][aktuellesFeld.zeile];
+            if(!linkerNachbar.istWand() && linkerNachbar.getEntfernung() < 0) {
+               linkerNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(linkerNachbar);
+            }
+         }
+         // rechtes Nachbarfeld:
+         if(aktuellesFeld.spalte < spaltenAnzahl - 1) {
+            Block rechterNachbar = felder[aktuellesFeld.spalte + 1][aktuellesFeld.zeile];
+            if(!rechterNachbar.istWand() && rechterNachbar.getEntfernung() < 0) {
+               rechterNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(rechterNachbar);
+            }
+         }
+         // oberes Nachbarfeld:
+         if(aktuellesFeld.zeile > 1) {
+            Block obererNachbar = felder[aktuellesFeld.spalte][aktuellesFeld.zeile - 1];
+            if(!obererNachbar.istWand() && obererNachbar.getEntfernung() < 0) {
+               obererNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(obererNachbar);
+            }
+         }
+         // unteres Nachbarfeld:
+         if(aktuellesFeld.zeile < zeilenAnzahl - 1) {
+            Block linkerNachbar = felder[aktuellesFeld.spalte][aktuellesFeld.zeile + 1];
+            if(!linkerNachbar.istWand() && linkerNachbar.getEntfernung() < 0) {
+               linkerNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(linkerNachbar);
+            }
+         }
+      }
+   }
+   void schritt() {
+      if(biene.spalte == diamant.spalte && biene.zeile == diamant.zeile) {
+         return; // Die Biene hat den Diamanten bereits erreicht => nichts mehr zu tun
+      }
+      // Bei allen Feldern ist jetzt der Abstand zum Diamanten hinterlegt. Wir suchen jetzt ein
+      // Nachbarfeld der Biene, das einen um eins geringeren Abstand hat als das Feld der Biene.
+      Block bienenfeld = felder[biene.spalte][biene.zeile];
+      int bienenAbstand = bienenfeld.getEntfernung();
+      if(felder[bienenfeld.spalte - 1][bienenfeld.zeile].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte - 1, biene.zeile);
+      } else
+      if(felder[bienenfeld.spalte + 1][bienenfeld.zeile].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte + 1, biene.zeile);
+      } else
+      if(felder[bienenfeld.spalte][bienenfeld.zeile - 1].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte, biene.zeile - 1);
+      } else
+      if(felder[bienenfeld.spalte][bienenfeld.zeile + 1].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte, biene.zeile + 1);
+      }
+   }
+   public void act() {
+      t++;
+      if(t == 30) {
+         t = 0;
+         schritt();
+      }
+   }
+   boolean istWand(int spalte, int zeile) {
+      return felder[spalte][zeile].istWand();
+   }
+   void levelAufbauen() {
+      String level = """
+      wwwwwwwwwwwwwwwwwwwwwwwww
+      w            w          w
+      w     w      w  wwwwwwwww
+      w     w      w          w
+      wwwwwww   wwwwwwwwwwww  w
+      w                  w    w
+      w            w     w    w
+      w            w          w
+      wwwwwwwwwwwwwwwwwwwwwwwww
+      """;
+      String[] lines = level.split("\n");
+      zeilenAnzahl = lines.length;
+      spaltenAnzahl = lines[0].length();
+      felder = new Block[spaltenAnzahl][zeilenAnzahl];
+      for (int zeile = 0; zeile < zeilenAnzahl; zeile++) {
+         String line = lines[zeile];
+         for (int spalte = 0; spalte < spaltenAnzahl; spalte++) {
+            char buchstabe = line.charAt(spalte);
+            felder[spalte][zeile] = new Block(spalte, zeile, buchstabe);
+         }
+      }
+   }
+}
+</script>
+<script type="text/plain" title="Block.java">
+class Block extends Sprite {
+   String art; // "w" bedeutet Wand, "b" bedeutet Boden
+   private int entfernung;
+   private Text entfernungsText;
+   int spalte;
+   int zeile;
+   public Block(int spalte, int zeile, String art) {
+      super(32 + 64 * spalte, 32 + 64 * zeile, SpriteLibrary.Plattforms, 4);
+      this.art = art;
+      this.spalte = spalte;
+      this.zeile = zeile;
+      if(art == "w") {
+         this.setImageIndex(48);
+      }
+      this.entfernungsText = new Text(16 + 64 * spalte, 16 + 64 * zeile, 32, "");
+      this.entfernungsText.setFillColor(Color.black);
+   }
+   public boolean istWand() {
+      return art == "w";
+   }
+   void setEntfernung(int entfernung) {
+      this.entfernung = entfernung;
+      this.entfernungsText.setText(entfernung);
+   }
+   int getEntfernung() {
+      return entfernung;
+   }
+}
+</script>
+<script type="text/plain" title="Figur.java">
+class Figur extends Sprite {
+   int spalte;
+   int zeile;
+   public Figur(int spalte, int zeile, int spriteIndex) {
+      super(32 + 64 * spalte, 32 + 64 * zeile, SpriteLibrary.Plattforms, spriteIndex);
+      this.spalte = spalte;
+      this.zeile = zeile;
+   }
+   public void geheZu(int spalte, int zeile) {
+      moveTo(32 + 64 * spalte, 32 + 64 * zeile);
+      this.spalte = spalte;
+      this.zeile = zeile;
+   }
+}
+</script>
+</div>
+</HTML>