/* 
 *  KaasMuis Oplossing v0.1
 *
 *  Opdracht 3 PRC 2006-2007 Joris van Rooij T3
 *
 *  GNU C compiler flags:
 *  -lm -lcurses -Wall -O2 [-DEBUG]
 */

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <unistd.h>
#include <curses.h>

#define N 15  /* dit is de grootte van het bord */
#define PAUZE 30 /* pauze interval, hoger is trager */
#define BRUTEFORCE 50 /* aantal pogingen om de kortste route te vinden */

/* deze zo laten */
#define KAASKLEUR 20
#define BLOKKLEUR 21
#define MUISKLEUR 22
#define NIKSKLEUR 23
#define DBUGKLEUR 24

typedef enum mazewaarde {LEEG, KAAS, MUIS, PAD, BLOK} Mazewaarde;
typedef Mazewaarde Maze[N][N];
typedef struct { int x; int y; } Positie;

void pauze(unsigned int msec);
void maakMazeLeeg(Maze bord);
void vulMazeRandom(Maze bord, Positie *muis, Positie *kaas);
void drukAfMaze(Maze bord);
void dbg (char *msg);
int was_there(unsigned char *histpath, int x, int y);
int seek_and_eat(Positie *curpos, const Positie cheese, int *path, int *pathc, unsigned char *histpath, Maze maze, int spathc);

void pauze(unsigned int msec) {
  /* pre : -
     post: er is msec miliseconden gewacht
     opmerking : dit is geen Ansi C helaas
     Opmerking : Omgebouwd tot GNU libc compatible
  */
  struct timespec tewachten, gewacht;
  tewachten.tv_sec = floor(msec/1000);
  tewachten.tv_nsec = (msec-tewachten.tv_sec*1000)*1000000;
  nanosleep(&tewachten, &gewacht);
}

void maakMazeLeeg(Maze bord) {
  /* pre :
     post: bord gevuld met LEEG
  */
  int rij, kolom;

  /* maak gehele bord leeg */
  for (rij=0; rij<N; rij=rij+1) {
    for(kolom=0; kolom<N; kolom++)
      bord[rij][kolom] = LEEG;
  }
}

void vulMazeRandom(Maze bord, Positie *muis, Positie *kaas) {
  /*
    pre : -
    post: het 3-de deel van het bord is gevuld met blokkades en
          Muis en Kaas op random posities in Maze
  */
  int i, rij, kolom, aantal;

  maakMazeLeeg(bord);

  aantal = (N*N) / 3;   /* aantal vakken dat gevuld wordt */
  srand(time(NULL));  /* initialiseren randomgenerator  */
  for (i=0; i< aantal; i++) {
    rij = rand()%N;
    kolom = rand()%N;
    bord[rij][kolom] = BLOK; /* dus een blokkade */
  }
  rij = rand()%N;
  kolom = rand()%N;
  muis->x = rij;
  muis->y = kolom;
  bord[rij][kolom] = MUIS;

  rij = rand()%N;
  kolom = rand()%N;
  kaas->x = rij;
  kaas->y = kolom;
  bord[rij][kolom] = KAAS;
}

void drukAfMaze(Maze bord) {
  /*
    pre  :
    post: (Ai:0<=i<N : (Aj:0<=j<N:
          bord[i][j] is linksboven op het scherm afgedrukt
          Als blok[i][j] == BLOK 0 dan op scherm B
          Anders
            Als bord[i][j]== MUIS dan op scherm M
            Anders
              Als bord[i][j]= KAAS dan op scherm K
              Anders
                Als bord[i][j] == PAD dan op scherm .
                Anders
                   op scherm een spatie
              ))
  */
  int rij, kolom;
  /* curses gebruiken voor maze opbouw */
  clear();
  refresh();
  /* bovenste rand */
  #ifdef EBUG
  printw("\n   ");
  char debug[100];
  for (kolom = 0; kolom < N; kolom++) {
    sprintf(debug, "%-2d ", kolom);
    printw(debug);
  }
  #endif
  printw("\n");
  for (rij = 0; rij < N; rij++) {
    #ifdef EBUG
    sprintf(debug, " %2d", rij);
    printw(debug);
    #endif
    for (kolom = 0; kolom < N; kolom++) {
      if (bord[rij][kolom] == BLOK) {
        attron(COLOR_PAIR(BLOKKLEUR));
        printw("   ");
        attroff(COLOR_PAIR(BLOKKLEUR));
      } else if (bord[rij][kolom] == MUIS) {
        attron(COLOR_PAIR(MUISKLEUR));
        printw(" M ");
        attroff(COLOR_PAIR(MUISKLEUR));
      } else if (bord[rij][kolom] == KAAS) {
        attron(COLOR_PAIR(KAASKLEUR));
         printw(" K ");
        attroff(COLOR_PAIR(KAASKLEUR));
      } else if (bord[rij][kolom] == PAD) {
        attron(COLOR_PAIR(NIKSKLEUR));
        printw(" . ");
        attroff(COLOR_PAIR(NIKSKLEUR));
      } else {
        attron(COLOR_PAIR(NIKSKLEUR));
        printw("   ");
        attroff(COLOR_PAIR(NIKSKLEUR));
      }
    }
    printw("\n");
  }
  refresh();
  #ifndef EBUG
  pauze(PAUZE);
  #endif
}

