#include <iostream.h>
#include <allegro.h>
#include <time.h>
#include <stdlib.h>

//Choose the right option
#define linux
//#define dos

#ifdef linux
#define GFX_DRIVER XWINDOWS
#endif

#ifdef dos
#define GFX_DRIVER AUTODETECT
#define KEY_ESC 1
#endif

//resolution:
#define maxx 800
#define maxy 600

#define wall 1  //int value of wall on map
#define floor 0 //int value of floor on map

///////////////////////////////////////////////////////
//Coordinate class
//
//Has x and y coordinates and some helper functions...
//
class coord
{
  public:
  int x,
      y;

  coord(): x(0), y(0) {} //empty constructor (used to show a NULL coordinate)
  coord (int a, int b): x(a), y(b) {}//integer constructor
  coord (const coord &c)//copy constructor
  {
    x=c.x;
    y=c.y;
  }

  ~coord(){}//empty destructor

  void setW(char* maze, int n)//sets a coord in a given maze to wall
  {  maze[x*n+y]=wall; }

  void setF(char* maze, int n)//sets a coord in a given maze to floor
  {  maze[x*n+y]=floor; }

  coord ret(int x_of, int y_of)//returns a coordinate after vector change
  {  return coord(x+x_of,y+y_of); }

  int m_pos(int n)//returns te coord. as an index in the maze
  {  return x*n+y; }

  operator int ()//int converter (used to determine NULL coordinates)  //
  {return int(x+y); }                                                 //
                                                                     //
};                                                                  //
/////////////////////////////////////////////////////////////////////
//                                                                 //
//Some small helper functions:                                     //
//                                                                 //
int operator!=(coord a, coord b)//unequal operator for coordiates  //
{                                                                  //
  return (a.x==b.x && a.y==b.y)?0:1;                               //
}

int operator==(coord a, coord b)//equal operator for coordinates
{
  return (a.x==b.x && a.y==b.y)?1:0;
}

int number_range(int a, int b) //genearte a random number in the set of <a,b>
{ return a+(random() % (b-a+1)); }

                                                          //
int odd(int x)//tells if the given integer is odd        //
{ return (x % 2);}                                      //
                                                       //
////////////////////////////////////////////////////////
//                                                    //
//Globals                                             //
//                                                    //
BITMAP *buffer;//graphic memory buffer                //
int counter(0);//needed to determine end of algorythm //
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//Function declarations                                                      //
//
//Main functions:
void draw_maze(BITMAP* dest, char* maze, int n);
     //draws a maze as a picture
void generate_maze(char* maze, int n, coord &beg, coord &end);
     //generates maze as a number array
//Helper functions:
coord find_next_random_move(coord pos, char* maze, int n);
     //finds next legal random move starting from a given position           //
void set_walls(coord c_old, coord c_new, char* maze, int n);                 //
     //sets walls from the given position                                    //
coord find_backspace(coord old, coord pos, char* maze, int n);               //
     //finds next legal backwards move from the given position               //
coord find_thin_wall(coord pos, char* maze, int n);                         //
     //finds a wall (if there is one) he can brake to reveal empty space   //
                                                                          //
///////////////////////////////////////////////////////////////////////////


////////////////////////////////
//  P R O G R A M   M A I N:  //
////////////////////////////////

