/* ThH & Maus Heinemann, Thomas MatNr.: 154269 eMail: theinema@cs.uni-magdeburg.de 14.06.1998 */ #include #include #include "hamster.h" /*** Struktur der Informationsspeicherung eines Feldes *************************************/ typedef struct Feld{unsigned char Koerner, /* Anzahl der Koerner auf einem Feld des Layrinths */ Info; /* Info -> Bit 0 ( 1) = ob Wand im Osten Bit 1 ( 2) = ob Wand im Norden Bit 2 ( 4) = ob Wand im Westen Bit 3 ( 8) = ob Wand im Sueden Bit 4 (16) = Feld erkundet Bit 5 (32) = Feld gehoert zum Labyrinth */ }Feld; /*** Struktur zur Kommunikation zwischen den Funktionen ************************************************/ typedef struct Kopf{Feld Labyrinth[127][127]; /* Informationen ueber das Labyrinth */ int X, /* momentane Position Ost-West-Richtung */ Y, /* momentane Position Nord-Sued-Richtung */ Punkte; /* Punkte, die auf momentanem Feld erreicht werden koennen */ unsigned char Abbruch, /* Abbruchinformation (!=0 -> aufhoeren mit Sammeln) */ Richtung, /* Richtung, in die der momentane Weg gegangen werden soll */ Maus; /* !=0 -> Hamster ist auf Weg zum Nest und konnte keinen weiteren Weg finden; bei jedem Schritt soll nach guenstigem Weg gesucht werden */ HAMSTER *hms; /* Hamster */ struct Weg *Wege, /* Anfang der Liste aller gespeicherten Wege durch das Labyrinth */ *WegCursor; /* momentaner Weg */ struct Wegfeld *Ziel; /* Zielfeld im momentanen Weg */ }Kopf; /*** Element der Liste aller Wege **************************************************/ typedef struct Weg{struct Weg *next; /* Zeiger auf naechstem Weg */ struct Wegfeld *Cursor; /* Zeiger auf momentanes Feld des Weges */ }Weg; /*** Element eines Weges (Feld eines Weges) **************************************/ typedef struct Wegfeld{struct Wegfeld *next, /* Zeiger auf naechstes Wegelement */ *prev; /* Zeiger auf vorheriges Wegelement */ int X, /* Position des Feldes (Ost-West) */ Y; /* Position des Feldes (Nord-Sued) */ }Wegfeld; /*** Ermitteln der Position des Hamsters im Labyrinth ***/ Kopf Fkt_Position(Kopf Hamster) {/* Position im Bereich -63 bis 63 ermitteln */ hms_pos(Hamster.hms, &Hamster.X, &Hamster.Y); /* da Labyrinthindizes von 0 bis 127 -> um 63 erhoehen */ Hamster.X+=63; Hamster.Y+=63; return(Hamster); } /*** Sammeln der Feldinformationen ************************************************/ Kopf Fkt_FelddatenSammeln(Kopf Hamster) {/* Position im Feld ermitteln (zum Speichern veraenderte Werte) */ Hamster=Fkt_Position(Hamster); /* Wenn das momentane Feld noch nicht erkundet wurde, so wird dies getan */ if(!(Hamster.Labyrinth[Hamster.X][Hamster.Y].Info&16)) {/* Richtung Osten */ while(hms_dir(Hamster.hms)!=HMS_EAST) {hms_turn(Hamster.hms, HMS_POS); }; switch(hms_look(Hamster.hms)) {case HMS_WALL :Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=1; break; case HMS_EMPTY:Hamster.Labyrinth[Hamster.X+1][Hamster.Y].Koerner=0; Hamster.Labyrinth[Hamster.X+1][Hamster.Y].Info|=32; break; case HMS_CORN :if(Hamster.Labyrinth[Hamster.X+1][Hamster.Y].Koerner==0) Hamster.Labyrinth[Hamster.X+1][Hamster.Y].Koerner=1; Hamster.Labyrinth[Hamster.X+1][Hamster.Y].Info|=32; break; default :fprintf(stderr,"hms_look gab unbekannten Wert zurueck\n"); break; }; /* Richtung Norden */ hms_turn(Hamster.hms, HMS_POS); switch(hms_look(Hamster.hms)) {case HMS_WALL :Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=2; break; case HMS_EMPTY:Hamster.Labyrinth[Hamster.X][Hamster.Y+1].Koerner=0; Hamster.Labyrinth[Hamster.X][Hamster.Y+1].Info|=32; break; case HMS_CORN :if(Hamster.Labyrinth[Hamster.X][Hamster.Y+1].Koerner==0) Hamster.Labyrinth[Hamster.X][Hamster.Y+1].Koerner=1; Hamster.Labyrinth[Hamster.X][Hamster.Y+1].Info|=32; break; default :fprintf(stderr,"hms_look gab unbekannten Wert zurueck\n"); break; }; /* Richtung Westen */ hms_turn(Hamster.hms, HMS_POS); switch(hms_look(Hamster.hms)) {case HMS_WALL :Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=4; break; case HMS_EMPTY:Hamster.Labyrinth[Hamster.X-1][Hamster.Y].Koerner=0; Hamster.Labyrinth[Hamster.X-1][Hamster.Y].Info|=32; break; case HMS_CORN :if(Hamster.Labyrinth[Hamster.X-1][Hamster.Y].Koerner==0) Hamster.Labyrinth[Hamster.X-1][Hamster.Y].Koerner=1; Hamster.Labyrinth[Hamster.X-1][Hamster.Y].Info|=32; break; default :fprintf(stderr,"hms_look gab unbekannten Wert zurueck\n"); break; }; /* Richtung Sueden */ hms_turn(Hamster.hms, HMS_POS); switch(hms_look(Hamster.hms)) {case HMS_WALL :Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=8; break; case HMS_EMPTY:Hamster.Labyrinth[Hamster.X][Hamster.Y-1].Koerner=0; Hamster.Labyrinth[Hamster.X][Hamster.Y-1].Info|=32; break; case HMS_CORN :if(Hamster.Labyrinth[Hamster.X][Hamster.Y-1].Koerner==0) Hamster.Labyrinth[Hamster.X][Hamster.Y-1].Koerner=1; Hamster.Labyrinth[Hamster.X][Hamster.Y-1].Info|=32; break; default :fprintf(stderr,"hms_look gab unbekannten Wert zurueck\n"); break; }; /* momentanes Feld als erkundet markieren */ Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=16; }; /* Folgendes, auch wenn Feld erkundet ist */ /* Koerneranzahl aktualisieren */ Hamster.Labyrinth[Hamster.X][Hamster.Y].Koerner=hms_corn(Hamster.hms); /* momentanes Feld als zum Labyrinth gehoerend makieren */ Hamster.Labyrinth[Hamster.X][Hamster.Y].Info|=32; /* Hamster zurueckgeben */ return(Hamster); } /*** einen Schritt auf momentanem Weg gehen *****************************************************/ Kopf Fkt_GezieltesGehen(Kopf Hamster) {switch(Hamster.Richtung) {case 0:/* einen Schritt vorwaerts den Weg entlang machen */ /* wenn Wegende nicht erreicht ist und Ost-West-Position des naechsten Feldes gleich Ost-West-Position des Hamsters ist -> naechstes Feld im Norden oder Sueden */ if( Hamster.WegCursor->Cursor->next!=NULL &&Hamster.WegCursor->Cursor->next->X==Hamster.X) {/* wenn Nord-Sued-Position des naechsten Feldes eins groesser ist als Nord-Sued-Position des Hamsters -> naechstes Feld im Norden */ if(Hamster.WegCursor->Cursor->next->Y==Hamster.Y+1) {/* Hamster in Richtung Norden drehen */ while(hms_dir(Hamster.hms)!=HMS_NORTH) {hms_turn(Hamster.hms, HMS_POS); }; /* einen Schritt tun */ hms_move(Hamster.hms); /* Zeiger des momentanen Feldes des Weges wird auf naechstes Feld gesetzt */ Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->next; /* Nord-Sued-Position des Hamsters um eins erhoehen */ Hamster.Y++; /* wenn Ziel erreicht oder es kein naechstes Feld gibt -> kein guenstiger Weg mehr (Hamster.Ziel=NULL) */ if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->next==NULL) Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* wenn Nord-Sued-Position des naechsten Feldes eins kleiner ist als Nord-Sued-Position des Hamsters -> naechstes Feld im Sueden */ if(Hamster.WegCursor->Cursor->next->Y==Hamster.Y-1) {/* Hamster in Richtung Sueden drehen */ while(hms_dir(Hamster.hms)!=HMS_SOUTH) {hms_turn(Hamster.hms, HMS_POS); }; /* einen Schritt tun */ hms_move(Hamster.hms); /* Zeiger des momentanen Feldes des Weges wird auf naechstes Feld gesetzt */ Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->next; /* Nord-Sued-Position des Hamsters um eins verringern */ Hamster.Y--; /* wenn Ziel erreicht oder es kein naechstes Feld gibt -> kein guenstiger Weg mehr (Hamster.Ziel=NULL) */ if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->next==NULL) Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* hat Nord-Sued-Position andere Werte -> Weg enthaelt Fehler kein guenstiger Weg mehr */ fprintf(stderr,"Fehler im Weg XY\n"); Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* wenn Nord-Sued-Position des naechsten Feldes gleich die des Hamsters ist & Ost-West-Position des naechsten Feldes eins groesser ist als die des Hamsters & Ende des Weges noch nicht erreicht ist -> naechstes Feld im Osten */ if( Hamster.WegCursor->Cursor->next!=NULL &&Hamster.WegCursor->Cursor->next->X==Hamster.X+1) {if(Hamster.WegCursor->Cursor->next->Y==Hamster.Y) {/* Hamster in Richtung Osten drehen */ while(hms_dir(Hamster.hms)!=HMS_EAST) {hms_turn(Hamster.hms, HMS_POS); }; /* einen Schritt tun */ hms_move(Hamster.hms); /* Zeiger des momentanen Feldes des Weges wird auf naechstes Feld gesetzt */ Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->next; /* Ost-West-Position des Hamsters um eins erhoehen */ Hamster.X++; /* wenn Ziel erreicht oder es kein naechstes Feld gibt -> kein guenstiger Weg mehr (Hamster.Ziel=NULL) */ if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->next==NULL) Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* hat Nord-Sued- & Ost-West-Position andere Werte -> Weg enthaelt Fehler kein guenstiger Weg mehr */ fprintf(stderr,"Fehler im Weg XY\n"); Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* wenn Nord-Sued-Position des naechsten Feldes gleich die des Hamsters ist & Ost-West-Position des naechsten Feldes eins kleiner ist als die des Hamsters & Ende des Weges noch nicht erreicht ist -> naechstes Feld im Westen */ if( Hamster.WegCursor->Cursor->next!=NULL &&Hamster.WegCursor->Cursor->next->X==Hamster.X-1) {if(Hamster.WegCursor->Cursor->next->Y==Hamster.Y) {/* Hamster in Richtung Westen drehen */ while(hms_dir(Hamster.hms)!=HMS_WEST) {hms_turn(Hamster.hms, HMS_POS); }; /* einen Schritt tun */ hms_move(Hamster.hms); /* Zeiger des momentanen Feldes des Weges wird auf naechstes Feld gesetzt */ Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->next; /* Ost-West-Position des Hamsters um eins verringern */ Hamster.X--; /* wenn Ziel erreicht oder es kein naechstes Feld gibt -> kein guenstiger Weg mehr (Hamster.Ziel=NULL) */ if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->next==NULL) Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* hat Nord-Sued- & Ost-West-Position andere Werte -> Weg enthaelt Fehler kein guenstiger Weg mehr */ fprintf(stderr,"Fehler im Weg XY\n"); Hamster.Ziel=NULL; /* Fkt. kann beendet werden */ return(Hamster); }; /* kam keine der anderen Moeglichkeiten in Frage -> im momentanen Weg muss Fehler sein */ fprintf(stderr,"Fehler im Weg\n"); /* dieser Weg ist dann kein guenstiger Weg */ Hamster.Ziel=NULL; break; case 1:/* einen Schritt rueckwaerts den Weg entlang machen */ /* (Verfahren analog erster Fall (0) -> erweiterte Kommentare weggelassen) */ if( Hamster.WegCursor->Cursor->prev!=NULL &&Hamster.WegCursor->Cursor->prev->X==Hamster.X) {/* Norden oder Sueden */ if(Hamster.WegCursor->Cursor->prev->Y==Hamster.Y+1) {/* Norden */ while(hms_dir(Hamster.hms)!=HMS_NORTH) {hms_turn(Hamster.hms, HMS_POS); }; hms_move(Hamster.hms); Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->prev; Hamster.Y++; if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->prev==NULL) Hamster.Ziel=NULL; return(Hamster); }; if(Hamster.WegCursor->Cursor->prev->Y==Hamster.Y-1) {/* Sueden */ while(hms_dir(Hamster.hms)!=HMS_SOUTH) {hms_turn(Hamster.hms, HMS_POS); }; hms_move(Hamster.hms); Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->prev; Hamster.Y--; if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->prev==NULL) Hamster.Ziel=NULL; return(Hamster); }; fprintf(stderr,"Fehler im Weg YX\n"); Hamster.Ziel=NULL; return(Hamster); }; if( Hamster.WegCursor->Cursor->prev!=NULL &&Hamster.WegCursor->Cursor->prev->X==Hamster.X+1) {if(Hamster.WegCursor->Cursor->prev->Y==Hamster.Y) {/* Osten */ while(hms_dir(Hamster.hms)!=HMS_EAST) {hms_turn(Hamster.hms, HMS_POS); }; hms_move(Hamster.hms); Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->prev; Hamster.X++; if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->prev==NULL) Hamster.Ziel=NULL; return(Hamster); }; fprintf(stderr,"Fehler im Weg YX\n"); Hamster.Ziel=NULL; return(Hamster); }; if( Hamster.WegCursor->Cursor->prev!=NULL &&Hamster.WegCursor->Cursor->prev->X==Hamster.X-1) {if(Hamster.WegCursor->Cursor->prev->Y==Hamster.Y) {/* Westen */ while(hms_dir(Hamster.hms)!=HMS_WEST) {hms_turn(Hamster.hms, HMS_POS); }; hms_move(Hamster.hms); Hamster.WegCursor->Cursor=Hamster.WegCursor->Cursor->prev; Hamster.X--; if( Hamster.Ziel==Hamster.WegCursor->Cursor ||Hamster.WegCursor->Cursor->prev==NULL) Hamster.Ziel=NULL; return(Hamster); }; fprintf(stderr,"Fehler im Weg YX\n"); Hamster.Ziel=NULL; return(Hamster); }; fprintf(stderr,"Fehler im Weg\n"); Hamster.Ziel=NULL; break; default:/* falscher Wert fuer die Richtung nur 0 (vorwaerts) & 1 (rueckwaerts) */ fprintf(stderr,"Falscher Wert in Hamster.Richtung\n"); break; }; return(Hamster); } /*** Speichern der Wege im Labyrinth *******************************************************/ Kopf Fkt_Wegdaten(Kopf Hamster) {Weg *Dummy; Wegfeld *Anfang, *Ende, *Dummy2, *Dummy3, *Start; unsigned char Vervielfachen, Osten, Norden, Westen, Sueden; /* 1. existiert kein Weg -> Weg mit momemtanen Feld einfuegen und WegCursor darauf setzen */ if(Hamster.Wege==NULL) {Hamster.Wege=(Weg *)malloc(sizeof(Weg)); Hamster.Wege->next=NULL; Hamster.Wege->Cursor=(Wegfeld *)malloc(sizeof(Wegfeld)); Hamster.Wege->Cursor->prev=NULL; Hamster.Wege->Cursor->next=NULL; Hamster.Wege->Cursor->X=Hamster.X; Hamster.Wege->Cursor->Y=Hamster.Y; Hamster.WegCursor=Hamster.Wege; }; /* 2. Wege erweitern, wenn das momentane Feld am Anfang oder Ende des Weges ist */ if( Hamster.WegCursor->Cursor->prev==NULL ||Hamster.WegCursor->Cursor->next==NULL) {/* 2.1 testen, ob Nachbarfelder im Weg vorhanden sind, und Anfang und Ende festlegen */ Osten=0; Norden=0; Westen=0; Sueden=0; for(Dummy2=Hamster.WegCursor->Cursor; Dummy2->prev!=NULL; Dummy2=Dummy2->prev); Anfang=Dummy2; while(Dummy2!=NULL) {if( Dummy2->X==Hamster.X+1 &&Dummy2->Y==Hamster.Y) Osten=1; if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y+1) Norden=1; if( Dummy2->X==Hamster.X-1 &&Dummy2->Y==Hamster.Y) Westen=1; if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y-1) Sueden=1; Ende=Dummy2; Dummy2=Dummy2->next; }; /* 2.2 Wege erweitern und gegebenenfalls vervielfachen */ Vervielfachen=0; if( Osten==0 &&!(Hamster.Labyrinth[Hamster.X][Hamster.Y].Info&1)) {if(Hamster.WegCursor->Cursor->prev==NULL) {Hamster.WegCursor->Cursor->prev=(Wegfeld *)malloc(sizeof(Wegfeld)); Hamster.WegCursor->Cursor->prev->prev=NULL; Hamster.WegCursor->Cursor->prev->next=Hamster.WegCursor->Cursor; Hamster.WegCursor->Cursor->prev->X=Hamster.X+1; Hamster.WegCursor->Cursor->prev->Y=Hamster.Y; Vervielfachen++; } else{if(Hamster.WegCursor->Cursor->next==NULL) {Hamster.WegCursor->Cursor->next=(Wegfeld *)malloc(sizeof(Wegfeld)); Hamster.WegCursor->Cursor->next->next=NULL; Hamster.WegCursor->Cursor->next->prev=Hamster.WegCursor->Cursor; Hamster.WegCursor->Cursor->next->X=Hamster.X+1; Hamster.WegCursor->Cursor->next->Y=Hamster.Y; Vervielfachen++; }; }; }; if( Norden==0 &&!(Hamster.Labyrinth[Hamster.X][Hamster.Y].Info&2)) {/* gegebenenfalls den Weg vervielfachen */ if(Vervielfachen==0) {Dummy=Hamster.WegCursor; } else{/* vervielfachen des Weges */ /* neuen Weg einfuegen */ Dummy=(Weg *)malloc(sizeof(Weg)); Dummy->next=Hamster.Wege; Hamster.Wege=Dummy; Dummy->Cursor=NULL; /* Elemente des Wege kopieren */ Start=NULL; Dummy3=Anfang; do{Dummy2=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy2->prev=Dummy->Cursor; Dummy2->next=NULL; if(Dummy->Cursor!=NULL) Dummy->Cursor->next=Dummy2; Dummy2->X=Dummy3->X; Dummy2->Y=Dummy3->Y; Dummy->Cursor=Dummy2; if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) Start=Dummy2; Dummy3=Dummy3->next; }while(Dummy3!=Ende->next); /* Cursor auf momentanes Feld setzen */ Dummy->Cursor=Start; }; /* Weg erweitern */ if(Dummy->Cursor->prev==NULL) {Dummy->Cursor->prev=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->prev->prev=NULL; Dummy->Cursor->prev->next=Dummy->Cursor; Dummy->Cursor->prev->X=Hamster.X; Dummy->Cursor->prev->Y=Hamster.Y+1; Vervielfachen++; } else{if(Dummy->Cursor->next==NULL) {Dummy->Cursor->next=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->next->next=NULL; Dummy->Cursor->next->prev=Dummy->Cursor; Dummy->Cursor->next->X=Hamster.X; Dummy->Cursor->next->Y=Hamster.Y+1; Vervielfachen++; }; }; }; if( Westen==0 &&!(Hamster.Labyrinth[Hamster.X][Hamster.Y].Info&4)) {/* gegebenenfalls den Weg vervielfachen */ if(Vervielfachen==0) {Dummy=Hamster.WegCursor; } else{/* vervielfachen des Weges */ /* neuen Weg einfuegen */ Dummy=(Weg *)malloc(sizeof(Weg)); Dummy->next=Hamster.Wege; Hamster.Wege=Dummy; Dummy->Cursor=NULL; /* Elemente des Wege kopieren */ Start=NULL; Dummy3=Anfang; do{Dummy2=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy2->prev=Dummy->Cursor; Dummy2->next=NULL; if(Dummy->Cursor!=NULL) Dummy->Cursor->next=Dummy2; Dummy2->X=Dummy3->X; Dummy2->Y=Dummy3->Y; Dummy->Cursor=Dummy2; if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) Start=Dummy2; Dummy3=Dummy3->next; }while(Dummy3!=Ende->next); /* Cursor auf momentanes Feld setzen */ Dummy->Cursor=Start; }; /* Weg erweitern */ if(Dummy->Cursor->prev==NULL) {Dummy->Cursor->prev=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->prev->prev=NULL; Dummy->Cursor->prev->next=Dummy->Cursor; Dummy->Cursor->prev->X=Hamster.X-1; Dummy->Cursor->prev->Y=Hamster.Y; Vervielfachen++; } else{if(Dummy->Cursor->next==NULL) {Dummy->Cursor->next=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->next->next=NULL; Dummy->Cursor->next->prev=Dummy->Cursor; Dummy->Cursor->next->X=Hamster.X-1; Dummy->Cursor->next->Y=Hamster.Y; Vervielfachen++; }; }; }; if( Sueden==0 &&!(Hamster.Labyrinth[Hamster.X][Hamster.Y].Info&8)) {/* gegebenenfalls den Weg vervielfachen */ if(Vervielfachen==0) {Dummy=Hamster.WegCursor; } else{/* vervielfachen des Weges */ /* neuen Weg einfuegen */ Dummy=(Weg *)malloc(sizeof(Weg)); Dummy->next=Hamster.Wege; Hamster.Wege=Dummy; Dummy->Cursor=NULL; /* Elemente des Wege kopieren */ Start=NULL; Dummy3=Anfang; do{Dummy2=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy2->prev=Dummy->Cursor; Dummy2->next=NULL; if(Dummy->Cursor!=NULL) Dummy->Cursor->next=Dummy2; Dummy2->X=Dummy3->X; Dummy2->Y=Dummy3->Y; Dummy->Cursor=Dummy2; if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) Start=Dummy2; Dummy3=Dummy3->next; }while(Dummy3!=Ende->next); /* Cursor auf momentanes Feld setzen */ Dummy->Cursor=Start; }; /* Weg erweitern */ if(Dummy->Cursor->prev==NULL) {Dummy->Cursor->prev=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->prev->prev=NULL; Dummy->Cursor->prev->next=Dummy->Cursor; Dummy->Cursor->prev->X=Hamster.X; Dummy->Cursor->prev->Y=Hamster.Y-1; Vervielfachen++; } else{if(Dummy->Cursor->next==NULL) {Dummy->Cursor->next=(Wegfeld *)malloc(sizeof(Wegfeld)); Dummy->Cursor->next->next=NULL; Dummy->Cursor->next->prev=Dummy->Cursor; Dummy->Cursor->next->X=Hamster.X; Dummy->Cursor->next->Y=Hamster.Y-1; Vervielfachen++; }; }; }; }; return(Hamster); } /*** Suchen eines guenstigen Weges *******************************************************************/ Kopf Fkt_GuenstigenWegSuchen(Kopf Hamster) {Weg *Dummy; Wegfeld *Dummy2, *Start, *Ziel, *Anfang, *Ende; unsigned char Richtung, Koerner=hms_load(Hamster.hms); int Punkte; /* kann der Hamster keine Koerner mehr aufnehmen, dann soll er zum Nest laufen -> Weg zum Nest suchen */ if(hms_load(Hamster.hms)==HMS_MAXLOAD) {/* alle Wege mit dem momentanen Feld und dem Nest durchlaufen und Kuerzesten merken */ Hamster.Punkte=-32768; for(Dummy=Hamster.Wege; Dummy!=NULL; Dummy=Dummy->next) {Start=NULL; Ziel=NULL; Richtung=0; Punkte=0; /* zum Anfang des Weges */ for(Dummy2=Dummy->Cursor; Dummy2->prev!=NULL; Dummy2=Dummy2->prev); while(Dummy2!=NULL) {/* momentanes Feld suchen */ if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) {Start=Dummy2; }; /* Nest suchen */ if( Dummy2->X==63 &&Dummy2->Y==63) {Ziel=Dummy2; /* ist momentanes Feld noch nicht gefunden -> Wegrichtung ist rueckwaerts */ if(Start==NULL) Richtung=1; }; Dummy2=Dummy2->next; }; /* existieren die beiden Felder im Weg, koennen Punkte berechnet werden */ if( Start!=NULL &&Ziel!=NULL) {/* Punkte berechnen und merken */ for(Dummy2=Start; Dummy2!=Ziel; Dummy2=Richtung==0?Dummy2->next:Dummy2->prev, Punkte--); /* Weg mit maximaler Punktezahl wird gemerkt */ if(Hamster.PunkteCursor=Start; Hamster.Ziel=Ziel; Hamster.Richtung=Richtung; Hamster.Maus=0; }; }; }; } /* kann der Hamster noch Koerner aufnehmen, dann soll er den guenstigsten Weg zum naechsten Maiskornhaufen gehen -> Weg suchen, bei dem die meisten Punkte gemacht werden koennen */ else{/* jeden Weg, der das momentane Feld enthaelt, durchlaufen mit Punkteberechnung und bestes Ergebnis merken */ /* hierbei duerfen keine Minuspunkte gemacht werden -> Minimumpunktegrenze gleich 0 */ Hamster.Punkte=0; for(Dummy=Hamster.Wege; Dummy!=NULL; Dummy=Dummy->next) {/* Anfang des Weges suchen */ for(Anfang=Dummy->Cursor; Anfang->prev!=NULL; Anfang=Anfang->prev); /* Ende des Weges suchen */ for(Ende=Dummy->Cursor; Ende->next!=NULL; Ende=Ende->next); /* momentanes Feld suchen */ for(Dummy->Cursor=Anfang; Dummy->Cursor!=Ende; Dummy->Cursor=Dummy->Cursor->next) {if( Dummy->Cursor->X==Hamster.X &&Dummy->Cursor->Y==Hamster.Y) break; }; /* ist momentanes Feld in diesem Weg -> schrittweise Punkteberechnung in beide Richtung */ if( Dummy->Cursor->X==Hamster.X &&Dummy->Cursor->Y==Hamster.Y) {Punkte=0; Koerner=hms_corn(Hamster.hms); for(Dummy2=Dummy->Cursor; Dummy2!=NULL; Dummy2=Dummy2->prev, Punkte--) {/* 10 Punkte pro abgelegtem Korn im Nest */ if( Dummy2->X==63 &&Dummy2->Y==63) {Punkte+=10*Koerner; Koerner=0; } /* 10 Punkte pro aufgehobenem Korn */ else{if(HMS_MAXLOAD-Koerner>=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner) {Punkte+=10*Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; Koerner+=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; } else{Punkte+=10*(HMS_MAXLOAD-Koerner); Koerner=HMS_MAXLOAD; }; }; if(Hamster.PunkteCursor; Dummy2!=NULL; Dummy2=Dummy2->next, Punkte--) {/* 10 Punkte pro abgelegtem Korn im Nest */ if( Dummy2->X==63 &&Dummy2->Y==63) {Punkte+=10*Koerner; Koerner=0; } /* 10 Punkte pro aufgehobenem Korn */ else{if(HMS_MAXLOAD-Koerner>=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner) {Punkte+=10*Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; Koerner+=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; } else{Punkte+=10*(HMS_MAXLOAD-Koerner); Koerner=HMS_MAXLOAD; }; }; if(Hamster.Punkte Weg zu unerkundetem Feld suchen, das aber nicht zu weit weg ist */ if( Hamster.Ziel==NULL ||Hamster.Maus!=0) {/* Schrittbegrenzung 120 */ Hamster.Punkte=-120; for(Dummy=Hamster.Wege; Dummy!=NULL; Dummy=Dummy->next) {Start=NULL; Anfang=NULL; Ende=NULL; for(Dummy2=Dummy->Cursor; Dummy2!=NULL; Dummy2=Dummy2->prev) {/* momentanes Feld suchen */ if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) Start=Dummy2; /* unerkundetes Feld suchen, das aber zum Labyrinth gehoert */ if( Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Info&32 &&!(Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Info&16)) Anfang=Dummy2; }; for(Dummy2=Dummy->Cursor; Dummy2!=NULL; Dummy2=Dummy2->next) {/* momentanes Feld suchen */ if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) Start=Dummy2; /* unerkundetes Feld suchen, das aber zum Labyrinth gehoert */ if( Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Info&32 &&!(Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Info&16)) Ende=Dummy2; }; /* momentanes Feld ist im Weg -> Punkteberechnung */ if(Start!=NULL) {if(Anfang!=NULL) {/* Punkteberechnung in Richtung Anfang */ Punkte=0; Koerner=hms_corn(Hamster.hms); for(Dummy2=Start; Dummy2!=Anfang->prev; Dummy2=Dummy2->prev) {if( Dummy2->X==63 &&Dummy2->Y==63) {Punkte+=10*Koerner; Koerner=0; } else{if(HMS_MAXLOAD-Koerner>=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner) {Punkte+=10*Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; Koerner+=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; } else{Punkte+=10*(HMS_MAXLOAD-Koerner); Koerner=HMS_MAXLOAD; }; }; Punkte--; }; if(Hamster.PunkteCursor=Start; Hamster.Ziel=Anfang; Hamster.Richtung=1; Hamster.Maus=0; }; }; if(Ende!=NULL) {/* Punkteberechnung in Richtung Ende */ Punkte=0; Koerner=hms_corn(Hamster.hms); for(Dummy2=Start; Dummy2!=Ende->next; Dummy2=Dummy2->next) {if( Dummy2->X==63 &&Dummy2->Y==63) {Punkte+=10*Koerner; Koerner=0; } else{if(HMS_MAXLOAD-Koerner>=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner) {Punkte+=10*Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; Koerner+=Hamster.Labyrinth[Dummy2->X][Dummy2->Y].Koerner; } else{Punkte+=10*(HMS_MAXLOAD-Koerner); Koerner=HMS_MAXLOAD; }; }; Punkte--; }; if(Hamster.PunkteCursor=Start; Hamster.Ziel=Ende; Hamster.Richtung=0; Hamster.Maus=0; }; }; }; }; }; /* ist kein Weg aufzufinden, soll Hamster zum Nest zuruecklaufen */ if(Hamster.Ziel==NULL) {/* ist Hamster im Nest, soll er keinen Weg zum Nest suchen */ if( Hamster.X==63 &&Hamster.Y==63) return(Hamster); /* alle Wege mit dem momentanen Feld und dem Nest durchlaufen und Kuerzesten merken (analog erstes zum Nest -> keinen Kommentare) */ Hamster.Punkte=-32768; for(Dummy=Hamster.Wege; Dummy!=NULL; Dummy=Dummy->next) {Start=NULL; Ziel=NULL; Richtung=0; Punkte=0; for(Dummy2=Dummy->Cursor; Dummy2->prev!=NULL; Dummy2=Dummy2->prev); while(Dummy2!=NULL) {if( Dummy2->X==Hamster.X &&Dummy2->Y==Hamster.Y) {Start=Dummy2; }; if( Dummy2->X==63 &&Dummy2->Y==63) {Ziel=Dummy2; if(Start==NULL) Richtung=1; }; Dummy2=Dummy2->next; }; if( Start!=NULL &&Ziel!=NULL) {/* Punkte berechnen und merken */ for(Dummy2=Start; Dummy2!=Ziel; Dummy2=Richtung==0?Dummy2->next:Dummy2->prev, Punkte--); if(Hamster.PunkteCursor=Start; Hamster.Ziel=Ziel; Hamster.Richtung=Richtung; /* 'Maus' besagt, daß Hamster auf Weg zum Nest, weil kein guenstiger Weg auffindbar war -> solange 'Maus' != 0 -> immer wieder nach neuen Wegen suchen (nach einem Schritt) */ Hamster.Maus=1; }; }; }; }; return(Hamster); } /*** Grundstruktur der Strategie *****************/ Kopf Fkt_Strategien(Kopf Hamster) {/* guenstigen Weg suchen, falls keiner vorliegt */ if( Hamster.Ziel==NULL ||Hamster.Maus!=0) Hamster=Fkt_GuenstigenWegSuchen(Hamster); /* Wird kein Weg mehr gefunden -> Abbruch */ if(Hamster.Ziel==NULL) {Hamster.Abbruch=1; return(Hamster); }; /* einen Schritt gehen */ Hamster=Fkt_GezieltesGehen(Hamster); return(Hamster); } /*** Hauptfkt. *******************************************************************/ void hms_ctrl(HAMSTER *hms) {Kopf Hamster; /* Hamster initialisieren */ Hamster.hms=hms; Hamster.Abbruch=0; Hamster.Wege=NULL; Hamster.WegCursor=NULL; Hamster.Ziel=NULL; Hamster.Richtung=0; Hamster.Maus=0; /* Labyrinth initialisieren */ for(Hamster.X=0; Hamster.X<127; Hamster.X++) {for(Hamster.Y=0; Hamster.Y<127; Hamster.Y++) {Hamster.Labyrinth[Hamster.X][Hamster.Y].Koerner=0; Hamster.Labyrinth[Hamster.X][Hamster.Y].Info=0; }; }; while(Hamster.Abbruch==0) {/* Informationen ueber das momentane Feld sammeln */ Hamster=Fkt_FelddatenSammeln(Hamster); /* Wegverknüpfungen aktualisieren */ Hamster=Fkt_Wegdaten(Hamster); /* Ist das Feld das Nest, dann alle Koerner ablegen */ if( Hamster.X==63 &&Hamster.Y==63) {hms_drop(Hamster.hms, HMS_MAXLOAD); } /* Bei jedem anderen Feld werden soviele Koerner wie moeglich aufgenommen */ else{hms_take(Hamster.hms, HMS_MAXLOAD); }; /* Bewegungsstrategien der Prioritaet nach durchlaufen */ Hamster=Fkt_Strategien(Hamster); }; }