// Improved version of David Gemelli's Maze Solver
// (original version first published 1998-10-19 on povray.binaries.scene-files)
// This version: 2019 by Jörg "Yadgar" Bleimann

#version 3.7;

#include "colors.inc"

#if (file_exists("maze.inc"))
  #include "maze.inc"
#else
  #error "No maze file found!"
#end

#declare CAMFACTOR = max(NbColumns,NbLines)/7;

camera {
     location <CAMFACTOR*5,CAMFACTOR*8,0>
     look_at <0,0,0>
     rotate <0,clock*360,0>
     translate <(NbColumns/2)-.5,0,(NbLines/2)-.5>
}

light_source {<160,320,40> color White rotate <0,clock*360,0>}

// a wall
#declare Wall =
box {<-0.5,0,-0.5> <0.5,0.7,0.5>
     texture {
          pigment{granite color_map{[0.0 Black][1.0 White]} scale 0.24}
          finish {ambient 0.2}}}

// the basic corridor
#declare Floor =
box {<-0.5,0,-0.5> <0.5,0.1,0.5>
     texture {pigment {color Blue} finish {ambient 0.2}}}

// to know where the maze has been visited
#declare Visited =
box {<-0.5,0,-0.5> <0.5,0.1,0.5>
     texture {pigment {color Red} finish {ambient 0.2}}}

// the exit way
#declare Path =
box {<-0.5,0,-0.5> <0.5,0.1,0.5>
     texture {pigment {color Yellow} finish {ambient 0.2}}}

#declare Arrow =
union {
     difference {
          box {<0,0,0> <3,3,1> translate <-1.5,-2,-.5>}
          box {<-2,0,-.6> <0,4,.6> rotate<0,0,-20> translate<-1.5,-2,0>}
          box {<0,0,-.6> <2,4,.6> rotate<0,0,20> translate<1.5,-2,0>}
     }
     difference {
          box {<0,0,0> <3,2,1> translate <-1.5,1,-.5>}
          box {<-2,0,-.6> <0,3,.6> rotate<0,0,-45> translate<-1.5,1,0>}
          box {<0,0,-.6> <2,3,.6> rotate<0,0,45> translate<1.5,1,0>}
     }
     translate <0,-.5,0>
     scale <.4,.6,.2>
     rotate <0,90,0>
}

#declare asize=(NbColumns-2)*(NbLines-2);
#declare solution = array[asize]; // all lab fields minus outer walls

#declare i=0;
#while(i<asize)
  #declare solution[i]=<-1,-1>;
  #declare i=i+1;
#end

#declare c=0;
#declare deadend=false;

