Hamster Tico (urspr. Ticonderoga)

ein Beitrag zum Hamsterwettbewerb 2002 der Fakultät für Informatik
der Otto-von-Guericke-Universität Magdeburg

entwickelt und programmiert von: Andreas Strehl

DOKUMENTATION

zu Version 1.0

Allgemeines:

Der Hamster Tico besteht aus den drei Klassen
- Tico (Hauptklasse)
- Feld (Hilfsklasse)
- Position (Hilfsklasse)

   
umgesetztes Suchprinzip:

Der Hamster durchsucht das Labyrinth im rekursiven Verfahren und untersucht dabei jedes Feld, welches sich über die Karte regulär erreichen läßt. Beim Betreten eines Feldes werden in Blickrichtung anfangend im Uhrzeigersinn die angrenzenden Felder auf Maisvorkommen untersucht. Durch das rekursive Suchprinzip beendet der Hamster die Untersuchung eines Feldes (erst) dann, wenn
a) alle angrenzenden Felder, die sich betreten lassen, untersucht sind oder
b) das Feld durch Mauerbegrenzungen eine Sackgasse bildet.
Für die Navigation wird eine interne Karte angelegt, in der neben den Informationen über die genaue Lage des Feldes, die Richtung in die die Heimkehr erfolgen soll, die Entfernung vom Heimatfeld (Laufweg, nicht Luftlinie, im folgendem relative Entfernung genannt), der Richtung für eine verkürzte Rückkehr (z.B. für einen Maiskorntransport) sowie die Entfernung auf diesem Wege. Ferner werden Informationen darüber gesammelt, ob das Feld schon einmal betreten wurde und ob die Erkundung vollständig abgeschlossen ist. Die Datenstruktur für die interne Karte wird dabei von der Klasse Feld durch Definition eines abstrakten Datentyps bereitgestellt.
Während der Suche wird ferner Protokoll über die aktuelle relative Entfernung zum Heimatfeld geführt. Bewegt sich der Hamster vom Heimatfeld weg, so legt er alle im Maul getragene Maiskörner auf dem Feld ab. Aufgrund des rekursiven Suchprinzips kehrt er im Laufe der Untersuchung auf jeden Fall zu diesem Feld zurück und kümmert sich erst dann um den Transport des Mais zum Heimatfeld. Bevor er dabei ein Feld entgültig verläßt (d.h. auch der rekursive Aufruf für dieses Feld beendet wird), wird das Feld komplett vom Mais geräumt. Sollten dabei mehr als 20 Maiskörner auf dem Feld liegen, schafft der Hamster diese zunächst über den kürzesten über die interne Karte errechneten Weg zurück zum Heimatfeld. Die dann übrigbleibenden Maiskörner werden im Maul zu dem Feld getragen, das den rekursiven Aufruf zur Felderkundung gestartet hat.
Durch dieses Prinzip kehrt der Hamster auf demselben Weg wieder zum Heimatfeld zurück, den er auf dem Hinweg genommen hat, sobald die Untersuchung des Labyrinths auf Mais vollständig abgeschlossen ist.
Obwohl bei den umfangreichen Tests keine Fehler auftraten, wurde dennoch eine Sicherung eingebaut, die den Hamster im Falle eines aufgetretenen Fehlers direkt zurück zum Heimatfeld steuert, ohne daß weitere Aktionen vorgenommen werden.

   
Interne Karte & Navigation: Um eine genaue Identifikation der einzelnen Felder und dadurch auch eine genaue Navigation zu ermöglichen, wird zu Beginn eine interne Karte in der maximal denkbaren Größe des Labyrinths erzeugt. Dabei wird ein Mauer-ähnliches Koordinatennetz schräg über das Labyrinth gelegt, wie auf der folgenden Grafik angedeutet:
 

Das Heimatfeld bekommt jedoch entgegen der hiesigen Darstellung die Koordinaten 60/60 zugeteilt, diese Darstellung soll lediglich dem Verständnis für das Prinzip der Berechnung der Koordinaten dienen.
Um eine eindeutige Möglichkeit zur Ermittlung der Blickrichtung zu haben, wurde bei der Entwicklung jeder Richtung eine Zahl zugewiesen. Beginnend mit der 0 für den Blick nach Norden erfolgt die Zuweisung für die Richtung im Uhrzeigersinn bis zur 5 (Blick nach Nordwest), siehe dazu die großen roten Ziffern.