int main(int argc, char** argv)
{
  if(argc!=2)//Argument check...
  {
    cout<<"Argument error..."<<endl
        <<"mazefull.exe [size] >>log.txt"<<endl;
    return -1;
  }

  int size=atoi(argv[1]);//reads the size variable from argument
  if(size<5) size=5;//it is best if size of maze is bigger than five
  if(!odd(size)) size++;//size should also be an odd number

  cout<<"Starting program..."<<endl;

  counter = (size-2)*(size-2);//calculating counter from size

  //Maze array:
  char* maze;
  maze = new char[size*size];

  coord beg,end; //begining and end coord. (used to print to screen)


  cout<<"GENERATE MAZE:"<<endl;

  //My main algorythm:
  generate_maze(maze,size,beg,end);

  cout<<"END GENERATE MAZE..."<<endl;

  cout<<"Initializing Allegro..."<<endl;
  //////////////////////////////////////////////
  //Allegro init. routines...
  allegro_init();
  install_keyboard();

  set_color_depth(32);
  if(set_gfx_mode(GFX_DRIVER,maxx,maxy,0,0)<0)//setting graphics
  {
    cout<<"Error setting graphics: "<<allegro_error<<endl;
    return -2;
  }                                                              //
                                                                 //
  /////////////////////////////////////////////////////////////////
  cout<<"Alegro initialized..."<<endl
      <<"Prepearing scene..."<<endl;


  buffer = create_bitmap(maxx,maxy);//creating mem. buffer
  clear(buffer);


  //Draws the array to the mem. buffer:
  draw_maze(buffer,maze,size);

  //Copies the buffer to screen...
  blit(buffer,screen,0,0,0,0,maxx,maxy);

  cout<<"Scene prepared..."<<endl;
  cout<<"Begining coordinates: x="<<beg.x<<" y="<<beg.y<<endl;
  cout<<"End coordinates: x="<<end.x<<" y="<<end.y<<endl;

  while(!key[KEY_ESC])//Wait for ESC pressed...
  {
  }
  
  cout<<"Shutting down..."<<endl;

  //Freeing memory:
  destroy_bitmap(buffer);
  delete [] maze;

  allegro_exit();//Usefull thing to do...

  cout<<"Finished succesfully..."<<endl;

  return 0;

}

#ifdef linux
END_OF_MAIN();
#endif

/////////////////////////////////////////////////////////////////////
//Some colors:
#define wall_c makecol32(125,125,125)
#define wall_c2 makecol32(0,0,0)
#define floor_c makecol32(255,255,150)
#define empty_c makecol32(255,255,255)

////////////////////////////////////////////////////////////////////
//                                                                //
//Draw maze array to graphic memory buffer...                     //
//
//(dest - mem.buffer, maze - maze array, n - size of maze array)
void draw_maze(BITMAP* dest, char* maze, int n)
{
  int w = dest->w,//gets size of mem. bufer
      h = dest->h;

  coord b,l;//begining and length coords on mem. buffer

  b.x=w/8;//this is where our maze will begin
  b.y=h/8;
  l.x=((3*w)/4)/n;//this is the length(size) of each cell
  l.y=((3*h)/4)/n;

  int i,j;//some temp variables

  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
    {
      if(maze[i*n+j]==1)//if current cell is a wall
      {
        rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,wall_c);
        rect(dest,1+b.x+i*l.x,1+b.y+j*l.y,b.x+(i+1)*l.x-1,b.y+(j+1)*l.y-1,wall_c2);
      }
      else if(maze[i*n+j]==-1)//if it is empty  (used for debug pourposes, but shouldn't usually occur)
        rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,empty_c);
      else /*maze[i*n+j]==0*/ //if it is a floor
        rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,floor_c);
    }

}

