declare [QTk]={Module.link ["x-oz://system/wp/QTk.ozf"]}

declare
fun {Maze}
   A B C E F G H I J K L M N O P Q 
   Desc=td(title:'Mickael MAISON s Maze Program'
	   canvas(handle:C bg:white width:420 height:420))

   %The record : 20 raws of 20 cells 
   Rec = {MakeRecord c [1 2 3 4 5 6]}
   FR = {AdjoinList Rec [1#1 2#1 3#1 4#1 5#0 6#0]}
   R = {MakeRecord r [1 2 3 4 5 6 7 8 9 10]}
   FC = {AdjoinList R [1#FR 2#FR 3#FR 4#FR 5#FR 6#FR 7#FR 8#FR 9#FR 10#FR 11#FR 12#FR 13#FR 14#FR 15#FR 16#FR 17#FR 18#FR 19#FR 20#FR]}
   Maze = {MakeRecord maze [1 2 3 4 5 6 7 8 9 10]}
   FG = {AdjoinList Maze [1#FC 2#FC 3#FC 4#FC 5#FC 6#FC 7#FC 8#FC 9#FC 10#FC 11#FC 12#FC 13#FC 14#FC 15#FC 16#FC 17#FC 18#FC 19#FC 20#FC]}
   
   %Draw the cols
   proc {Drawcols H N}
      {H create(line N 10 N 410)}
      if N < 410 then {Drawcols H N+20}
      end
   end
   
   %Draw the raws
   proc {Drawraws H N}
      {H create(line 10 N 410 N)}
      if N < 410 then {Drawraws H N+20}
      end
   end
   
   %Random procedure
   fun {Random Min Max}
      if Max == Min then Min
      else Min + {OS.rand} mod Max
      end
   end

   %Update a cell
   fun {UpdateRecord A R C I V}
      U X Y Z
   in
      X = A.R 
      Y = X.C
      Z = {AdjoinAt Y I V}
      U = {AdjoinAt X C Z} 
      {AdjoinAt A R U}
   end

   %Set the boundaries (North / South)
   fun {BoundaryRows A B C D}
      Z
   in
      Z = {UpdateRecord A B C D 4}
      if C < 20 then {BoundaryRows Z B C+1 D}
      else Z
      end
   end

   %Set the boundaries (East / West)
   fun {BoundaryCols A B C D}
      Z
   in
      Z = {UpdateRecord A B C D 4}
      if B < 20 then {BoundaryCols Z B+1 C D}
      else Z
      end
   end

   %Choose a wall at random
   fun {ChooseWall A B C}
      E F G H
   in
      E = A.B
      F = E.C
      H = {Random 1 4}
      G = F.H
      if G == 4 orelse G == 0 then {ChooseWall A B C}
      else H
      end
   end

   %Choose a direction at random
   fun {ChooseDir A B C}
      E F G H I J
   in
      E = A.B
      F = E.C
      H = {Random 1 4}
      G = F.H
      if G \= 0 orelse H == F.6 then {ChooseDir A B C}
      else
	 if H == 1 then
	    I = B-1
	    J = C
	 end
	 if H == 2 then
	    I = B+1
	    J = C
	 end
	 if H == 3 then
	    I = B
	    J = C+1
	 end
	 if H == 4 then
	    I = B
	    J = C-1
	 end
	 if {Visited A I J} == 0 then H
	 else {ChooseDir A B C}
	 end
      end
   end
   
   %Return if the cell has been visited or not
   fun {Visited A B C}
      E F G
   in
      E = A.B
      F = E.C
      G = F.5
      G
   end

   %Return if it's the end cell
   fun {IsEnd A B C}
      E F G
   in
      E = A.B
      F = E.C
      G = F.6
      G
   end

   %Return if there's unvisited cells
   fun {Around A B C}
      D E F G
   in
      if B > 1 then
	 D = {Visited A B-1 C}
      else
	 D = 1
      end
      if D == 1 then 
	 if C > 1 then
	    E = {Visited A B C-1}
	 else
	    E = 1
	 end
	 if E == 1 then
	    if B < 20 then
	       F = {Visited A B+1 C}
	    else
	       F = 1
	    end
	    if F == 1 then
	       if C < 20 then
		  G = {Visited A B C+1}
	       else
		  G = 1
	       end
	       if G == 1 then
		  0 %All the cells are visited
	       else
		  1
	       end
	    else
	       1
	    end
	 else
	    1
	 end
      else
	 1
      end
   end

   %Delete a wall
   proc {DelWall A C B D}
      H I J K
   in
      if D == 1 then
	 %Break the wall on the North
	 H = 10 + 20 * (B-1) + 1
	 I = 10 + 20 * (C-1) 
	 J = H + 20 - 1
	 K = I
      end
      if D == 2 then
	 %Break the wall on the South
	 H = 10 + 20 * (B-1) + 1
	 I = 10 + 20 * C
	 J = H + 20 - 1
	 K = I
      end
      if D == 3 then
	 %Break the wall on the East
	 H = 10 + 20 * (B) 
	 I = 10 + 20 * (C-1) + 1
	 J = H
	 K = I + 20 - 1
      end
      if D == 4 then
	 %Break the wall on the West
	 H = 10 + 20 * (B-1)
	 I = 10 + 20 * (C-1) + 1
	 J = H 
	 K = I + 20 - 1
      end
      {A create(line H I J K fill:white)}
   end

   %Set the start and end cells
   fun {ChooseCell A B C D E}
      H I J
   in
      J = {UpdateRecord E C D 6 B}
      H = 20 + 20 * (D-1)
      I = 20 + 20 * (C-1)+1
      if B == 0 then
	 %Start cell
	 {A create(text H I text:"S" fill:blue)}
      else
	 %End cell
	 {A create(text H I text:"E" fill:red)}
      end
      J
   end

   %Reset the visited and previous fields to 0
   fun {ClearRec A B C}
      D E F G
   in
      D = {UpdateRecord A B C 5 0}
      E = {UpdateRecord D B C 6 0}
      if B < 20 then
	 F = {ClearRec E B+1 C}
	 F
      else
	 if C < 20 then
	    G = {ClearRec E 1 C+1}
	    G
	 else
	    E
	 end
      end
   end

    %Return if there's unvisited cells
   fun {IsDir A B C}
      D E F G I J
   in
      I = A.B
      J = I.C
      if J.1 == 0 then
	 D = {Visited A B-1 C}
      else
	 D = 1
      end
      if D == 1 then 
	 if J.2 == 0 then
	    E = {Visited A B+1 C}
	 else
	    E = 1
	 end
	 if E == 1 then
	    if J.3 == 0 then
	       F = {Visited A B C+1}
	    else
	       F = 1
	    end
	    if F == 1 then
	       if J.4 == 0 then
		  G = {Visited A B C-1}
	       else
		  G = 1
	       end
	       if G == 1 then
		  0 %There's no possible move
	       else
		  1
	       end
	    else
	       1
	    end
	 else
	    1
	 end
      else
	 1
      end
   end

   %Draw the path where the program goes
   proc {DrawLine A B C D E F}
      H I J K
   in
      H = 20 + 20 * (B-1)
      I = 20 + 20 * (C-1)
      J = 20 + 20 * (D-1)
      K = 20 + 20 * (E-1)
      if F == 1 then
	 %New or correct path in red
	 {A create(line I H K J fill:red width:3)}
      else
	 %Wrong path in gray
	 {A create(line I H K J fill:gray width:3)}
      end
   end
   
   %Create the complete maze
   fun {CreateMaze Q A B C}
      D E I J K L M N O P R S U
   in
      %Set the cell visited
      D = {UpdateRecord A B C 5 1}
      %Check if there's a cell around which hasn't been visited
      if {Around D B C} == 0 then
	 %Get the last cell
	 L = D.B
	 M = L.C
	 if M.6 \= 0 then
	    if M.6 == 1 then
	       I = B+1
	       J = C
	    end
	    if M.6 == 2 then
	       I = B-1
	       J = C
	    end
	    if M.6 == 3 then
	       I = B
	       J = C-1
	    end
	    if M.6 == 4 then
	       I = B
	       J = C+1
	    end
	    %Return to the last cell
	    O = {CreateMaze Q D I J}
	 else
	    D
	 end
      else
         %Choose a wall
	 E = {ChooseWall D B C}
	 %Get the position of the new cell
	 if E == 1 then
	    I = B-1
	    J = C
	    U = 2
	 end
	 if E == 2 then
	    I = B+1
	    J = C
	    U = 1
	 end
	 if E == 3 then
	    J = C+1
	    I = B
	    U = 4
	 end
	 if E == 4 then
	    J = C-1
	    I = B
	    U = 3
	 end
	 if {Visited A I J} == 0 then
	    %Delete the wall in the canva
	    {DelWall Q B C E}
	    %Delete the wall in memry
	    K = {UpdateRecord D B C E 0}
	    %Set the direction
	    N = {UpdateRecord K I J 6 E}
	    %Delete the wall in the new cell
	    R = {UpdateRecord N I J U 0}
	    P = {CreateMaze Q R I J}
	 else
	    %set the wall unbreakable
	    K = {UpdateRecord D B C E 2}
	    S = {CreateMaze Q K B C}
	 end
      end
   end

   %Solve a complete maze
   proc {Solve Q A B C}
      D E L M I J N U
   in
      %Set the cell visited
      D = {UpdateRecord A B C 5 1}
      L = D.B
      M = L.C
      if {IsEnd D B C} \= 5 then
	 %Get the last cell
	 if {IsDir D B C} == 0 then
	    if M.6 == 1 then
	       I = B-1
	       J = C
	    end
	    if M.6 == 2 then
	       I = B+1
	       J = C
	    end
	    if M.6 == 3 then
	       I = B
	       J = C+1
	    end
	    if M.6 == 4 then
	       I = B
	       J = C-1
	    end
	    %Return to the last cell
	    {DrawLine Q B C I J 2}
	    {Solve Q D I J}
	 else
	  %Get the cell
	    E = {ChooseDir D B C}
	    if E == 1 then
	       I = B-1
	       J = C
	       U = 2
	    end
	    if E == 2 then
	       I = B+1
	       J = C
	       U = 1
	    end
	    if E == 3 then
	       J = C+1
	       I = B
	       U = 4
	    end
	    if E == 4 then
	       J = C-1
	       I = B
	       U = 3
	    end
	    if D.I.J.6 \= 5 then
	       N = {UpdateRecord D I J 6 U}
	       {DrawLine Q B C I J 1}
	       {Solve Q N I J}
	    else
	       {DrawLine Q B C I J 1}
	       {Solve Q D I J}
	    end
	 end
      end
   end
   
   

in
   %Draw the grid
   {{QTk.build Desc} show}
   {Drawcols C 10}
   {Drawraws C 10}
   
   %Set the boundaries
   E = {BoundaryRows FG 1 1 1} %North
   F = {BoundaryRows E 20 1 2} %South
   G = {BoundaryCols F 1 20 3} %East
   H = {BoundaryCols G 1 1 4}  %West
   
   %Choose a random cell
   A = {Random 1 20}
   B = {Random 1 20}
   I = {UpdateRecord H A B 6 0}

   %Create the maze
   J = {CreateMaze C I A B}

   %Clear the record
   K = {ClearRec J 1 1}
   
   %Choose the start cell
   O = {Random 1 20}
   P = {Random 1 20}
   L = {ChooseCell C 0 O P K}

   %Choose the finish cell
   N = {Random 1 20}
   Q = {Random 1 20}
   M = {ChooseCell C 5 N Q L}

   %Solve the maze
   {Solve C M O P}
   
   C
end

declare
Grid = {Maze}