/*---------------------------------------------------------------------- Programm : thamster.c Autor : Thomas Kirschnick ----------------------------------------------------------------------*/ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Präprozessoranweisungen */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #include #include #include "hamster.h" /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Globale Variablen */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ char firstdir; short int distanz, strdist=0, startKr; short int optdist = 0,optik=0; /*------ Typdefinitionen für 2 dynamische Datenstrukturen a) Wegliste, in welcher während einer Optimierungsfunktion die nächsten anzusteuernden Labyrinthpunkte abgelegt werden b) Datenbaum, in welchem die neu erkundeten "Kreuzungen" dynamisch abgelegt werden*/ typedef struct datumrecord *DATAPTR; typedef struct datumrecord { short int con_to_home[2]; /* link zum Startfeld (0-> direction; 1->distanz)*/ short int links[4][2]; /* 1st index == direction 2nd index == connection , distance ( init : {0,0}) (Wand,Sackgasse) --> connection = -1 */ /* -1 Wand oder SACKGASSE sonst Koordinate der Kreuzung*/ unsigned char korn; char status; /* 1 - Kreuzung ist interessant, anliegenden Strecken nicht erkundet,noch voll 0 - Kreuzung unint., anliegende Strecken leer Kreuzungsfeld auch leer*/ } DATUM; typedef struct baum *BAUMPTR; typedef struct baum { short int koordinate; /* absolute Koordinate des Feldes */ DATAPTR datum; /* Daten für das Feld */ BAUMPTR left; /* link auf kleineren Nachfolger */ BAUMPTR right; /* link auf größeren Nachfolger */ } BAUMELEMENT; typedef struct wegliste *WEGPTR; typedef struct wegliste { WEGPTR next; short int element; } WEGELEM; WEGPTR optlsg = NULL; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Funktionen */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Funktion zum Aufsuchen eines gegebenen Listenelements bei festgelegter Koordinate, Rückgabe von NULL wenn das Element noch nicht existent ist*/ BAUMPTR find (BAUMPTR tree,int koordinate) { /* Anfang Korrektur, Christian Borgelt, 15.06.1998 */ /* Die Funktion `find' sollte einen BAUMPTR zur"uckliefern, */ /* dies geschieht jedoch nur im untersten else-Zweig. In den */ /* anderen F"allen wird zwar die Funktion `find' rekursiv aufgerufen, */ /* aber ihr Ergebnis nicht zur"uckgegeben. Auf derartige Fehler macht */ /* normalerweise der Compiler aufmerksam. In der Tat erhielt ich die */ /* Warnung: kirschnick.c: In function `find': */ /* kirschnick.c:76: warning: control reaches end of non-void function */ /* Gleiches gilt "ubrigens auch f"ur andere Funktionen. (opp_dir, etc.) */ /* Wenn dieses Programm funktioniert hat, so wohl nur deshalb, weil */ /* die R"uckgabe aus der Rekursion von einem bestimmten Compiler so */ /* "uber ein Prozessorregister geregelt wurde, da\3 zuf"allig der in */ /* den Tiefen der Rekursion gesetzte Wert an der richtigen Stelle */ /* stand. Dies w"are reiner Zufall. */ #if 0 if ( koordinate < tree->koordinate && tree->left != NULL ) find (tree->left,koordinate ); else if ( koordinate > tree->koordinate && tree->right != NULL ) find (tree->right,koordinate ); else return tree; #else if ( koordinate < tree->koordinate && tree->left != NULL ) return find (tree->left,koordinate ); else if ( koordinate > tree->koordinate && tree->right != NULL ) return find (tree->right,koordinate ); else return tree; #endif /* Ende Korrektur, Christian Borgelt, 15.06.1998 */ } /*--------------------------------------------------------------------*/ char opp_dir (int dir) { switch (dir) { case 0 : return 2;break; case 1 : return 3;break; case 2 : return 0;break; case 3 : return 1;break; } } /*--------------------------------------------------------------------*/ short int calc_koordinate(HAMSTER *hms ) /* Umwandeln der relativen Labyrinthposition in einen aboluten Wert*/ { int x,y; short int position; hms_pos( hms , &x , &y); /* Position im Labyrinth*/ position = y * HMS_MAXYEXT + x; return ( position >= 0 )?position+1:position+HMS_MAXXEXT*HMS_MAXYEXT+1; } /*--------------------------------------------------------------------*/ /* Überprüfe den Status der Kreuzungen in der Datenliste */ int status_check ( BAUMPTR satz) { int status=0; if ( satz->datum != NULL ) if ( satz->datum->status == 1 ) return 1; if ( satz->left != NULL && status == 0) status = status_check ( satz->left ); if ( satz->right != NULL && status == 0) status = status_check ( satz->right ); return status; /* return 1, wenn es Kreuzungen mit Status == 1 in der Liste gibt, sonst return 0 --> Funktionsende */ } /*--------------------------------------------------------------------*/ /* Überprüfen ob angrezende Felder evtl. bekannte Kreuzungen sind */ int check_nachbarfeld (BAUMPTR data,BAUMPTR satz,HAMSTER *hms,char hiri) { BAUMPTR tmp; short int pos,aktpos; int x,y; aktpos = calc_koordinate(hms); hms_pos( hms , &x , &y); /* Position im Labyrinth*/ switch (hiri) { case 0: x++;break; case 1: y++;break; case 2: x--;break; case 3: y--;break; } pos = y * HMS_MAXYEXT + x; /* absolute Koordinate des Nachbarfeldes (hiri)*/ if ( pos >= 0 ) pos++; else pos += HMS_MAXXEXT*HMS_MAXYEXT+1; tmp = find ( data,pos); /* finde Nachbardatensatz*/ if ( tmp->datum == NULL ) return 1; /* unbekannt --> status unverändert*/ satz->datum->links[hiri][0] = pos; satz->datum->links[hiri][1] = 1; tmp->datum->links[opp_dir ( hiri)][0] = aktpos; tmp->datum->links[opp_dir ( hiri)][1] = 1; /* Vergleiche links zum Startfeld */ if ( tmp->datum->con_to_home[1]+1 < satz->datum->con_to_home[1] ) { satz->datum->con_to_home[1] = tmp->datum->con_to_home[1]+1; satz->datum->con_to_home[0] = hiri; } if ( satz->datum->con_to_home[1]+1 < tmp->datum->con_to_home[1] ) { tmp->datum->con_to_home[1] = satz->datum->con_to_home[1]+1; tmp->datum->con_to_home[0] = opp_dir(hiri); } if (tmp->datum->links[2][0] != 0 && tmp->datum->links[3][0] != 0 && tmp->datum->links[0][0] !=0 && tmp->datum->links[1][0] != 0 && tmp->datum->korn == 0) tmp->datum->status = 0; return 0; /* in Richtung Hiri bekannte Strecke */ } /*--------------------------------------------------------------------*/ char pruefen(HAMSTER *hms, BAUMPTR list, BAUMPTR data) /* Funktion zum überprüfen des Status von Kreuzungen */ { char count=0; int status = hms_corn (hms); /* Korn im Feld */ if (list->datum->status == 1) /*Überprüfe Ausgänge auf unbekannte Streckenteile wenn Kreuzung noch int. ist*/ { for ( count=0;count<4;count++) if ( list->datum->links[count][0] == 0 ) status += check_nachbarfeld(data,list,hms,count); } return (status > 0)?1:0; /* return 1 , falls es unbekannte anliegende Strecken gibt return 0 , falls alle angrenzenden Strecken bekannt sind und auf dem Feld kein Korn mehr liegt*/ } /*--------------------------------------------------------------------*/ /* Kreuzung in Liste mit absoluter Position einfügen*/ void add_kreuzung(HAMSTER *hms,BAUMPTR tree ,short int koordinate) { BAUMPTR pos; char count,dir; DATAPTR tmp = (DATAPTR)malloc(sizeof(DATUM)); if ( !tmp ) { fprintf (stderr,"Nicht genügend Arbeitsspeicher für den tHamster !-->Abbruch"); exit; } tmp->con_to_home[0] = opp_dir (hms_dir(hms)); tmp->con_to_home[1] = distanz; tmp->korn = hms_corn (hms); /* Restliches Korn auf Feld*/ tmp->status = 1; /* Attribute auf 0 setzen */ /* Möglichen 4 Ausgänge auf Wände testen und gegebenenfalls das entsprechenden Ausgangsattribut auf -1 (Wand) setzen*/ for ( count = 0 ; count < 4; count++) { tmp->links[count][1] = 0; dir = hms_dir (hms); if (hms_look (hms) == 2 ) /*Wand == 2*/ tmp->links[dir][0] = -1; else tmp->links[dir][0] = 0; hms_turn (hms , HMS_LEFT); } pos = find (tree,koordinate); pos->datum = tmp; return; /* return erweiterte Liste*/ } /*--------------------------------------------------------------------*/ char get_typ (HAMSTER *hms) /* Bestimme Art des gegenwärtigen Labyrinthfeldes */ { char i , free_dir=0; if ( calc_koordinate(hms) == 1) /* Ausgangsfeld ? -->droppen return 0*/ { hms_drop (hms, HMS_MAXLOAD); distanz = 0; return 0; } for ( i = 0; i < 4 ; i++) /*Teste alle Richtungen auf Wände*/ { hms_turn (hms , HMS_LEFT); if ( hms_look(hms) != HMS_WALL ) free_dir++; } if (free_dir > 2) free_dir = 0; return free_dir; /* return : 0 -> Kreuzung 1 -> Sackgasse 2 -> normale Strecke */ } /*--------------------------------------------------------------------*/ WEGPTR attach_attop( short int position,WEGPTR wegliste) { WEGPTR tmp; tmp = (WEGPTR)malloc(sizeof(WEGELEM)); if ( !tmp ) { fprintf (stderr,"Nicht genügend Arbeitsspeicher für den tHamster !-->Abbruch"); exit; } tmp->element = position; tmp->next = wegliste; return tmp; } /*--------------------------------------------------------------------*/ WEGPTR delete_firstelement (WEGPTR list ) { WEGPTR pos=list->next; free (list); return (pos); } /*--------------------------------------------------------------------*/ void advance (HAMSTER *hms) /* bewegt den Hamster 1 Feld weiter */ { /* test gerade aus, links , 180° */ if ( hms_look(hms) == HMS_WALL ) hms_turn ( hms, HMS_LEFT ); if ( hms_look(hms) == HMS_WALL ) { hms_turn ( hms, HMS_RIGHT ); hms_turn ( hms, HMS_RIGHT ); } hms_move(hms); return; } /*--------------------------------------------------------------------*/ void go_back_to_start (HAMSTER *hms,BAUMPTR tree ) { BAUMPTR tmp; short int richtung,pos,aim; pos = calc_koordinate(hms); while ( pos != 1 ) { tmp = find (tree,pos); richtung = tmp->datum->con_to_home[0]; aim = tmp->datum->links[richtung][0]; while ( richtung != hms_dir (hms)) hms_turn ( hms, HMS_LEFT ); do { advance (hms); } while ( aim != calc_koordinate (hms) ); pos = calc_koordinate(hms); } return; } /*--------------------------------------------------------------------*/ void optimize (short int koordinate, int distance , BAUMPTR tree, int lastelement, short int dynamic[4097][2]) { char i; BAUMPTR tmp; if ( distance > optdist ) return ; /* Weg ist zu lang Rek.Abbruch */ if ( distance < dynamic[koordinate][0] ) /* besserer Weg zur current Kr.gefunden */ { dynamic[koordinate][0] = distance; dynamic[koordinate][1] = lastelement; } else return ; tmp = find ( tree , koordinate); if ( tmp->datum->status == 1 ) /* int.Kr gefunden */ { optik = koordinate; optdist = distance; return; } else /* Rekursionsaufrufe */ { for ( i=0 ; i<4 ; i++) { if ( tmp->datum->links[i][0] > 0 && lastelement != tmp->datum->links[i][0]) optimize ( tmp->datum->links[i][0] , distance+tmp->datum->links[i][1] , tree, koordinate , dynamic); } } return; } /*--------------------------------------------------------------------*/ void go_to_intKr(HAMSTER *hms,BAUMPTR tree,short int koordinate) { short int i,dynamic [4097][2],anfang,ende,j,compdist; WEGPTR weg=NULL; BAUMPTR tmp = find (tree , koordinate); /* finde datensatz */ optdist=120-distanz; if (optdist < 0) go_back_to_start ( hms, tree ); /* Weitergehen lohnt so nicht mehr */ if ( koordinate == 1 ) return; /* bereits auf Startfeld */ if (optdist > 64 ) optdist = 64; /* Rekursionsabbruchbedingung */ for ( i=0 ; i < 4097; i++) /* init array */ { dynamic[i][0] = 20000; /* current distance to Kr */ dynamic[i][1] = 0; /* last Kr representing 1st value */ } for ( i=0 ; i<4 ; i++) /* Rekursion optimaler Weg */ { if ( tmp->datum->links[i][0] > 0 ) /* no wall ! */ optimize ( tmp->datum->links[i][0] , tmp->datum->links[i][1] , tree, koordinate , dynamic ); } /* optimaler Weg ist in optLsg abgespeichert */ /* Gehe zur Kreuzung , dabei Speicherplatz von optLsg freigeben*/ if ( optik == 0 ) go_back_to_start ( hms,tree); else /* Gehe zur berechneten Kreuzung */ { ende = optik; anfang = dynamic[ende][1]; while ( koordinate != ende ) /* den Weg logisch zurückgehen & abspeichern */ { compdist = 0; i=0; tmp = find (tree,anfang); for ( j=0; j<4 ; j++) /* Überprüfen, ob Kreuzung auf mehreren Wegen mit link connected ist */ { if (tmp->datum->links[j][0] == ende ) { if ( tmp->datum->links[j][1] < compdist || compdist == 0) { i = j; compdist = tmp->datum->links[j][1]; } } } weg = attach_attop( i, weg); ende = anfang; anfang = dynamic[ende][1]; } while ( weg != NULL ) /*HAMSTER phys. zur Kr. bewegen */ { while ( weg->element != hms_dir (hms) ) hms_turn ( hms, HMS_LEFT ); weg = delete_firstelement ( weg ); do { advance (hms); distanz ++; } while ( get_typ (hms) != 0); } } optdist = 0; optik = 0; return; } /*--------------------------------------------------------------------*/ void setIndizes (HAMSTER *hms,BAUMPTR tree,short int pos) { BAUMPTR tmp = find (tree , pos); char i; short int dir = hms_dir (hms); tmp->datum->links[opp_dir(dir)][0] = startKr; tmp->datum->links[opp_dir(dir)][1] = strdist; /* Check ob end Kr uninteressant geworden ist */ tmp->datum->korn = hms_corn (hms); tmp->datum->status = pruefen( hms,tmp,tree); /* Setze Attribute für Ausgangskreuzung*/ tmp = find (tree, startKr); tmp->datum->links[firstdir][0] = pos; tmp->datum->links[firstdir][1] = strdist; /*Check ob start Kr uninteressant geworden*/ dir = tmp->datum->korn; for ( i=0 ; i<4 ; i++) if ( tmp->datum->links[i][0] == 0) dir += 1; if ( dir == 0 ) tmp->datum->status = 0; return; } /*--------------------------------------------------------------------*/ void check_rueckweg (HAMSTER *hms,BAUMPTR tree ,BAUMPTR satz) { /* Aufruf->bei Erreichen einer Kreuzung nach Streckenerkundung berechnen, ob kürzerere Verknüpfung zum Startfeld möglich ist */ char i=0,j; BAUMPTR tmp; short int con,compdist=0; if ( satz->koordinate == 1 ) return; /* testen ob direkte Links besser zum Startfeld connected sind */ for ( i=0 ; i<4 ; i++) { con = satz->datum->links[i][0]; if ( con > 0) /* nur bekannte Verbindung austesten */ { tmp = find (tree,con); compdist = tmp->datum->con_to_home[1] + satz->datum->links[i][1]; if ( compdist < satz->datum->con_to_home[1] ) { satz->datum->con_to_home[0] = i; satz->datum->con_to_home[1] = compdist; } } } distanz = satz->datum->con_to_home[1]; /* Umschreiben der Verbindung zum Startfeld, falls Änderung vorgenommen wurde */ for ( i=0 ; i < 4 ; i++) { con = satz->datum->links[i][0]; /* link zum Nachbarfeld */ if ( con > 1 ) /* Startfeld excluden */ { tmp = find (tree,con); if ( ( satz->datum->con_to_home[1] + satz->datum->links[i][1] ) < tmp->datum->con_to_home[1] ) { tmp->datum->con_to_home[1] = satz->datum->con_to_home[1] + satz->datum->links[i][1]; compdist = 0; for ( j=0; j<4 ; j++) /* Überprüfen, ob Kreuzung auf mehreren Wegen mit link connected ist */ { if ( tmp->datum->links[j][0] == satz->koordinate ) { if ( tmp->datum->links[j][1] < compdist || compdist == 0) { con = j; compdist = tmp->datum->links[j][1]; } } } tmp->datum->con_to_home[0] = con; check_rueckweg (hms, tree,tmp); /* Rekursion bei Änderung des Links */ } } } return; } /*--------------------------------------------------------------------*/ BAUMPTR find_next_ik (BAUMPTR tree) { BAUMPTR optkrl,optkrr; int w=0,a[3]={32000,32000,32000}; if ( tree->left == NULL && tree->right == NULL ) return tree; /* Blatt */ if ( tree->left == NULL ) {optkrr = find_next_ik (tree->right);optkrl = NULL;} else if ( tree->right== NULL ) {optkrl = find_next_ik (tree->left);optkrr = NULL;} else { optkrl = find_next_ik (tree->left); optkrr = find_next_ik (tree->right); } /* bestimme minimale Entfernung durch rek.Aufrufe */ if ( optkrl != NULL && optkrl->datum != NULL && optkrl->datum->status == 1) { a[0] = optkrl->datum->con_to_home[1];w=1;} if ( optkrr != NULL && optkrr->datum != NULL && optkrr->datum->status == 1) { a[1] = optkrr->datum->con_to_home[1];w=1;} if ( tree != NULL && tree->datum != NULL && tree->datum->status == 1) { a[2] = tree->datum->con_to_home[1];w=1;} if ( w == 0) return NULL; w=0; if ( a[0] > a[1] ) {a[0]=a[1];w=1;} if ( a[0] > a[2] ) {a[0]=a[2];w=2;} if ( w == 0 ) return optkrl; if ( w == 1 ) return optkrr; if ( w == 2 ) return tree; } /*-------------------------------------------------------------------- Funktion führt den Hamster auf dem kürzesten Weg vom Startfeld zur nächsten interessanten Kreuzung. Jede Kreuzung referenziert auf das Startfeld durch con_to_home Dabei sind die Richtung, von dieser Kreuzung ausgehend, sowie die Entfernung abgespeichert */ char go_from_start (HAMSTER *hms,BAUMPTR tree) { BAUMPTR tmp; WEGPTR weg=NULL; short int koor,i,dir,ende,j,compdist; tmp = find_next_ik (tree); /* Bestimme Zielkreuzung */ if (tmp == NULL || tmp->datum->con_to_home[1] > 119) return -1; koor = tmp->koordinate; while ( koor != 1) /* Weg zum Start logisch zurückgehen */ { i=0; ende = koor; dir = tmp->datum->con_to_home[0]; koor = tmp->datum->links[dir][0]; tmp = find (tree,koor); compdist = 0; for ( j=0; j<4 ; j++) /* Überprüfen, ob Kreuzung auf mehreren Wegen mit link connected ist */ { if (tmp->datum->links[j][0] == ende) { if ( tmp->datum->links[j][1] < compdist || compdist == 0) { i = j; compdist = tmp->datum->links[j][1]; } } } weg = attach_attop( i, weg); } while ( weg != NULL ) /*HAMSTER phys. zur Kr. bewegen */ { while ( weg->element != hms_dir (hms) ) hms_turn ( hms, HMS_LEFT ); weg = delete_firstelement ( weg ); do { advance (hms); distanz ++; } while ( get_typ (hms) != 0); } return 0; } /*--------------------------------------------------------------------*/ void zurueckgehen ( HAMSTER *hms ) { /* turn 180°*/ hms_turn ( hms, HMS_LEFT ); hms_turn ( hms, HMS_LEFT ); /* Zurückgehen bis Kreuzung erreicht distanz -- */ do { advance(hms); /* Gehe 1 freies Feld weiter */ distanz--; } while ( calc_koordinate(hms) != startKr ); /* bis Kreuzung erreicht ist*/ return; } /*--------------------------------------------------------------------*/ char random_dir ( HAMSTER *hms, BAUMPTR tmp) { char dir=-1,i; for ( i=0; i<4 ; i++) { hms_turn ( hms, HMS_LEFT ); if ( hms_look(hms) == 1 ) dir = hms_dir(hms); } if ( dir == -1 ) { do { dir = rand() % 4; if ( tmp->datum->links[dir][0] != 0 ) dir = 5; } while ( dir > 3); } return dir; } /*--------------------------------------------------------------------*/ void kreuzung (HAMSTER *hms,BAUMPTR tree,char *lmodus) { char dir,stat,quit=0; short int pos = calc_koordinate( hms ); BAUMPTR tmp = find (tree , pos); if (tmp->datum == NULL) /* Kreuzung bekannt ? --> hinzufügen */ { add_kreuzung(hms, tree ,pos); tmp = find (tree , pos); } else { tmp->datum->korn = hms_corn (hms); /* update, falls Korn aufgenomen wurde */ if ( distanz > tmp->datum->con_to_home[1] ) distanz = tmp->datum->con_to_home[1]; } if ( startKr ) { setIndizes (hms , tree , pos ); /*Indizes für neu erkundete Strecke setzen */ check_rueckweg ( hms, tree ,tmp); /* Rückwegoptimierung */ } if ( tmp->datum->status ) tmp->datum->status = pruefen( hms,tmp,tree); /* Statustest */ stat = tmp->datum->status; if ( status_check (tree) == 0 ) *lmodus = -1; if ( *lmodus == 1 ) /* zur nächsten Kreuzung wenn Laufmodus = 1*/ { /* check ob Status von aktueller Kr. = 0 --> uninteressant*/ /* suche nächstes Ziel aus Liste, falls es noch intKr gibt */ /* auf kürzesten Weg hinbewegen */ if (stat == 0) { do { if ( pos == 1) { quit = go_from_start ( hms,tree); pos = calc_koordinate( hms ); if ( pos == 1 || quit == -1 ) {*lmodus = -1;return;} /* keine int.Kr. mehr da */ } else go_to_intKr(hms,tree,pos); startKr = 0; strdist = 0; hms_take (hms,HMS_MAXLOAD); if ( hms_load(hms) != HMS_MAXLOAD ) { pos = calc_koordinate( hms ); tmp = find (tree , pos); tmp->datum->korn = hms_corn(hms); tmp->datum->status = pruefen( hms,tmp,tree); } else *lmodus = 0; if ( status_check(tree) == 0) *lmodus = -1; if ( *lmodus != 1 ) return; } while ( tmp->datum->status == 0 ); /* Solange, bis int.Kr.gefunden ist */ } /* ausgehend von gegenwärtiger Kreuzung , bei der Status ==1 sein muß , wird die neue zu beschreitende Richtung bestimmt*/ /* tmp enthält Daten der aktuellen Kreuzung*/ dir = random_dir ( hms,tmp ); /* Randomize next aim */ /* set start Kreuzung , first direction*/ startKr = calc_koordinate( hms ); firstdir = dir; /* Drehen bis korrekte Richtung gefunden*/ while ( dir != hms_dir (hms)) hms_turn ( hms, HMS_LEFT ); hms_move (hms); strdist = 1; distanz ++; hms_take (hms,HMS_MAXLOAD); /* Überprüfen ob sich der Laufmodus geändert hat */ if ( hms_load(hms) == HMS_MAXLOAD ) *lmodus = 0; } return ; } /*--------------------------------------------------------------------*/ void sackgasse (HAMSTER *hms,BAUMPTR tree,char *lmodus) { BAUMPTR tmp; int c=hms_corn(hms),weg; weg = distanz; zurueckgehen ( hms ); if ( weg > 119 ) weg = 1; else weg = 0; /* Attribute stetzen -> firstdir = -1 */ if ( c * 20 < 2*strdist || weg ) { tmp = find (tree , startKr); tmp->datum->links[firstdir][0] = -1; /* Überprüfe, ob sich dadurch der Status der "Kreuzung" geändert hat*/ tmp->datum->status = pruefen ( hms , tmp,tree); } if ( hms_load(hms) == HMS_MAXLOAD ) *lmodus = 0; startKr = 0; strdist=0; return; } /*--------------------------------------------------------------------*/ void strecke (HAMSTER *hms,BAUMPTR tree, char *lmodus) { advance( hms ); /* Gehe ein Feld voran */ strdist ++; /* Entfernungen ++ */ distanz ++; /* check Korn evtl. in Rückwegmodus wechseln */ hms_take (hms,HMS_MAXLOAD); if ( distanz > 119 ) sackgasse (hms,tree,lmodus); else if ( hms_load(hms) == HMS_MAXLOAD ) *lmodus = 0; return ; } /*--------------------------------------------------------------------*/ /* Sammle solange bis maximale Traglast erreicht ist */ char sammel (HAMSTER *hms, BAUMPTR tree) { char feldtyp,sg=0, laufmodus = 1; /* Modus 1 --> Sammelmodus ; Modus 0 --> Rückweg*/ do { feldtyp = get_typ(hms); /*Kreuzung==0,Sackgasse==1,Strecke==2*/ if (feldtyp == 0) kreuzung (hms,tree,&laufmodus); if (feldtyp == 1) sackgasse (hms,tree,&laufmodus); if (feldtyp == 2) strecke (hms,tree,&laufmodus); } while ( laufmodus == 1 ); /* Solange im Sammelmodus */ if ( laufmodus == 0 ) { feldtyp = get_typ(hms); if (feldtyp == 0) kreuzung (hms,tree,&laufmodus); if (feldtyp == 1) sackgasse (hms,tree,&laufmodus); if (feldtyp == 2) zurueckgehen (hms); } return laufmodus; } /*--------------------------------------------------------------------*/ /* Funktion zum Aufbau des kompletten Binärbaums */ BAUMPTR create_tree ( short int ug , short int og) { short int mw; BAUMPTR tmp = (BAUMPTR)malloc(sizeof(BAUMELEMENT)); if ( !tmp ) { fprintf (stderr,"Nicht genügend Arbeitsspeicher für den tHamster !-->Abbruch"); exit; } if ( ug == og) { tmp->koordinate = ug; tmp->datum = NULL; tmp->left = NULL; tmp->right = NULL; return tmp; } if ( og - ug == 1) { tmp->koordinate = og; tmp->datum = NULL; tmp->left = create_tree ( ug , ug ); tmp->right = NULL; return tmp; } mw = (ug + og) / 2; tmp->koordinate = mw; tmp->datum = NULL; tmp->left = create_tree ( ug , mw - 1 ); tmp->right = create_tree ( mw + 1 , og ); return tmp; } /*--------------------------------------------------------------------*/ void delete_tree ( BAUMPTR tree ) { if ( tree->left ) delete_tree ( tree->left ); if ( tree->right ) delete_tree ( tree->right ); free ( tree ); return; } /*--------------------------------------------------------------------*/ /*--------------------------------------------------------------------*/ /*--------------------------------------------------------------------*/ void hms_ctrl (HAMSTER *hms) { BAUMPTR kopf = create_tree ( 1 , 4096 ); /* Definiere Binärbaum */ char z=0; do { startKr = 0; distanz = 0; z = sammel( hms ,kopf ); /* sammel Korn*/ if ( calc_koordinate(hms) > 1 ) go_back_to_start ( hms,kopf ); /* Gehe zurück, lege Korn ab*/ } while ( status_check (kopf) || z != -1); /* Sammle weiter, wenn es noch interessante Kreuzungen gibt*/ delete_tree ( kopf ); return; }