Dokumentation des Hamsters "ALAH"
Die Grundidee war es, einen Hamster zu schaffen,
welcher alle Felder im einfachen Labyrinth erreicht, untersucht und "leert".
:-)
Die Karte unseres Hamster
Als Grundlage gaben wir dem Hamster eine Karte,
welche aus einem zweidimensionalen Feld besteht!
In dieser Karte wurden sämtliche Daten über die
einzelnen Felder im Labyrinth gespeichert. Zu diesen Daten gehören
Informationen über Wände, Körner, das Herkunftsfeld, den kürzesten Heimweg,
die Feldnummer, und die Information, ob man auf diesem Feld schon war.
Dazu folgende Übersicht:
|
karte[x][y][0 bis 5] |
Wenn sich in der jeweiligen
Richtung (0-5) eine Wand befindet wird der Wert auf 1 gesetzt, sonst ist
er 0.
|
 |
|
karte[x][y][6] |
beschreibt die Richtung aus
der der Hamster gekommen ist, als er zum ersten Mal das betreffende Feld
betreten hat, da diese den Weg nach Hause sichert
|
|
karte[x][y][7] |
gibt die Anzahl der Ausgänge des Feldes an |
|
karte[x][y][8] |
gibt an ob auf dem Feld Körner
liegen (belegt mit 0 oder 1) |
|
karte[x][y][10] |
wenn das Feld schon einmal
betreten wurde gleich 1, sonst gleich 0 |
|
karte[x][y][11] |
gibt die Anzahl der Schritte
zum Heimatfeld an |
|
karte[x][y][12] |
die Richtung in der der kürzeste
Weg zum Heimatfeld liegt. Wenn der Hamster 20 Körner trägt, wird
karte[x][y][11] der Nachbarfelder
verglichen und wenn sich ein kürzerer Heimweg ergibt (als über
karte[x][y][6]), dreht sich der Hamster
in diese Richtung und führt
gogogo() aus |
|
karte[x][y][13] |
Feldnummer. Wenn das
Labyrinth schon größtenteils erkundet ist und sich der Hamster gerade
zufällig auf dem Heimatfeld befindet, soll
verhindert werden das er noch einmal losläuft um dabei höchstwahrscheinlich
nur Punkte zu verlieren |
Die Koordinaten der Karte
 |
Wie man im Bild (links oben) sicherlich sehen kann ist
die HomeZone des Hamsters auch der Mittelpunkt unserer Karte, mit den
Koordinaten (75/75).
Die Bezeichnung der restlichen Koordinaten ist recht
simpel.
Bewegungen in Richtung der X-Achse (NE, SE, SW, NW)
sind nicht direkt möglich! Dabei verändert sich auch der Y-Wert der
Koordinate!
Wenn man also z.B. nach NE geht, erhöht sich sowohl
der Wert der X- als auch der Wert der Y-Koordinate
Bewegungen entlang der Y-Achse sind allerdings
möglich!
Allerdings steigt der Wert der Y-Koordinate mit einem Schritt
in Richtung N oder S um "2". Dadurch ist es auch in
einem Labyrinth, bestehend aus Sechsecken, eine normale Karte zu
verwenden.
Erklären würde ich die Erhöhung um "2"
bei Bewegungen in Richtung N oder S damit, das sich die Y-Koordinate bei
Bewegungen nach NE, SE, SW, NW um "1" verändert. Denn wenn
man von einem beliebigen Punkt aus nach NW und danach nach NE geht, ist
die neue Koordinate gleich der Koordinate welche man mit einem einfachen
Schritt nach Norden erreicht! (Bild, links unten)
|
 |
