Computerorientierte Mathematik

Übersicht

Achtung! Eine ausdruckbare Version dieser Seite findet ihr hier.

• Abgabetermin
• Aufgabenstellung
• Beispiel-Applet
• Vorbereitungen
• Aufgabendetails
• Dokumentation
• Download für zu Hause

vorzuführen.

Die Roboter-Aufgabe wird weitergeführt. Dabei bekommt ihr einiges neues fast geschenkt. Dafür sollt ihr diesmal in Eurem Applet Kürzeste-Wege-Bäume berechnen und zeichnen. Die konkrete Aufgabenstellung findet Ihr weiter unten. Es ist wieder wichtig, diese Informationen vollständig und gründlich durchzulesen!

Die Idee des Spiels basiert weiterhin auf dem Brettspiel "Rasende Roboter" von Alex Randolph, das in Deutschland bei Hans im Glück erschienen ist.

Implementiert ein Applet, in dem ein Spielbrett mit Robotern und Hindernissen dargestellt wird und indem auf Mausklick Kürzeste-Wege-Bäume gezeichnet werden, so wie in diesem Beispiel:

    mkdir ~/programs/program7
    

    cp -r ~co1-002/robotmaze2/* ~/programs/program7
    

Ihr erhaltet so nicht nur die aktuelle Version des robotmaze-Packages, sondern auch ein zweites Package, das digraph-Package.

Falls Ihr zuhause arbeiten wollt, so findet Ihr alles in folgenden Dateien:

• Linux: Prog07.tar.gz
  (auspacken mit tar xzvf Prog06.tar.gz)
• Windows: Prog07.zip

Nun kopiert Ihr Eure eigenen Java- und HTML-Files in das neue Verzeichnis:

    cp ~/programs/program6/*.java  ~/programs/program6/*.html ~/programs/program7/
    

./MyMazeMatrix.java:5: MyMazeMatrix should be declared abstract; 
it does not define setShortestPathToDraw(robotmaze.MazeObject,
digraph.ShortestPathElement[][]) in robotmaze.MazeMatrix
public class MyMazeMatrix extends MazeMatrix
       ^
1 error
    

   import digraph.*;
   import java.awt.*;
    

   public SimpleDigraph getDigraph(MazeObject[] ignore) {
     return null;
   }

   public int getNodeOfCell(MazePosition pos) {
     return 0;
   }

   public MazePosition getCellOfNode(int n) {
     return null;
   }

   public void setShortestPathToDraw(MazeObject obj,
                                     ShortestPathElement[][] shortestPath){
   }

   public void drawShortestPathTree(Graphics g,
                                    int xOffset,
                                    int yOffset,
                                    int cellWidth,
                                    int cellHeight) {
   }
    

Jetzt kommt noch ein kleiner freiwilliger Teil, zum einen um Aufgabe 38 vom 9. Übungsblatt zu bearbeiten, zum Teil um aus dem Maze ein richtiges kleines Spiel zu machen. Falls ihr nur das Notwendige (Pflicht-Teil) bearbeiten wollt, dann solltet ihr bei den Aufgabendetails weiterlesen.

Es freut mich, dass ihr diesen Teil nicht übersprungen habt ;-)!!
Folgende Änderung ist notwendig, um die freiwillige Hausaufgabe zu bearbeiten:

• Ersetzt die (von uns vorgegebenen) Methode ClickAtObject durch die neue Version, damit die MissileLaunch's richtig funktionieren:

      /** 
       * Do some actions when the user clicked on a maze object 
       */
      public void clickedAtObject(MazeEvent event)
      {
  	MazeObject obj = mazeMatrix.getObject(event.getPosition());
  	obj.click(event);
  	statusLine.setText(obj.toString());
  	
  	if (lastClickedObject!=null) {
  	    // if this object was selected
  	    if (lastClickedObject.isSelected()) {
  		lastClickedObject.unclick();
  		lastClickedObject = null;
  	    }
  	}
  	 
  	// select object
  	if (obj.isSelected())
  	    lastClickedObject = obj;
      }
  	

Der Weihnachtsmann hat in dem Labyrinth ein paar Geschenke verteilt, die Eure Roboter für Euch einsammeln können. Natürlich wollt ihr nicht zulange warten, bis die Roboter alle Geschenke eingesammelt haben. Deshalb könnt ihr jeden Schritt, den die Roboter (und andere Objekte) in dem Labyrinth machen zählen.

Um die Roboter dazu zu bewegen, Geschenke zu sammeln und die Schrittzahl zu zählen sind noch weitere Modifikationen nötig, die aber rein freiwillig von Euch gemacht werden können:

