/*----------------------------------------------------------------------
  File    : hamster.c
  Contents: hamster control program
  Author  : Christian Klukas
  Hinweis : Der Quelltext wird bei mir mit 3 Warnungen compiliert,
            welche ignoriert werden koennen.
  History : 16.10.97 file created by Christian Borgelt
            21.02.98 Beginn der Entwicklung.
            23.02.98 Neuer Versuch :)
            14.03.98 Globale Var. werden verringert
            24.03.98 Test im UNIX System -> einiges überarbeitet
            26.03.98 Neue Routine für optimalen Weg -> extrem schnell
                     und praktisch :)
            29.03.98 Korn-Sammeln an einem Abend implementiert :)
            30.03.98 Alles Korn einzusammeln ist manchmal nicht so gut...
                     Strategie entsprechend modifiziert
            06.04.98 Modifikationen abgeschlossen. Hamster erkundet nicht
                     mehr das gesammte Lab. und sammelt nicht alles
                     Korn ein.
            08.04.98 Quelltext optimiert -> weniger Zeilen, weniger
                     Compiler-Warnungen
            23.04.98 Punkte-Check-Routine entwickelt.
                     (Liest Hamster-ID per memcpy aus, vorsicht falls
                      Hamsterstruktur geändert wird)
            23.04.98 Ende der Entwicklung,
                     Beginn Erstellung der Dokumentation
            16.05.98 memcpy ist nicht erlaubt :(
                     statt dessen globale Variable "exitnow"
            06.06.98 Letzte Kontrolle vor endgültiger Abgabe
  ----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "hamster.h"

/* neu: Strategie-Variablen.  *-> Standard-Option */
int linksrechts=1;    /*  3-> stets nach rechts
                          2-> stets nach links
                         *1-> bei Erkundung abwechselnd nach links/rechts
                          0-> bei Erkundung geradlinig
                       */
int kornsammeln=1;    /* *1-> Korn wird bereits während der Erkundung
                              gesammelt
                          0-> Korn wird erst nach der Erkundung gesammelt
                       */
int sortieren=1;      /* *1-> Zielkoordinaten werden nach Entfernung
                              sortiert
                          0-> Keine Sortierung
                       */
/*----------------------------------------------------------------------*/

int exitnow=0;              /* statt memcpy-Nutzung für exit */
                            /* X->nicht betreten; B->betreten */
int FeldUnbekannt=0;	       /* X   Achtung: Das Feld ist nicht besucht wenn */
                            /*     Feld[x,y]==FeldUnbekannt ODER */
int FeldLeerUnbekannt=1;    /* X   Feld[x,y] zwar Leer aber unbekannt */
int FeldLeer=2;    	       /* B   Feld schon besucht */
int FeldMitKorn=3; 	       /* X   Kornmenge unbekannt */
int FeldMauer=4; 	          /* B   Wird niemals im Feld eingefügt */
int KornVerschiebung=4;     /* B */
      /* falls Feldspeicher>4 --> FeldMitKorn, wobei Kornmenge bekannt ist */
      /*                          Kornmenge=feld[x,y]-KornVerschiebung */
/*----------------------------------------------------------------------*/
#define Nord HMS_NORTH      /* Richtungsdef. die vorgeg. ist  */
#define Sued HMS_SOUTH	    /* dagegen N, S, ... von mir def. */
#define West HMS_WEST
#define Ost  HMS_EAST
int N=1;		    /* Achtung: Nord, Süd, ... */
int S=2;		    /* ist nicht mit N, S, ... vergleichbar */
int W=3;		    /* (N<>Nord!, ...) */
int E=4;


HAMSTER *myhamster;	       /* Globale Hamster-Variable */

int lauf=0;                 /* Laufvariable für getfirst/getnext */
int Stapel[4000][3];        /* Stapelvariable speichert die */
                            /* Handlungsalternativen */
                            /* 3-Dimensional da x und y Koor; */
                            /* außerdem noch Hilfsvariable, die */
                            /* bei der Sortierung benötigt wird */
                            /* siehe "SortiereKoordinaten()" */
int StapelHoehe=-1;         /* Startet bei -1, damit bei 0 begonnen */
                            /* wird zu speichern, siehe Push */


int FeldAdd=HMS_MAXXEXT+1; /* Verschiebung, damit keine neg. Feldzugriffe */
int Feld[HMS_MAXXEXT*2+2][HMS_MAXYEXT*2+2][5];  /* Feld-Array: */
                    /* x,y,t --> x,y ->Feldposition */
                    /* t=0 Feldinhalt */
                    /* t=1,2,3,4 Mauer in Richtung N,S,W,O? 0=nein 1=ja */

typedef struct
{ int x,y;
} Punkt;

typedef struct
{                          /* falls SP==EP -> alles durchsuchen */
   Punkt StartPunkt;	      /* Punkt an der die Entferung==0 */
                           /* falls EndPunkt<>StartPunkt */
                           /* der Punkt zu dem der Hamster mit */
                           /* GeheOptimal geht!!! */
   Punkt EndPunkt;         /* falls<>StartPunkt der Punkt an dem */
                           /* der Hamster gerade steht!!! */
                           /* Speichert die Entferungen zum Startpunkt */
   int Feld[HMS_MAXXEXT*2+2][HMS_MAXYEXT*2+2];
} EntfernungsFeld;