Die Berechnung der Koordinaten der jeweiligen Felder folgt dem in grünen Ziffern und Zeichen dargestellten Prinzip. Dadurch wird eine genaue und eindeutige Navigation im Labyrinth sichergestellt.

Die Klassen und ihre Funktionsweisen
Tico Die Klasse Tico übernimmt die Steuerung des Hamsters durch das Labyrinth und die Verarbeitung der durch die beiden anderen Klassen bereitgestellten Datenstrukturen. Zu diesem Zweck besitzt sie folgende Methoden:
run()

übernimmt die globale Steuerung des Programms und ruft für die einzelnen Aktionen Methoden aus der Klasse Tico auf. Zunächst wird dabei aus einem Array und dem Datentyp Feld (welcher in der Klasse Feld definiert wird) eine interne Karte erzeugt. Danach findet eine Rundum-Erkundung des Heimatfeldes und der Aufruf der rekursiven Suche statt, beginnend mit dem Feld in Richtung 0 (also nördlich) des Heimatfeldes.
Kehrt der Hamster von seiner Suche mittels Rekursion zurück, wird zur Sicherheit noch einmal die Methode heimkehren() gestartet, um sicherzustellen, dass sich der Hamster bei Beendigung der Suche tatsächlich auf dem Heimatfeld befindet.
Sollte im Laufe des Programmes eine Exception auftreten, wird diese in der Methode run() aufgefangen und der Hamster durch die nachfolgende Methode heimkehren() zum Heimatfeld zurückgesteuert.

kornSuchen(boolean) steuert die Kornsuche. Dabei wird zwecks Felderkundung die unten beschriebene Methode feldErkunden() aufgerufen. Desweiteren werden im Uhrzeigersinn - sofern möglich - die vorausliegenden Felder betreten, sollte dabei das zu betretende Feld weiter von dem Heimatfeld entfernt liegen, werden alle im Maul getragenden Maiskörner abgelegt und auf dem Rückweg mitgenommen.
kornHeimschaffen() prüft zunächst, ob sich der Hamster auf dem Heimatfeld befindet. Sollte dies nicht der Fall sein, wird geprüft, ob sich mehr als 20 Körner auf dem Feld befinden. Sollte dies der Fall sein, werden die Maiskörner bis auf 20 verbleibende durch den Aufruf von aufKuerzestemWegHeimschaffen() auf dem kürzesten errechneten Weg zum Heimatfeld geschafft, ansonsten werden die Maiskörner in das Maul aufgenommen.
kornAblegen() prüft zunächst, ob sich der Hamster auf dem Heimatfeld befindet. Sollte dies der Fall sein, wird das Mais abgelegt und die Methode beendet. Anderenfalls wird geprüft, ob sich mit dem im Maul getragenen und nun abzulegendem Mais mehr als hundert Maiskörner auf dem Feld befinden würden. Um zu verhindern, dass sich der Hamster dann in einer Endlosschleife geraten würde, wird in diesem Fall die Methode
aufKuerzestemWegHeimschaffen() aufgerufen, andernfalls das Korn abgelegt.
aufKuerzestemWegHeimschaffen()

speichert zunächst die Koordinaten des jetzigen Standortes und die Blickrichtung, um den Hamster nach der Rückkehr wieder exakt so zu positionieren.
Danach wird der
Hamster mithilfe der in der internen Karte gespeicherten Werten für eine verkürzte Heimkehr zum Heimatfeld gesteuert, legt das Korn dort ab und
steuert den Hamster anschließend zum Ausgangsfeld zurück

  feldErkunden() dreht den Hamster einmal im Uhrzeigersinn um 360° und setzt dabei in der internen Karte die Werte für die Entfernung vom Heimatfeld, die Richtung, von der das Feld betreten wurde, ferner für die kürzeste Entfernung vom Heimatfeld und die einzuschlagende Richtung, sowie ob das Feld bereits erkundet wurde.
  heimkehren() steuert den Hamster mit den in der internen Karte gespeicherten Informationen zurück zum Heimatfeld
