/*----------------------------------------------------------------------
  File    : cdhamster.c
  Contents: hamster control program
  Author  : Christian Decomain
  Version : 0.01.002
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "hamster.h"

                                       /* field status constants */
#define FIELD_UNKNOWN   0
#define FIELD_UNVISITED 1
#define FIELD_VISITED   2
#define FIELD_START     3


typedef struct {                       /* a field of the maze */
  int stat;                            /* status of the field */
  int corn;                            /* amount of corn on the field */
  int e;                               /* status of the northern neighbor */
  int n;                               /* status of the eastern neighbor */
  int w;                               /* status of the southern neighbor */
  int s;                               /* status of the western neighbor */
  int dist;                            /* distance to start field */
  int bfsval;                          /* distance value for bfs */
  int bfsdir;                          /* direction value for bfs */
} TFIELD;
typedef struct posxy{                  /* position structure */
  int x;
  int y;
} TPOS;
typedef struct queue{                  /* queue for bfs */
  struct posxy key;
  struct queue *next;
} TQUEUE;
typedef struct stack{                  /* stack for backtracking */
  int key;
  struct stack *next;
} TSTACK;

/* forward declarations */
int look   (HAMSTER *hms,              /* look and update map */
            int dir,
            TPOS pos,
            TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1]);
int turn   (HAMSTER *hms,              /* turn and return new direction */
            int turn);
int move   (HAMSTER *hms,              /* move forward and update position */
            int dir,
            TPOS *ppos);
int mindist(TPOS pos,                  /* neighbors' min home dist */
            TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1]);
int mindir (TPOS pos,                  /* neighbor with min home dist */
            TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1]);
TQUEUE *qpusht(TQUEUE *queue,          /* pushtail to queue */
            TPOS pos);
TQUEUE *qpop(TQUEUE *queue,            /* pop from queue */
            TPOS *pos);
int qempty (TQUEUE *queue);            /* queue empty? */
TSTACK *spush(TSTACK *stack,           /* push to stack */
            int n);
TSTACK *spop(TSTACK *stack,            /* pop from stack */
            int *n);
int sempty (TSTACK *stack);            /* stack empty */
void bfsdist(TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1]);
                                       /* set map[][].dist indices */

