#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

/* Maze builder!
   Peter Sorotokin,
   1986-1996 - 10th anniversary! - it was my first program */

#ifdef MY_RAND

#include <math.h>

#define srand my_srand
#define rand my_rand

double x0 = 0.1;

void my_srand( seed )
int seed;
{
  x0 = 0.1 + 0.8/seed;
}

int my_rand()
{
  x0 = 0.5*(1+sin(exp(100*x0)));
  if( x0 == 0 )
    x0 = 1e-15;
  return 0x7FFFFFFF*x0;
}

#endif

enum form_enum { PS_FORM, ASCII_FORM, TAB_FORM } form = PS_FORM;
enum ent_enum  { NS_ENT, WE_ENT, NSWE_ENT, OFF_ENT } ent = NS_ENT;
const char * outfile = "maze.ps";
int height = 20;
int width = 20;
double box_h = 0.0;
double box_w = 0.0;
int got_seed = 0;

void parse_args( int argc, char * argv[] )
{
  int i = 1;
  int help = 0;
  while( i < argc )
    {
      if( strcmp(argv[i],"-size") == 0 )
	{
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -size option value\n" );
	      break;
	    }
	  if( sscanf( argv[i], "%dx%d", &width, &height ) != 2 )
	    fprintf( stderr, 
                "maze: bad option: -size %s - WIDTHxHEIGHT expected\n",
                argv[i]);
	  if( width < 3 )
	    {
	      fprintf( stderr, "maze: width cannot be less then 3\n"); 
	      width = 3;
	    }
	  if( height < 3 )
	    {
	      fprintf( stderr, "maze: height cannot be less then 3\n"); 
	      height = 3;
	    }
	  i++;
	  continue;
	}
      else if( strcmp(argv[i],"-box") == 0 )
	{
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -box option value\n" );
	      break;
	    }
	  if( sscanf( argv[i], "%lfx%lf", &box_w, &box_h ) != 2 )
	    fprintf( stderr, 
                "maze: bad option: -box %s - PSWIDTHxPSHEIGHT expected\n",
                argv[i]);
	  if( box_w < 0 )
	    {
	      fprintf( stderr, "maze: box width cannot be less then zero\n"); 
	      box_w = 0.0;
	    }
	  if( box_h < 0 )
	    {
	      fprintf( stderr, "maze: box height cannot be less then zero\n"); 
	      box_h = 0.0;
	    }
	  i++;
	  continue;
	}
      else if( strcmp( argv[i], "-out" ) == 0 )
	{
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -out option value\n" );
	      break;
	    }
	  if( freopen( argv[i], "w", stdout ) == NULL )
	    perror(argv[i]);
	  i++;
	  continue;
	}
      else if( strcmp( argv[i], "-form" ) == 0 )
	{
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -form option value\n" );
	      break;
	    }
	  if(strcmp(argv[i],"ps")==0||strcmp(argv[i],"PS")==0)
	    form = PS_FORM;
	  else if(strcmp(argv[i],"ascii")==0||strcmp(argv[i],"ASCII")==0)
	    form = ASCII_FORM;
	  else if(strcmp(argv[i],"tab")==0||strcmp(argv[i],"TAB")==0)
	    form = TAB_FORM;
	  else
	    fprintf(stderr,
               "maze: bad -form %s option - PS, ASCII or TAB expected\n",
	       argv[i]);
	  i++;
	  continue;
	}
      else if( strcmp(argv[i],"-seed") == 0 )
	{
	  unsigned int seed;
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -seed option value\n" );
	      break;
	    }
	  if( sscanf( argv[i], "%d", &seed ) != 1 )
	    fprintf( stderr, 
                "maze: bad option: -seed %s - INTEGER expected\n",
                argv[i]);
	   else
	    {
	      srand( seed );
	      got_seed = 1;
	    }
	  i++;
	  continue;
	}
      else if( strcmp( argv[i], "-ent" ) == 0 )
	{
	  if( ++i >= argc )
	    {
	      fprintf( stderr, "maze: no -ent option value\n" );
	      break;
	    }
	  if(strcmp(argv[i],"ns")==0||strcmp(argv[i],"NS")==0)
	    ent = NS_ENT;
	  else if(strcmp(argv[i],"we")==0||strcmp(argv[i],"WE")==0)
	    ent = WE_ENT;
	  else if(strcmp(argv[i],"nswe")==0||strcmp(argv[i],"NSWE")==0)
	    ent = NSWE_ENT;
	  else if(strcmp(argv[i],"off")==0||strcmp(argv[i],"OFF")==0)
	    ent = OFF_ENT;
	  else
	    fprintf(stderr,
               "maze: bad option: -ent %s  - NS, WE, NSWE or OFF expected\n",
	       argv[i]);
	  i++;
	  continue;
	}
      else
	{
	  if( strcmp( argv[i], "-help" ) != 0 )
	    fprintf(stderr,"maze: unknown option %s\n",argv[i]);
	  i++;
	  help = 1;
	}
    }
