Informatik 11

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Exkurs zu Game Development: Lee's Algorithm ======
{{ :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. 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>