#macro search(px,py,lab,r)
/*   #local r1=0;
  #local r2=0;
  #local r3=0;
  #local r4=0; */
  #if (lab[py-1][px] = 2 | lab[py+1][px] = 2 | lab[py][px-1] = 2 | lab[py][px+1] = 2) // exit found!
    #if (lab[py-1][px] = 2) // exit north
      #declare py=py-1;
    #end  
    #if (lab[py+1][px] = 2) // exit south
      #declare py=py+1;
    #end  
    #if (lab[py][px-1] = 2) // exit west
      #declare px=px-1;
    #end  
    #if (lab[py][px+1] = 2) // exit east
      #declare px=px+1;
    #end  
    #declare c=c+1;
    #declare solution[c]=<py,px>;
    #declare r = 1;
    #break
  #end
  // (wall) or (been before)
  #if ((lab[py][px] = 1)|(lab[py][px] = 3))
      #declare r = 0;
  #end
  // a corridor
  #if (lab[py][px] = 0 | (deadend=true & lab[py][px]=3) | (lab[py][px]=3 & (lab[py-1][px]=0 | lab[py+1][px]=0 | lab[py][px-1]=0 | lab[py][px+1]=0)))
    // to mark where we've been
    #declare lab[py][px] = 3;
    #declare solution[c]=<py,px>;
    #declare px2 = px + 1;
    #declare px3 = px - 1;
    #declare py2 = py + 1;
    #declare py3 = py - 1;
  #end
  #if (deadend=false)
    #if (lab[py][px2]=0 | (lab[py][px2]=0 & lab[py][px]=3))
      #declare px=px2;
      #if ((lab[py][px+1]=1 | lab[py][px+1]=3) & (lab[py+1][px]=1 | lab[py+1][px]=3) & (lab[py-1][px]=1 | lab[py-1][px]=3))
	#declare deadend=true;
	#warning "Dead end in the east!"
      #end
    #else
      #if (lab[py][px3]=0 | (lab[py][px3]=0 & lab[py][px]=3))
	#declare px=px3;
	#if ((lab[py][px-1]=1 | lab[py][px-1]=3) & (lab[py+1][px]=1 | lab[py+1][px]=3) & (lab[py-1][px]=1 | lab[py-1][px]=3))
	  #declare deadend=true;
	  #warning "Dead end in the west!"
	#end
      #else
	#if (lab[py2][px]=0 | (lab[py2][px]=0 & lab[py][px]=3))
	  #declare py=py2;
	  #if ((lab[py+1][px]=1 | lab[py+1][px]=3) & (lab[py][px-1]=1 | lab[py][px-1]=3) & (lab[py][px+1]=1 | lab[py][px+1]=3))
	    #declare deadend=true;
	    #warning "Dead end in the south!"
	  #end
	#else
	  #if (lab[py3][px]=0 | (lab[py3][px]=0 & lab[py][px]=3))
	    #declare py=py3;
	    #if ((lab[py-1][px]=1 | lab[py-1][px]=3) & (lab[py][px-1]=1 | lab[py][px-1]=3) & (lab[py][px+1]=1 | lab[py][px+1]=3))
	      #declare deadend=true;
	      #warning "Dead end in the north!"
	    #end
	  #end
	#end
      #end
    #end
    #declare c=c+1;
    #declare solution[c]=<py,px>;
  #end
  
  #if (deadend=true) // go backwards until you reach a field with at least one adjacent not-yet-visited corridor field
    #declare lab[py][px]=3;
    #declare solution[c]=<-1,-1>;
    #declare c=c-1;
    #declare py=solution[c].x;
    #declare px=solution[c].y;
    #if (lab[py+1][px]=0 | lab[py-1][px]=0 | lab[py][px+1]=0 | lab[py][px-1]=0)
      #declare deadend=false;
    #end
  #end
#end

#declare px=DebutX;
#declare py=DebutY;
#if (GrilleLaby[py][px]=1)
  #error "Entry square cannot be a wall!"
#end

#declare r=0;
#declare i=0;
#while(r=0 /*& i<410*/)
  search(px,py,GrilleLaby,r)
  #declare i=i+1;
  #warning concat(str(c,2,0),"\t",str(deadend,2,0),"\t",str(px,2,0),",",str(py,2,0))
#end


#declare i=0; // creating path
#while(solution[i].x > -1)
  #declare GrilleLaby[solution[i].x][solution[i].y] = 2;
  #declare i=i+1;
#end

//an arrow above the exit
object 
{
  Arrow
  texture {pigment{color Orange} finish{ambient 0.6}}
  translate <solution[c].x,2.8,solution[c].y>
}




// the display part
#declare Line = 0;
#while (Line < NbLines)
  #declare Column = 0;
  #while (Column < NbColumns)
          object {
               // a wall
               #if (GrilleLaby[Line][Column] = 1)
                    Wall
               #else
                    // the default corridor
                    #if (GrilleLaby[Line][Column] = 0)
                         Floor
                    #else
                         // the explored corridor
                         #if (GrilleLaby[Line][Column] = 3)
                              Visited
                         // the exit
                         #else
                              Path
                         #end
                    #end
               #end
               translate<Line,0,Column>
          }
          #declare Column = Column + 1;
     #end
     #declare Line = Line + 1;
#end

  



// an arrow above the entrance
object {
     Arrow
     texture {pigment{color Magenta} finish{ambient 0.2}}
     rotate <0,0,180>
     translate <DebutY,2.8,DebutX>
}