int punkte=0;               /* Punktestand */

/* ********************************************************* */
/* Punkte-Verwaltung                                         */
void MyHMSGO(void)
{  hms_move(myhamster);
   punkte--;
}
void MyHMSDROP(void)
{  int load;
   load=hms_load(myhamster);
   hms_drop(myhamster, HMS_MAXLOAD);
   punkte+=(load-hms_load(myhamster))*20;
}
/* ********************************************************* */

     /* Wand-Information speichern */
     /* setmode = 1 oder 0 (wand da oder nicht) */
     /* Jede Wand wird doppelt gespeichert (einmal in (xp,yp) und
        einmal in (x,y). */
void SetWand(int xp, int yp, int x, int y, int setmode)
{  if (y-yp== 1) {Feld[xp+FeldAdd][yp+FeldAdd][N]=setmode;
                  Feld[x+FeldAdd][y+FeldAdd][S]=setmode;}  /* BR: Nord */
   if (y-yp==-1) {Feld[xp+FeldAdd][yp+FeldAdd][S]=setmode;
                  Feld[x+FeldAdd][y+FeldAdd][N]=setmode;}  /* BR: Süd */
   if (x-xp==-1) {Feld[xp+FeldAdd][yp+FeldAdd][W]=setmode;
                  Feld[x+FeldAdd][y+FeldAdd][E]=setmode;}  /* BR: West */
   if (x-xp== 1) {Feld[xp+FeldAdd][yp+FeldAdd][E]=setmode;
                  Feld[x+FeldAdd][y+FeldAdd][W]=setmode;}  /* BR: Ost */
}

     /* Ermittelt, ob das Feld(x,y) bereits besucht ist */
int Erkundet(int x, int y)
{  int info;
   info=Feld[x+FeldAdd][y+FeldAdd][0];
   if ((info==FeldUnbekannt)||(info==FeldLeerUnbekannt)||(info==FeldMitKorn))
         return 0;   /* Falls noch nicht betreten */
   else  return 1;
}

      /* Speichert im Feld-Speicher die neuen Informationen */
		/* xp, yp -> Position des Hamsters */
		/* x,y -> Position der Information */
		/* info-> codierte Infos, siehe oben */
void NeueInfos(int xp, int yp, int x, int y, int info)
{ if (info==FeldMauer)
  { SetWand(xp, yp, x, y, 1);   /* Wände setzen */
  } else
  {                /* Wenn der Hamster nicht auf dem Feld steht dann */
      if ( (xp!=x)||(yp!=y) )
	                /* nur setzen wenn Feld noch nicht besucht, */
      	{         /* da sonst Informationen verloren gehen würden */
            if ( !Erkundet(x,y) ) Feld[x+FeldAdd][y+FeldAdd][0]=info;
         }
         else Feld[x+FeldAdd][y+FeldAdd][0]=info;
		SetWand(xp, yp, x, y, 0);
  }
}

      /* Ermittelt Infos, die der Hamster durch Schauen auf das */
      /* nächste Feld ermittelt; Kann nicht die Kornmenge ermitteln */
      /* return-> codierte Infos */
int GetLookInfo(void)
{  int t;
   t=hms_look(myhamster);
   if (t==HMS_EMPTY) return FeldLeerUnbekannt; else
   if (t==HMS_CORN)  return FeldMitKorn; else
   if (t==HMS_WALL)  return FeldMauer;
   return FeldUnbekannt;    /* Dieser Fall dürfte niemals auftreten */
}

      /* Ähnlich wie getlookinfo, kann aber best. wieviel Korn */
      /* vorhanden ist, da der Hamster auf dem Feld steht */
      /* return -> codierte Infos */
int GetPosInfo(void)
{  int t;
   t=hms_corn(myhamster);   /* Ermittelt die Kornmenge auf dem akt. Feld */
   if (t==0) return FeldLeer;
      else return t+KornVerschiebung;  /* Ansonsten Kornmenge codieren */
}

      /* Speichert neue Koordinaten, an denen Handlungsmöglichkeiten */
      /* bestehen */
void PushKoor(int x, int y)
{  if (StapelHoehe>=4000)
   { fprintf(stderr, "FEHLER: Push-Max. erreicht!"); StapelHoehe=-1; }
   StapelHoehe++;
   Stapel[StapelHoehe][0]=x;
   Stapel[StapelHoehe][1]=y;
}
int GetRichtung(void)
{  return hms_dir(myhamster); }

int GetX(void)
{  int x,y;
   hms_pos(myhamster, &x, &y);
   return x;
}
int GetY(void)
{  int x,y;
   hms_pos(myhamster, &x, &y);
   return y;
}

   /* Holt die letzten bekannten Koordinaten vom Stapel, */
   /* an denen noch Handlungsspielraum besteht, d.h. */
   /* an dem noch unerforschtes Gebiet grenzt */
int PopKoor(int *x, int *y)
{  if (StapelHoehe==-1) return 0;
   *x=Stapel[StapelHoehe][0];
   *y=Stapel[StapelHoehe][1];
   StapelHoehe--;
   return 1;
}