void dbg (char *msg) {
  #ifdef EBUG
  attron(COLOR_PAIR(DBUGKLEUR));
  printw(msg);
  attroff(COLOR_PAIR(DBUGKLEUR));
  refresh();
  getchar();
  #endif
}

int was_there(unsigned char *histpath, int x, int y) {
  return (histpath[y * N + x] != 0x00);
}

int seek_and_eat(Positie *curpos, const Positie cheese, int *path, int *pathc, unsigned char *histpath, Maze maze, int spathc) {
  int ret;
  char debug[100];
  sprintf(debug, "Coor: %d,%d Step: %d Trigger: %#x\n", curpos->x, curpos->y, *pathc, histpath[curpos->y * N + curpos->x]);
  dbg(debug);
  /* Zitten we al niet met onze snuit in de kaas? */
  if (curpos->x == cheese.x && curpos->y == cheese.y) {
    maze[curpos->x][curpos->y] = KAAS;
    drukAfMaze(maze);
    return 1;
  }
  /* Buffertje beschermen tegen overflow en speedup
     voor als hij te lang wordt qua pad */
  if (*pathc >= spathc) {
    maze[curpos->x][curpos->y] = LEEG;
    dbg("Te lang pad\n");
    return 0;
  }
  maze[curpos->x][curpos->y] = PAD;
  switch (rand()%4) {
    case 0:
    /* Ren Boven */
    histpath[curpos->y * N + curpos->x] |= 0xC0;
    if (curpos->x != 0) {
      if (maze[curpos->x-1][curpos->y] != BLOK && !was_there(histpath, curpos->x-1, curpos->y)) {
        dbg("Wel Boven\n");
        curpos->x--;
        path[(*pathc)++] = curpos->y * N + curpos->x;
        maze[curpos->x][curpos->y] = MUIS;
        drukAfMaze(maze);
        ret = seek_and_eat(curpos, cheese, path, pathc, histpath, maze, spathc);
        if (ret != 0)
          return ret;
      } else dbg("Niet Boven\n");
    } else dbg("Niet Boven\n");
    break;
    case 1:
    /* Ren Links */
    histpath[curpos->y * N + curpos->x] |= 0x30;
    if (curpos->y != 0) {
      if (maze[curpos->x][curpos->y-1] != BLOK && !was_there(histpath, curpos->x, curpos->y-1)) {
        dbg("Wel Links\n");
        curpos->y--;
        path[(*pathc)++] = curpos->y * N + curpos->x;
        maze[curpos->x][curpos->y] = MUIS;
        drukAfMaze(maze);
        ret = seek_and_eat(curpos, cheese, path, pathc, histpath, maze, spathc);
        if (ret != 0)
          return ret;
      } else dbg("Niet Links\n");
    } else dbg("Niet Links\n");
    break;
    case 2:
    /* Ren Onder */
    histpath[curpos->y * N + curpos->x] |= 0x0C;
    if (curpos->x != N-1) {
      if (maze[curpos->x+1][curpos->y] != BLOK && !was_there(histpath, curpos->x+1, curpos->y)) {
        dbg("Wel Onder\n");
        curpos->x++;
        path[(*pathc)++] = curpos->y * N + curpos->x;
        maze[curpos->x][curpos->y] = MUIS;
        drukAfMaze(maze);
        ret = seek_and_eat(curpos, cheese, path, pathc, histpath, maze, spathc);
        if (ret != 0)
          return ret;
      } else dbg("Niet Onder\n");
    } else dbg("Niet Onder\n");
    break;
    case 3:
    histpath[curpos->y * N + curpos->x] |= 0x03;
    /* Ren Rechts */
    if (curpos->y != N-1) {
      if (maze[curpos->x][curpos->y+1] != BLOK && !was_there(histpath, curpos->x, curpos->y+1)) {
        dbg("Wel Rechts\n");
        curpos->y++;
        path[(*pathc)++] = curpos->y * N + curpos->x;
        maze[curpos->x][curpos->y] = MUIS;
        drukAfMaze(maze);
        ret = seek_and_eat(curpos, cheese, path, pathc, histpath, maze, spathc);
        if (ret != 0)
          return ret;
      } else dbg("Niet Rechts\n");
    } else dbg("Niet Rechts\n");
  }
  if (histpath[curpos->y * N + curpos->x] == 0xFF) {
    /* We zitten vast! Ren terug! */
    dbg("Moet Terug\n");
    maze[curpos->x][curpos->y] = LEEG;
    curpos->x = path[(*pathc)-2]%N;
    curpos->y = path[(*pathc)-2]/N;
    maze[curpos->x][curpos->y] = MUIS;
    drukAfMaze(maze);
    (*pathc)--;
    if (*pathc == 1)
      return 0;
  }
  return seek_and_eat(curpos, cheese, path, pathc, histpath, maze, spathc);
}

