Hamsterwettbewerb 2002
Otto-von-Guericke-Universität Magdeburg


Dokumentation zum Hamster (Bommel)

Der Schöpfer des Hamsters: Mirko Otto (Matrikelnr.:163945)

Die Aufgabe: Es ist ein Hamster zu schreiben, der so durch ein Labyrinth läuft, dass er möglichst viel Getreide mit möglichst wenigen Schritten einsammelt.

Gliederung

- Sammelstrategie -
- Informationsspeicherung -
- Lauf- und Suchstrategie -
- Die Klassen des Hamsters -
- Die Methoden der einzelnen Klassen -

Sammelstrategie

Der Hamster verfolgt eine einfache Strategie, er besucht immer das am nächsten gelegene Feld. Dabei gibt es nur eine Bedingung, entweder auf dem Feld muss Korn liegen oder es muss ein Feld sein, auf welchem der Hamster noch nicht stand. Sobald er genug gesammelt hat, läuft er auf dem kürzesten Weg nach Hause.

Ein Problem in erweiterten Labyrinthen besteht darin, wenn mein Hamster eine Klippe runter springt, sieht er das Heimatfeld nicht mehr.
Ich habe das Problem folgendermaßen gelöst:
Wenn mein Hamster genug Korn gesammelt hat und sein Heimatfeld nicht sehen kann, ändert er seine Strategie ein wenig. Er sucht sich Felder, auf denen er bis jetzt noch nicht gestanden hat. Irgendwann sieht er sein Heimatfeld wieder und dann geht es normal weiter.

Informationsspeicherung

Die Informationen werden in einem 3D-int-Array(Map) gespeichert, wobei die ersten zwei Dimensionen das Labyrinth widerspiegeln und in der dritten Dimension Informationen über die einzelnen Zellen gespeichert werden.
Die ersten zwei Dimensionen des Labyrinthes werden wie folgt in das Array abgebildet:

Labyrinth Array
Bewegungen im Array

Labyrinth

Richtung x / y - Achse
N y - 1
NE x + 1
SE x + 1, y + 1
S y + 1
SW x - 1
NW x - 1, y - 1

Die dritte Dimension baut sich folgendermaßen auf:
0, ...,5: Info, was in Richtung der einzelnen Laufrichtungen liegt(Wand, keine Wand, Klippe hoch, Klippe runter).
6: Hier wird gespeichert, ob das Feld gesehen oder schon betreten wurde.
7: In diesem Feld stehen die Entfernungen, es dient auch zur Neuberechnung der Entfernungen.
8: Anzahl der Körner.

Das Array hat eine Standartgröße von 61 x 61 und das Heimatfeld des Hamsters liegt an der x / y - Position (30, 30).

zum Seitenanfang

Lauf- und Suchstrategie

Seinen Lauf und den Weg, den der Hamster zurücklegt, bestimmt er selbstständig. Er bekommt Bedingungen mit auf den Weg, welche in der Klasse Infopoint verankert sind. Diese Bedingungen lauten folgendermaßen:

1. Gehe zum Feld, welches weniger weit weg ist und auf dem du noch nicht standest.
2. Gehe zum Feld, welches weniger weit weg ist und auf dem du schon einmal standest.
3. Gehe zum Feld, welches gleich weit weg ist und auf dem du noch nicht standest.
4. Gehe zum Feld, welches gleich weit weg ist und auf dem du schon einmal standest.
5. Gehe zum Feld, welches weiter weit weg ist und auf dem du noch nicht standest.
6. Gehe zum Feld, welches weiter weit weg ist und auf dem du schon einmal standest.

Diese Bedingungen werden dem Hamster bei jedem Schritt zur Auswahl gestellt, und danach läuft er. Die Richtung spielt dabei keine Rolle, nur der kürzeste Weg.

zum Seitenanfang

Die Klassen des Hamsters

Klasse Funktion
Bommel.java Die Hauptklasse des Hamsters. Sie ruft die anderen Klassen auf, welche die Funktionen enthalten.
Const.java Diese Klasse enthält zusätzliche Konstanten, sie wird von allen anderen Klassen implementiert und benötigt.
Coordinate.java Ich gehe immer mit dem Hamster mit und für die Bewegung in der Karte, habe ich diese Klasse entworfen. Sie ermöglicht es mir, mich mit einfachen Befehlen(z.B. go, go_N, ...) in dem Feld zu bewegen.
Direction.java Ist für die Richtung und das Drehen des Hamsters zuständig. Wenn sich der Hamster mit "turn(TURN_RIGHT)" dreht, dann drehe ich mich im Feld mit right_Dir() mit.
Infopoint.java In dieser Klasse wird entschieden, welches Feld der Hamster als nächstes betritt.
Map.java Hier wird die Struktur zur Speicherung aller Daten bereitgestellt. Es werden Informationen gesammelt und gespeichert, die Wege neu berechnet und Felder geprüft.

Zum Seitenanfang

Die Methoden der einzelnen Klassen


Bommel.java