int PunktErkundet(Punkt p)
{ return Erkundet(p.x, p.y); }

   /* Ermittelt, ob das Feld vor dem Hamster bereits besucht ist */
   /* Blickrichtung vorgegeben */
int VorDirErkundet(int x, int y, int richtung)
{  if (richtung==Nord) return Erkundet(x,y+1);
   if (richtung==Sued) return Erkundet(x,y-1);
   if (richtung==West) return Erkundet(x-1,y);
   if (richtung==Ost)  return Erkundet(x+1,y);
   return 0;
}

   /* Ermittelt, ob das Feld vor dem Hamster bereits besucht ist */
   /* Blickrichtung wird ermittelt */
int VorDirErkundetOP(void)
{  return VorDirErkundet(GetX(), GetY(), GetRichtung());  }

int KannGeradeAusUnabhVomBetreten(int x, int y, int dir)
{  int Ausrichtung;
   Ausrichtung=dir;
   if   (  /* Richtung              Keine Wand */
            ( (Ausrichtung==Nord) && !(Feld[x+FeldAdd][y+FeldAdd][N]) ) ||
            ( (Ausrichtung==Sued) && !(Feld[x+FeldAdd][y+FeldAdd][S]) ) ||
            ( (Ausrichtung==West) && !(Feld[x+FeldAdd][y+FeldAdd][W]) ) ||
            ( (Ausrichtung==Ost)  && !(Feld[x+FeldAdd][y+FeldAdd][E]) )
        )
            return 1;		/* Falls in Blickrichtung keine Mauer */
      else  return 0; 		/* Falls vor einem eine Wand */
}

/* Ermittelt, ob geradeaus gegangen werden kann */
/* Wenn das Feld in Blickrichtung bereits betreten ist dann gehts nicht */
/* weiter!  dir --> vorgeg. Blickrichtung! */
int KannGeradeAus(int x, int y, int dir)
{  if ( KannGeradeAusUnabhVomBetreten(x,y,dir)
         && (!VorDirErkundet(x,y,dir))  /* ... und noch nicht erkundet */
      )     return 1;		/* Falls in Blickrichtung keine Mauer */
      else  return 0; 		/* Falls vor einem eine Wand */
}

int PunktKannGeradeAusUnabhVomBetreten(Punkt p, int dir)
{ return KannGeradeAusUnabhVomBetreten(p.x, p.y, dir); }

      /* --> wenn ein Feld(x,y) von bereits erkundeten Feldern umgeben ist
      // und das Feld bisher als "FeldLeerUnbekannt" klassifiziert ist,
      // dann kann auf die Erkundung verzichtet werden. Das Feld wird
      // als "FeldLeer"   _______    eingestuft --> es wird nicht mehr besucht
      //                 |   <-  |
      //         ---------  ---  |
      //          ->        |X   |
      //         ---------  ---  |
      //                 |_->____|    X wird nicht besucht
      // (funktioniert auch gut bei leerem Labyrinth)
      */
int ErkundungNotwendig(int x, int y)
{  int freicount=0;
   if ((Feld[x+FeldAdd][y+FeldAdd][N]==0) &&
       !VorDirErkundet(x,y,Nord)) freicount++;
   if ((Feld[x+FeldAdd][y+FeldAdd][S]==0) &&
       !VorDirErkundet(x,y,Sued)) freicount++;
   if ((Feld[x+FeldAdd][y+FeldAdd][W]==0) &&
       !VorDirErkundet(x,y,West)) freicount++;
   if ((Feld[x+FeldAdd][y+FeldAdd][E]==0) &&
       !VorDirErkundet(x,y,Ost))  freicount++;
   if (freicount>1) return 1;
   if (   Erkundet(x,y+1) && Erkundet(x-1,y)
       && Erkundet(x,y-1) && Erkundet(x+1,y)
       && (Feld[x+FeldAdd][y+FeldAdd][0]==FeldLeerUnbekannt) )
      {	NeueInfos(x,y,x,y, FeldLeer); fprintf(stderr, "o");
      	return 0; /* Erkundung nicht notwendig */
      }
   return 1;       /* Erkundung notwendig */
}

   /* Drehdicheinmal-> Informationen sammeln */
   /* Return immer = 1 für true, da stehts möglich */
int DrehDichEinmal(void)
{  int NichtErkundet=0;  /* Speichert die noch nicht besuchte Anzahl an Orten */
   int r; 	             /* Zähler für Drehung */
   int Ausrichtung;      /* Speicher für die Blickrichtung */
   int x, y; 	          /* Pos.info */

   hms_pos(myhamster, &x, &y); 	/* Akt. Pos. ermitteln */
           /* Infos an aktueller Position verwerten */
   NeueInfos(x,y, x,y, GetPosInfo() );
           /* 4 mal nach rechts drehen */
   for (r=0; r<=3; r++)
   {  hms_turn(myhamster, HMS_RIGHT);
      Ausrichtung=hms_dir(myhamster);   /* Blickrichtung ermitteln */
         /* Je nach Blickrichtung werden dem Speicher die Infos geg. */
      if (Ausrichtung==Nord) NeueInfos(x,y, x,y+1, GetLookInfo() ); else
      if (Ausrichtung==Sued) NeueInfos(x,y, x,y-1, GetLookInfo() ); else
      if (Ausrichtung==West) NeueInfos(x,y, x-1,y, GetLookInfo() ); else
      if (Ausrichtung==Ost)  NeueInfos(x,y, x+1,y, GetLookInfo() );
      if (KannGeradeAus(x,y,Ausrichtung) ) NichtErkundet++;
   }
      /* falls mehr als eine Position noch nicht erkundet, dann Position */
      /* im Stapel speichern */
   if (NichtErkundet>1) PushKoor(x, y);

   if ( (!ErkundungNotwendig(x,y+1)) ||  /* Bei der Erkundung überprüfen, ob */
        (!ErkundungNotwendig(x,y-1)) ||  /* die umgebenen Felder besucht  */
        (!ErkundungNotwendig(x-1,y)) ||  /* werden müssen, falls nicht */
        (!ErkundungNotwendig(x+1,y))     /* dreht sich der hamster einmal */
      ) { fprintf(stderr, "E"); DrehDichEinmal(); }

   return 1;
}

