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

 


Die Funktionsweise des Hamsters


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.



Die interne Karte


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.








Die Wegfindung



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.




Die Klassen und Methoden

nach oben

Klassen
Methoden
Rückgabewert
void

startmap()

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


Felder


Felder

public void Felder()

Konstruktor zum Erzeugen eines Feldes. Damit sind alle Variablen der Klasse Felder frei zugänglich und können dem jeweiligen Feld angepasst werden.

zurück


Map


Map

public void Map()

Konstruktor zum Erzeugen der Map.

zurück

startmap

public void starmap()

Initialisiert die Map. Es wird das Startfeld und der Array, in dem das Startfeld liegt, angelegt, und dieser dann der Ringliste hinzugefügt.

zurück

kartenindex

public int kartenindex()

Gibt die Anzahl der momentan benutzen Ringe zurück und damit einen Indikator für die Größe der Karte.


zurück

gesehnesfeld

public void gesehenesfeld(int korn, int feldnr, int ringnr)

Fügt ein Feld der Karte hinzu. Existiert der Ring noch nicht, so wird auch dieser neu erstellt.

zurück

feldaenderung

public void feldaenderung(int korn, int feldnr, int ringnr)

Dient zum Ändern der Menge an Korn, die auf dem übergebenem Feld liegt.

zurück

korn

public int korn( int feldnr, int ringnr)

Gibt die Menge an Korn des übergebenen Feldes wieder.

zurück

unbekannt

public void unbekannt(boolean ja, int feldnr, int ringnr)

Setzt den Status -Unbekannt- für das übergebene Feld.

zurück

istunbekannt

public boolean istunbekannt(int feldnr, int ringnr)

Gibt zurück, ob das Feld unbekannt ist.

zurück

besucht

public void besucht(int feldnr, int ringnr)

Setzt das entsprechende Feld auf "Besucht" (true).

zurück

istbesucht

public boolean istbesucht(int feldnr, int ringnr)

Gibt zurück, ob das übergebene Feld bereits besucht wurde.

zurück

entfernung

public void entfernung(int feldnr, int ringnr, int entfernung)

Setzt die Entfernungsvariable auf den übergebenen Wert.

zurück

wentfernung

public int wentfernung (int feldnr, int ringnr)

Gibt die "Entfernung" des aktuellen Feldes zurück.

zurück

resetentfernung

public void resetentfernung()

Setzt alle Entfernungen wieder auf einen Maximalwert.

zurück

freir

public void freir(int richtung, int feldnr, int ringnr)

Dem Feld wir mitgeteilt, ob in die entsprechende Richtung eine Wand(false) steht.

zurück

gfreir

public boolean gfreir(int richtung, intfeldnr, int ringnr)

Gibt zurück, ob von dem Feld in der übergebenen Richtung eine Wand steht (false).

zurück

felderrechnung

public boolean felderrechnung()

Gibt zurück, ob noch unbekannte Felder existieren, die noch nicht besucht wurden.
Gleichzeitig setzt die Methode Felder, die noch nicht besucht wurden, auf "Besucht", falls es
nutzlos wäre, sie zu besuchen (z.B.: Felder, die nur von bekannten Feldern umgeben sind und auf denen
kein Korn liegt).


zurück


Ber

feldnr

public int feldnr(int dir,int akfeld, int akring)

Gibt die Nachbarfeldnummer des akutellen Feldes in Richtung "dir" zurück.

zurück

ringnr

public int ringnr(int dir, int akfeld, int akring)

Gibt die Nachbarringnummer des aktuellen Feldes in Richtung "dir" zurück.

zurück


Fitty

run

public void run()

Vom Wettbewerb geforderte Hauptmethode.
In ihr werden die Erkundungs- und Kornsammelmethoden so lange aufgerufen, bis eine von diesen wie Schleife abbricht und
damit die run-Methode an ihr Ende kommt und der Hamster fertig ist.

zurück

nehmekorn

public void nehmekorn(int akfeld,int akring)

Nimmt von dem Feld die größtmögliche Menge an Korn auf.

zurück

drehen

public void drehen(int akdir, int dir)

Dreht den Hamster von der aktuellen Richtung (akdir) in die gewünschte Richtung (dir).

zurück

dirr

public int dirr(int dir, int plus)

Berechnet die Richtung, wenn man zu der übergebenen Richtung (dir) einen Wert addiert (plus). Ähnelt dem Modulo 7 ohne die null.

zurück

check

public void check(int akring, int akfeld, akdir)

Schaut sich von dem aktuellen Feld alle Nachbarfelder an und schreibt die so erlangten Informationen in die Map.

zurück

erkundungsschritt

public boolean erkundungsschritt (int akring, int akfeld, int akdir)

Macht einen Schritt in unbekanntes Gebiet bzw. ruft die freifeldsuche auf, um ein solches zu finden und
geht dann dorthin. Ist der Hamster voll, veranlasst die Methode auch seine Leerung am Heimatfeld.
Die Motode liefert true zurück, sobald kein unbesuchtes Feld mehr existiert.


zurück

geheweg

public void geheweg(ArryList weg, int akdir)

Geht den Weg, der ihm als ArrayList übergeben wird - wobei nur alle Zahlen von 1-6 ab Position 3 der ArrayList interpretiert werden.

zurück

freifeldsuche

public ArrayList freifeldsuche(int akfeld, int akring)

Gibt eine ArrayList mit dem Weg zum nächsten unbekannten Feld zurück - wobei an Position 0 der Liste die Feldnummer, an Position 1 die Ringnummer und an Psoition 2 die Anzahl an Schritten zum gefundenen Feld stehen. Erst ab Position 3 ist der Weg (siehe geheweg).

zurück

gohome

public ArrayList gohome(int akfeld, int akring)

Liefert den Weg zum Heimatfeld. (Vergleiche: freifelsuche)


zurück

kornfeldsuche

public boolean kornfeldsuche(int akfeld, int akring, int akdir)

Sucht nach Korn auf der Karte und bringt es zum Heimatfeld. Liefert true, sobald (effektiv) kein Korn mehr auf der Karte.

zurück

obj2int

public int obj2int(Object obj)

Wandelt das Objekt in eine int um und gibt diese zurück.

zurück

int2obj

public Object int2obj(int in)

Wandelt die int in ein Objekt um und gibt dies zurück.

zurück























s