/*
Maze generator for POV-Ray, with Tarjan's sets method
Copyright (C) 2005  Pierre Schwartz (khayyam)  ->  khayyam_zozo@hotmail.com 

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/


#include <stdio.h>
#include <stdlib.h> 

typedef enum{false, true}bool;

unsigned long hauteur=0, largeur=0;

bool ***murs;  // 0: horizontal, 1: vertical
bool ***done;
//                              > 0:horizontal, 1:vertical    


bool possible(int departx, int departy, int arriveex, int arriveey, int code)
{
     if ((departx==arriveex) && (departy==arriveey))
         return true;
     else
     {
          // en haut
          if (code!= 2) 
             {
                 if ((murs[departx][departy][0]==0) && (departy-1>=0))
                    if (possible(departx, departy-1, arriveex, arriveey, 1)) return true;
             }    
          // en bas
          if (code!=1)
             {
                 if ((murs[departx][departy+1][0]==0) && (departy+1<hauteur))
                    if (possible(departx, departy+1, arriveex, arriveey, 2)) return true;
             } 
          // à droite
          if (code!=4)
             {
                 if ((murs[departx+1][departy][1]==0) && (departx+1<largeur))
                    if (possible(departx+1, departy, arriveex, arriveey, 3)) return true;
             } 
          // à gauche
          if (code!=3)
             {
                 if ((murs[departx][departy][1]==0) && (departx-1>=0))
                    if (possible(departx-1, departy, arriveex, arriveey, 4)) return true;
             }     
          return false;
     }       
}    


int main(int argc, char **argv)
{  
  if (argc != 3) 
  {printf("manque d'arguments\n");
   return 1;
  }  
  
  largeur = atol(argv[1]);
  hauteur = atol(argv[2]);
  
  if ((largeur < 3) || (hauteur < 3))
  {printf("arguments invalides\n");
   return 1;
  }   
  
  int i,j,k;
 
  murs = (bool***)malloc((largeur+1)*sizeof(bool**));
  done = (bool***)malloc((largeur+1)*sizeof(bool**));
  for (i=0; i<largeur+1; i++)
      {
         murs[i] = (bool**)malloc((hauteur+1)*sizeof(bool*));
         done[i] = (bool**)malloc((hauteur+1)*sizeof(bool*));
         for (j=0; j<hauteur+1; j++)
             {
                 murs[i][j] = (bool*)malloc(2*sizeof(bool));
                 done[i][j] = (bool*)malloc(2*sizeof(bool));                 
             }    
      }    
  
  
  // initialisation du tableau à 1, on met des murs partout
  for (i=0; i<largeur+1; i++)
     for (j=0; j<hauteur+1; j++)
        for (k=0; k<2; k++)
             { murs[i][j][k]=1;
               done[i][j][k]=0;
             }    
                         
  srand(time(NULL));
  unsigned long a_faire=(largeur-1)*hauteur+(hauteur-1)*largeur;
  bool choix;
  unsigned long nb_done=0;
  
  printf("creation du labyrinthe ...");
  
  while (nb_done!=a_faire)
  {
      //on choisit un mur vertical ou horizontal
      // i : abscisse
      // j : ordoonée    
      do
      {
      choix=rand()%2;
      if (choix==0)
          {
              j=1+rand()%(hauteur-1);
              i=rand()%largeur;
          }       
      else
          {
              j=rand()%hauteur;
              i=1+rand()%(largeur-1);
          }
      }    
      while (done[i][j][choix]==1); 
  

      // on teste le mur i,j,choix
      if (choix==0)
          {
              if (!possible(i,j,i,j-1,0))
                 murs[i][j][0]=0;
              done[i][j][0]=1;
          }
      
      if (choix==1)
          {
              if (!possible(i,j,i-1,j,0))
                  murs[i][j][1]=0;
              done[i][j][1]=1; 
          }    
   nb_done++;
  }  // while pour tout le tableau  


FILE *fichier=fopen("labyrinthe.inc", "w");
fprintf(fichier, "#declare LARGEUR = %d;\n", largeur);
fprintf(fichier, "#declare HAUTEUR = %d;\n\n", hauteur);

fprintf(fichier, "#declare laby = object{\nunion{\n");
for (i=0; i<largeur; i++)
   for (j=0; j<hauteur+1; j++)
     {
       if (((i==0) && (j==0)) || ((i==largeur-1) && (j==hauteur))) continue;
       if (murs[i][j][0])
         fprintf(fichier, "box{<%2.1f,0,%2.1f>, <%2.1f,1,%2.1f>}\n",i-.1,j-.1, i+1.1,j+.1);   
     }    
         
for (i=0; i<largeur+1; i++)
    for (j=0; j<hauteur; j++)         
    {
      if (murs[i][j][1])
         fprintf(fichier, "box{<%2.1f,0,%2.1f>, <%2.1f,1,%2.1f>}\n",i-.1,j+.1,i+.1,j+1.1);      
    }    
                    
fprintf(fichier, "pigment{Red}\n");
fprintf(fichier,"}}\n");
fclose(fichier); 

for (i=0; i<largeur+1; i++)
      {
         for (j=0; j<hauteur+1; j++)
             {
                 free(murs[i][j]);
                 free(done[i][j]);
             }    
         free(murs[i]);
         free(done[i]);
      }     
  free(murs);
  free(done);

return 0;
}