int KannGeradeAusOP(void)
{ return KannGeradeAus(GetX(), GetY(), GetRichtung()); }

   /* Ermittelt, ob eine Möglichkeit der weiteren Bew. existiert, */
   /* d.h. ob es mind. 2 Felder im Umkreis begehbar sind: */
   /* (1 Feld wo man herkommt, 1 wo man hinwill) */
   /* ausser man steht auf dem Startfeld, dann genügt 1 Feld! */
   /* UND ob eines der freien Felder noch nicht betreten ist */
int ErkundungMoeglichMP(int x, int y)
{
   int FreieFelder, nichtbetreten;
   nichtbetreten=0;
   FreieFelder=0;
   if (KannGeradeAus(x,y,Nord) ) nichtbetreten++;
   if (KannGeradeAus(x,y,Sued) ) nichtbetreten++;
   if (KannGeradeAus(x,y,Ost) )  nichtbetreten++;
   if (KannGeradeAus(x,y,West) ) nichtbetreten++;
   if (Feld[x+FeldAdd][y+FeldAdd][N]==0) FreieFelder++;
   if (Feld[x+FeldAdd][y+FeldAdd][S]==0) FreieFelder++;
   if (Feld[x+FeldAdd][y+FeldAdd][W]==0) FreieFelder++;
   if (Feld[x+FeldAdd][y+FeldAdd][E]==0) FreieFelder++;
   if (nichtbetreten==0) return 0;
   if ( (x==0) && (y==0) )	    /* Falls am Startpunkt */
   {  if (FreieFelder>0) return 1;
         else return 0;
   } else                           /* Wenn nicht am Startpunkt, dann */
   {  if (FreieFelder>1) return 1;  /* min. 2 freie Felder notwendig */
         else return 0;             /* 1 wo man herkam 1 wo man hin will */
   }
}

int ErkundungMoeglich(void)
{  return ErkundungMoeglichMP(GetX(), GetY()); }

   /* dir->hms_right/hms_left */
   /* return->Blickrichtung, wenn sich der Hamster nach R/L drehen würde */
int GetBlickRichtung(int dir)
{  int br;
   br=GetRichtung();
   if ( ( (br==Nord) && (dir==HMS_RIGHT) ) ||
        ( (br==Sued) && (dir==HMS_LEFT)  )    ) return Ost;
   if ( ( (br==Sued) && (dir==HMS_RIGHT) ) ||
        ( (br==Nord) && (dir==HMS_LEFT)  )    ) return West;
   if ( ( (br==Ost)  && (dir==HMS_LEFT)  ) ||
        ( (br==West) && (dir==HMS_RIGHT) )    ) return Nord;
   if ( ( (br==West) && (dir==HMS_LEFT)  ) ||
        ( (br==Ost)  && (dir==HMS_RIGHT) )    ) return Sued;
   return br; /* sollte niemals erreicht werden */
}

   /* Ermittelt, ob nach rechts gegangen werden kann */
   /* Benutzt KannGeradeAus :) */
int NachRechtsFallsOK(void)
{  int erg;  /* erg->kann geradeaus? */
   erg=KannGeradeAus(GetX(), GetY(), GetBlickRichtung(HMS_RIGHT));
   if (erg) hms_turn(myhamster, HMS_RIGHT);
   return erg;
}

   /* Ermittelt, ob nach links gegangen werden kann */
int NachLinksFallsOK(void)
{  int erg;
   erg=KannGeradeAus(GetX(), GetY(), GetBlickRichtung(HMS_LEFT));
   if (erg) hms_turn(myhamster, HMS_LEFT);
   return erg;
}

   /* Drehung des Hamsters in eine best. Richtung */
void DreheNach(int dir)
{
   int ausr;
   ausr=hms_dir(myhamster);
   if ( ( (ausr==Nord) && (dir==W) ) ||
        ( (ausr==West) && (dir==S) ) ||
        ( (ausr==Sued) && (dir==E) ) ||
        ( (ausr==Ost)  && (dir==N) ) )  hms_turn(myhamster, HMS_LEFT);
   ausr=hms_dir(myhamster);
   while (!( ( (ausr==Nord) && (dir==N) ) || ( (ausr==Sued) && (dir==S) ) ||
             ( (ausr==Ost)  && (dir==E) ) || ( (ausr==West) && (dir==W) ) )
         )
   {  hms_turn(myhamster, HMS_RIGHT);
      ausr=hms_dir(myhamster);
   }
}

