/*_______________________________________________________________________________________
  File    : hamster8.c
  Contents: hamster control program
  Author  : Stefan Weidner
  History : 16.10.1997 file created by Christian Borgelt
			18.01.1998 first changes (more steps, first decisions, ...)
			27.02.1998 first explorations -> array lab[][] (north,east,south,west)
			31.03.1998 improve lab[][] (explored,corn), first case instructions
			01.04.1998 decision-making on directions (wall positions)
			05.04.1998 block blind alleys (from the end to the entry)
			23.04.1998 notice way back
			20.05.1998 avoid cross ways / correct way back
			28.05.1998 first test: best_way (lab[][].best)/ opt_way (shortest way back)
			01.06.1998 improve decision-making (hms_corn_around, hms-_unexplored, ...)
			09.06.1998 opt_way (shortest way back), empty_cnt
			12.06.1998 last optimizations
  _______________________________________________________________________________________*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "hamster.h"

/*_______________________________________________________________________________________
  Initialisierung Struktur Feld, um Eigenschaften eines jeden Labyrinthfeldes abspeichern 
  zu können:
			explored			  - Feld erforscht / nicht erforscht
			north,west,south,east - Informationen über angrenzende Felder
			corn				  - aktuelle Kornmenge auf Feld
  _______________________________________________________________________________________*/

struct Feld
	{ char explored, north, west, south, east, corn;
	  int best;
/* Start Korrektur, Christian Borgelt, 25.06.1998 */
/* Da die Initialisierung mit ``={0,0,0,0,0,0,4096};'' sowieso ohne */
/* Wirkung ist, weil es in hms_ctrl eine Schleife gibt, die die */
/* ganze Matrix initialisiert, kann sie auch weggelassen werden. */
/* I.a. wird das ausf"uhrbare Programm dadurch deutlich kleiner. */
#if 0
	} lab[130][130] = {0,0,0,0,0,0,4096};			     /* Erklärung siehe 4.1 best_way */
#else
	} lab[130][130];    /* Erklärung siehe 4.1 best_way */
#endif
/* Ende Korrektur, Christian Borgelt, 25.06.1998 */

/*_______________________________________________________________________________________
  Funktion zum Speichern folgender Informationen noch nicht erforschter Felder in lab[][]:
   forward, left, right : 0 - leeres Feld
						  1 - Feld mit Korn
						  2 - Wand
   explored				: 1 - Feld jetzt erforscht
   corn					: aktuelle Kornmenge
  _______________________________________________________________________________________*/

void explore (HAMSTER *hms,int x, int y, char *way, int i)  
{ char forward, left, right;										  /* Blickrichtungen */
  forward = hms_look(hms);
  hms_turn(hms,1); left = hms_look(hms);
  hms_turn(hms,-1); hms_turn(hms,-1); right = hms_look(hms);  
  hms_turn(hms,1);
  lab[x][y].explored = 1;										   /* Feld nun erforscht */
  lab[x][y].corn = hms_corn(hms);								   /* aktuelle Kornmenge */
  
  switch (way[i-1])			             /* Belegung von lab[][].{north,east,south,west} */
  { case 0 : lab[x][y].west  = forward;  /* richtet sich nach Blickrichtung des Hamsters */
			 lab[x][y].south = left; 
			 lab[x][y].north = right; 
			 break;
	case 1 : lab[x][y].south = forward; 
			 lab[x][y].east  = left; 
			 lab[x][y].west  = right; 
			 break; 
	case 2 : lab[x][y].east  = forward; 
			 lab[x][y].north = left; 
			 lab[x][y].south = right; 
			 break;
	case 3 : lab[x][y].north = forward; 
			 lab[x][y].west  = left; 
			 lab[x][y].east  = right; 
			 break; 
  }			 
}


/*_______________________________________________________________________________________		
  Funktion zum Berechnen des Minimums eines Zahlenquadrupels
  _______________________________________________________________________________________*/

int min4(int a, int b, int c, int d)
{ if (b<a) a=b;
  if (c<a) a=c;
  if (d<a) a=d;
  return a;
}


/*_______________________________________________________________________________________		
  Funktion zur Belegung des Wertes lab[][].best, der den minimalen Weg zum Ausgangsfeld 
  angibt 
  _______________________________________________________________________________________*/

