Hamster Contest 2002 - CornCadger Dokumentation
Uebersicht
Problem
Aufgabenstellung war es in einer gegebenen Umgebung einen Hamster zu
programmieren, der in einem Labyrinth, welches bestimmte Regeln erfuellt,
Koerner einsammeln und sie fuer seinen Winterschlaf auf sein Heimatfeld
verfrachten. Konkret sollte eine Subklasse der Klasse
algds.contest2002.Hamster (oder algds.contest2002.Hamster2 fuer die
erweiterten Labyrinthe) implementiert werden. Der Hamster wird nach
Beendigung seines Lauf folgendermassen bewertet:
P = 10 * gesammelteKoerner - gegangeneSchritte - 200 *
gemachteKollisionen
Zusaetzlich gibt es Punktabzuege fuer Absturz oder Zeitueberschreitung
oder wenn der Hamster am Ende nicht auf seinem Heimatfeld ist.
Kollisionen sind also erstmal gar nicht gut. Bei einer ordentlichen
Programmierung sollten diese auch nicht auftreten(Augen auf).
Ziel ist es also den Hamster so zu Programmieren, dass er mit moeglichst
wenig Schritten moeglichst viele Koerner einsammelt.
zur Uebersicht
Theoretischer Loesungsansatz / Strategie
Ich hab mich fuer den erweiterten Hamster entschieden.
In den erweiterten Labyrinthen, im Gegensatz zu den einfachen Labyrinthen,
koennen Hoehenunterschiede auftreten, wodurch sich Haenge und Klippen
ergeben. Dadurch ergeben sich zusaetzliche Schwierigkeiten, aber auch
Moeglichkeiten in der Strategie des Hamsters.
Mein Hamster ist grundsaetzlich ein neugieriger Hamster :-). Wobei er nicht
uebermuetig wird. Eigentlich ganz einfach: Er erforscht und sammelt so lange
bis er genug gesammelt hat und macht sich dann auf den Heimweg, um das Korn
loszuwerden. Das macht er so lange, bis es nichts mehr zu sammeln oder zu
erforschen gibt, oder bis es sich nicht mehr lohnen wuerde.
Das Erforschen
Beim Erforschen sucht der Hamster als erstes das Feld, welches er als
naechstes erforschen will. Potentielle Kandidaten hierfuer sind Felder mit
Korn und Felder die unerforscht sind. Felder sind unerforscht, wenn unbekannt
ist, ob das Feld Korn oder nicht hat und/oder wenn von Nachbarnfelder nicht
die Information vorhanden ist, die von dem Feld aus erreichbar ist. Also ist
ein Feld z.B. trotzdem erforscht, wenn bekannt ist ob das Feld Korn hat und
die Waende zum Teil unbekannt sind,
aber dafuer die Nachbarfelder bereits von woanders betrachtet wurden.
Dies hat den Vorteil, dass die Anzahl der unerforschten Felder sich schneller
verringert und das Labyrinth theoretisch schneller erforscht wird.
Der Nachteil ist, dass es passieren kann, dass dadurch Abkuerzungen die
ueber solche Felder mit unbekannten Waenden fuehren, nicht erkannt werden,
weil wie gesagt die Verbindung zwischen zwei Feldern unbekannt ist.
Diese potentiellen Felder werden gefiltert, so dass zum Schluss sich ein Pfad
ergibt, den der Hamster dann entlang geht und das Feld am Ende erforscht.
Beim Filtern werden jeweils 2 Pfade miteinander verglichen.
Filterstruktur(von oben nach unten):
Kuerzerer Pfad -->bester Pfad
|
(Pfade gleichlang)
|
Ist Endfeld unerforscht? -->bester Pfad
| |
(keins unerforscht) (beide unerforscht)
| |
| Unbekannt ob Feld Korn hat? -->bester Pfad
| | |
| (bei beiden bekannt) (bei beiden unbekannt)
| | |
| | Lieg Feld hoeher? -->bester Pfad
| | |
| | (gleich hoch)
| | |
| | Mehr unbetrachtete Nachbarfelder? -->bester Pfad
| | |
| | (gleiche Anzahl unbetrachteter Nachbarfelder)
| | +--------------------------------------------+
| | |
| Hat Feld kein Korn? -->bester Pfad |
| | |
| Mehr unbetrachtete Nachbarfelder? -->bester Pfad |
| | |
| (gleiche Anzahl unbetrachteter Nachbarfelder) |
| +--------------------------------------------+ |
| | |
+------+ | |
| | |
Unbekannt ob Feld Korn hat? -->bester Pfad | |
| | | |
(bei beiden unbekannt) (bei beiden bekannt) | |
| | | |
| +-+-------------------------+ |
| | |
| Hat Feld kein Korn? -->bester Pfad |
| | | |
| (beide haben keins) (beide Felder haben Korn) |
| +-------+ | |
| | | |
\ / Ist Anzahl der Koerner unbekannt? -->bester Pfad |
| | | |
| (bei beiden unbekannt) (bei beiden bekannt) |
| +--------+ | |
| | Anzahl Koerner genau benoetigte Menge? -->bester Pfad |
\ / | |
| (Anzahl nicht passend) |
| | |
| Kleinere Anzahl von Koernern? -->bester Pfad |
| | |
| (gleiche Anzahl) |
| | |
+----------------------+---------+-----------------------------------+
|
Liegt Feld auf kleinerem Radius? -->bester Pfad
|
(gleicher Radius)
|
Felder unbekannten Waenden auf dem Pfag liegt naeher? -->bester Pfad
|
(nein)
|
Weniger Klippen auf dem Pfad? -->bester Pfad
|
(gleich Anzahl)
|
Feld liegt hoeher? -->bester Pfad
|
(gleich hoch)
|
Mehr Felder mit unbekannten Waenden? -->bester Pfad
|
Pfade gleich gut :-(
Wie man sieht alles in allem eine schoen komplizierte Sache. Diese Struktur
hat sich aus mehreren ergeben durch Test mit verschiedenen Labyrinthen.
Im Durchschnitt hat dieser Filterbaum die besten Ergebnisse gebracht.
Die Pfade die zu den potentiellen Feldern fuehren werden nacheinander mit dem
besten bisher gefundenen Pfad ueber diese Filterstruktur verglichen. Als
erster Vergleichspfad wird der erste Pfad in der Liste genommen. Der Vergleich
beginnt also mit dem zweiten Pfad. Sind die beiden Pfade gleich gut,
bleibt es bei dem bisher besten.
Die Pfade werden in einer Breitensuche vom gegenwaertigen Standpunkt des
Hamsters aus gesucht. Dabei wird in alle Richtungen jeweils 1 Schritt
gegangen. Treffen sich zwei Pfade wird nur der bessere von beiden zur weiteren
Suche verwendet. Damit spart man sich ne Menge Arbeit. :-) Sobald ein
potentielles Feld erreicht wird, wird der Schritt
fuer alle anderen Pfade noch zuende gegangen.
Haben nun alle Pfade Klippen, so werden Alternativen ohne Klippen
fuer diese Klippen-Pfade
gesucht und mit den bisherigen Pfaden verglichen. Wenn ein Weg ueber die
Klippe zu einem Endfeld einer gefundenen Alternative kuerzer als dieser
alternative Pfad ist, so wird der Pfad ueber die Klippe genommen. Wenn
nicht, so wird der schnelleste Pfad zur Alternative gesucht und dieser
Pfad genommen. Die Pfade die sich so nun ergeben werden wie oben beschrieben
gefiltert, so dass nur noch ein Pfad uebrig bleibt.
Dann geht der Hamster wie gesagt diesen Pfad entlang. Traegt er bereits Korn,
so achtet er darauf, ob er ueber das Heimatfeld laeuft, wo er das Korn ja
verstauen kann, oder ob er das Heimatfeld streift, und eine CLIFFDOWN
dazwischenliegt, so dass er das Korn auf das Heimatfeld werfen kann. Auch
stellt er nach jedem Schritt sicher, dass das Feld komplett erforscht
ist.
Ist er am Zielfeld angekommen, erforscht er es und nimmt so viel Koerner wie
moeglich auf.
Der Weg heim
Der Weg nach Hause beginnt wie beim Erforschen mit einer Breitensuche. Nur
dass hier das Heimatfeld das einzige potentielle Ziefeld ist. Gefiltert wird
hier nur waehrend der Suche.
Filterkriterien(von oben nach unten):
1. kuerzester Pfad
2. hat Pfad Klippen
3. ist Platz um Korn die Klippe runter zu werfen
4. mehr unbekannte Nachbarfelder auf dem Pfad
5. mehr Felder mit unbekannten Waenden auf dem Pfad
6. Feld mit unbekannten Waenden ist naeher
7. mehr Felder mit unbekannter Anzahl an Koernern auf dem Pfad
Wenn das letzte Feld bereits das Zielfeld ist, kommen folgende Kriterien
hinzu:
3.1. ist die Klippe naeher
3.2. liegt die erste Klippe direkt am Zielfeld
Wenn er dann einen besten Weg hat, verhaelt er sich folgerndermassen:
Zuerst dreht er sich in Richtung des naechsten Feldes auf dem Pfad.
Ist dort eine Klippe, und hinter der Klippe ist genug Platz, so wirft er das
gesamte Korn dort runter und unterbricht seinen Weg nach Hause, um weiter
zu erforschen.
Nun ueberprueft er ob auf dem Feld auf dem er steht kein Korn liegt und ob es
noch unerforschte Nachbarfelder gibt. Wenn dem so ist und das unerforschte
Nachbarsfeld (das ungehorsame Nachbarskind :-) nicht in Richtung des
Heimweges liegt(es grenzt nicht an den Heimweg), so legt er das gesamte Korn
ab und geht zu diesem Nachbarsfeld.
Ansonsten geht er einen Schritt weiter. Nun checkt er, ob alle Mauern
erforscht wurden. Wenn nicht, erforscht er sie und unterbricht den Heimweg,
weil dadurch ein neuer, besserer Heimweg entstanden sein koennte.
Es wird nun wieder die Heimwegsuche von vorne angefangen.
Wenn er dann irgendwann zu Hause ankommt, verstaut er das Korn und ist
bereit fuer neue Abenteuer, sprich Erforschen.
Wird ueberhaupt kein Heimweg gefunden, wird erst einmal weiter geforscht,
irgendwann wird man schon nen Heimweg finden. :-)
zur Uebersicht
CornCadger Classes / Datenstrukturen / Implementation
Ich habe ausser der Klassen im Hauptverzeichnis(corncadger) auch noch zwei
Libraries angelegt: corncadger.search und corncadger.move.
corncadger:
Die hauptsaechlichen Datenstrukturen, zur Speicherung der Labyrinthdaten sind
direkt im corncadger Verzeichnis.
CornCadger.java - der Hamster hoechst persoenlich
DebugWindow.java - ein Fester fuer Debug-Ausgaben, wird z.Zt. nicht verwendet
Field.java - repraesentiert ein Feld im Labyrinth
HamsterNeeds.java - Speichert die derzeitigen Beduerfnisse/Situation des
Hamsters
Map.java - Speichert das Labyrinth
Path.java - Verkettete Liste von Feldern, ein Pfad halt
readme.html - diese Dokumentation
Ein paar Worte zur Map:
Ich speichere die Fields in einem Array. Vergleiche, Pfadsuche oder aehnliches
fuehre ich jedoch nicht mit Array-Koordinaten durch. Jedenfalls nicht direkt.
Hierzu nehme ich jeweils die 6 Richtungen, in denen ein Feld liegen kann.
Indiziert habe ich diese rechtsdrehend von 0 bis 5, wobei 0 Norden bedeutet,
was aber egal
ist, da es alles relativ zur Anfangsblickrichtung gesehen wird. So gibt es
die zwei Methoden int wallAt(Field _field, int _dir) und Field
neighborAt(Field _field) die mir relativ zu _field den Mauertyp bzw. das
Nachbarfeld zurueckgeben. (neighbor ist die amerikanische Schreibweise, nur
falls es Fragen gibt :-)
Hier fuer Neugierige die beiden Umrechnungsmethoden, die mir die
Blickrichtung in
Array-Koordination umrechnet. Insgesamt ist es ein 30x120 Array wobei der
Mittelpunkt immer bei 14:59 liegt. Beide sind in Field als Instanz-Methoden
implementiert.
static int _xdivs1[] = {0, 1, 1, 0, 0, 0};
static int _xdivs2[] = {0, 0, 0, 0, -1, -1};
int _xCoordForNeighbor(int _dir) {
if (_dir < 0 || _dir > 5) return Field.UNKNOWN;
int tmp = ((this.y & 1) == 1)
? this.x + _xdivs1[_dir]
: this.x + _xdivs2[_dir];
return ((tmp < 0) || (tmp > 29)) ? Field.UNKNOWN : tmp;
}
static int _ydivs[] = {-2, -1, 1, 2, 1, -1};
int _yCoordForNeighbor(int _dir) {
if (_dir < 0 || _dir > 5) return Field.UNKNOWN;
int tmp = this.y + _ydivs[_dir];
return ((tmp < 0) || (tmp > 119)) ? Field.UNKNOWN : tmp;
}
Des weiteren gibt es dann hier noch einige Hilfsmethoden, um Informationen
ueber Felder bzw. Feldkomplexe herauszubekommen.
corncadger.search:
corncadger.search enthaelt Klassen zur Suche von Pfaden. Die wichtigeste
Klasse ist PathSearch, die die Methode bestPath enthaelt. Je nach
Subklasse von PathSearch gibt diese Methode den besten Pfad zum Erforschen,
fuer den Heimweg oder z.B. die beste Verbindung zwischen zwei Feldern
zurueck.
Criteria.java - stellt ein Filterkriterium dar, hat jede
Menge Subklassen
CriteriaTree.java - stellt einen Filterbaum dar(siehe
Strategie)
CriteriaTreeNode.java - ist ein Knoten in diesem Kriterienbaum
Distance.java - Klasse zum ermitteln der Distanz zwischen
2 Feldern
ExploreFieldPathCrawl.java - Subklasse von FieldPathCrawl,
spezialisiert auf Suche von zu
erforschenden Feldern und dazugehoerigen
Pfaden
ExploreHomePathCrawl.java - Subklasse von FieldPathCrawl,
spezialisiert auf Suche des Heimweges,
wenn mit HomePathCrawl keiner gefunden
wurde
ExploreHomePathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filtern von Heimwegen, wenn
er mit ExploreHomePathCrawl gesucht wird
ExplorePathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filtern von Erforschungswegen
FastestPathCrawl.java - Subklasse von FieldPathCrawl,
spezialisiert auf die Suche des
schnellsten Pfades
FieldPathCrawl.java - Superklasse fuer alle Suchklassen. Hier
ist der Breitensuchalgorithmus wie oben
beschrieben implementiert
FlagCriteria.java - Subklasse von Criteria, spezialisiert auf
Ja/Nein Criterien
HomePathCrawl.java - Subklasse von FieldPathCrawl,
spezialisiert auf die Suche des Heimweges
HomePathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filtern von Heimwegen
InverseExploreFieldPathCrawl.java - Subklasse von InverseFieldPathCrawl,
spezialisiert auf die Suche von Pfaden zu
unerforschten Feldern, wird derzeit
nicht verwendet
InverseFastestPathCrawl.java - Subklasse von InverseFieldPathCrawl,
spezialisiert auf die Suche des
schnellsten Pfades zwischen zwei Feldern
InverseFieldPathCrawl.java - Subklasse von FieldPathCrawl,
spezialisiert auf die Suche von Wegen vom
Zielpunkt aus(rueckwaerts)
InverseHomePathCrawl.java - Subklasse von InverseFieldPathCrawl,
spezialisiert auf die Suche des Heimweges
InverseHomePathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filtern von Pfaden fuer
den Heimweg, bei der Suche mit
InverseFieldPathCrawl
InverseWayPathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filtern von Pfaden fuer
die Wegsuche vom Zielpunkt aus
LookAround.java - Hilfsklasse zum ermitteln von
Feld-Eigenschaften
MapCreationCrawl.java - Subklasse von FieldPathCrawl, wird beim
Erstellen der Map verwendet, um
Default-Werte zu setzen und den Radius
in den Feldern zu speichern
MapInit.java - Hilfsklasse zum Erstellen der Map
NeighborCheckCrawl.java - Subklasse von FieldPathCrawl
spezialisiert zur Ermitteln von
Eigenschaften von Felder und Feldkomplexen
PathCache.java - Hilfsklasse zum Cachen von Pfaden, da die
Such jeweils doch ziemlich lange dauern
kann, wird bei jeder neuen Entdeckung
geloescht
PathSearch.java - Superklasse fuer alle Pfadsuchen, ist
abstrakt, enthaelt jedoch Methoden zur
Initialisierung von Subklassen, die
je nach Aufgabe den besten Pfad suchen
PathSet.java - Superklasse fuer alle Pfadmengen
StandardPathSet.java - Subklasse von PathSet, implementiert die
Standard-Eigenschaften zum Speichern von
Pfaden
WayPathSet.java - Subklasse von PathSet, spezialisiert auf
das Speichern/Filter von Pfaden fuer die
SchnellsterPfadSuche
Public sind von diesen Klassen nur LookAround, MapInit, PathCache und
PathSearch. Die anderen Klassen dienen nur den anderen Klassen beim
erfuellen ihrer Aufgaben.
corncadger.move:
In dieser Library gibt es die Klasse HamsterMover. Sie ist abtrakt und je nach
Subklasse wird in der Methode moveHamster(Path _p) der Hamster entlang
dem uebergebenem Pfad bewegt und je nach den Bedingungen
gehandelt(siehe Strategie).
HamsterMover.java - Superklasse aller 'Beweger',
In diesem File sind ausserdem ExploreMover und
WithoutStopMover implementiert
HomeMover.java - Subklasse von HamsterMover, spezialisiert fuer den Heimweg
Durch die vielen Subklassen (besonders von Criteria) habe fuer diese
Implementation des Hamsters insgesamt 75 Klassen erstellt. (boah) Ok, ich
geb' zu es ist zum Teil schon recht obskur aber ich habe probiert gemaess der
objektorientierten Ideale eine schoene Implementation dieses Problems zu
schreiben. Es gibt halt auch Klassen die nur aus 2 Zeilen bestehen
(siehe Criteria.java), dennoch erfuellen Sie ihren ganz speziellen Zweck.
Dadurch habe ich z.B. fuer den gesamten ExploreCriteriaTree, so wie er oben
dargestellt ist, in der Implementation nur 9 If-Anweisungen. Ist das nicht
toll!? Naja Leute, denkt was ihr wollt!
zur Uebersicht
Martin Hoerning
Last modified: Sun Apr 28 13:28:42 Westeuropäische Sommerzeit 2002