Recursive Runner

Strategie:

Recursive Runner arbeitet sich rekursiv durch das Labyrinth, d.h. er besucht von jedem Feld aus alle angrenzenden Felder, sofern sie zugänglich sind und er sie noch nicht betreten hat. Auf dieses Weise werden systematisch sämtliche Felder abgelaufen. Bei der Auswahl des als nächstem zu betretendem Feld sucht er nach angrenzenden Feldern, die von besuchten Feldern eingekreist sind, und besucht diese zuerst. Gibt es keine solchen Felder, richtet er sich zum Startfeld hin aus und sucht von dort ausgehend abwechselnd rechts und links nach einem freien Feld, das er dann besucht (so bleibt der Hamster möglichst nah bei der Mitte und kann den kürzesten Heimweg benutzen).

Kann er von einem Feld aus nicht mehr weiter, kehrt er auf das vorherige Feld zurück. Auf diese Weise arbeitet sich Recursive Runner vor, bis er nicht mehr weiter kommt, und sammelt auf dem Rückweg alle Körner ein. Hat er die maximale Anzahl eingesammelt, läuft er auf dem kürzesten Weg nach Hause, legt die Körner ab und kehrt wieder an den Punkt zurück, an dem er aufgehört hat. Ansonsten legt er die Körner an der nächsten Abzweigung ab und besucht diese. Hat er alle Felder abgearbeitet, beendet er seinen Lauf.

Datenstruktur:

Jedes Feld des Labyrinths erhält ein Koordinatenpaar (x,y), das wie folgt entsteht:
Das Startfeld hat die Koordinate (0,0). Die positive X-Achse zeigt nach oben, die negative nach unten; die positive Y-Achse zeigt nach rechts unten, die negative nach links oben. Nach rechts oben erhöhen sich x und y um je 1, nach links unten verringern sich x und y um je 1.

Das Labyrinth wird als zweidimensionales Array repräsentiert, dessen Elemente aus dem Datentyp Position bestehen. Position ist ein Datentyp, der Informationen über ein Feld enthält:

Weiter besitzt der Datentyp Methoden, um die Variablen zu verändern, nach der oben beschriebenen Weise das nächste zu besuchende Feld auszumachen, die Nachbarfelder zu überprüfen usw.

Sonstiges:

Der Hamster besitzt einen Kompass, mit dem er immer seine absolute Ausrichtung erkennt (die Richtungen werden durch die Zahlen 0-5 repräsentiert, wobei 'oben' durch 0 dargestellt wird und die weiteren Zahlen im Uhrzeigersinn liegen), und einen globalen Koordinatenanzeiger. Zur Aktualisierung habe ich die turn- und forward-Methoden der Hamster-Klasse überschrieben und dem Aufruf der jeweiligen Super-Methode die entsprechende Änderung von Kompass und Koordinaten hinzugefügt.

Das Kernstück des Hamsters ist die Methode visit: hier schaut sich der Hamster von einem Feld aus nach den Nachbarfeldern um und korrigiert gegebenenfalls die Richtung des kürzesten Heimwegs. Dann besucht er in einer Schleife alle zugänglichen und unbetretenen Nachbarfelder. Anschließend sammelt er eventuell vorhandenes Korn auf und kehrt auf das Feld zurück, von dem er kam. Wenn er die maximale Anzahl an Körnern trägt, wird die Rekursion von der Methode homeRun unterbrochen. Ist der Hamster durch einen Homerun nach Hause zurückgekehrt und hat die Körner abgelegt, prüft er mittels der Variablen destroy und einiger etwas umständlicher Konstruktionen, ob es sich lohnt, wieder zu dem Feld zurückzukehren, von dem aus er nach Hause gelaufen ist. Ist das der Fall, geht er wieder zurück; andernfalls werden die rekursiven Aufrufe von visit beendet, und der Hamster bricht vom Startfeld aus wieder zum Sammeln auf, wobei schon abgearbeitete Zweige nicht mehr beachtet werden.