int best_way (int x, int y)
{ int count=0;	 						 /* Erläuterung Hilfsvariable siehe 4.1 best_way */
  if (lab[x][y].east!=2)  count+=1; 
  if (lab[x][y].north!=2) count+=2;
  if (lab[x][y].west!=2)  count+=4;
  if (lab[x][y].south!=2) count+=8;
  switch (count)										   /* Prinzip siehe 4.1 best_way */
  { case 1  : return lab[x+1][y].best+1;			  
    case 2  : return lab[x][y+1].best+1;
    case 3  : return min4(lab[x+1][y].best,lab[x][y+1].best,500,500)+1;
    case 4  : return lab[x-1][y].best+1;
	case 5  : return min4(lab[x+1][y].best,lab[x-1][y].best,500,500)+1;
	case 6  : return min4(lab[x][y+1].best,lab[x-1][y].best,500,500)+1;
	case 7  : return min4(lab[x+1][y].best,lab[x][y+1].best,
						  lab[x-1][y].best,500)+1;
	case 8  : return lab[x][y-1].best+1;
	case 9  : return min4(lab[x+1][y].best,lab[x][y-1].best,500,500)+1;
	case 10 : return min4(lab[x][y+1].best,lab[x][y-1].best,500,500)+1;
	case 11 : return min4(lab[x+1][y].best,lab[x][y+1].best,
					      lab[x][y-1].best,500)+1;
	case 12 : return min4(lab[x-1][y].best,lab[x][y-1].best,500,500)+1;
	case 13 : return min4(lab[x+1][y].best,lab[x-1][y].best,
						  lab[x][y-1].best,500)+1;
	case 14 : return min4(lab[x][y+1].best,lab[x-1][y].best,
						  lab[x][y-1].best,500)+1;
	case 15 : return min4(lab[x+1][y].best,lab[x][y+1].best,
						  lab[x-1][y].best,lab[x][y-1].best)+1;
  }
}


/*_______________________________________________________________________________________		 
  Funktion zur Überprüfung des Rückweges auf Doppelfelder. 
  Prinzip: Durch Rekursion werden alle betretenen Felder zurückberechnet. Wenn das 
		   aktuelle Feld schon einmal besucht war, wird das Indizé [i-1] bzw. [a] auf 
		   das alte zurückgesetzt.
           Falls dies nicht der Fall ist, wird i zurückgegeben.	
  _______________________________________________________________________________________*/

unsigned char hms_cross (char *way, int i)
{ int x=0,y=0,a=i-1;							 /* x,y - temporäre Koordinatenvariablen */
  char stopped=0;								                     /* a - Laufvariable */
  while ((way[a]!=-1)&&(!stopped))							/* stopped - Abbruchvariable */
  { switch (way[a])
	{ case 0 : x++; break;
	  case 1 : y++; break;
	  case 2 : x--; break;
	  case 3 : y--; break;
	}
    if ((x==0)&&(y==0)) return a;   /* Rückgabe neues Indizé a bei Erreichung Doppelfeld */
    a--;
  }
  return i;											 /* Rückgabe ursprüngliches Indizé i */
}  


/*_______________________________________________________________________________________
  Funktion zum Blockieren von Sackgassen, indem im Rücken des Hamsters eine imaginäre 
  Wand gesetzt wird
  _______________________________________________________________________________________*/

void block (HAMSTER *hms, int x, int y)
{ switch (hms_dir(hms))
	{ case 0 : lab[1+x][y].west   = 2; break;
	  case 1 : lab[x][1+y].south  = 2; break;
	  case 2 : lab[-1+x][y].east  = 2; break;
	  case 3 : lab[x][-1+y].north = 2; break;
	}
}


/*_______________________________________________________________________________________
  Funktion zum Überprüfung auf Wände (auch imaginär)
  Wenn Wand vor Hamster, dann 1, sonst 0
  _______________________________________________________________________________________*/

char hms_wall (HAMSTER *hms, int x, int y)    /* Überprüfen, ob geradeaus eine Wand */
{ switch (hms_dir(hms))
  { case 0 : return (lab[64+x][64+y].east == 2 ? 1 : 0);  break; 
    case 1 : return (lab[64+x][64+y].north == 2 ? 1 : 0); break;
	case 2 : return (lab[64+x][64+y].west == 2 ? 1 : 0);  break;
	case 3 : return (lab[64+x][64+y].south == 2 ? 1 : 0); break;
  }
}

/*_______________________________________________________________________________________		
  Funktion zur Bestimmung eines Wertes x mit:

              x = 1 , wenn auf einem Nachbarfeld Korn liegt
              x = 0 , wenn dort kein Korn liegt
  _______________________________________________________________________________________*/