vorwaerts()
verhindert, daß der Hamster gegen eine Wand läuft und dadurch Kollisionen verursacht , ruft die Methode forward() auf und setzt ferner die Werte für das Feld in der internen Karte
drehen(int) dreht den Hamster mithilfe der Methode turn(int) und korrigiert ggf. den Wert der Klassenvariable blickrichtung.
  inRichtungDrehen(int) dreht den Hamster mithilfe der Methode drehen() in die angegebene Richtung - codiert nach dem o.a. Navigationsprinzip
  umgekehrteRichtungErmitteln(int) errechnet für die interne Verarbeitung gemäß dem o.a. Navigationsprinzip die umgekehrte Richtung der Blickrichtung
  inUmgekehrteRichtungDrehen() dreht den Hamster mithilfe der Methoden umgekehrteRichtungErmitteln(int) und inRichtungDrehen(int) um 180°
  xKoordinateVorausliegendesFeld() berechnet nach dem o.a. Navigationsprinzip die X-Koordinate des in Blickrichtung vorausliegenden Feldes
  yKoordinateVorausliegendesFeld() berechnet nach dem o.a. Navigationsprinzip die Y-Koordinate des in Blickrichtung vorausliegenden Feldes
  karteAnlegen() initialisiert und füllt die Felder des Arrays der internen Karte mit Variablen vom Typ Feld und setzt den Wert bereitsBetreten für das Heimatfeld auf true
  warnung(String) wurde zum Entwickeln des Hamsters benötigt und gibt eine Warnung für den Programmierer auf dem Bildschirm aus
  getHamsterAuthor() gibt den Autor des Hamsters als String zurück
  getVersion() gibt den Versionscode als String zurück
  getHamsterDate() gibt das Datum der letzten Änderung als String zurück
   
     
Position Diese Klasse definiert einen Abstrakten Datentyp mit zwei Instanzvariablen X und Y, sowie einer Navigationsmethode vorwaerts(). Die Klasse wird zur Navigation durch die Klasse Tico benutzt.
  vorwaerts(int) nimmt nach dem o.a. Navigationsprinzip mithilfe des übergebenen Wertes die Berechnung der Koordinaten vor und ändert die beiden Klassenvariablen entsprechend..
   
     
Feld

Diese Klasse definiert einen Abstrakten Datentyp mit den Instanzvariablen

posX
int
speichert die X-Koordinate des Feldes
posY
int
speichert die Y-Koordinate des Feldes
bereitsBetreten
boolean
speichert ob das Feld bereits betreten wurde
allesErkundet
boolean
speichert ob das Feld bereits vollständig erkundet wurde
entfernungHeimatfeld
int
speichert die relative Entfernung vom Heimatfeld
wegHeim
int
speichert die Richtung des Weges zum Heimatfeld (aus welcher der Hamster das Feld zuerst betreten hat)
kuerzesterKorntransportRichtung
int
speichert ggf. die Richtung für einen kürzeren Korntransport zum Heimatfeld
kuerzesterKorntransportEntfernung
int
speichert ggf. die Entfernung für einen kürzeren Korntransport zum Heimatfeld
rueckweg
int
speichert bei einem kürzeren Korntransport die Richtung für die Rückkehr zum Ausgangsfeld, wenn die Methode aufKuerzestemWegHeimschaffen() aufgerufen wurde, damit der Hamster wieder zurückfindet

Die Klasse stellt die Grundlagen für die interne Karte bereit. Folgende Methoden stehen zur Verfügung:

  getBereitsBetreten() liefert den Wert der Variable bereitsBetreten zurück
  getAllesErkundet() liefert den Wert der Variable allesErkundet zurück
  getEntferungHeimatfeld() liefert den Wert der Variable entfernungHeimatfeld zurück
  getWegHeim() liefert den Wert der Variable wegHeim zurück
getkuerzesterKorntransportRichtung liefert den Wert der Variable kuerzesterKorntransportRichtung zurück
  getkuerzesterKorntransportEntfernung liefert den Wert der Variable kuerzesterKorntransportEntfernung zurück
  getRueckweg() liefert den Wert der Variable rückweg zurück
  setBereitsBetreten(boolean) setzt die Variable bereitsBetreten auf den übergebenen Wert
  setAllesErkundet(boolean) setzt die Variable allesErkundet auf den übergebenen Wert
  setEntfernungHeimatfeld(int) setzt die Variable entfernungHeimatfeld auf den übergebenen Wert
  setWegHeim(int) setzt die Variable wegHeim auf den übergebenen Wert
  setKuerzesterKorntransportRichtung(int) setzt die Variable kuerzesterKorntransportRichtung auf den übergebenen Wert
  setKuerzesterKorntransportEntfernung(int) setzt die Variable kuerzesterKorntransportEntfernung auf den übergebenen Wert
  setRueckweg(int) setzt die Variable rueckweg auf den übergebenen Wert


--- Ende der Dokumentation ---

Andreas Strehl, 26.04.2002