Hamsterwettbewerb
2002
der Otto-von-Guericke-Universität Magdeburg
Dokumentation
zu dem Hamster "Fitty"
Autor und geistiger Vater des Hamsters: Mathias Fiedler
Matrikelnr.:162669
Im Folgenden möchte ich Ihnen die Funktionsweise des Hamsters "Fitty"
und alle in ihm verwendeten Klassen und Methoden näher bringen.
Gliederung:
+
Funktionsweise
des Hamsters
+ Die interne Karte
+ Die Wegfindung
+ Klassen
& Methoden
+ Bemerkungen des Autors
Der
Hamster "Fitty" versucht zuerst das Labyrinth auf möglichst
simple Weise abzulaufen. Dabei schaut er sich um und sammelt Informationen
über alle seine Nachbarfelder und notiert diese in seiner internen Karte.
Nun macht er einen Schritt. Er geht dabei nur auf ein Feld, wenn es noch nicht
besucht wurde bzw. Korn enthält und wenn natürlich keine Wand im
Weg ist. Treffen diese Eigenschaften auf das Feld direkt vor ihm nicht zu,
so versucht er es halb rechts. Hat er dort auch keinen Erfolg, versucht er
es halb links, dann stark rechts und stark links. Findet er ein solches Feld,
geht er einen Schritt nach vorn. Ist der Hamster jedoch von Wänden und
besuchten Felder "umzingelt", so sucht er in seiner Karte ein Feld
mit den oben genannten Eigenschaften. Findet er eines, so macht er sich auf
den kürzesten Weg dorthin und setzt sein Erkunden fort. Bei diesem Vorgehen
sammelt Fitty alles Korn ein, auf das er "tritt". Sobald seine Backen
voll sind, wird der kürzeste Weg nach Hause berechnet, wo er das Korn
ablädt. Von dort aus setzt er sein Erkunden nach dem oben beschriebenen
Verfahren fort. Der Hamster beendet seinen Lauf, sobald keine erreichbaren
bzw. unbesuchten Felder mehr in seiner Karte verzeichnet sind, oder er vom
Startpunkt aus einen Weg mit mehr als 100 Schritten errechnet; denn bei Wegen
jenseits der 100 sammelt der Hamster nur noch Minuspunkte. Um die Effizienz
von Fitty noch weiter zu steigern, rechnet er vor jedem Schritt Felder "raus".
Das bedeutet, dass er Felder, die er noch nicht besucht hat, als besucht markiert.
Solche Felder sind unbesuchte Felder, die nur von mindestens 5 besuchten Feldern
umgeben sind.
Einer der Hintergedanken beim erstellen der Karte war stets, dass das Labyrinth
beliebig groß werden könnte. Deshalb hatte ich von Anfang an Abstand
von einem Array genommen. Aus diesem Grund ist die Grundlage meiner Struktur
eine ArrayList, welche das Labyrinth in Ringe teilt. Die ArrayList ist hierfür
besonders geeignet, da man auf ihre Elemente schnell zugreifen kann und sie
beliebig erweiterbar ist. Damit sind dem Labyrinth keine Grenzen gesetzt.
Die Elemente der ArrayList sind gewöhliche Arrays bestehend aus Felder-Objekten
(siehe Grafik).
Die Felder-Objekte wiederum sind in einer Klasse definiert, die als Container
für folgende Informationen dient:
- Menge an Korn auf dem Feld
- ist das Feld schon besucht worden
- ist das Feld schon gesehen worden
- in welcher Richtung sind Wände
- die Entfernung zum aktuellen Feld (wichtig für die Wegberechnung)
Problem der Dateistruktur ist nur, dass sich die Berechnung der Nummern der
Nachbarfelder schwer gestaltet. Deshalb musste dafür eine weitere Klasse
eingeführt werden : "Ber". Hier wir nur das Feld x auf dem
Ring y berechnet, wenn man vom aktuellen Feld in Richtung z geht.
Ist diese Klasse jedoch erst einmal geschrieben, lässt es sich mit dieser
Struktur schnell und ohne Probleme arbeiten - mit dem oben genannten Vorteil,
dass man im Vorraus nicht wissen muss, wie groß das Labyrinth wird.
Wenn Fitty das nächste Feld mit einer bestimmten Eigenschaft (z.B.:
mit Korn) sucht, so macht er folgendes:
Er nummeriert alle 6 Nachbarfelder aufsteigend durch ("Entfernung")
und erstellt je eine Liste, in der das aktuelle Feld und die Richtung gespeichert
wird und packt diese Liste wieder in eine andere Liste. Aus der wird nun
das unterste Element entfernt und die Funktion mit dem dort gespeicherten
Feld neu aufgerufen. Allerdings wird nur das Nachbarfeld mit der nächsthöheren
"Entfernung" nummeriert, dessen "Entfernung" nicht niedriger
ist. Damit wird erreicht, dass die "Entfernungs"-Nummer immer
die aktuell kürzeste zum Ausgangsfeld ist. Landet dieser Algorithmus
nun auf dem gesuchten Feld, so wird die Liste zurückgegeben, mit der
das gesuchte Feld erreicht wurde. Da in dieser Liste immer die Richtung
gespeichert wurde, muss man jetzt nur die Liste von vorne nach hinten durchlaufen
und man erhält den direkten Weg. Den muss der Hamster dann nur noch
beschreiten.
Klassen
|
Methoden |
Rückgabewert
|
---|---|---|
void
|
||
void
|
||
int
|
||
void
|
||
void
|
||
int
|
||
void
|
||
boolean
|
||
void
|
||
boolean
|
||
void
|
||
int
|
||
void
|
||
void
|
||
boolean
|
||
boolean
|
||
int
|
||
int
|
||
void
|
||
void
|
||
void
|
||
int
|
||
void
|
||
boolean
|
||
void
|
||
ArrayList
|
||
ArrayList
|
||
boolean
|
||
int
|
||
Object
|