if( help )
  {
    fputs("\n\
Maze builder, Peter Sorotokin,\n   1986-1996\n\n\
Valid options are:\n\
 -size WxH   size of the maze (20x20 is default)\n\
 -out  file  output file name (stdout by default)\n\
 -form FORM  output format: PS(PostScript), ASCII or TAB(data table)\n\
 -box  WxH   bounding box in inches (for PostScript only)\n\
 -seed NUM   seed number for random number generator (default - from time)\n\
 -entr ENT   entrances: NS(North-South, default), WE, NSWE, OFF\n\
 -help       print this help and exit(1)\n\n",
     stderr);
    exit(1);
  }
}

unsigned char * vert;
unsigned char * hor;
int           * zone;
int           * zsize;

void init_maze()
{
  int i,j;
  vert = (unsigned char *)malloc(sizeof(unsigned char)*height*(width+1));
  for( i = 0 ; i <= width ; i++ )
    for( j = 0 ; j < height ; j++ )
      vert[i*height+j] = 1;
  hor = (unsigned char *)malloc(sizeof(unsigned char)*(height+1)*width);
  for( i = 0 ; i < width ; i++ )
    for( j = 0 ; j <= height ; j++ )
      hor[i*(height+1)+j] = 1;
  zone  = (int *)malloc(sizeof(int)*height*width);
  zsize = (int *)malloc(sizeof(int)*height*width);
  for( i = 0 ; i < width ; i++ )
    for( j = 0 ; j < height ; j++ )
      {
	zone[i*height+j] = i*height+j;
	zsize[i*height+j] = 1;
      }
}

double default_dim( double * dim, int intr, double max )
{
  if( *dim == 0 )
    {
      *dim = 0.4*intr;
      if( *dim > max )
	*dim = max-0.4;
    }
  if( *dim < max )
    return (max - *dim)/2;
   else
    return 0.0;
}

static char ps_prologue[] = "\
%%!PS-Adobe-2.0\n\
%%%%Title: MAZE\n\
%%%%Creator: MAZE\n\
%%%%BoundingBox: 0 0 612 792\n\
%%%%EndComments\n\
\n\
1 setlinecap\n\
%s\
/m { moveto } bind def\n\
/L { lineto } bind def\n\
/N { newpath } bind def\n\
/S { stroke } bind def\n\
%%%%Page: 1 1\n\
%%%%PageBoundingBox: 0 0 612 792\n";

void maze_ps_print( FILE * fp )
{
  double x0 = 72.0*default_dim( &box_w, width,  8.5 );
  double y0 = 72.0*default_dim( &box_h, height, 11.0 );
  double w = box_w*72.0;
  double h = box_h*72.0;
  double hy = h/height, hx = w/width;
  int i,j;
  fprintf( fp, ps_prologue, (hx<5||hy<5?"0 setlinewidth\n":"") );
  for( i = 0 ; i <= width ; i++ )
    {
      j = 0;
      while( j < height )
	{
	  while( j < height && !vert[i*height+j] )
	    j++;
	  if( j >= height )
	    break;
	  fprintf(fp,"N %g %g m ",x0+hx*i,y0+hy*j);
	  while( j < height && vert[i*height+j] )
	    j++;
	  fprintf(fp,"%g %g L S\n",x0+hx*i,y0+hy*j);
	}
    }
  for( j = 0 ; j <= height ; j++ )
    {
      i = 0;
      while( i < width )
	{
	  while( i < width && !hor[i*(height+1)+j] )
	    i++;
	  if( i >= width )
	    break;
	  fprintf(fp,"N %f %f m ",x0+hx*i,y0+hy*j);
	  while( i < width && hor[i*(height+1)+j] )
	    i++;
	  fprintf(fp,"%f %f L S\n",x0+hx*i,y0+hy*j);
	}
    }
  fprintf(fp,"showpage\n");
}

