Dokumentation des Hamsters H2D2
von Christian Semrau


Der Hamster speichert Informationen ueber den bekannten Teil des Labyrinths in einer Klasse Map, die ein zweidimensionales Array von Cell-Objekten hat.
Diese Karte ist ein Parallelogramm von Zellen, bei dem die Spalten nach rechts hin jeweils um eine halbe Zeile runtergezogen sind (man hat dann ein zweidimensionales Koordinatensystem mit (0,0) in der linken oberen Ecke des Parallelogramms, X-Richtung geht nach rechts unten, Y-Richtung geht nach unten). Darin eingebettet ist das sechseckige Labyrinth wie in der Abbildung, nur mit einer Breite und Hoehe von 61 Zellen, da der Hamster die Groesse des Labyrinths nicht kennt. (Die Anordnung entspricht ansonsten derjenigen der Wettbewerbsumgebung.)
Der Hamster verwendet die Konstanten N, NE, SE, S, SW, NW, um Richtungen anzugeben. Die Koordinatendifferenzen zu den Nachbarfeldern sind N:(0,-1), NE:(+1,-1), SE:(+1,0), S:(0,+1), SW:(-1,+1), NW:(-1,0).
Das Heimatfeld des Hamsters ist dabei stets in der Mitte (wie in der Dokumentation der Umgebung garantiert) auf Feld (30,30).

Jedes Cell-Objekt speichert folgende Informationen ueber ein Feld des Labyrinths (einen Knoten des zugehoerigen Graphen):
  • die Koordinaten des Feldes als IntPoint
  • die Maismenge auf dem Feld
    Der Wert ist groesser als 0 fuer die bekannte Anzahl, gleich 0 fuer leer, -1 fuer "unbekannt", und -2 fuer "mindestens eins"
  • die Art der Verbindungen zu den Nachbarfeldern (Kanten zwischen den Knoten):
    UNKNOWN="unbekannt",
    FREE="frei",
    WALL="Wand",
    UP="Klippe hoch",
    DOWN="Klippe runter".
    Schraegen sind "frei".
  • ob das Feld schon gesehen wurde und ob es schon betreten wurde:
    NOTSEEN="noch nicht gesehen",
    JUSTSEEN="gesehen, aber nicht betreten",
    ENTERED="betreten".
  • die Cell-Objekte der Nachbarfelder fuer bequemeren Zugriff

Nach der Initialisierung der Karte, bei der die Cell-Objekte erzeugt und miteinander verknuepft werden, beginnt H2D2 die Erkundung.

Die laeuft in einer Endlosschleife, die mit einer eigenen Exception unterbrochen wird. Diese DoStopException wird ausserhalb der Schleife abgefangen und dann die run-Methode verlassen. Auf diese Weise erspart sich H2D2 staendige Abfragen nach einer Statusvariable, und fehlerhaftes Verhalten fuehrt zu einem sofortigem Abbruch (z.B. der Versuch, gegen eine Wand zu laufen).

In der Schleife bewegt sich H2D2 zum naechsten "interessanten Feld", schaut sich da um, und nimmt dann Getreide auf wenn welches dort liegt. Wenn er danach die Backen voll hat, geht er nach Hause und startet die naechste Runde vom Heimatfeld.

"Interessant" sind Felder, die Mais haben (also Kornanzahl groesser 0 oder "mindestens eins"), oder die ein Nachbarfeld haben, das der Hamster noch nicht gesehen hat (NOTSEEN) (ein Feld hat nur dann als Kornmenge den Wert "unbekannt", wenn es noch nicht gesehen wurde).

Wenn H2D2 in seiner Umgebung (die 6 Nachbarfelder) ein Feld findet, das interessant ist, dann geht er dort hin und schaut sich um. Beim Umschauen werden Informationen ueber die Art der Verbindung zu den Nachbarfeldern gespeichert (freier Weg, Klippen, Korn...)

Findet H2D2 kein interessantes Feld in direkter Nachbarschaft, dann startet er eine Suchroutine, um das naechstliegende Zielfeld zu ermitteln. Diese Suchroutine verwendet eine Breitensuche analog Dijkstras Algorithmus, um fuer jedes untersuchte Feld die Entfernung zum Hamsterfeld zu bestimmen. Sobald ein interessantes Feld gefunden wurde, stoppt die Suche und der Hamster laeuft zu dem gefundenen Feld.

Dadurch, dass H2D2 nur nach Feldern ausschaut, die moeglicherweise noch Mais enthalten, gelingt es ihm, das Labyrinth zu erkunden, ohne zwanghaft jedes einzelne Feld betreten zu muessen (noch nicht betretene Felder ohne Mais sind nur dann interessant, wenn sie an ungesehene Felder angrenzen). Fruehere Versionen von H2D2 und auch andere Hamster erkennen einzelne Felder, die von betretenen Nachbarn umgeben sind, und koennen diese auch als "betreten" markieren, um auf diese Weise ab und zu einige Schritte zu sparen. H2D2 kann komplette Reihen von JUSTSEEN-Feldern verkraften.
Das ergibt aber das Problem, dass er mit der normalen Suchroutine nicht immer den kuerzestmoeglichen Weg nach Hause findet (ueber bekannte freie Kanten und absteigende Klippen). Deshalb errechnet er zusaetzlich zum Weg ueber bekannte Kanten noch einen Weg, bei dem Kanten zwischen gesehenen Feldern als "frei" betrachtet werden. (Noch nicht gesehene Felder werden dabei nicht betrachtet.) Wenn dieser "moegliche Weg" kuerzer ist als der bekannte, dann versucht H2D2, diesen Weg zu gehen. Wenn dieser Weg nicht begehbar ist, weil eine neu entdeckte Wand den Weg versperrt, sucht H2D2 erneut den Heimweg, und umgeht so die Wand. Nach ein paar gescheiterten Versuchen (neuentdeckten Waenden oder Klippen) gibt er dieses Probieren aber auf und benutzt direkt den Weg ueber als frei bekannte Kanten. Wenn H2D2 auf dem Heimweg ist, und er findet nicht mal einen moeglichen Weg nach Hause (was passieren kann, wenn er beim Heimgehen eine neuentdeckte Klippe runterspringt), dann bricht er das Nachhausegehen ab und kuemmert sich wieder um die Erkundung. Stellt er aber fest, dass es nichts mehr zu entdecken gibt, und findet keinen moeglichen Heimweg, dann bricht er seinen Lauf ab mit der Meldung, dass er eingesperrt ist.


10.04.2002
Christian Semrau