char hms_corn_around (int x, int y)
{ return (((lab[64+x][64+y].north == 1) || (lab[64+x][64+y].east == 1) || 
           (lab[64+x][64+y].south == 1) || (lab[64+x][64+y].west == 1)
		  ) ? 1 : 0
		 );
}


/*_______________________________________________________________________________________		
  Funktion zur Bestimmung eines Wertes x mit:

              x = -1   , wenn alle Nachbarfelder erforscht sind
              x = 0..3 , wenn ein Nachbarfeld unerforscht ist (Himmelsrichtung)
  _______________________________________________________________________________________*/

char hms_unexplored (int x, int y)
{ if (!(lab[x+1][y].explored)&&(lab[x][y].east!=2))  return 0;
  if (!(lab[x][y+1].explored)&&(lab[x][y].north!=2)) return 1;  
  if (!(lab[x-1][y].explored)&&(lab[x][y].west!=2))  return 2;
  if (!(lab[x][y-1].explored)&&(lab[x][y].south!=2)) return 3;
  return -1;
}


/*_______________________________________________________________________________________		
  Funktion zur Berechnung des kürzesten Rückweges zum Ausgangsfeld, indem bei
  jedem Schritt die optimale Richtung bestimmt wird
  _______________________________________________________________________________________*/ 

int opt_way (int x, int y)
{ int count=0;						 /* Erläuterung Hilfsvariable siehe 4. ..... opt_way */
  if (lab[x][y].east!=2)  count+=1; 
  if (lab[x][y].north!=2) count+=2;
  if (lab[x][y].west!=2)  count+=4;
  if (lab[x][y].south!=2) count+=8;
  switch (count)
  { case 1 : return 0;								  /* Prinzip siehe 4. ..... best_way */
    case 2 : return 1; 
    case 3 : return (min4(lab[x+1][y].best,lab[x][y+1].best,500,500)
		   		      == lab[x+1][y].best ? 0 : 1);
    case 4 : return 2;
	case 5 : return (min4(lab[x+1][y].best,lab[x-1][y].best,500,500)
					  == lab[x+1][y].best ? 0 : 2);
	case 6 : return (min4(lab[x][y+1].best,lab[x-1][y].best,500,500)
					  == lab[x][y+1].best ? 1 : 2);
	case 7 : if (min4(lab[x+1][y].best,lab[x][y+1].best,
				 	   lab[x-1][y].best,500) == lab[x+1][y].best) return 0;
			  return (min4(lab[x+1][y].best,lab[x][y+1].best,
					  	   lab[x-1][y].best,500) == lab[x][y+1].best ? 1 : 2);
	case 8 : return 3;
	case 9 : return (min4(lab[x+1][y].best,lab[x][y-1].best,500,500)
					  == lab[x+1][y].best ? 0 : 3);
	case 10 : return (min4(lab[x][y+1].best,lab[x][y-1].best,500,500)
					  == lab[x][y+1].best ? 1 : 3);
	case 11 : if (min4(lab[x+1][y].best,lab[x][y+1].best,
				       lab[x][y-1].best,500) == lab[x+1][y].best) return 0;
			  return (min4(lab[x+1][y].best,lab[x][y+1].best,
						   lab[x][y-1].best,500) == lab[x][y+1].best ? 1 : 3); 
	case 12 : return (min4(lab[x-1][y].best,lab[x][y-1].best,500,500)
					  == lab[x-1][y].best ? 2 : 3);
	case 13 : if (min4(lab[x+1][y].best,lab[x-1][y].best,
					   lab[x][y-1].best,500) == lab[x+1][y].best) return 0;
		  	  return (min4(lab[x+1][y].best,lab[x-1][y].best,
					       lab[x][y-1].best,500) == lab[x-1][y].best ? 2 : 3);
	case 14 : if (min4(lab[x][y+1].best,lab[x-1][y].best,
					   lab[x][y-1].best,500) == lab[x][y+1].best) return 1;
			  return (min4(lab[x][y+1].best,lab[x-1][y].best,
						   lab[x][y-1].best,500) == lab[x-1][y].best ? 2 : 3);
	case 15 : if (min4(lab[x+1][y].best,lab[x][y+1].best,
  					   lab[x-1][y].best,lab[x][y-1].best) == lab[x+1][y].best)
			     return 0;			
			  if (min4(lab[x+1][y].best,lab[x][y+1].best,
  					   lab[x-1][y].best,lab[x][y-1].best) == lab[x][y+1].best)	
				 return 1;
			  return (min4(lab[x+1][y].best,lab[x][y+1].best,
					  	   lab[x-1][y].best,lab[x][y-1].best)
					  == lab[x-1][y].best ? 2 : 3);
  }	
}


	
/*_______________________________________________________________________________________
  Hamsterkontrollprogramm
  _______________________________________________________________________________________*/