/* hamster control function */
void hms_ctrl (HAMSTER *hms)
{
  TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1]; /* map of the maze */
  TPOS   pos;                          /* position of hamster in map */
  TPOS   tmppos,tmppos2,result;        /* temporaty positon values */
  int    dir;                          /* direction of hamsters view */
  int    unvcnt = 0;                   /* counter for unvisited fields */
  int    corncnt = 0;                  /* counter for all corn in maze */
  int    i1, i2;                       /* some index variables */
  int    ret;                          /* integer return value */
  int    found;                        /* another integer value */
  TQUEUE *queue=NULL;                  /* a queue for bfs calculations */
  TSTACK *stack=NULL;                  /* a stack for backtracking */

                                       /* initialize the map */
  for (i1=0; i1<HMS_MAXXEXT*2+1; i1++) {
    for (i2=0; i2<HMS_MAXYEXT*2+1; i2++) {
      map[i1][i2].stat = FIELD_UNKNOWN;
      map[i1][i2].corn = 0;
      map[i1][i2].e = map[i1][i2].n = map[i1][i2].w = map[i1][i2].s
	= HMS_EMPTY;
      map[i1][i2].dist = INT_MAX;
    }
  }
  map[HMS_MAXXEXT][HMS_MAXYEXT].stat = FIELD_START;
  map[HMS_MAXXEXT][HMS_MAXYEXT].dist = 0;
  
                                       /* initialize the hamster stats */
  pos.x  = HMS_MAXXEXT;
  pos.y  = HMS_MAXYEXT;
  dir    = hms_dir(hms);

                                       /* let's look around */
  unvcnt += look(hms, dir, pos, map);
  dir     = turn(hms, HMS_LEFT);
  unvcnt += look(hms, dir, pos, map);
  dir     = turn(hms, HMS_LEFT);
  unvcnt += look(hms, dir, pos, map);
  dir     = turn(hms, HMS_LEFT);
  unvcnt += look(hms, dir, pos, map);

  while (unvcnt > 0) {                 /* walk through the maze */
    for (i1=0; i1<HMS_MAXXEXT*2+1; i1++) {
      for (i2=0; i2<HMS_MAXYEXT*2+1; i2++) {
	map[i1][i2].bfsval=INT_MAX;
      }
    }
    map[pos.x][pos.y].bfsval=0;
    queue=qpusht(queue,pos);
    found = 0;
    while (!qempty(queue)) {          /* do bfs for nearest unvis. field */
      queue=qpop(queue, &tmppos);
      if ((map[tmppos.x][tmppos.y].e!=HMS_WALL)&& 
	  (map[tmppos.x+1][tmppos.y].bfsval==INT_MAX)) {
	tmppos2.x=tmppos.x+1;
	tmppos2.y=tmppos.y;
	map[tmppos2.x][tmppos2.y].bfsval=map[tmppos.x][tmppos.y].bfsval+1;
	map[tmppos2.x][tmppos2.y].bfsdir=HMS_EAST;
	if (map[tmppos2.x][tmppos2.y].stat==FIELD_UNVISITED) {
	  if (found) {
	    if ((abs(tmppos2.x-HMS_MAXXEXT)+abs(tmppos2.y-HMS_MAXYEXT))<
		(abs(result.x -HMS_MAXXEXT)+abs(result.y -HMS_MAXYEXT))) {
	      result=tmppos2;
	    }
	  } else {
	    result=tmppos2;
	    found=1;
	  }
	} else {
	  if (!found) queue=qpusht(queue,tmppos2);
	}
      }
      if ((map[tmppos.x][tmppos.y].n!=HMS_WALL)&& 
	  (map[tmppos.x][tmppos.y+1].bfsval==INT_MAX)) {
	tmppos2.x=tmppos.x;
	tmppos2.y=tmppos.y+1;
	map[tmppos2.x][tmppos2.y].bfsval=map[tmppos.x][tmppos.y].bfsval+1;
	map[tmppos2.x][tmppos2.y].bfsdir=HMS_NORTH;
	if (map[tmppos2.x][tmppos2.y].stat==FIELD_UNVISITED) {
	  if (found) {
	    if ((abs(tmppos2.x-HMS_MAXXEXT)+abs(tmppos2.y-HMS_MAXYEXT))<
		(abs(result.x -HMS_MAXXEXT)+abs(result.y -HMS_MAXYEXT))) {
	      result=tmppos2;
	    }
	  } else {
	    result=tmppos2;
	    found=1;
	  }
	} else {
	  if (!found) queue=qpusht(queue,tmppos2);
	}
      }
      if ((map[tmppos.x][tmppos.y].w!=HMS_WALL)&& 
	  (map[tmppos.x-1][tmppos.y].bfsval==INT_MAX)) {
	tmppos2.x=tmppos.x-1;
	tmppos2.y=tmppos.y;
	map[tmppos2.x][tmppos2.y].bfsval=map[tmppos.x][tmppos.y].bfsval+1;
	map[tmppos2.x][tmppos2.y].bfsdir=HMS_WEST;
	if (map[tmppos2.x][tmppos2.y].stat==FIELD_UNVISITED) {
	  if (found) {
	    if ((abs(tmppos2.x-HMS_MAXXEXT)+abs(tmppos2.y-HMS_MAXYEXT))<
		(abs(result.x -HMS_MAXXEXT)+abs(result.y -HMS_MAXYEXT))) {
	      result=tmppos2;
	    }
	  } else {
	    result=tmppos2;
	    found=1;
	  }
	} else {
	  if (!found) queue=qpusht(queue,tmppos2);
	}
      }
      if ((map[tmppos.x][tmppos.y].s!=HMS_WALL)&& 
	  (map[tmppos.x][tmppos.y-1].bfsval==INT_MAX)) {
	tmppos2.x=tmppos.x;
	tmppos2.y=tmppos.y-1;
	map[tmppos2.x][tmppos2.y].bfsval=map[tmppos.x][tmppos.y].bfsval+1;
	map[tmppos2.x][tmppos2.y].bfsdir=HMS_SOUTH;
	if (map[tmppos2.x][tmppos2.y].stat==FIELD_UNVISITED) {
	  if (found) {
	    if ((abs(tmppos2.x-HMS_MAXXEXT)+abs(tmppos2.y-HMS_MAXYEXT))<
		(abs(result.x -HMS_MAXXEXT)+abs(result.y -HMS_MAXYEXT))) {
	      result=tmppos2;
	    }
	  } else {
	    result=tmppos2;
	    found=1;
	  }
	} else {
	  if (!found) queue=qpusht(queue,tmppos2);
	}
      }
    }
    tmppos=result;                     /* compute way to field */
    for(i1=map[result.x][result.y].bfsval;i1>0;i1--){
      stack=spush(stack, map[tmppos.x][tmppos.y].bfsdir);
      switch (map[tmppos.x][tmppos.y].bfsdir) {
      case HMS_EAST: 
	tmppos.x--;
	break;
      case HMS_NORTH:
	tmppos.y--;
	break;
      case HMS_WEST:
	tmppos.x++;
	break;
      case HMS_SOUTH:
	tmppos.y++;
	break;
      }
    }
    while (!sempty(stack)) {           /* move to computed field */
      stack=spop(stack, &ret);
      while (dir!=ret) dir=turn(hms, HMS_LEFT);
      move(hms, dir, &pos);
    }
                                       /* look around and update map */
    unvcnt += look(hms, dir, pos, map);
    dir     = turn(hms, HMS_LEFT);
    unvcnt += look(hms, dir, pos, map);
    dir     = turn(hms, HMS_LEFT);
    dir     = turn(hms, HMS_LEFT);
    unvcnt += look(hms, dir, pos, map);
    map[pos.x][pos.y].stat=FIELD_VISITED;
    unvcnt--;
    corncnt+=map[pos.x][pos.y].corn=hms_corn(hms);
    /*map[pos.x][pos.y].dist=mindist(pos,map)+1;*/
    bfsdist(map);

    if (map[pos.x][pos.y].corn) {      /* if corn on field */
      ret = hms_take(hms, HMS_MAXLOAD);/* take corn */
      corncnt -= ret;
      map[pos.x][pos.y].corn -= ret;
      while (map[pos.x][pos.y].corn) { /* if still corn on field */
	while (map[pos.x][pos.y].dist>0) { /* move home */
	  while (dir!=mindir(pos, map)) {
	    dir = turn(hms, HMS_LEFT);
	  }
	  move(hms, dir, &pos);
	  stack=spush(stack,dir);      /* store way home */
	}
	hms_drop(hms, HMS_MAXLOAD);    /* drop loaded corn */
	while (!sempty(stack)) {       /* backtrack */
	  stack=spop(stack, &ret);
	  switch (ret) {
	  case HMS_EAST:
	    while (dir!=HMS_WEST) {
	      dir = turn(hms, HMS_LEFT);
	    }
	    break;
	  case HMS_NORTH:
	    while (dir!=HMS_SOUTH) {
	      dir = turn(hms, HMS_LEFT);
	    }
	    break;
	  case HMS_WEST:
	    while (dir!=HMS_EAST) {
	      dir = turn(hms, HMS_LEFT);
	    }
	    break;
	  case HMS_SOUTH:
	    while (dir!=HMS_NORTH) {
	      dir = turn(hms, HMS_LEFT);
	    }
	    break;
	  }
	  move(hms, dir, &pos);
	}
	ret = hms_take(hms, HMS_MAXLOAD);/* take corn */
	corncnt -= ret;
	map[pos.x][pos.y].corn -= ret;
      }
      if (hms_load(hms)==HMS_MAXLOAD) {
	while (map[pos.x][pos.y].dist>0) { /* move home */
	  while (dir!=mindir(pos, map)) {
	    dir = turn(hms, HMS_LEFT);
	  }
	  move(hms, dir, &pos);
	}
	hms_drop(hms, HMS_MAXLOAD);
      }
    }
  }

  if (20*hms_load(hms)>map[pos.x][pos.y].dist) {
    while (map[pos.x][pos.y].dist>0) { /* move home */
      while (dir!=mindir(pos, map)) {
	dir = turn(hms, HMS_LEFT);
      }
      move(hms, dir, &pos);
    }
    hms_drop(hms, HMS_MAXLOAD);
  }
    
}