• Ersetzt in Eurem Applet die Deklaration

   
     MazeMatrix mazeMatrix;
  	

  durch

   
     MazeMatrixCollecting mazeMatrix;
  	

• Fügt in Euer Applet einen Counter ein. Einen Counter könnt ihr wie ein Label behandeln. (Er leitet sich auch von der Klasse Label ab.)

  Wann immer ihr eine neue MyMazeMatrix erzeugt habt, fügt

     counter.reset();
     mazeMatrix.setCounter(counter);
  	

  ein.
• Jetzt muß für jeden Roboter in Eurem Labyrinth ein Geschenk passender Farbe versteck werden. Das soll beim Füllen der Matrix geschen kann etwa wie folgt aussehen.

          // nRobots ist die Anzahl der Roboter in dem Maze und
          // isRobot[c] ist true, wenn der Roboter der Farbe c existiert.
  	try {
  	    Collectable collect;
  	    cellCount =0;
  	    freeCells = mazeMatrix.getFreeCells(nRobots);
  	    
  	    // now set the four presents into the matrix
  	    for (int c=0; c>RobotColor.numberOfColors(); c++) 
  		if (isRobot[c]) {
  		    collect = new Present(mazeMatrix,c);
  		    collect.addMazeListener(new MazeListener() {
  			    public void actionPerformed(MazeEvent e)
  			    {
  				clickedAtCollectable(e);
  			    }
  			});
  		    mazeMatrix.setCollectable(freeCells[cellCount],collect);
  		    cellCount++;
  		}
  	}
  	catch (RobotColorException e) {
  	    statusLine.setText("Exception: "+e.getMessage()); 
  	    return;
  	}
  	catch (MazeMatrixException e) {
  	    statusLine.setText("Exception: "+e.getMessage()); 
  	    return;
  	}
  	

• Ihr braucht noch folgende Methode, die ausgeführt wird, wenn man auf ein Geschenk klickt.

      /** 
       * Do some actions when the user clicked on a collectable object 
       */
      public void clickedAtCollectable(MazeEvent event)
      {
  	Collectable obj = mazeMatrix.getCollectable(event.getPosition());
  	obj.click(event);
  	statusLine.setText(obj.toString());
  	clickedAt(event);
      }
  	

• Leitet Eure MyMazeMatrix nicht von MazeMatrix sondern von MazeMatrixCollecting ab.

Am besten geht ihr in folgenden Schritten vor:

• Schreibt zunächst eine Graphenklasse, die das Interface SimpleDigraph aus dem digraph implementiert:

  import digraph.*;
  
  public class MyDigraph implements SimpleDigraph
  {
     :
     :
  }
  	

  Diese Klasse soll einen Konstruktor enthalten, der die Anzahl der Knoten des Graphen als Parameter erhält, und alle Methoden des SimpleDigraph-Interface implementieren.

  Diese Klasse ist ganz allgemein zu halten und darf keinerlei Informationen verwenden, die sich speziell auf das Roboter-Spiel beziehen. Wer weiß, vielleicht braucht ihr die Klasse noch einmal...

• Neuer Hinweis: Die Methoden hasInArc und hasOutArc sollen besonders effizient geschrieben werden. Dazu ist es hilfreich, sich in zwei entsprechenden Arrays (vom Typ boolean) zu merken, welche Knoten Rein- oder Rauskanten haben.

• Achtung! Veränderung! Ihr müsst eine Klasse (Namensvorschlag: Floy-Warshall) schreiben, die das Interface ShortestPathAlgorithm implementiert.
  DieseKlasse sollte einen Konstruktor haben, der einen SimpleDigraph übergebenbekommt und diesen in einer globalen Variablen speichert. Außerdem soll diese Klasse eine Methode

      public ShortestPathElement[][] computeShortestPathTrees();
  	

  enthalten, die die Distanz- und Tree-Matrix berechnet und als zweidimensionales Arrey vom Typ ShortestPathElement zurückliefert. Sagen wir, diese Matrix heißt bei Euch distMatrix, so soll der Eintrag distMatrix[i][j] gleich null sein, falls es keinen kürzesten Weg von i nach j gibt, oder distMatrix[i][j].distance gibt die Länge eines kürzesten Weges von i nach j an und distMatrix[i][j].parent den Vorgänger von j auf diesem Weg.

  Also nochmal: Statt unendlich in der Distanz-Matrix oder -1 in der Tree-Matrix arbeitet man mit null in der ShortestPathElement-Matrix!!!!! (Symbolische Konstanten wie final int infinity=10000; haben enorme Nachteile und sollten vermieden werden, wenn es sich elegant umgehen läßt. Und da ihr hier mit einer Matrix von Objekten, nämlich ShortestPathElement, arbeitet, kann man es elegant umgehen. )

  In dieser Methode soll der Floyd-Warshall-Algorithmus implementiert werden, da er effizienter ist als der Bellman-Ford-Algorithmus.Hier findet ihr noch einmal eine Beschreibung des Floyd-Warshall-Algorithmuis. Beachtet, dass man den Algorithmus noch beschleunigen kann, indem man die beiden inneren Schleifen nur dann ausführt, wenn der aktuelle Knoten k, der nun erstmals als Unterwegsknoten zugelassen ist, sowohl rein- als auch raus-Kanten enthält.

