#include #include #include "hamster.h" #define HMS_MITTEX HMS_MAXXEXT-1 #define HMS_MITTEY HMS_MAXYEXT-1 unsigned char feld[HMS_MAXXEXT+HMS_MITTEX][HMS_MAXYEXT+HMS_MITTEY]; /* Funktion, die die Markierung des Feldes direkt vor dem Hamster liefert */ unsigned char feld_vorn(HAMSTER *hms) { int x,y; /* Variablen für x,y-Koordinaten */ hms_pos(hms,&x,&y); /* Positionskoordinaten bestimmen */ switch (hms_dir(hms)) /* je nachdem, wo der Hamster hinschaut... */ { case HMS_SOUTH : y--; /* y-Koordinate des nächsten Feldes ist um */ break; /* eins kleiner, als die des aktuellen Feldes */ case HMS_WEST : x--; /* x-Koordinate des nächsten Feldes ist um */ break; /* eins kleiner, als die des aktuellen Feldes */ case HMS_NORTH : y++; /* y-Koordinate des nächsten Feldes ist um */ break; /* eins größer, als die des aktuellen Feldes */ case HMS_EAST : x++; /* x-Koordinate des nächsten Feldes ist um */ /* eins größer, als die des aktuellen Feldes */ } return feld[HMS_MITTEX+x][HMS_MITTEY+y]; /* Markierung des nächsten Feldes wird zurückgegeben */ } /* Funktion zum testen, ob das nächste Feld betretbar ist oder nicht */ char betretbar(HAMSTER *hms) { int x,y; /* Variablen für x,y-Koordinaten */ hms_pos(hms,&x,&y); /* Positionskoordinaten bestimmen */ if (hms_look(hms)==HMS_WALL) return 0; /* nächstes Feld nicht betretbar, wenn eine Mauer im Weg ist ==> 0 */ /* nächstes Feld darf betreten werden, wenn es vorher noch nie betreten wurde*/ return (feld_vorn(hms)==0); } /* rekursive Funktion zum Entscheiden, wie der Hamster weitergehen soll */ unsigned char bewege_hms(HAMSTER *hms, unsigned char entf) { unsigned char h, ausgaenge, zurueck, nochmal; /* h : Zählvariablen ausgaenge : Anzahl der vom aktuellen Feld aus betretbaren Nachbarfelder zurueck : Richtung, aus der der Hamster das aktuelle Feld betreten hat nochmal : 1.) Rückgabewert der nächsttieferen 'bewege_hms'-Funktion, der angibt, ob der Hamster noch Mais zurücklassen mußte, weil sein Maul voll war (nochmal=1) ODER ob er den gesamten Mais einsammeln konnte (nochmal=0) 2.) Rückgabewert der aktuellen 'bewege_hms'-Funktion, der angibt, ob das aktuelle Feld nochmals betreten werden muß, weil der Hamster noch Mais zurücklassen mußte (nochmal!=0) ODER ob er den gesamten Mais einsammeln konnte (nochmal=0)*/ int x, y; /* Variablen für x,y-Koordinaten */ ausgaenge=0; /* Anzahl der betretbaren Nachbarfelder ist Null */ hms_pos(hms, &x, &y); /* Positionskoordinaten bestimmen */ feld[HMS_MITTEX+x][HMS_MITTEY+y]=entf; /* aktuelles Feld bekommt spezifische Markierung (=Entfernung zum Ausgang) */ /* bei vorliegender Implementierung der Himmelsrichtungen ist es möglich, die entgegengesetzte Himmelsrichtung (aus der der Hamster ja kam) rechnerisch zu bestimmen: */ zurueck=(hms_dir(hms)+2)%4; /* ((aktuelle Blickrichtung)+2) mod 4 = a) (0+2) mod 4 = 2 ==> (OSTEN +2) mod 4 = WESTEN b) (1+2) mod 4 = 3 ==> (NORDEN +2) mod 4 = SÜDEN c) (2+2) mod 4 = 0 ==> (WESTEN +2) mod 4 = OSTEN d) (3+2) mod 4 = 1 ==> (SÜDEN +2) mod 4 = NORDEN */ if ((x==0) && (y==0)) zurueck=4; /* wenn der Hamster auf seinem Ausgangsfeld steht, so darf er sich keine 'echte' Rück- richtung merken, da er ja dieses Feld nicht von einem anderen Feld aus betreten hat */ if (entf==255) /* Hamster darf sich maximal 255 Felder vom Aus- gangsfeld entfernen (sonst Zahlenbereichsüber- schreitung wegen 'unsigned char') ==> falls Maximum von 255 erreicht: zurück */ { while (hms_dir(hms)!=zurueck) hms_turn(hms, HMS_POS); /* Hamster dreht sich, bis er in die Richtung schaut, aus der der gekommen ist*/ nochmal=hms_corn(hms)-hms_take(hms,HMS_MAXLOAD); /* Hamster zählt, wieviel Mais auf seinem Feld liegt (hms_corn(hms)) und nimmt soviel auf, wie er kann (hms_take(hms,HMS_MAXLOAD)) wegen vorliegender Implementation der Funktionen 'hms_corn' und 'hms_take' ist es dem Hamster möglich, zu berechnen, ob er dieses Feld noch einmal be- treten muß (um noch vorhandenen Mais einzusammeln) oder ob er es 'vergessen' kann: Wenn er das Feld abräumt ist die Differenz 'nochmal' Null; wenn er nicht mehr alles in sein Maul bekommt, ist 'nochmal' größer als Null (aber <255 !) */ feld[HMS_MITTEX+x][HMS_MITTEY+y]=0; /* weil der Hamster 'gezwungen' wurde, zurückzugehen, darf er sich dieses Feld noch freihalten, falls er von einem anderen Feld aus günstiger auf dieses Feld kommt */ h=hms_move(hms); /* Hamster geht auf das Feld, von dem aus er das aktuelle Feld betreten hat */ if (nochmal) return 1; /* wenn er noch Mais zurückgelassen hat, so merkt er sich das */ return 0; /* wenn er das Feld abgeräumt hat, so braucht er es nicht noch einmal betreten */ } for (h=1; h<=4; h++) /* Schleife 4-mal ausführen (wegen 4 Himmelsrichtungen) */ { if ((betretbar(hms)) && (hms_dir(hms)!=zurueck)) /* wenn der Hamster nicht in eine Sackgasse und auch nicht in Richtung des Feldes, von dem er gekommen ist, blickt : */ { ausgaenge++; /* Hamster zählt die möglichen Alternativen, vom aktuellen Feld aus weiterzugehen */ } hms_turn(hms, HMS_POS); /* am Ende eines jeden Schleifendurchlaufes dreht er sich um 90 Grad */ } if (ausgaenge>1) /* wenn mehr als eine Möglichkeit gibt, das aktuelle Feld zu verlassen */ { for (h=1; h<=ausgaenge; h++) /* Hamster prüft alle Möglichkeiten */ { nochmal=0; /* 'nochmal' dient hier nur als Hilfsvariable! dient dazu, daß der Hamster sich in ungünstigen Fällen nicht endlos im Kreis bewegt */ while (((betretbar(hms)==0) || (hms_dir(hms)==zurueck)) && (4>nochmal++)) hms_turn(hms, HMS_POS); /* Hamster dreht sich solange das Feld vor ihm eine Sackgasse ist oder das Feld ist, von dem aus er das aktuelle Feld betreten hat wegen '&& (4>nochmal)' dreht sich der Hamster aber maximal um 360 Grad */ if (nochmal<5) /* Hamster hat einen möglichen Weg gefunden, wenn er sich um weniger als 360 Grad gedreht hat */ do /* Schleife dann wird mindestens einmal ausgeführt */ { nochmal=hms_move(hms); /* Hamster geht auf das nächste Feld */ nochmal=bewege_hms(hms,entf+1); /* erneuter Funktionsaufruf, wobei festge- legt wird, daß das nächste Feld eine um eins größere Entfernung zum Ausgangsfeld hat; der Rückgabewert wird an 'nochmal' übergeben */ /* alles Folgende innerhalb der 'if (ausgaenge>1)'-Schleife wird erst nach der Rückkehr des Hamsters auf das Feld(x,y) ausgeführt ! */ if (hms_load(hms)>hms_drop(hms,hms_load(hms))) /* falls die Anzahl der Maiskörner, die der Hamster im Maul hat, größer ist, als die Anzahl der Maiskörner, die er ablegen kann, so kann er folgern, daß das Feld schon zu voll ist, um noch Mais abzulegen; er muß dann seinen Mais zum nächsten Knotenfeld bringen */ { nochmal=hms_take(hms,HMS_MAXLOAD); /* Hamster füllt sich sein Maul voll */ nochmal=1; /* merkt sich, daß er dieses Feld noch- mals betreten muß */ while (hms_dir(hms)!=zurueck) hms_turn(hms, HMS_POS); /* Hamster dreht sich, bis er in die Richtung schaut, aus der der gekommen ist*/ feld[HMS_MITTEX+x][HMS_MITTEY+y]=0; /* markiert aktuelles Feld als 'noch betretbar' */ h=hms_move(hms); /* Hamster geht auf das Feld, von dem aus er das aktuelle Feld betreten hat */ return nochmal; /* Variable 'nochmal'(=1) wird zurückgeliefert */ } if (nochmal) /* falls der Hamster noch einmal zurück muß, um */ { /* noch verbliebenen Mais einzusammeln, so dreht */ hms_turn(hms, HMS_POS); /* er sich um 180 Grad und blickt somit in die */ hms_turn(hms, HMS_POS); /* Richtung, von der aus er auf das aktuelle Feld*/ } /* zurückkam */ } while (nochmal); /* das Ganze wiederholt er so lange, wie noch Mais über den aktuellen Ausgang zu bergen ist */ } nochmal=(hms_corn(hms)-hms_take(hms,HMS_MAXLOAD)); /* Hamster zählt, wieviel Mais auf seinem Feld liegt (hms_corn(hms)) und nimmt soviel auf, wie er kann (hms_take(hms,HMS_MAXLOAD)) wegen vorliegender Implementation der Funktionen 'hms_corn' und 'hms_take' ist es dem Hamster möglich, zu berechnen, ob er dieses Feld noch einmal be- treten muß (um noch vorhandenen Mais einzusammeln) oder ob er es 'vergessen' kann: Wenn er das Feld abräumt ist die Differenz 'nochmal' Null; wenn er nicht mehr alles in sein Maul bekommt, ist 'nochmal' größer als Null (aber <255 !) */ if (nochmal) feld[HMS_MITTEX+x][HMS_MITTEY+y]=0; /* wenn das Feld nochmal betreten werden muß, so markiert es das Programm als 'betretbar'*/ else feld[HMS_MITTEX+x][HMS_MITTEY+y]=255; /* ansonsten markiert es das Feld als nicht mehr betretbar */ } else if (ausgaenge==1) /* wenn es nur einen Ausgang aus dem aktuellen Feld gibt (außer Rückweg)... */ { while ((betretbar(hms)==0) || (hms_dir(hms)==zurueck)) hms_turn(hms, HMS_POS); /* Hamster dreht sich, bis er den gesichteten Ausgang gefunden hat */ nochmal=hms_move(hms); /* Hamster geht hinein */ nochmal=bewege_hms(hms,entf+1); /* rekursive Funktion wird erneut aufgerufen */ if ((nochmal) || (hms_corn(hms)-hms_take(hms,HMS_MAXLOAD))) /* wenn der Hamster noch einmal diesen Ausgang betreten muß, weil dort noch Mais liegt, so muß er auch das aktuelle Feld als 'betretbar' markieren, damit der noch vorhandene Mais eingesammelt werden kann. Ausserdem muß er das aktuelle Feld auch als 'betretbar' markieren, wenn er nicht den gesamten Mais aufnehmen konnte. */ { feld[HMS_MITTEX+x][HMS_MITTEY+y]=0; /* Feld wird als 'betretbar' markiert */ nochmal=1; /* Feld muß noch einmal betreten werden --> nochmal=1 */ } else feld[HMS_MITTEX+x][HMS_MITTEY+y]=255;/* ansonsten wird das Feld als nicht mehr betretbar markiert */ } else { nochmal=hms_corn(hms)-hms_take(hms,HMS_MAXLOAD); /* Hamster zählt, wieviel Mais auf seinem Feld liegt (hms_corn(hms)) und nimmt soviel auf, wie er kann (hms_take(hms,HMS_MAXLOAD)) wegen vorliegender Implementation der Funktionen 'hms_corn' und 'hms_take' ist es dem Hamster möglich, zu berechnen, ob er dieses Feld noch einmal be- treten muß (um noch vorhandenen Mais einzusammeln) oder ob er es 'vergessen' kann: Wenn er das Feld abräumt ist die Differenz 'nochmal' Null; wenn er nicht mehr alles in sein Maul bekommt, ist 'nochmal' größer als Null (aber <255 !) */ if (nochmal) feld[HMS_MITTEX+x][HMS_MITTEY+y]=0; /* wenn das Feld nochmal betreten werden muß, so markiert es das Programm als 'betretbar'*/ else feld[HMS_MITTEX+x][HMS_MITTEY+y]=255; /* ansonsten wird das Feld als nicht mehr betretbar markiert */ } while ((hms_dir(hms)!=zurueck) && (zurueck!=4)) hms_turn(hms, HMS_POS); /* Hamster dreht sich solange, bis er in die Richtung schaut, aus der er das aktuelle Feld betreten hat. Wenn (zurueck==4), der Hamster also auf dem Ausgangsfeld steht, dann braucht der Hamster sich nicht drehen */ if ((x) || (y)) h=hms_move(hms); /* wenn er nicht auf dem Ausgangsfeld steht, wird er einen Schritt vorwärts bewegt */ return nochmal; /* Rückgabewert (0 oder 1) wird zurückgegeben */ } /* Funktion, die die Variablen initialisiert und dann die rekursive Funktion bewege_hms aufruft */ void hms_ctrl (HAMSTER *hms) { int x, y; /* Koordinaten einer Matrix */ for (x=HMS_MITTEX*2; x>=0; x--) /* die Zellen aller Zeilen... */ for (y=HMS_MITTEY*2; y>=0; y--) /* ...und Spalten der Matrix... */ { feld[x][y]=0; /* ...werden mit 0 initialisiert. --> alle Felder sind am Anfang betretbar */ } while (bewege_hms(hms,1)) hms_drop(hms,hms_load(hms)); /* solange sich noch Mais im Labyrinth be- findet wird es durch- sucht und das Maul über dem Ausgangsfeld entleert */ hms_drop(hms,hms_load(hms)); /* zum Schluß entleert der Hamster sein Maul... */ } /* und ist fertig */