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