void hms_ctrl (HAMSTER *hms)
{ char forward, left, right;										  /* Blickrichtungen */                
  int  x, y;													   /* Positionsvariablen */ 
  char no_way = 0, brain, turn;											/* Zählvariablen */
  short int move_cnt = 0, empty_cnt = 0;								/* Zählvariablen */
  short int a, b, i = 1, j = 0;											/* Zählvariablen */
  char way[200];															  /* Rückweg */
  
  way[0] = -1;													  /* Anfangswert Rückweg */    
  srand;											 /* Initialisierung Zufallsgenerator */

  /* Anfangsbelegung Speicherarray */

  /* Anfang Korrektur, Christian Borgelt, 15.06.1998 */
  /* lab is definiert als lab[130][130], d.h. diese Matrix kann mit */
  /* Indices 0 bis 129 angesprochen werden. Die untigen Schleifen */
  /* werden jedoch auch f"ur einen Index von 130 ausgef"uhrt. Dies */
  /* f"uhrt zu einer schweren Speicherverletzung und damit zu einem */
  /* Programmabsturz. Korrekt sind Schleifenbedingungen < 130, s.u. */
#if 1
  for(a=0;a<130;a++)
   for(b=0;b<130;b++)
#else
  for(a=0;a<=130;a++)
   for(b=0;b<=130;b++)
#endif
  /* Ende Korrektur, Christian Borgelt, 15.06.1998 */
   { lab[a][b].explored=0;
	 lab[a][b].north=0;
	 lab[a][b].east=0;
	 lab[a][b].south=0;
	 lab[a][b].west=0;
	 lab[a][b].corn=0;
	 lab[a][b].best=4096;
   }
   
  /* Anfangsfeld */ 
    
  lab[64][64].east  = hms_look(hms);  hms_turn(hms,-1);				/* Himmelsrichtungen */
  lab[64][64].south = hms_look(hms);  hms_turn(hms,-1);
  lab[64][64].west  = hms_look(hms);  hms_turn(hms,-1);
  lab[64][64].north = hms_look(hms); 
  lab[64][64].explored = 1;											   /* Feld erforscht */
  lab[64][64].best = 0;											 /* Rückweg Ursprung = 0 */

  while ((move_cnt < 200)&&(empty_cnt<10))           /* Erklärung siehe 4.2 Struktogramm */
  {	hms_pos(hms, &x, &y);										   /* Position bestimmen */ 
    if (!(lab[64+x][64+y].explored)) explore(hms,64+x,64+y,way,i);    /* Feld erforschen */
    if ((x == 0) && (y == 0))										/* wenn Ausgangsfeld */
	{ no_way = 0;
	  if (hms_load(hms)==0) empty_cnt++;
	  else empty_cnt=0;
	  hms_drop(hms, HMS_MAXLOAD); 										 /* Mais ablegen */
	  move_cnt = 0;      
	  i = 1;		
	}
    else if (hms_corn(hms))					                       /* wenn Mais auf Feld */
		{ hms_take(hms, HMS_MAXLOAD);								   /* Mais aufnehmen */
	      lab[64+x][64+y].corn = hms_corn(hms);						 /* Korn-Info ändern */
		  if (!(hms_corn(hms)))                        /* Korn-Info Nachbarfelder ändern */
		  { if (lab[64+x][65+y].south != 2) lab[64+x][65+y].south = 0;
		    if (lab[64+x][63+y].north != 2) lab[64+x][63+y].north = 0; 
			if (lab[65+x][64+y].west  != 2) lab[65+x][64+y].west  = 0; 
			if (lab[63+x][64+y].east  != 2) lab[63+x][64+y].east  = 0; 
		  }
		}   
    if (hms_load(hms) < HMS_MAXLOAD)						   /* wenn Backen nicht voll */
	{ brain = 0;			  
	  switch (hms_dir(hms))				  /* Umwandlung Labyrinth-Infos in Fall-Variable */
	  { case 0 : forward = lab[64+x][64+y].east;
				 left    = lab[64+x][64+y].north;
				 right   = lab[64+x][64+y].south; break;
	    case 1 : forward = lab[64+x][64+y].north;
				 left    = lab[64+x][64+y].west;
				 right   = lab[64+x][64+y].east;  break; 
		case 2 : forward = lab[64+x][64+y].west;
				 left    = lab[64+x][64+y].south;
				 right   = lab[64+x][64+y].north; break;
		case 3 : forward = lab[64+x][64+y].south;
				 left    = lab[64+x][64+y].east;
				 right   = lab[64+x][64+y].west;  break;
	  }
	  if (forward == 2) brain+=1;    
	  if (left == 2)    brain+=2;
	  if (right == 2)   brain+=4; 
	  if (hms_corn_around(x,y))							 /* wenn Korn auf Nachbarfeldern */
	  { while (hms_look(hms) != HMS_CORN) hms_turn(hms,1);  /* drehen, bis Mais zu sehen */
	    no_way = 0;		
	  }
	  else  if (hms_unexplored(64+x,64+y)!=-1)         /* wenn unerforschtes Nachbarfeld */
	  { while (hms_unexplored(64+x,64+y)!=hms_dir(hms)) hms_turn(hms,1);
	    no_way=0;									   /* drehen, bis unerforschtes Feld */
	  }
      else switch (brain)										/* Abfrage Fall-Variable */
	  { case 0 : if (no_way)			             /* Erklärung siehe 4.2 Struktogramm */
				 { no_way = 0; 
				   do  hms_turn(hms,1);  
				   while ((hms_dir(hms) == way[i-1]) || (hms_wall(hms,x,y)));				      
				 }
				 else if (!(rand() % 2)) break;                /* 2 : 1 Chance forward ! */
					  else brain++; 	              
		case 1 : if (no_way) 
				 { no_way = 0; 
				   do  hms_turn(hms,1); 
				   while ((hms_dir(hms) == way[i-1]) || (hms_wall(hms,x,y)));
				 }
			     else { turn = (rand() % 2 ? 1 : -1); hms_turn(hms,turn); }
				 break;								       /* 1 : 1 Chance right :left ! */
		case 2 : if (no_way) 
				 { no_way = 0; 	
				   do  hms_turn(hms,1); 
				   while ((hms_dir(hms) == way[i-1]) || (hms_wall(hms,x,y)));				      
				 }
				 else if (!(rand() % 3)) hms_turn(hms,-1); 
				 break;										   /* 2 : 1 Chance forward ! */
	    case 3 : hms_turn(hms,-1);
			     if (no_way) { i--; block(hms,64+x,64+y); } break; 
		case 4 : if (no_way)
				 { no_way = 0;  
				   do  hms_turn(hms,1);
				   while ((hms_dir(hms) == way[i-1]) || (hms_wall(hms,x,y)));				      
				 }
				 else if (!(rand() % 3)) hms_turn(hms,1); 
				 break;										   /* 2 : 1 Chance forward ! */
		case 5 : hms_turn(hms,1);
			     if (no_way) { i--; block(hms,64+x,64+y); } break; 
		case 6 : if (no_way) { i--; block(hms,64+x,64+y); } break; 
		case 7 : hms_turn(hms,1); hms_turn(hms,1);						    /* Sackgasse */
				 if (!(lab[64+x][64+y].corn) && ((x) || (y)))   
				 { no_way = 1; i--; block(hms,64+x,64+y); }	
				 if ((lab[64+x][64+y].corn) && ((x)||(y)))   
				 { no_way = 1; i++; } 
				 break; 
	  }	
	
	  if ((x)||(y))	lab[64+x][64+y].best=best_way(64+x,64+y);	   /* Belegung best-Wert */
	  hms_move(hms); move_cnt++;									  /* Hamster bewegen */
	  if (!(no_way)) 
	  { switch (hms_dir(hms))										 /* Belegung Rückweg */
		{ case 0 : way[i] = 2; break;
		  case 1 : way[i] = 3; break;
	      case 2 : way[i] = 0; break;
		  case 3 : way[i] = 1; break;
		} 
	  i++;
	  i=hms_cross(way,i);									/* Überprüfung auf Schlangen */
	  }
	} 
	else
	{ while (hms_dir(hms) != opt_way(64+x,64+y)) hms_turn(hms,1);   /* optimaler Rückweg */  
      hms_move(hms); move_cnt++; i--;								  /* Hamster bewegen */
	}
  }
}