• Als nächstes müßt Ihr aus Eurer MazeMatrix einen geeigneten Digraphen erzeugen. Dazu implementiert Ihr in Eurer MyMazeMatrix-Klasse die Methode

       public SimpleDigraph getDigraph(MazeObject[] ignore);
  	

  Für jede Zelle Eurer Matrix sollt ihr einen Knoten erzeugen, die von links-oben nach rechts-unten zeilenweise durchnummeriert werden (bei 0 anfangen!). Für die Umrechnung von einer Zelle (gegeben durch die MazePosition) in die Knoten-Nummer und umgekehrt implementiert Ihr die Methoden

      public int getNodeOfCell(MazePosition pos);
      public MazePosition getCellOfNode(int n);
  	

  Jetzt müssen noch Kanten in den Digraphen eingefügt werden. Und zwar braucht man von jeder Zelle aus, auf der kein Objekt steht in jede Richtung, in die ein Roboter ziehen kann, eine Kante zu der Zelle, auf der der Roboter stehen bleiben würde (also lastFreeCell). So kann jeder Knoten maximal vier raus-Kanten haben. Da jede Kante genau einem möglichen Zug entspricht, sind die Gewichte für jede Kante gleich eins.

  Was soll das Array MazeObject[] ignore? Das Array ignore ist eine Menge von Objekten in der MazeMatrix, die bei der Erzeugung des Graphen ignoriert werden sollen. D.h. es soll so getan werden, als ob diese Objekte nicht in der Matrix stehen. Dazu kann man sie am besten am Anfang der Methode aus der Matrix entfernen und am Ende der Methode wieder an die richtige Stelle der Matrix zurück packen.

  Insbesondere ein Roboter, für den die Distanzmatrix berechnet werden soll, sollte bei der Bildung des Graphen ignoriert werden, denn dieser Roboter bewegt sich ja in dem Maze und wird sich nicht selbst als Stopper verwenden können. (Es ist möglich, über seine eigene Startposition im Laufe mehrerer Züge hinwegzuziehen!)

• Mit der Methode

      public void setShortestPathToDraw(MazeObject obj,
                                        ShortestPathElement[][] shortestPath);
  	

  soll Eurer MazeMatrix später mitgeteilt werden, wenn eine neue Kürzeste-Wege-Matrix berechnet wurde, und zu welchem MazeObject diese gehört.

  Hier noch ein Hinweis, der schon per Email umging:
  Die Methode setShortestPathToDraw wird immer dann aufgerufen, wenn entweder ein neues Object angeklickt wurde, für das die Kürzeste-Wege-Matrix berechnet wurde oder sich diese Matrix für das bisherige Object geändert hat. Die Methode erhält als Parameter sowohl das Object (als Startknoten (=Wurzel) des Kürzesten-Wege-Baums) als auch seine KW-Matrix. Beides muü in globalen Variablen der Klasse gespeichert werden, damit später beim Zeichnen darauf zugegriffen werden kann. Das kann dann etwa so aussehen:

            
    public class MyMazeMatrix extends MazeMatrixCollecting
    {
       MazeObject startShortestPathTree=null;
       ShortestPathElement[][] shortestPathMatrix = null;
       :
       :
       /** Sets the Shortest Path predecessor matrix and the object to start
           the shortest path tree.*/
       public void setShortestPathToDraw(MazeObject obj,
                                         ShortestPathElement[][] shortestPath) {
         startShortestPathTree = obj;
         shortestPathMatrix = shortestPath;
       }
       :
       :
     }
  

  Übrigens: Methoden, deren Name mit set beginnt werden meist nur dazu verwendet, die übergebenen Parameter in globalen Variablen zu speichern (eventuell noch mit einer Konsistenz-Prüfung). So können auch private-deklarierte Instanzvariablen von außen geändert werden, wobei in der set-Methode jedoch noch Sicherheitüberprüfungen stattfinden können.