Bewegungsstrategie des Hamsters
Unser Hamster ist zur Abwechslung mal
nicht direkt links- oder rechtsgerichtet. Wenn er die Möglichkeit hat, bewegt
er sich Richtung N.
Sollte dies nicht möglich sein, sucht
er im Uhrzeigersinn die Himmelsrichtungen ab, um so einen neuen, noch nicht erkundeten, Weg zu
finden.
1. Möglichkeit. Wenn er solch eine Richtung finden, dann geht er auch in diese
Richtung
Das heißt, er prüft für jede Richtung, in welcher sich keine Wand befindet,
ob das nächste Feld schon mal betreten wurde.
|
for (int i = 0; i
< 6; i++) {
schau(i);
if
((karte[x][y][i] == 1 ) && (karte[x1][y1][10] == 0)) {
if (karte[x][y][7] > 1) {
turnto(i);
if ((richtung == 0)
&& (lr ==3)){}
else if ((richtung == 1) && (lr ==4)) {}
else if ((richtung ==
2) && (lr ==5)) {}
else if ((richtung ==
3) && (lr ==0)) {}
else if ((richtung ==
4) && (lr ==1)) {}
else if ((richtung ==
5) && (lr ==2)) {}
else {
gogogo();
break;
}
}
}
} |
2. Möglichkeit: Es gibt keinen Weg mehr den er noch
nicht erkundet hat.
Wenn dem so ist, wird die Variable "endlos" in der Methode
"wohin()" nicht auf "false" gesetzt. In diesem Fall bewegt sich
unserer Hamster zurück zu einer Kreuzung (oder dem
Heimatfeld), von dem aus er einen neuen Weg sucht.
Das ruft den folgenden Vorgang auf::
|
if (endlos==true){
if ((leer )
> Feldnummer * 0.296)
turnto(karte[x][y][13]);
else
turnto(karte[x][y][6]);
if (verbose())
logln("Jetzt sitze ich in der Klemme!");
gogogo();
} |
Die Berechnung der 29,6% kommt daher zustande, das unserer Hamster letztendlich
den selben weg zurückgehen würde, den er
auch gekommen ist. Daher würde er in einem leeren Labyrinth alle Felder noch
einmal entlang laufen, obwohl sie schon erkundet sind.
Da wird jetzt dadurch umgangen, das er prüft, ob ein bestimmter Anteil leerer
Felder in einem Labyrinth sind, und er so auf dem
Kürzesten Weg wieder nach Hause gehen kann!
3.
Möglichkeit: Der Hamster steht auf der HomeZone, und
versucht sich in Richtung "9" zu drehen
Sollte dieser Fall eintreten, hat der Hamster aller umliegenden Gänge besucht,
und wir nun in der Methode "wohin()"
die Variable "endlos" auf "true" setzen. Da der Hamster nun
versucht sich in Richtung "9" zu drehen, was nur auf der HomeZone
vorkommen kann, wird in der Methode "turnto(x)" dieser Wert
abgefangen. Daraufhin wird "fertig" auf "true" gesetzt,
was den Lauf unseres Hamsters beendet.
|
//Dreht den
Hamster in die vorgegebene Richtung. Wenn "richtung"=9 dann
wird der Lauf des Hamsters beendet.
public
void turnto(int direction){
if
(direction != 9) {
while
(richtung < direction)
nachrechts();
while
(richtung > direction)
nachlinks();
}
else
fertig = true;
}//turnto//
bzw. //Steht
auf dem Startfeld und hat nichts mehr zu tun (wird in der Methode "laufen()" geprüft)
if ((karte[x][y][6]
== 9) && (endlos==true)) fertig = true;
|
Daraus folgt dann das Beenden des Laufes, da unser Hamster nur laufen soll
solange "fertig" gleich "false" ist.
|
//Solange er
nicht fertig ist soll er laufen, erkunden und sammeln
while (!fertig) {
laufen();
} |
Die Sammelstrategie unseres Hamster
Der Hamster sammelt eigentlich nach einem ganz einfachen Prinzip. Wenn er
etwas findet, dann nimmt er es mit!
Aufgerufen wird die Methode
"sammeln()" in der Methode "wohin()", da der Hamster da ja
überlegt was er als nächstes tun soll!
Hat er also Körner gefunden,
nimmt er diese, und prüft ob weiterhin Körner auf diesem Feld liegen.
|
if (
(karte[x][y][8] == 1) && (!atHome() ) ){
//Nimmt falls vorhanden Korn auf
take(CORNCARRY_MAX);
if
(verbose()) logln("Nehme Korn auf");
if
(getCarriedCorn() == CORNCARRY_MAX) {
maulvoll
= true;
if (verbose()) logln("Habe die Schnauze voll");
}
} |
Sollte er bei seinem Limit von 20 Körner angekommen sein, setzt er die Variable
"maulvoll" auf "true".
Wenn nicht, setzt er seinen Weg fort, bis er irgendwann mal sein Limit erreicht!
Für den Fall das er sein Limit erreicht hat, prüft er Dinge:
|
//Bedingungen fürs
Weg sparen. Bei einer Entfernung von über 99 Schritten zum
Heimatfeld, bricht der Hamster die Erkundung ab, da sich der Aufwand für
die möglicherweise erhaltenen Punkte nicht mehr lohnt.
Er könnte
maximal 20 Körner mitnehmen -> 200Punkte. Aber er würde dabei
genauso viele, oder noch mehr Punkte verlieren.
if
( ( ( (maulvoll == true) && ( (karte[x][y][7] < 2)
&&( ( ( (lookHere() & CORNMASK) == CORN) == false) ) ) )
|| (
(maulvoll == true) && ( getAvailableCorn() * 10 <
karte[x][y][11] * 2) && (karte[x][y][7] < 2) )
||
(karte[x][y][11] > 99) ) ) {
} |
| Stehe ich in einer Sackgasse? |
Ja(1) |
Liegen hier noch genügend Körner um einen weiteren
Besuch dieses Feldes zu rechtfertigen? |
Ja (1.1) |
DANN: Bringe von hier aus die Körner zurück,
um anschließend die Suche von hier aus fortzusetzen. |
| Nein(1.2) |
Gehe bis zur letzten Kreuzung (bzw. HomeZone)
zurück, um von dort aus die Körner zurückzubringen, und die Suche von
dort fortzusetzen. |
| Nein(2) |
Unter diesen umständen bringt der
Hamster die Körner zum Mittelpunkt zurück, und kehrt zu diesem Feld
zurück. |
Fall 1.1 + Fall 2 : Bei dem Weg den der Hamster zurück geht,
handelt es sich um den kürzesten ihm zu dieser Zeit bekannten Weg.
Dieser wird dabei in dem String "Feldweg" gespeichert, um ihn nach dem
ablegen der Körner wieder zurückzugehen.
Dabei wird auch die Methode "andererichtung" verwendet, welche einfach
den entgegengesetzten Wert der aktuellen
Richtung zurückgibt.
|
// erstelle einen
Weg, um nach dem Körner wegbringen, auf dem aktuellen Punkt die Suche
fortzusetzen
if (maulvoll == true){
Feldweg
= "";
while
(!atHome()){
turnto(karte[x][y][13]);
Feldweg
+= "" + andererichtung(karte[x][y][13]);
gogogo();
}
dropHere(CORNCARRY_MAX); //Körner ablegen
if
(verbose()) logln("Körner rauswürgen");
maulvoll
= false;
int f = Feldweg.length() - 1;
//Gehe auf dem "Feldweg" wieder zu dem
int
test = 0;
//aktuellen Punkt zurück
while (
f >= 0){
test =
Integer.parseInt("" + Feldweg.charAt(f));
turnto(test);
gogogo();
f--;
} |
Fall 1.2: Auf dem aktuellen Feld liegen entweder keine, oder
unzureichend Körner, um die Bedingung zu erfüllen, das der Hamster
dieses Feld noch einmal besuchen soll. um also nicht wieder auf dieses Feld
zurückzukehren, geht der Hamster gleich soweit zurück,
bis er entweder auf der HomeZone, oder auf einer Kreuzung mit noch nicht
erkundeten Wegen landet!
|
// Wenn das Maul
voll ist, und der Hamster in einer Sackgasse steht, geht der Hamster bis
zur nächsten Kreuzung zurück, da dieser Zweig dann nicht mehr besucht
werden muss.
while
((karte[x][y][7] < 3) && (!atHome())){
turnto(karte[x][y][6]);
gogogo();
}
//prüfe
ob von dieser Kreuzung aus noch Wege erkundet werden müssen
// bhsg = "B"in
"h"ier "s"chon (überall) "g"ewesen
bhsg = true;
while
( (bhsg == true) && (!atHome())) {
for
(int i = 0; i < 6; i++) {
schau(i);
if
((karte[x][y][i] == 1 ) && (karte[x1][y1][10] == 1)) {}
else
if ((karte[x][y][i] == 1 ) && (karte[x1][y1][10] == 0))
bhsg =
false;
}
if (bhsg)
{
if (verbose()) logln("BIN HIER ÜBERALL SCHON
GEWESEN");
turnto(karte[x][y][6]);
gogogo();
}
} |
Hat er solch einen Wegpunkt gefunden, setzt er seinen Weg wie im Fall 1.1 oder 2
fort. Das heißt, von dort aus baut er sich seinen
"Feldweg" auf, legt die Körner ab, geht den "Feldweg"
zurück, und setzt seine suche fort!.
Damit haben wir den Hamster eigentlich so erklärt, wie er sich in allen
Labyrinthen verhält! (zumindest hat er es bis jetzt getan)
Nicht umgesetzte Ideen: Hamster der zwischen
verschiedenen Punkten navigieren kann (durch unsere Karte nicht ohne weiteres
möglich)
Hamster der erst sammelt, wenn er wirklich die kürzesten Wege zum Heimatfeld
gefunden hat
...
Falls irgendwelche Stellen oder Eigenschaften des Hamsters noch nicht
ausführlich genug beschrieben sind machen wir das auf Anfrage gerne!
mfg. Stephan Kanus & Christoph Faust