Methode Wirkung
run Hier werden die Strukturen(Map, Coordinate, Direction) neu angelegt und initialisiert, dann wird die Hauptlaufmethode goShopping aufgerufen.
lookAround Dreht sich im Kreis und schaut in alle Richtungen, um Aufzeichnungen zu machen. Dies macht er aber nur, wenn das Feld noch nicht als betreten gekennzeichnet und er nicht zu Hause ist.
goShopping Die wichtigste Methode überhaupt, hier laufen alle anderen Methoden zusammen oder werden hier aufgerufen. Hier wird entschieden, ob er sammeln geht, nach Hause geht oder ob er Schluss macht.
goHome Geht nach Hause und legt dann alles an Korn ab, was er hat.
goHome_Ext Siehe goHome, es gibt einen einzigen Zusatz. Wenn er ein Feld vor zu Hause steht und vor ihm in Richtung Home eine Klippe ist, dann schmeißt er das Korn darüber.
goZiel Geht zum Ziel. Wenn er zufällig über das Heimatfeld läuft, legt er auch gleich alle Körner ab.
search_next_ZField Ruft die Methode calc_new_distance_ZMap(Klasse Map) auf, es werden neue Entfernungen berechnet.
search_next_ZField_Ext Siehe search_next_ZField, die Berechnung erfolgt für erweiterte Labyrinthe.
search_next_Field_Ext Ruft die Methode calc_new_distance_Ext_Map(Klasse Map) auf.
dropAll Legt alles an Körner ab, was er hat.

nach oben

Const.java

Definition von Konstanten.
Eine kurze Beschreibung der einzelnen Konstanten, wird im Quelltext der Klasse Const.java gegeben.

nach oben

Coordinate.java

Methode Wirkung
equals Überprüft, ob zwei Koordinaten gleich sind.
get_x Gibt die x-Koordinate zurück.
get_y Die y-Koordinate wird zurückgegeben.
set_Field Setzt auf die Koordinate, die der Methode übergeben wird.
set_Home Setzt die Koordinate auf das Heimatfeld des Hamsters.
Hilfsmethoden
(go_N, go_NE, ..., goNW)
Geht in verschiedene Richtungen, in der Map.
go Nutzt die Hilfsmethoden(go_N, go_NE, ..., goNW) und die Richtung(Direction), um sich in der Map zu bewegen.

nach oben

Direction.java

Methode Wirkung
get_Dir Gibt die Richtung zurück, in die der Hamster gerade schaut.
right_Dir Dreht sich nach rechts.

nach oben

Infopoint.java

Hier wird ein kleines Array erzeugt, welches die Werte aus den umliegenden Feldern aufnimmt. So kann schneller und einfacher geprüft werden, in welche Richtung der Hamster gehen soll.
Die Laufrichtung des Hamsters ist davon abhängig, in welcher Richtung das Array in der Methode bestWay_Info durchlaufen wird.

Methode Wirkung
init_Info Initialisierung des Arrays.
fuell_Info Das Array wird mit Werten aus den umliegenden Feldern gefüllt.
bestWay_Info Entscheidung für den besten Weg, nach bestimmten Gesichtspunkten (siehe Lauf- und Suchstrategie).

nach oben

Map.java

Methode Wirkung
init_Map Das Feld wird zu Begin mit Standartwerten initialisiert.
initDIST_Map In der Karte werden die Entfernungen zurückgesetzt, zur Neuberechnung der Distanzen. Hier wird auch gleich mit check_Field geprüft und Felder die ich nicht mehr betreten muss, werden dann auf besucht gesetzt.
get_minIndiz_Ext_Map Gibt das INDIZ(gesehen und noch nicht betreten) Feld zurück, welches am wenigsten weit weg ist.
get_minCorn_Ext_Map Es wird das Feld zurückgegeben, auf welchem Korn liegt und am wenigsten weit weg ist.
set_value_Map Hilfsmethode, setzt einen Wert in die Karte. Es gibt noch weitere Hilfsmethoden, wie set_N, set_NE ... set_NW, diese setzen ebenfalls Werte in die Karte.
get_value_Map Eine weitere Hilfsmethode, diese gibt einen Wert aus der Karte zurück. Es gibt noch weitere Hilfsmethoden, wie get_N, get_NE ... get_NW, diese geben ebenfalls Werte aus der Karte zurück.
calc_pot_ZField Das gilt nur für INDIZ(gesehen und noch nicht betreten) Felder.
Es wird geprüft, ob ein weiteres INDIZ Feld nebenan ist. Wenn dies der Fall ist und kein Korn auf beiden liegt, dann werden diese beiden Felder als Felder betrachtet, die nicht mehr besucht werden müssen.
check_Field Das gilt nur für INDIZ(gesehen und noch nicht betreten) Felder.
Es wird geprüft, ob alle Felder rings um dieses INDIZ Feld, als besucht gekennzeichnet sind. Wenn dies der Fall ist, wird das INDIZ Feld mit entsprechenden Werten aufgefüllt und als VISIT(gesehen und besucht) gekennzeichnet.
check_INDIZ_Field Ruft die Methode check_Field für alle INDIZ Felder rund um den jetzigen Standort auf.
calc_new_distance_ZMap Berechnet die Entfernungen neu, für alle Felder die erreichbar sind. Die Berechnung beginnt ausgehend vom Zielfeld und wird abgebrochen, wenn der jetzige Standpunkt erreicht ist oder alle Felder berechnet sind.
calc_new_distance_Ext_ZMap Siehe calc_new_distance_ZMap, die Berechnung erfolgt hier für erweiterte Labyrinthe.
calc_new_distance_Ext_Map Es werden alle erreichbaren Felder, die ich vom jetzigen Standort sehen kann, mit neuen Distanzwerten berechnet. Diese Methode wird für erweiterte Labyrinthe benötigt, um festzustellen welche Felder erreichbar sind oder auch nicht.
set_visit_Map Diese Methode indiziert die Felder beim Laufen mit neuen Abstandswerten, so ist eine vollständige Neuberechnung während des Laufes nicht nötig. Hier werden auch die Werte INDIZ und VISIT gesetzt, für alle Felder die ich sehe und(oder) betrete.

nach oben

Zum Seitenanfang