/***********************************************************************
 ***********************************************************************/

typedef struct queuenode *SchlangenElementP;
typedef struct queuenode
   {
      int x,y, counter;
      SchlangenElementP next;
   } SchlangenElement;

SchlangenElementP head, tail;

void getSchlange(Punkt *p, int *counter)
{
   SchlangenElement *temp;
   p->x=head->x;
   p->y=head->y;
   *counter=head->counter;
   temp=head;
   head=head->next;
   if (head==NULL) tail=NULL;
   free(temp);
}
void putSchlange(int x, int y, int counter,EntfernungsFeld *Efeld)
{
   SchlangenElementP temp;
   temp=(SchlangenElementP)malloc( sizeof(SchlangenElement) );
   if (temp==NULL)
   {
      fprintf(stderr, "\nPROGRAMM AUF GRUND VON SPEICHERMANGEL GESTOPPT");
      fprintf(stderr, "\nTEST BITTE WIEDERHOLEN - MEHR SPEICHER BEREITSTELLEN");
      exit(0);
   }
   temp->x=x;
   temp->y=y;
   temp->counter=counter;
   temp->next=NULL;
   if (tail==NULL) head=temp;
      else tail->next=temp;
   tail=temp;
   Efeld->Feld[x+FeldAdd][y+FeldAdd]=counter;
}

void PunktPutSchlange(Punkt p, int counter, EntfernungsFeld *Efeld)
{
   putSchlange(p.x, p.y, counter, Efeld);
}

void queueinitialize(void)
{
   head=NULL;
   tail=NULL;
}

int queueempty(void)
{
   if (head==NULL) return 1;
      else return 0;
}

/* Schlangenverwaltung ENDE */

/* Entferungsfeld erstellen */
int ErstelleEntfernungsFeld(EntfernungsFeld *Efeld)
{
   Punkt AP;	/* Aktueller Punkt */
   int counter;	/* Entferungszaehler */
   int x,y, ZielPunktPruefung=1;
   if ((Efeld->EndPunkt.x==Efeld->StartPunkt.x)&&
       (Efeld->EndPunkt.y==Efeld->StartPunkt.y))
       ZielPunktPruefung=0;

   if (ZielPunktPruefung) fprintf(stderr, "+"); else fprintf(stderr, "X");

   if (!PunktErkundet(Efeld->StartPunkt)) return 0;
   if (!PunktErkundet(Efeld->EndPunkt))   return 0;
   for (x=0; x<HMS_MAXXEXT*2+2; x++)
      for (y=0; y<HMS_MAXYEXT*2+2; y++)
       	Efeld->Feld[x][y]=2000000000; /* bel. grosse Zahl (groesser */
   queueinitialize();                  /* als die max. anzunehmende Entf.) */
   PunktPutSchlange(Efeld->StartPunkt, 0, Efeld); /* Entf. am Startp.=0 */
   while (!queueempty())
   {
      getSchlange(&AP, &counter);
      if (   (Efeld->Feld[AP.x+FeldAdd][AP.y+1+FeldAdd]>counter+1)
          && PunktKannGeradeAusUnabhVomBetreten(AP, Nord) )
      	putSchlange(AP.x, AP.y+1, counter+1, Efeld);

      if (   (Efeld->Feld[AP.x+FeldAdd][AP.y-1+FeldAdd]>counter+1)
      	  && PunktKannGeradeAusUnabhVomBetreten(AP, Sued) )
      	putSchlange(AP.x, AP.y-1, counter+1, Efeld);

      if (   (Efeld->Feld[AP.x-1+FeldAdd][AP.y+FeldAdd]>counter+1)
      	  && PunktKannGeradeAusUnabhVomBetreten(AP, West) )
      	putSchlange(AP.x-1, AP.y, counter+1, Efeld);

      if (   (Efeld->Feld[AP.x+1+FeldAdd][AP.y+FeldAdd]>counter+1)
      	  && PunktKannGeradeAusUnabhVomBetreten(AP, Ost) )
      	putSchlange(AP.x+1, AP.y, counter+1, Efeld);
      if ( ZielPunktPruefung )
      if ( (Efeld->EndPunkt.x==AP.x)&&(Efeld->EndPunkt.y==AP.y) )
      { while (!queueempty()) getSchlange(&AP, &counter); /* --> ENDE */ }
   };
   return 1;   /* alles OK */
}
/* Beendet das Programm falls die Punkte 5% (geändert in 50%)
   unter das bisherige
   Maximum sinken, oder falls die Punkte sich in mehr als 5%
   der Fälle verringert haben (%-Zahlen sind willkürlich gewählt) */