///////////////////////////////////////////////////////////////////////
//
//The heart of the program:
//MAZE GENERATING ALGORYTHM
//
//
//(maze-maze array, n-size of maze array, beg/end-coordinates)
void generate_maze(char* maze, int n, coord &beg, coord &end)
{

  int i,j;


  cout<<"clearing surface"<<endl;
  //Clearing surface
  for(i=1; i<(n-1); i++)
    for(j=1; j<(n-1); j++)
      maze[i*n+j]=-1;//Sets interior to empty

  //making outer walls
  for(i=0; i<2; i++)
    for(j=0; j<n; j++)
      maze[i*(n-1)*n+j]=wall;//Makes walls around everything

  for(i=0; i<n; i++)
    for(j=0; j<2; j++)
     maze[i*n+j*(n-1)]=wall;//Here same as above...
  /////


  srandom(time(NULL));

  //Looking for begining and end
  cout<<"setting begining and end"<<endl;

  beg.x=number_range(1,3);
  switch(beg.x)
  {
    case 1:
      beg.x=0;
      beg.y=1+2*number_range(0,(n-3)/2);//only odd ones
      break;
    case 2:
      beg.x=1+2*number_range(0,(n-3)/2);
      beg.y= (n-1) * number_range(0,1);
      break;
    case 3:
      beg.x=n-1;
      beg.y=1+2*number_range(0,(n-3)/2);
  }

  end.x=beg.x;

  while(end.x==beg.x || end.y==beg.y)
  {
    end.x=number_range(1,3);
    switch(end.x)
    {
      case 1:
        end.x=0;
        end.y=1+2*number_range(0,(n-3)/2);
        break;
      case 2:
        end.x=1+2*number_range(0,(n-3)/2);
        end.y= (n-1) * number_range(0,1);
        break;
      case 3:
        end.x=n-1;
        end.y=1+2*number_range(0,(n-3)/2);
    }
  }


  //Sets beg/end to floor:
  maze[beg.x*n+beg.y]=floor;
  maze[end.x*n+end.y]=floor;

  //////////////////////////////////////
  //HERE BEGINS THE FUN PART:         //
  //                                  //
  cout<<"starting algorythm:"<<endl;  //

  coord pos,//current position
        t,//temp var. one - used to retrieve next move
        t2,//temp var. two - used to retrieve backspace move
        t3;//temp var. three - used to hold old move (backspace procedure)

  pos=end;//set postion to end //we move from end to begining making the maze harder//

  t=find_next_random_move(pos, maze, n);//speaks for itslef

  pos=t;//it's okay to make first move
  pos.setF(maze,n);//set that to floor
  counter--;//decrement counter!
  cout<<"."<<flush;

  //MAIN LOOP:
  do
  {
    t=find_next_random_move(pos, maze, n);//find next move
    if(!(int)t)//if no such move is possible
    {
      t3=t2=pos;
      while(!(int)t)//while no escape possible
      {
        t3=t2;
        t2=find_backspace(pos,t2,maze,n);//find a way back
        if(!(int)t2) t2=t3;//if stuck
        if(t2.x<=0 || t2.x>=(n-1) || t2.y<=0 || t2.y>=(n-1)) t2=t3;//avoids leaving the maze
        pos=t3;
        cout<<"B"<<flush;
        t= find_thin_wall(pos,maze,n);//looks if there is a way out through a wall
        if((int)t)//if so
        {
          pos=t;//set current position to that wall
          pos.setF(maze,n);//brake it!
          cout<<"X"<<flush;
        }
      }
    }
    else//if we have a free next move (normal procedure)
    {
      set_walls(pos,t,maze,n);//set walls around the old position
      pos=t;
      pos.setF(maze,n);//set floor to new pos.
      counter--;//decrease counter!
      cout<<"."<<flush;
    }
  }
  while(counter);//does the loop while we still have something to build...
                               //
  //Here ends all :(          //
  /////////////////////////////
  cout<<endl;
  return;

}



/////////////////////////////////////////
//
//Helper functions:
//
//
///////////////////////////
//Find next random move:
//
//(pos-current position, maze-maze array, n-size of maze)
//
coord find_next_random_move(coord pos, char* maze, int n)
{
  coord m[3];//Possible moves...
  int i(0);//Counter of legal moves

  //Checks if given moves are legal
  if(maze[(pos.ret(-1,0)).m_pos(n)]==-1 && pos.x>0
  && (odd(pos.y) || maze[(pos.ret(1,0)).m_pos(n)]==floor))//this is a rather complicated condition...
  {
    m[i]=pos.ret(-1,0);
    i++;
  }

  if(maze[(pos.ret(1,0)).m_pos(n)]==-1 && pos.x<(n-1)
    && (odd(pos.y) || maze[(pos.ret(-1,0)).m_pos(n)]==floor))
  {
    m[i]=pos.ret(1,0);
    i++;
  }

  if(maze[(pos.ret(0,-1)).m_pos(n)]==-1 && pos.y>0
    && (odd(pos.x) || maze[(pos.ret(0,1)).m_pos(n)]==floor))
  {
    m[i]=pos.ret(0,-1);
    i++;
  }

  if(maze[(pos.ret(0,1)).m_pos(n)]==-1 && pos.y<(n-1)
    && (odd(pos.x) || maze[(pos.ret(0,-1)).m_pos(n)]==floor))
  {
    m[i]=pos.ret(0,1);
    i++;
  }

  if(i==0) return coord();//If no legal move found return NULL coord

  return m[number_range(0,i-1)];//Else return a random one from the legal ones

}

