Lehrveranstaltung Algorithmen und Datenstrukturen

Dokumentation der Implementierung des Hamstersteuerprogramms "tr{ok" für einfache Labyrinthe

von Timo Heinrich, Matrikelnummer 163609

 

 

1.) Aufgabenstellung:

"Ein Hamster, der seinen Wintervorrat an Getreide noch nicht gesammelt hat, wird in einem Labyrinth ausgesetzt. In diesem Labyrinth sind Maiskörner verteilt. Die Aufgabe des Hamsters ist es, möglichst viele Maiskörner zu sammeln und zu seinem Heimatfeld (von dem er startet) zu bringen. Dabei muss er die Sammelwege möglichst kurz halten. Am Ende muss er wieder zuhause sein, um seinen Winterschlaf beginnen zu können. In diesem Programmierwettbewerb soll ein Programm geschrieben werden, das den Hamster so durch das Labyrinth steuert, dass er moeglichst viel Getreide mit moeglichst wenigen Schritten einsammelt. Dazu steht eine Reihe von Funktionen zur Verfügung, mit denen dem Hamster bestimmte einfache Befehle gegeben werden können (z.B. "Drehe Dich nach links!", "Gehe ein Feld geradeaus!", "Nimm drei Maiskörner auf!") oder mit denen man Informationen über die Umgebung des Hamster erhält (z.B. "Wieviel Mais liegt auf dem Feld auf dem ich gerade bin?", "Was sehe ich vor mir?").

Wie gut ein Programm die Aufgabe gelöst hat, wird anhand der Anzahl der gesammelten Maiskörner und der Länge des beim Sammeln zurückgelegten Weges entschieden. (...)

Ein Labyrinth besteht aus sechseckigen Feldern, die wie Bienenwaben angeordnet sind und ein Sechseck bilden. Durch Waende zwischen den Feldern bilden sich Gänge und Räume. Auf einigen Feldern liegen Maiskörner. Das ganze Labyrinth ist von Wänden umrandet, so dass der Hamster nicht "rausfallen" kann. Das Heimatfeld des Hamsters ist immer das mittlere Feld des Labyrinths. (...) Die Ausdehnung des Labyrinths ist dem Hamster nicht von vornherein bekannt, es gibt aber die Beschraenkung auf eine Seitenlaenge von hoechstens 30 Feldern. Es muss nicht jedes Feld des Labyrinths erreichbar sein, es ist aber auf den Wettbewerbslabyrinthen sichergestellt, dass man von jedem erreichbaren Feld wieder heimkommt."

 

2.) Zur Implementierung:

Gegeben war eine Programmumgebung, die sogenannte "World", die dem Hamster bestimmte Informationen bereitstellt. Der Hamster sollte die vorgegeben Klasse "Hamster" erweitern und dabei die run-Methode überschreiben. Verwendete Programmiersprache ist Java.

 

3.) Zum Vorgehen:

Meinen Hamster tr{ok habe ich in vier aufeinanderfolgenden Stufen implementiert und dabei versucht die folgenden Ziele nacheinander zu erreichen:

 

4.) Zur Laufstrategie:

Auf seinem Weg durch das Labyrinth besucht der Hamster zunächst die nördlichste unbekannte Zelle (Norden bezeichnet dabei die Blickrichtung beim Start des Hamsterlaufs).

Ist der Hamster auf seiner Suche nur noch von Wänden oder bekannten Zellen umgeben, sucht er die zuletzt entdeckte unbekannte Zelle auf.

Besonderheit:

 

5.) Sammelstrategie:

Dabei unterscheidet er nicht zwischen Zellen mit Mais und Zellen ohne Mais. Findet der Hamster auf einer Zelle Mais, so nimmt er die größtmögliche Anzahl von Körnern auf. Ist er voll, kehrt er um und geht zum Heimatfeld, wo er den Mais ablegt. Dann nimmt er die Suche dort wieder auf, wo er sie abgebrochen hat.

Besonderheiten:

 

6.) Zentrale Datenstruktur Labyrinth:

Die Informationen, die der Hamster auf seinem Weg durch das Labyrinth über die betretenen Zellen sammelt, speichert er in Zelle-Objekten. Diese Objekte legt er in einem Array der Größe 60 mal 60 ab (entspricht der maximalen Seitenlänge eines Labyrinths). Jede Zelle ist durch eindeutige Koordinaten ansprechbar, die den Indizes des Arrays entsprechen. Das Heimatfeld besitzt dabei die Koordinaten (30|30).

Die Klasse Zelle hat dabei folgende Attribute:

sowie weitere temporäre Attribute, die bei der Ermittlung der Wege benötigt werden.

 

7.) Programmstruktur:

Die run-Methode ruft in einer while Schleife die Methoden auf, die die Stufen bei der Maissuche des Hamsters kennzeichnen:

Der Hamster erkundet unbekannte Zellen und sammelt Mais. Dazu werden folgende Methoden benötigt:

Der Hamster sammelt Informationen über die aktuelle Zelle

Der Hamster hebt den Mais der aktuellen Zelle auf

Der Hamster entscheidet über die Richtung des nächsten Schritts. Existiert keine umliegende unbekannte Zelle, ruft er folgende Methoden auf:

ermittelt die zuletzt entdeckte unbekannte Zelle anhand der in den Zelle-Objekten gespeicherten Zeiger (Himmelsrichtungen), die die Herkunftsrichtung beim Anlegen der Zelle wiedergeben. Diese Zeiger werden virtuell verfolgt, bis eine Zelle mit angrenzenden noch nicht entdeckten Zellen gefunden wird. Um einen kurzen Weg zu dieser unbekannten Zelle zu ermöglichen, wird die zurückgelegte Distanz gespeichert (analog zur Distanz zum Heimatfeld)

gibt die jeweils günstigste Himmelsrichtung auf dem Weg zur unbekannten Zelle zurück

Der Hamster macht den nächsten Schritt und legt die betretene Zelle an, falls sie noch nicht existiert

Der Hamster sucht das Heimatfeld auf und das auf möglichst kurzem Weg

ruft distanzenKontrolle für alle bisher gespeicherten Zellen auf

Die in einer Zelle gespeicherten Information über die Distanz zum Heimweg werden mit der in direkt benachbarten Zellen abgeglichen. Die Methode gibt außerdem die Himmelsrichtung der benachbarten Zelle mit der kleinsten Entfernung zum Heimatfeld zurück

Siehe oben

Der Hamster läßt den Mais auf dem Heimatfeld zurück

Der Hamster geht zu der Stelle, an der er die Suche nach Mais abgebrochen hat bzw. zur nächsten unbekannten Zelle. Dazu ruft er unbekannteFinden (siehe oben) auf

 

8.) Verbesserungsmöglichkeiten:

Die Sammelstrategie ließe sich vermutlich verbessern, indem der Hamster statt der nördlichsten noch nicht betretenen Zelle sich kreisförmig um die Heimatzelle fortbewegen würde. So könnte vermieden werden, daß der Hamster zuerst weit entfernte Maisvorkommen einsammelt und sie auf Umwegen nach Hause bringt, die durch eine unsystematische Erkundung entstanden sind.

Ein weiteres Manko der vorliegenden Implementation ist die Reihenfolge in der unbekannte Zellen aufgesucht werden, falls der Hamster seine unmittelbare Umgebung bereits kennt. Dabei sucht der Hamster nämlich nicht die jeweils am nächsten liegende Zelle, sondern die zuletzt entdeckte unbekannte Zelle. Dies liegt an der dezentralen Speicherung der unbekannten Zellen in den Zelle-Objekten ("in Richtung Westen liegt eine noch nicht besuchte Zelle"). Statt dessen könnten diese Informationen zentral gespeichert werden und dann effizient abgearbeitet werden.

Weiterhin wäre es möglich durch das Erzeugen von "Dummy"-Zellen Erkundungsschritte einzusparen. Diese Zellen könnten angelegt werden, falls der Hamster eine unbekannte Zelle entdeckt, diese aber nicht besucht. Diese Zelle dürfte keinen Mais enthalten und könnte selbständig, sobald ihre Umgebung bekannt ist oder aus anderen "Dummy"-Zellen besteht, zu einer vollwertigen Zelle mutieren.