void PunkteCheck(void)
{
   static int sammelreste=0;
   static int plus=0;
   static int minus=0;
   static int maxpunkte=0;
   static int last=0;
/* int id; */
   if (last!=0)
   {
      if (punkte<last) minus++;
        else           plus++;
   }
   last=punkte;
   if (punkte>maxpunkte) maxpunkte=punkte;
   fprintf(stderr, "\nAktueller Punktestand: %d\n", punkte);
   if ((minus+plus)>3)
   if ( ( (minus>plus*0.05)&&(punkte<last) ) ||
        ( (maxpunkte-last)>maxpunkte*0.2 )
      )
   {
     if (!sammelreste)
     {
        sammelreste=1;
        fprintf(stderr, "\nPunkte-Kontrolle bricht Erkundung ab.\n");
        SammelResteEin();
     }
     fprintf(stderr, "\nPunkte-Kontrolle beendet \
Hamster-Steuerung vorzeitig.\n");
/*
//   memcpy(&id, myhamster, sizeof(int));
//   printf("d %d\n", id);
//   exit(0);
*/
     exitnow=1;
   };
}

/* Geht zu dem Punkt, an dem die Entfernung=0 ist. */
/* Falls dieser Punkt erreicht wird-->return 1, sonst return 0 */
int GehOptimal(EntfernungsFeld *Efeld, int KornNehmenErlaubt)
{
   int x, y, AktEntf, ende=0;
   hms_pos(myhamster, &x, &y);
   fprintf(stderr, " %d ", abs(Efeld->StartPunkt.x-Efeld->EndPunkt.x)
                          +abs(Efeld->StartPunkt.y-Efeld->EndPunkt.y)
                          -Efeld->Feld[x+FeldAdd][y+FeldAdd]);
   while ( (Efeld->Feld[x+FeldAdd][y+FeldAdd]!=0) && !ende )
   {
      AktEntf=Efeld->Feld[x+FeldAdd][y+FeldAdd];
      if (   (Efeld->Feld[x+FeldAdd][y+1+FeldAdd]<AktEntf)
          && KannGeradeAusUnabhVomBetreten(x, y, Nord) )
      	DreheNach(N); else
      if (   (Efeld->Feld[x+FeldAdd][y-1+FeldAdd]<AktEntf)
      	  && KannGeradeAusUnabhVomBetreten(x, y, Sued) )
      	DreheNach(S); else
      if (   (Efeld->Feld[x-1+FeldAdd][y+FeldAdd]<AktEntf)
      	  && KannGeradeAusUnabhVomBetreten(x, y, West) )
      	DreheNach(W); else
      if (   (Efeld->Feld[x+1+FeldAdd][y+FeldAdd]<AktEntf)
      	  && KannGeradeAusUnabhVomBetreten(x, y, Ost) )
      	DreheNach(E); else return 0;
      MyHMSGO();
      hms_pos(myhamster, &x, &y);
      if ( (x==0)&&(y==0) )
      {
         MyHMSDROP();
         PunkteCheck();
         if (exitnow) return 0;
      }
      if (KornNehmenErlaubt)
      if (Feld[x+FeldAdd][y+FeldAdd][0]>KornVerschiebung)
      {
         hms_take(myhamster, HMS_MAXLOAD);
         NeueInfos(x,y, x,y, GetPosInfo() );
         if ( hms_load(myhamster)==HMS_MAXLOAD )
         {
            GeheVonNach(x,y, 0, 0);
            if (exitnow) return 0;
            PushKoor(Efeld->StartPunkt.x, Efeld->StartPunkt.y);
            ende=1;
         }
      }
   }
   return 1;
}

/***********************************************************************
 ***********************************************************************/

int GeheVonNach(int vx, int vy, int nx, int ny)
{
   EntfernungsFeld feld;

	feld.EndPunkt.x=vx;   feld.EndPunkt.y=vy;
	feld.StartPunkt.x=nx; feld.StartPunkt.y=ny;

   if (!ErstelleEntfernungsFeld(&feld)) return 0;

   if (!GehOptimal(&feld, kornsammeln)) return 0;

   return 1;
}

void CheckKorn(int counter)
{  int x, y, korn, load;
   hms_pos(myhamster, &x, &y);
   korn=Feld[x+FeldAdd][y+FeldAdd][0]-KornVerschiebung;
   if ( (korn>0) || (counter*2>20*HMS_MAXLOAD) )
   {  load=hms_load(myhamster);
      hms_take(myhamster, HMS_MAXLOAD);
      NeueInfos(x,y, x,y, GetPosInfo() );
      if ( ( (load+korn)>HMS_MAXLOAD ) || (counter*2>20*HMS_MAXLOAD) )
      {  if (GeheVonNach(x,y,0,0))
         {  PushKoor(x,y);
            if (counter*2>20*HMS_MAXLOAD)
              fprintf(stderr, "[Z]");
         }  else { MyHMSDROP();
                   NeueInfos(x,y, x,y, GetPosInfo() );
                 }
      }
   }
}

int KornDa(void)
{
   int x,y;
   int korn=0;
   for (x=0;x<=HMS_MAXXEXT*2+1;x++)
      for (y=0;y<=HMS_MAXYEXT*2+1;y++)
      { if (Feld[x][y][0]>KornVerschiebung)
          korn=korn+Feld[x][y][0]-KornVerschiebung;
      }
   return korn;
}

int BerEntf(int vx, int vy, int nx, int ny)
{
   EntfernungsFeld feld;

	feld.EndPunkt.x=vx;   feld.EndPunkt.y=vy;
	feld.StartPunkt.x=nx; feld.StartPunkt.y=ny;

   if (!ErstelleEntfernungsFeld(&feld)) return 0;
   return feld.Feld[vx+FeldAdd][vy+FeldAdd];
}

   /* Der Hamster geht solange geradeaus, wie er kann */
   /* dann geht er falls er kann nach rechts, sonst nach links */
   /* falls beides nicht möglich ist, dann ist er (hier) fertig */
