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