/* enhanced hms_look */
int look (HAMSTER *hms,
          int dir,
          TPOS pos,
          TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1])
{
  int ir;                              /* storage of integer results */
  int unvcnt = 0;                      /* counter for unvisited fields */

  ir = hms_look(hms);                  /* look forward */
  switch (dir) {                       /* update map */
  case HMS_EAST:
    map[pos.x][pos.y].e = ir;
    if ((ir != HMS_WALL) && (map[pos.x+1][pos.y].stat == FIELD_UNKNOWN)){
      map[pos.x+1][pos.y].stat = FIELD_UNVISITED;
      unvcnt++;
    }
    break;
  case HMS_NORTH:
    map[pos.x][pos.y].n = ir;
    if ((ir != HMS_WALL) && (map[pos.x][pos.y+1].stat == FIELD_UNKNOWN)){
      map[pos.x][pos.y+1].stat = FIELD_UNVISITED;
      unvcnt++;
    }
    break;
  case HMS_WEST:
    map[pos.x][pos.y].w = ir;
    if ((ir != HMS_WALL) && (map[pos.x-1][pos.y].stat == FIELD_UNKNOWN)){
      map[pos.x-1][pos.y].stat = FIELD_UNVISITED;
      unvcnt++;
    }
    break;
  case HMS_SOUTH:
    map[pos.x][pos.y].s = ir;
    if ((ir != HMS_WALL) && (map[pos.x][pos.y-1].stat == FIELD_UNKNOWN)){
      map[pos.x][pos.y-1].stat = FIELD_UNVISITED;
      unvcnt++;
    }
    break;
  }
  return unvcnt;
}