void maze_ascii_print( FILE * fp )
{
  int i,j,k;
  j = height;
  while( 1 )
    {
      fputc( '+', fp );
      for( i = 0 ; i < width ; i++ )
	fputs( (hor[i*(height+1)+j]?"---+":"   +"), fp );
      fputc( '\n', fp );
      if( --j < 0 )
	break;
      for( k = 0 ; k < 2 ; k++ )
	{
	  for( i = 0 ; i < width ; i++ )
	    fputs( (vert[i*height+j]?"|   ":"    "), fp );
	  fputs( (vert[i*height+j]?"|\n":" \n"), fp );
	}
    }
}

void maze_tab_print( FILE * fp )
{
  int i,j;
  fprintf( fp, "Maze table\nSize %d %d\nHorizontal:\n", width, height );
  for( j = height ; j >= 0 ; j-- )
    {
      for( i = 0 ; i < width ; i++ )
	fputc( (hor[i*(height+1)+j]?'1':'0'), fp );
      fputc('\n',fp);
    }
  fputs("Vertical:\n",fp);
  for( j = height-1 ; j >= 0 ; j-- )
    {
      for( i = 0 ; i <= width ; i++ )
	fputc( (vert[i*height+j]?'1':'0'), fp );
      fputc( '\n', fp );
    }
}

int find_set( int z )
{
  while( zone[z] != z )
    z = zone[z];
  return z;
}

void merge( int s1, int s2 )
{
  if( zsize[s1] > zsize[s2] )
    {
      zone[s2] = s1;
      zsize[s1] += zsize[s2];
    }
   else
    {
      zone[s1] = s2;
      zsize[s2] += zsize[s1];
    }
}

void build_maze()
{
  int niter;
  int attempts = 0;
  int to_break = height*width-1;
  for( niter = to_break ; niter > 0 ; niter-- )
    {
      int broke = 0;
      int zone1, zone2;
      int isvert,i,j;
      do
	{
          attempts++;
	  isvert = rand()%2;
	  if( isvert )
	    {
	      i = 1 + rand()%(width-1);
	      j = rand()%height;
	      zone1 = (i-1)*height+j;
	      zone2 = i*height+j;
	    }
	   else
	    {
	      i = rand()%width;
	      j = 1 + rand()%(height-1);
	      zone1 = i*height+j-1;
	      zone2 = i*height+j;
	    }
	  zone1 = find_set(zone1);
	  zone2 = find_set(zone2);
	}
       while( zone1 == zone2 );
      merge(zone1,zone2);
      if( isvert )
	vert[i*height+j] = 0;
       else
        hor[i*(height+1)+j] = 0;
    }
 fprintf( stderr, "Building complete, ratio %g\n",
   ((double)to_break)/attempts );
}

void make_entrances()
{
  switch( ent )
    {
      case NS_ENT :
	hor[(1+rand()%(width-2))*(height+1)+height] = 0;
	hor[(1+rand()%(width-2))*(height+1)] = 0;
	break;
      case WE_ENT :
	vert[1+rand()%(height-2)] = 0;
	vert[width*height+1+rand()%(height-2)] = 0;
	break;
      case NSWE_ENT :
	hor[(1+rand()%(width-2))*(height+1)+height] = 0;
	hor[(1+rand()%(width-2))*(height+1)] = 0;
	vert[1+rand()%(height-2)] = 0;
	vert[width*height+1+rand()%(height-2)] = 0;
	break;
      default:
	;
    }
}

int main( int argc, char * argv[] )
{
  parse_args( argc, argv );
  if( ! got_seed )
    {
      srand( (unsigned int)time( NULL ) );
    }
  init_maze();
  make_entrances();
  build_maze();
  switch( form )
    {
      case PS_FORM :
	maze_ps_print( stdout );
	break;
      case ASCII_FORM :
	maze_ascii_print( stdout );
	break;
      case TAB_FORM :
	maze_tab_print( stdout );
	break;
    }
  return 0;
}