void GehLos(void)
{
   int lr=0, ergebnis, counter;

   counter=BerEntf(0,0,GetX(),GetY());

   DrehDichEinmal();
         /* Bei jedem Schritt einmal umgucken. */
	 /* Und Informationen sammeln */
   while ( (ErkundungMoeglich()) && (!exitnow) )
   {
      ergebnis=1;
      /*if (!KannGeradeAusOP()) /* (Aktivieren, wenn der Hamster
                                  vorzugsweise geradeaus gehen soll */

      if ( (linksrechts!=0) || (!KannGeradeAusOP())) /* 0->stets geradeaus */
      if (lr==0)
      {  lr=1;
         if (linksrechts==3) lr=0; /* 3->stets nach rechts */
         if (!NachRechtsFallsOK())
            if (!KannGeradeAusOP())
              ergebnis=NachLinksFallsOK();
      } else
      {  lr=0;
         if (linksrechts==2) lr=1; /* 2->stets nach links */
         if (!NachLinksFallsOK())
            if (!KannGeradeAusOP())
               ergebnis=NachRechtsFallsOK();
      }

      if (!ergebnis)
      {  hms_turn(myhamster, HMS_RIGHT);
         hms_turn(myhamster, HMS_RIGHT);
         fprintf(stderr, "!F!");
      }
      /* es geht weiter */
      MyHMSGO();
      counter++;
      DrehDichEinmal();
      if (counter*2>20*HMS_MAXLOAD)
         counter=BerEntf(0,0,GetX(),GetY());
      if (kornsammeln) CheckKorn(counter);
   }
} /* GehLos */


int GetFirstKoor(int *x, int *y)
{
   if (StapelHoehe==-1) return 0;
   lauf=0;
   *x=Stapel[lauf][0];
   *y=Stapel[lauf][1];
   return 1;
}
int GetNextKoor(int *x, int *y)
{
   lauf+=1;
   if (lauf>StapelHoehe) return 0;
   *x=Stapel[lauf][0];
   *y=Stapel[lauf][1];
   return 1;
}

void SortiereKoordinaten(int vx, int vy)
{
   int i, j, v1, v2, v3;
   EntfernungsFeld feld;

	feld.EndPunkt.x=vx;    feld.EndPunkt.y=vy;
	feld.StartPunkt.x=vx;  feld.StartPunkt.y=vy;

   ErstelleEntfernungsFeld(&feld);

   for (i=0; i<=StapelHoehe; i++)   /* Entf. einspeichern */
   {   Stapel[i][2]=feld.Feld[Stapel[i][0]+FeldAdd][Stapel[i][1]+FeldAdd];  }

   /* Benutzt Insertion-Sort */
   /* Sortieren durch Einfügen */
   /* besonders ideal für "fast sortierte" Daten */
   if (StapelHoehe>0)
   for (i=1; i<=StapelHoehe; i++)
   {
      v1=Stapel[i][0]; v2=Stapel[i][1]; v3=Stapel[i][2];
      j=i;
      while ( (j>0) && (Stapel[j-1][2]<v3) )
      {
          Stapel[j][0]=Stapel[j-1][0];
          Stapel[j][1]=Stapel[j-1][1];
          Stapel[j][2]=Stapel[j-1][2];
          j--;
      }
      Stapel[j][0]=v1; Stapel[j][1]=v2; Stapel[j][2]=v3;
   }
}

   /* Ermittelt die zuletzt gefundenene unerforschte Stelle */
   /* Die Stellen wurden bei der Erkundung ermittelt */
   /* werden aber nochmal auf Gültigkeit überprüft, da */
   /* sie evtl. schon durch eine neue Route aufgeklärt wurden */
   /* return = 0 --> alles Erforscht */
   /* return = 1 --> Stelle gefunden */
int SucheNaechsteUnerforschteStelle(int vonx, int vony, int *x, int *y)
{
  if (sortieren) SortiereKoordinaten(vonx, vony);
  do
  { if (!PopKoor(x, y)) return 0; }
  while ( !ErkundungMoeglichMP(*x, *y) || !ErkundungNotwendig(*x,*y) );
  if ( ( (vonx==0) && (vony==0) ) && ( (*x!=0) && (y!=0) ) )
  {
     if ( BerEntf(*x,*y,0,0)*2 > (HMS_MAXLOAD*20) ) return 0;
  }
  return 1;
}

int GeheZumLetztenPunkt(void)
{
   int vonx, vony, nachx, nachy;

   hms_pos(myhamster, &vonx, &vony);

   if (!SucheNaechsteUnerforschteStelle(vonx, vony, &nachx, &nachy))	return 0;
   if (!GeheVonNach(vonx, vony, nachx, nachy)) return 0;

   return 1;
}


void HamsterSteuerung(void)
{
   int LabyrinthErforscht=0; /* Noch ist das Labyrinth nicht erforscht */
   fprintf(stderr, "Erkunde Labyrinth...\n");
   do
   {    GehLos();
        if ( !GeheZumLetztenPunkt() ) LabyrinthErforscht=1;
   } while ((!LabyrinthErforscht) && (!exitnow));
}