/* enhanced hms_turn */
int turn (HAMSTER *hms, int turn)
{
  hms_turn(hms, turn);                 /* turn hamster */
  return hms_dir(hms);                 /* return new hamster direction */
}

/* move forward and update position */
int move (HAMSTER *hms, int dir, TPOS *ppos)
{
  if (hms_look(hms)==HMS_WALL) {
    return 1;
  } else {
    hms_move(hms);
    switch (dir) {
    case HMS_EAST:
      ppos->x++;
      break;
    case HMS_NORTH:
      ppos->y++;
      break;
    case HMS_WEST:
      ppos->x--;
      break;
    case HMS_SOUTH:
      ppos->y--;
      break;
    }
  }
  return 0;
}

/* returns minimum home distance of reachable neighbors */
int mindist (TPOS pos,
             TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1])
{
  int min = INT_MAX;
  if ((map[pos.x][pos.y].e!=HMS_WALL)&&(map[pos.x+1][pos.y].dist<min)) {
    min = map[pos.x+1][pos.y].dist;
  }
  if ((map[pos.x][pos.y].n!=HMS_WALL)&&(map[pos.x][pos.y+1].dist<min)) {
    min = map[pos.x][pos.y+1].dist;
  }
  if ((map[pos.x][pos.y].w!=HMS_WALL)&&(map[pos.x-1][pos.y].dist<min)) {
    min = map[pos.x-1][pos.y].dist;
  }
  if ((map[pos.x][pos.y].s!=HMS_WALL)&&(map[pos.x][pos.y-1].dist<min)) {
    min = map[pos.x][pos.y-1].dist;
  }
  return min;
}

/* returns direction of neighbor with minimum home distance */
int mindir (TPOS pos,
            TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1])
{
  int mval = INT_MAX, mdir;
  
  if ((map[pos.x+1][pos.y].dist<mval)&&(map[pos.x][pos.y].e!=HMS_WALL)) {
    mval = map[pos.x+1][pos.y].dist;
    mdir = HMS_EAST;
  }
  if ((map[pos.x][pos.y+1].dist<mval)&&(map[pos.x][pos.y].n!=HMS_WALL)) {
    mval = map[pos.x][pos.y+1].dist;
    mdir = HMS_NORTH;
  }
  if ((map[pos.x-1][pos.y].dist<mval)&&(map[pos.x][pos.y].w!=HMS_WALL)) {
    mval = map[pos.x-1][pos.y].dist;
    mdir = HMS_WEST;
  }
  if ((map[pos.x][pos.y-1].dist<mval)&&(map[pos.x][pos.y].s!=HMS_WALL)) {
    mdir = HMS_SOUTH;
  }
  return mdir;
}