• Schließlich soll der Kürzeste-Wege-Baum gezeichnet werden. Dazu muß die Methode

      public void drawShortestPathTree(Graphics g, 
                                       int xOffset, int yOffset, 
                                       int cellWidth, int cellHeight);
  	

  in Eurer MazeMatrix-Klasse implementiert werden. Diese Methode erhält ein Objekt g der Klasse java.awt.Graphics mit dem auf dem Bildschirm (genauer gesagt in ein Canvas) zeichnen kann. Z.B. kann man mit g.setColor(Color.orange); die Farbe setzen, mitg.fillOval(x,y,xRadius,yRadius); eine Ellipse malen oder mit g.drawLine(xFrom,yFrom,xTo,yTo); eine Linie zeichnen.

  Ihr sollt nun den Kürzesten-Wege-Baum von der aktuellen Position des Objekts zeichnen, dem die aktuelle Distanzmatrix gehört. Zusätzlich soll in jede Zelle, die von diesem Objekt erreichbar ist, die Entfernung in Schritten von dem Objekt geschrieben werden (g.drawString(entfernungAlsString,x, y);).

  Um die richtigen Bildschirm-Koordinaten zu bestimmen, die der Mitte einer Zelle entsprechen, muß man folgende Umrechnung vornehemen:
  xBildschirm = cellColumn*cellWidth + cellWidth/2 + xOffset
yBildschirm = cellRow *cellHeight + cellHeight/2 + yOffset,
  wobei cellWidth und cellHeight die Breite bzw. Höhe einer Zelle und xOffset und yOffset die Breite bzw Höhe der Randes des Maze sind.

  Neue Zusatz-Info!
  Wenn ihr die Methode implementiert habt, kann Eure MazeMatrix den Digraphen zeichen, aber wie überredet ihr sie dazu, das auch zu tun? Da braucht ihr nicht viel machen, außer dem Maze bescheid geben, dass ihr grundsätzlich an der Anzeige des Graphen interessiert seid, siehe unten bei den Checkboxen. Der Rest passiert automatisch event-gesteuert (also per Zuruf) wenn das Maze zu der Überzeugung gelangt ist, es sei eine gute Idee, den Graphen mal wieder neu zu zeichnen. Das läuft also ähnlich wie mit der paint-Methode eines Canvas ab. (Genaugenommen wird Eure Methode drawShortestPathTree -indirekt- von der paint-Methode des Maze-Canvas aufgerufen.)

• So, jetzt noch ein paar unbedeutende Änderungen in Eurem Applet:
  import digraph.*;

• Fügt in Euer Applet eine Checkbox ein, um die Anzeige des Kürzesten-Wege-Baums ein odes aus zu schalten.

  Neue Zusatz-Info!
  Immer wenn die Checkbox ihren Status ändert, müsst ihr das dem Maze mitteilen (auch am Programm-Anfang!). Dazu ruft ihr an geeigneter Stelle

      maze.setPathes(b);
  	

  auf, wobei b ein boolean ist, der angibt, ob das Zeichnen ein (true) oder aus (false) sein soll.

• In der Methode ClickAtObject müßt ihr dafür sorgen, dass beim Klicken auf ein Objekt die Distanzmatrix neu berechnet wird, falls es nötig ist. Dies könnte etwa wie folgt aussehen:

  	// calculate shortest path matrix
  	if (obj.canMove()) {
  	    if (lastShortPathObject!=obj) {
  		lastShortPathObject = obj;
  		MazeObject[] ignore = new MazeObject[1];
  		ignore[0]=obj;
  		lastShortPath = mazeMatrix.getDigraph(ignore).computeShortestPathTrees();
  		mazeMatrix.setShortestPathToDraw(obj,lastShortPath);
  	    }
  	}
  	else {
  	    lastShortPathObject = null;
  	    lastShortPath = null;
  	    mazeMatrix.setShortestPathToDraw(lastShortPathObject,lastShortPath);
  	}
  	

  Allerdings merkt man so nicht, wenn seit der letzten Berechnung etwas explodiert ist. (Klickt mal auf eine Bombe und dann ganz schnell auf einen Roboter in der Umgebung!) Habt Ihr irgendeine Idee, wie man dieses Problem umgehen kann? (Für den sinnvollsten, am leichtesten zu realisierenden Lösungsvorschlag, der die Matrix nicht zu oft neu berechnet, wäre ich bereit, auf dem nächsten CoMa-Abend eine Cola oder ähnliches zu spendieren. Also: Lösungsvorschläge an Andreas
  Aktueller Stand: Ich habe schon einige sehr brauchbare Ideen vernommen, so dass es wohl schwer wird, den Preis noch zu ergattern!)