//#line 1000 "maze.h" //for debugging purposes
//////////////////////////////////////////////////////////////////////
//Maze header file
//
//Conatins usefull functions to generate a maze...
//
//
#include <allegro.h>
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
//#include <personal/random_n.h>
////

#define wall 1  //number value of wall on map
#define floor 0 //number 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
  {
    if(x<0) x=0;
    if(x>=n) x=0;
    if(y<0) y=0;
    if(y>=n) y=0;

    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+(rand() % (b-a+1)); }

                                                          //
int odd(int x)//tells if the given integer is odd        //
{ return (x % 2);}                                      //
                                                       //
////////////////////////////////////////////////////////


//////////////////////////////////////
//MAZE CLASS:
class maze_t
{
public:

	int counter;//needed to determine end of algorythm
        char* maze;//maze array
	int n; //size of maze
	coord beg, end;//start and finish coordinates of the maze

	maze_t(int size);//does all the helpful initialization of maze array
	maze_t();//creates an empty zero-size array (not usefull to anyone)

	~maze_t();//deletes the maze array

#ifdef ALLEGRO_H
	void draw(BITMAP*,coord);//draws a maze as a picture
#endif

	void generate();//generates maze as a number array

        char & operator[](coord pos)//returns a reference of a cell in the maze array
        { return maze[(pos.m_pos(n))]; }

private:

	coord find_next_random_move(coord);//finds next legal random move starting from a given position
	void set_walls(coord,coord);//sets walls from the given position
	coord find_backspace(coord,coord);//finds next legal backwards move from the given position               
	coord find_thin_wall(coord);//finds a wall (if there is one) he can brake to reveal empty space   

};



#ifdef ALLEGRO_H
////////////////////////////////////////////////////////////////////
//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)
#define pos_c makecol32(255,50,25)

////////////////////////////////////////////////////////////////////
//                                                                //
//Draw maze array to graphic memory buffer...                     //
//
//(dest - mem.buffer, maze - maze array, n - size of maze array)
//(pos - draws a red marker on map on the given pos, skips if you send "coord()")
void maze_t::draw(BITMAP* dest, coord pos=coord())
{
  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]==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);
	  else //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);
    }

	//if there is a player to be drawn then draw it:
    if(pos!=coord()) rectfill(dest,b.x+pos.x*l.x+(l.x/4),b.y+pos.y*l.y+(l.y/4),b.x+(pos.x+1)*l.x-(l.x/4),b.y+(pos.y+1)*l.y-(l.y/4),pos_c);

}
#endif

///////////////////////////////////////////////////////////////////////
//
//Checks the corectness of the size of the maze array, creates the maze
//array and intializes the counter...
//
//
maze_t::maze_t(int size)
{
  n=size;

  if(n<5) n=5;
  if(n>200) n=200; //not recommended to go over 200 (it's slow even so)
  if(!odd(n)) n++;

  maze = new char[n*n];

  counter = (n-2) * (n-2); //this is the amount of cells without the outer walls

  beg=end=coord();
}

//////////////////////////////////
//Empty constructor & destrucor://
maze_t::maze_t()
{
	n=0;
	maze=NULL;
	counter=0;
	beg=end=coord();
}

maze_t::~maze_t()
{
	delete [] maze;
	maze=NULL;
	n=0;
	counter=0;
	beg=end=coord();
}								//
//////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////
//
//The heart of the program:
//MAZE GENERATING ALGORYTHM
//
//
//
void maze_t::generate()
{

  int i,j;

  //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
      //coord(i*(n-1),j)).setW(maze,n);
  
  for(i=0; i<n; i++)
    for(j=0; j<2; j++)
	  maze[i*n+j*(n-1)]=wall;//Here same as above...
	  //coord(i,j*(n-1)).setW(maze,n);
  /////

  srand(time(0));
  //init_mm();
	
  //Looking for begining and end
  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:         //
  //                                  //
  
  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);//speaks for itslef

  pos=t;//it's okay to make first move
  pos.setF(maze,n);//set that to floor
  counter--;//decrement counter!
  //MAIN LOOP:
  do
  {
    t=find_next_random_move(pos);//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);//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;
        t= find_thin_wall(pos);//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!
        }
      }
    }
    else//if we have a free next move (normal procedure)
    {
      set_walls(pos,t);//set walls around the old position
      pos=t;
      pos.setF(maze,n);//set floor to new pos.
      counter--;//decrease counter!
    }
  }
  while(counter);//does the loop while we still have something to build...
                               //
  //Here ends all :(          //
  /////////////////////////////
  cout<<endl;
  return;

}



/////////////////////////////////////////
//
//Private functions:
//
//
///////////////////////////
//Find next random move:
//
//(pos-current position)
//
coord maze_t::find_next_random_move(coord pos)
{
  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)
void maze_t::set_walls(coord c_old, coord c_new)
{

  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)
coord maze_t::find_backspace(coord old, coord pos)
{
  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 maze_t::find_thin_wall(coord pos)
{
  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)];

}