#include "PathSearch.h"

/*
looks for val in every position in the maze and marks it neighbours if they are free
with val-1
*/
int fill(int m[X_MAZE][Y_MAZE],int val){
  int x,y,r;
  r = 0;
  for(x=0;x<X_MAZE;x++){
    for(y=0;y<Y_MAZE;y++){
      if(m[x][y]==val){
        if( (x-1>=0) && (m[x-1][y]==0 || m[x-1][y]<val-1) ){
           m[x-1][y]=val-1;
           r=1;
        }
        if( (y-1>=0) && (m[x][y-1]==0 || m[x][y-1]<val-1) ){
           m[x][y-1]=val-1;
           r=1;
        }
        if( (x+1<X_MAZE) && (m[x+1][y]==0 || m[x+1][y]<val-1) ){
           m[x+1][y]=val-1;
           r=1;
        }
        if( (y+1<Y_MAZE) && (m[x][y+1]==0 || m[x][y+1]<val-1) ){
           m[x][y+1]=val-1;
           r=1;
        }
      }
    }
  }
  return r;
}


int PathSearch(int m[X_MAZE][Y_MAZE],MazePositionType p,MazePositionType g){
  int i,j,value,val,ret;
  int mm[X_MAZE][Y_MAZE];
  /*copy maze*/
  for(i=0;i<X_MAZE;i++){
    for(j=0;j<Y_MAZE;j++){
      if(m[i][j]<0)
        mm[i][j]=0;
      else
        mm[i][j]=m[i][j];
    }
  }
  /*mark goal with -1*/
  mm[g.x][g.y]=-1;
  ret=1;
  value = -1;
  /*expansion*/
  while(ret==1){
    ret = fill(mm,value);
    value--;
  }
  /*back track*/
  for(i=0;i<X_MAZE;i++){
    for(j=0;j<Y_MAZE;j++){
      val = X_MAZE*Y_MAZE*(-1);
      if(mm[i][j]<0){
        if(j+1<Y_MAZE && mm[i][j+1]<0) {val=mm[i][j+1]; m[i][j]=0;}/*north*/
        if(i-1>=0 && mm[i-1][j]<0 && val<mm[i-1][j]) {val=mm[i-1][j];m[i][j]=-1;}/*west*/
        if(j-1>=0 && mm[i][j-1]<0 && val<mm[i][j-1]) {val=mm[i][j-1];m[i][j]=-2;}/*south*/
        if(i+1<X_MAZE && mm[i+1][j]<0 && val<mm[i+1][j]) {val=mm[i+1][j];m[i][j]=-3;}/*east*/
      }
    }
  }
  /*check if there is a path*/
  if(mm[p.x][p.y]>=0) return 0; else return 1;
}