///////////////////////
//
//Sets walls....
//
//(c_old-walls are made around this point
// c_new-walls are made from this perspective
// maze-maze array, n-size of maze)
void set_walls(coord c_old, coord c_new, char* maze,int n)
{

  int t;

  if((c_new.x-c_old.x)==1)//Checks the position of two coords in relation to each other
  {
    t=(c_old.ret(0,-1)).m_pos(n);//Finds where to put first wall
    if(maze[t]==-1)//If that place is empty....
    {
      maze[t]=wall;//Put a wall here
      counter--;//Decrease counter! (very important)
    }

    t=(c_old.ret(0,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    return;//Exit function here (no need to to other checks)
  }

  if((c_old.x-c_new.x)==1)
  {
    t=(c_old.ret(1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(0,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(0,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    return;
  }



  if((c_new.y-c_old.y)==1)
  {
    t=(c_old.ret(0,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,-1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    return;
  }



  if((c_old.y-c_new.y)==1)

  {
    t=(c_old.ret(0,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,0)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(-1,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    t=(c_old.ret(1,1)).m_pos(n);
    if(maze[t]==-1)
    {
      maze[t]=wall;
      counter--;
    }

    return;
  }

}

//////////////////////////////////////////////////
//
//Finds a good way back:
//
//(old - a place we came from [no reason to go back there]
// pos - a place we are know on
// maze-maze array, n-size of maze)
coord find_backspace(coord old, coord pos, char* maze, int n)
{
  coord t,//used for clearness
        m[4];//Possible moves

  int i(0);//Counter of legal moves

  t=pos.ret(0,-1);
  if(maze[t.m_pos(n)]==floor && t!=old)
  {
    m[i] = t;
    i++;
  }

  t=pos.ret(0,1);
  if(maze[t.m_pos(n)]==floor && t!=old)
  {
    m[i] = t;
    i++;
  }


  t = pos.ret(1,0);
  if(maze[t.m_pos(n)]==floor && t!=old)
  {
    m[i] = t;
    i++;
  }


  t = pos.ret(-1,0);
  if(maze[t.m_pos(n)]==floor && t!=old)
  {
    m[i] = t;
    i++;
  }

  if(i==0) return coord();

  return m[number_range(0,i-1)];

}

//////////////////////////////////////////////////
//
//Finds a wall one could brake to discover empty space from the other side...
//
//
coord find_thin_wall(coord pos, char* maze, int n)
{
  coord m[4];//Possible walls
  int i(0);//Counter of legal ones

  if(maze[(pos.ret(-2,0)).m_pos(n)]==-1
  &&pos.x>1)//so it wouldn't break open the maze
  {
    m[i]=pos.ret(-1,0);
    i++;
  }

  if(maze[(pos.ret(2,0)).m_pos(n)]==-1 && pos.x<(n-2))
  {
    m[i]=pos.ret(1,0);
    i++;
  }

  if(maze[(pos.ret(0,-2)).m_pos(n)]==-1 && pos.y>1)
  {
    m[i]=pos.ret(0,-1);
    i++;
  }

  if(maze[(pos.ret(0,2)).m_pos(n)]==-1 && pos.y<(n-2))
  {
    m[i]=pos.ret(0,1);
    i++;
  }


  if(i==0) return coord();

  return m[number_range(0,i-1)];

}