/* return = 0 --> Fehler
          = 1 --> Alles OK */
/* Darf erst aufgerufen werden, wenn alles erforscht ist, da
   der globale Stapel für die nicht erkundtschafteten Felder
   zweckempfrendet (für die Postionen der Kornhaufen) wird */
int SammelResteEin(void)
{  int x, y, zx, zy, korn, load, pushed, KeinZiel;
   EntfernungsFeld feld;

   DrehDichEinmal();

   fprintf(stderr, "\nSammle restliches Korn ein.\n");
   while ( (KornDa()) && (!exitnow) )
   {  StapelHoehe=-1;  /* Stapel löschen */

      hms_pos(myhamster, &x, &y);

	   feld.EndPunkt.x=x;   feld.EndPunkt.y=y;
	   feld.StartPunkt.x=x; feld.StartPunkt.y=y;

      if (!ErstelleEntfernungsFeld(&feld)) return 0;

      load=hms_load(myhamster);
      hms_take(myhamster, HMS_MAXLOAD);
      NeueInfos(x,y, x,y, GetPosInfo() );

      if (hms_load(myhamster)<HMS_MAXLOAD)
      {  pushed=0;
         for (x=0;x<=HMS_MAXXEXT*2+1;x++)
            for (y=0;y<=HMS_MAXYEXT*2+1;y++)
            {   if (Feld[x][y][0]>KornVerschiebung)
                {  korn=Feld[x][y][0]-KornVerschiebung;
                   if ( ( (korn+load)<HMS_MAXLOAD ) &&
                        ( ( 1.666*feld.Feld[x][y] )<(korn-load)*20)
                      )
                   {  PushKoor(x-FeldAdd,y-FeldAdd);
                      pushed=1;
                   }
                }
            }
            if (!pushed) /* falls kein Kornhaufen klein genug ist */
            {      /* das ganze nochmal aber unabh. von der Kornmenge */
               for (x=0;x<=HMS_MAXXEXT*2+1;x++)
                  for (y=0;y<=HMS_MAXYEXT*2+1;y++)
                  {  korn=Feld[x][y][0];
                     if ( (korn>KornVerschiebung) &&
                          ( ( 1.666*feld.Feld[x][y] ) < (korn-load)*20) )
                     {  PushKoor(x-FeldAdd,y-FeldAdd);  }
                  }
            }
         hms_pos(myhamster, &x, &y);
         SortiereKoordinaten(x,y);  /* Korn-Postionen nach Entf. sortieren */
         if (!PopKoor(&zx, &zy)) KeinZiel=1; else KeinZiel=0;
      } else
      { zx=0; zy=0; }
      if (!KeinZiel)
      { if ( (feld.Feld[x][y]+BerEntf(zx,zy,0,0))<korn*20 ) KeinZiel=1; }
      if (KeinZiel)
      { if ( (x==0) && (y==0) ) return 1;
        GeheVonNach(x,y,0,0);
      } else
      GeheVonNach(x,y,zx,zy);
   }
   hms_pos(myhamster, &x, &y);
   load=hms_load(myhamster);
   if (load>0) GeheVonNach(x,y,0,0);
   return 1;
}

void LabInit(void)
{  int x,y;
   for (x=0;x<=HMS_MAXXEXT*2+1;x++)
      for (y=0;y<=HMS_MAXYEXT*2+1;y++)
      {  Feld[x][y][0]=FeldUnbekannt;       /* Feld-Typ setzen */
      	Feld[x][y][N]=1; Feld[x][y][S]=1;
         Feld[x][y][W]=1; Feld[x][y][E]=1;  /* Überall Mauern */
      }
}

void ViewVerhalten(void)
{
  fprintf(stderr, "\n---------------- Hamster-Verhalten ---------------\n");
  fprintf(stderr, "Hamster geht ");
  if (linksrechts==3)
     fprintf(stderr, "stets nach rechts."); else
  if (linksrechts==2)
     fprintf(stderr, "stets nach links."); else
  if (linksrechts==1)
     fprintf(stderr, "abwechselnd nach rechts und nach links. (+)"); else
  if (linksrechts==0)
     fprintf(stderr, "stets geradeaus."); else
     fprintf(stderr, "undefiniert. (Fehler)");

  if (kornsammeln) fprintf(stderr, "\nHamster sammelt Korn. (+)"); else
                   fprintf(stderr, "\nHamster sammelt das Korn später.");

  if (sortieren) fprintf(stderr, "\nZielkoordinaten werden sortiert. (+)"); else
                 fprintf(stderr, "\nZielkoordinaten werden nicht sortiert.");
  fprintf(stderr, "\n--------------------------------------------------\n");
}

void hms_ctrl (HAMSTER *hms)
{
  fprintf(stderr, "Hamsterprogramm gestartet... ");
  ViewVerhalten();
  myhamster=hms;
  LabInit();				                    /* Labyrint-Startwerte setzen */
  HamsterSteuerung();
  if (!exitnow)
  {
     SammelResteEin();
     fprintf(stderr, "\nHamsterprogramm wird regulär beendet. ");
     fprintf(stderr, "Punktestand: %d\n", punkte);
  }
}