int main(int argc, char *argv[]) {
  Maze bord;
  int x[N*N], oplossing[N*N];
  unsigned char histpath[N*N];
  Positie muis;
  Positie muist;
  Positie kaas;
  int i, ret, p;
  int lengtePad = 0;
  int kortstePad = N*N;

  /* ncurses mode, woohoo */
  initscr();
  start_color();
  init_pair(KAASKLEUR, COLOR_YELLOW, COLOR_WHITE);
  init_pair(MUISKLEUR, COLOR_RED, COLOR_WHITE);
  init_pair(BLOKKLEUR, COLOR_BLACK, COLOR_BLACK);
  init_pair(NIKSKLEUR, COLOR_BLUE, COLOR_WHITE);
  init_pair(DBUGKLEUR, COLOR_WHITE, COLOR_BLACK);

  vulMazeRandom(bord, &muis, &kaas);
  drukAfMaze(bord);

  /***********************************************************/ 
  /* genereer hier een korste route van de muis naar de kaas */
  /***********************************************************/ 
  
  for (p = 0; p < BRUTEFORCE; p++) {
    muist = muis;
    for (i = 0; i < N*N; i++) {
      histpath[i] = 0x00;
      if (bord[i%N][i/N] == PAD)
        bord[i%N][i/N] = LEEG;
    }
    lengtePad = 0;
    drukAfMaze(bord);
    ret = seek_and_eat(&muist, kaas, x, &lengtePad, histpath, bord, kortstePad);
    if (ret == 0) {
      drukAfMaze(bord);
      printw("\nGeen oplossing gevonden !!\n");
      refresh();
    } else {
      drukAfMaze(bord);
      printw("\nKaas gevonden !!\n");
      if (lengtePad < kortstePad) {
        kortstePad = lengtePad;
        for (i = 0; i < N*N; i++)
          oplossing[i] = x[i];
        printw("En is het kortste pad tot nu toe !!\n");
      }
      refresh();
    }
    #ifdef EBUG
    getchar();
    #endif
  }
  for (i = 0; i < N*N; i++) {
    if (bord[i%N][i/N] == PAD)
      bord[i%N][i/N] = LEEG;
  }
  if (kortstePad < N*N) {
    for (p = 1; p < kortstePad; p++) {
      if (p == 1)
        bord[oplossing[p]%N][oplossing[p]/N] = MUIS;
      else if (p == kortstePad-1)
        bord[oplossing[p]%N][oplossing[p]/N] = KAAS;
      else
        bord[oplossing[p]%N][oplossing[p]/N] = PAD;
    }
    drukAfMaze(bord);
    printw("\nKortste resultaat");
    refresh();
  } else {
    printw("\nKaas onbereikbaar");
    refresh();
  }
  /* ncurses moet ook dood na toets */
  getchar();
  endwin();
  return 0;
}