/* Queue operations */
TQUEUE *qpusht(TQUEUE *queue,TPOS pos)
{
  TQUEUE *tmp;
  TQUEUE *cur=queue;
  
  tmp=(TQUEUE *)malloc(sizeof(TQUEUE));
  tmp->next=NULL;
  tmp->key=pos;

  if (cur==NULL) return tmp;

  while(cur->next!=NULL) cur=cur->next;
  cur->next=tmp;

  return queue;
}
TQUEUE *qpop  (TQUEUE *queue, TPOS *pos)
{
  TQUEUE *tmp;
  tmp=queue->next;

  *pos=queue->key;
  free(queue);

  return tmp;
}
int qempty(TQUEUE *queue)
{
  if (queue==NULL) return 1;
  return 0;
}

/* stack operations */
TSTACK *spush(TSTACK *stack, int n)
{
  TSTACK *tmp;
  tmp=(TSTACK *)malloc(sizeof(TSTACK));

  tmp->key=n;
  tmp->next=stack;

  return tmp;
}
TSTACK *spop(TSTACK *stack, int *n)
{
  TSTACK *tmp;
  tmp=stack->next;

  *n=stack->key;
  free(stack);

  return tmp;
}
int sempty (TSTACK *stack)
{
  if (stack==NULL) return 1;
  return 0;
}

/* set minimum home distance index fields */
void bfsdist(TFIELD map[HMS_MAXXEXT*2+1][HMS_MAXYEXT*2+1])
{
  TQUEUE *queue = NULL;
  TPOS tmppos, tmppos2;
  int i1,i2;
  
  tmppos.x=HMS_MAXXEXT;
  tmppos.y=HMS_MAXYEXT;

  queue=qpusht(queue,tmppos);
  
  for (i1=0; i1<HMS_MAXXEXT*2+1; i1++) {
    for (i2=0; i2<HMS_MAXYEXT*2+1; i2++) {
      if (map[i1][i2].stat==FIELD_VISITED) {
	map[i1][i2].dist=INT_MAX-1;
      } else {
	map[i1][i2].dist=INT_MAX;
      }
    }
  }

  map[tmppos.x][tmppos.y].dist=0;

  while (!qempty(queue)) {          /* do bfs for all visited fields */
    queue=qpop(queue, &tmppos);
    if ((map[tmppos.x][tmppos.y].e!=HMS_WALL)&& 
	(map[tmppos.x+1][tmppos.y].dist==INT_MAX-1)) {
      tmppos2.x=tmppos.x+1;
      tmppos2.y=tmppos.y;
      map[tmppos2.x][tmppos2.y].dist=map[tmppos.x][tmppos.y].dist+1;
      queue=qpusht(queue,tmppos2);
    }
    if ((map[tmppos.x][tmppos.y].n!=HMS_WALL)&& 
	(map[tmppos.x][tmppos.y+1].dist==INT_MAX-1)) {
      tmppos2.x=tmppos.x;
      tmppos2.y=tmppos.y+1;
      map[tmppos2.x][tmppos2.y].dist=map[tmppos.x][tmppos.y].dist+1;
      queue=qpusht(queue,tmppos2);
    }
    if ((map[tmppos.x][tmppos.y].w!=HMS_WALL)&& 
	(map[tmppos.x-1][tmppos.y].dist==INT_MAX-1)) {
      tmppos2.x=tmppos.x-1;
      tmppos2.y=tmppos.y;
      map[tmppos2.x][tmppos2.y].dist=map[tmppos.x][tmppos.y].dist+1;
      queue=qpusht(queue,tmppos2);
    }
    if ((map[tmppos.x][tmppos.y].s!=HMS_WALL)&& 
	(map[tmppos.x][tmppos.y-1].dist==INT_MAX-1)) {
      tmppos2.x=tmppos.x;
      tmppos2.y=tmppos.y-1;
      map[tmppos2.x][tmppos2.y].dist=map[tmppos.x][tmppos.y].dist+1;
      queue=qpusht(queue,tmppos2);
    }
  }
}