% {\tt tiling.mp} 
% {\bf Truchet's problem: macros}
%==================================================
% D. Roegel's solution for Denis Girou's {\tt pstricks} competition.
% This solution is written in {\tt METAPOST}.
% The source file may be formatted using the {\tt mft} program.
% (the program used for volumes B and E of {\it Computers \& Typesetting\/})
% Send comments and improvements to {\tt roegel@loria.fr}.
% -------------------------------------------------------------------------
% \underbar{History}:
% 9-10 June 1995 (lines)
% 13-14 June 1995 (surfaces)
% 16 June 1995 (comments and restructuring)
% 21 June 1995 (some more formatting for {\tt mft})
% 26 June 1995 (some simplifications)
%  9 July 1995 (macros and examples were split and code better organized)
%
% This is my first ``large'' {\tt METAPOST} program. I'm still learning!
% Therefore lots of things are clumsy and I don't pretend this
% is an example of good {\tt METAPOST} programming.
% I had however great fun writing it!
%
% \underbar{Some highlights}:
% The coloring of lines worked after circa 4 hours $\ldots$
% The only real problem I met was that an infinite loop occured
% when |follow_line| was following a cyclic path.
%
% Concerning the coloration of surfaces, I needed some time
% until I noticed that two colors were sufficient!
% Once you notice this and draw all the conclusions, the task is trivial.
% -------------------------------------------------------------------------
%
% A tiling |Nx| $\times$ |Ny| is a matrix of tiles indexed by |x| 
% ranging between
% |0| and |Nx-1| and |y| ranging between |0| and |Ny-1|.
% Two kinds of tiles are considered. We will refer to them as `tile 0'
% and `tile 1'. Each tile has three parts, marked {\tt*}, {\tt+} and {\tt x}.
% {\catcode`\.=13\gdef\os{\obeyspaces\tt\frenchspacing
%                         \catcode`\.=13\def.{\char124 }}}
% {\os
% Tile 0: |" ------ "| Tile 1: |" ------ "|
%         |".* .   ."|         |".  . * ."|
%         |"._/ + _."|         |"._ +\ _."|
%         |".    /x."|         |".x\    ."|
%         |".___.__."|         |".__.___."|} 
%
% ---------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Tiling orientation and color initialization: BEGINNING
%-----------------------------------------------------------------------------

% We define the tiling randomly.
def init_tiling(expr nx,ny) =
   for i:=0 upto nx-1:
     for j:=0 upto ny-1:
       tile[i][j]:=coin; % we throw a coin for each tile.
     endfor;
   endfor;
  enddef;

% The `coin' macro behaves like a coin and yields randomly |0| or |1|.
% This is used for the initial tiling.
def coin = floor(uniformdeviate 2) enddef;

% We let |-1| mean ``no color yet''.
def init_colors = 
   for i:=0 upto Nx-1: for j:=0 upto Ny-1: 
     tilecolor[i][j][0]:=-1; % right
     tilecolor[i][j][1]:=-1; % up
     tilecolor[i][j][2]:=-1; % left
     tilecolor[i][j][3]:=-1; % down
   endfor; endfor;
  enddef;

def init_partcolors = 
   for i:=0 upto Nx-1: 
      for j:=0 upto Ny-1: 
         tilepartcolor[i][j][0]:=-1; % up left  or up right
         tilepartcolor[i][j][1]:=-1; % middle   
         tilepartcolor[i][j][2]:=-1; % down right or down left
      endfor; 
   endfor;
  enddef;

% The macro |TileColors| allows to define or redefine the colors.
% Only two colors are necessary.

def TileColors(expr ca, cb) =
   def partcolor(expr c) = 
      if c=0: ca
      else: cb
      fi
   enddef;
  enddef;

% The default colors are |red| and |(1,1,0)| (in RGB coordinates)
TileColors(red, (1,1,0));

% A useful color. We might also have used the \.{color} type.
def yellow = (1,1,0) enddef; % RGB definition

% The basic pattern is the following quartercircle;
% It is used later on, shifted and rotated.
def define_basetile(expr u) =
    path upperleft;
    upperleft:=((0,0.5){right}..{up}(0.5,1)) scaled u;
  enddef;

% Here, we define the paths corresponding to the upper left and middle 
% parts of the tile 0.

def define_basetilepart(expr u) =
    path tilepart[];
    % left upper corner of a standard tile
    tilepart0:=((0,0.5){right}..{up}(0.5,1)--(0,1)--cycle) scaled u;
    % middle part of the standard tile
    tilepart1:=((0,0.5){right}..{up}(0.5,1)--(1,1)--
                (1,0.5){left}..{down}(0.5,0)--(0,0)--cycle) scaled u;
  enddef;

% The external frame is drawn outside the rectangle (0,0) -- (nx*u,ny*u). 
% Guess why ?
vardef draw_boundaries(expr nx,ny) =
    numeric u,delta;
    u=TilingUnit;delta=.5mm;
    pickup pencircle scaled (2*delta);
    draw(0-delta,0-delta)--(0-delta,ny*u+delta)--
        (nx*u+delta,ny*u+delta)--(nx*u+delta,0-delta)--cycle;
    for i:=1 upto nx-1:draw(i*u,0)--(i*u,ny*u);endfor;
    for i:=1 upto ny-1:draw(0,i*u)--(nx*u,i*u);endfor;
  enddef;

%-----------------------------------------------------------------------------
% Tiling orientation and color initialization: END
%-----------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Computation of line colors: BEGINNING
%-----------------------------------------------------------------------------
% The macro |compute_linecolors| `computes' the colors of the lines.
% As a matter of fact, all what it does is going through all
% the tiles, choose a not yet colored line, and follow it on
% both directions, and simultaneously coloring it.
% For each line a new color is used.
%
vardef compute_linecolors = 
   numeric k;
   init_colors;
   for i:=0 upto Nx-1: 
      for j:=0 upto Ny-1: 
         forever:
            k:=not_colored_direction(i,j);% choose a non colored line.
            exitif k=-1; % there is none, go to the next tile.
            follow_line(i,j,k,nextcolor); % Follow this line and color it with
                                     % |nextcolor|.
            k:=dual(i,j,k);          % Get the opposite direction.
            if tilecolor[i][j][k] = -1: % If it is not yet colored, 
                follow_line(i,j,k,nextcolor); % follow the line.
            fi;
            nextcolor:=nextcolor+1; 
          endfor;
       endfor; 
    endfor;
  enddef;

% This macro gives a direction not yet colored.
% If there is none, it yields |-1|.
def not_colored_direction(expr x,y) = 
   if     tilecolor[x][y][0] = -1 : 0
   elseif tilecolor[x][y][1] = -1 : 1
   elseif tilecolor[x][y][2] = -1 : 2
   elseif tilecolor[x][y][3] = -1 : 3
   else: -1
   fi
  enddef;

% Colour a line and follow it.
% Notice that for each tile except the first one, two directions
% must be colored.
%
vardef follow_line(expr x,y,d,c) = % |x|,|y| are the beginning coordinates
                           % |d| is the direction in which we advance
                           % |c| is the color used
   tilecolor[x][y][d]:=c;xx:=x;yy:=y;dd:=d;
   forever:
      exitif last_tile(xx,yy,dd); % are we at an edge ?
      next_tile;% get the new values of |xx|, |yy| and |dd|.
      du:=dual(xx,yy,dd);
      exitif tilecolor[xx][yy][du] > -1; % are we in a cycle ?
      tilecolor[xx][yy][du]:=c;tilecolor[xx][yy][dd]:=c;
    endfor;
  enddef;


% This macro gives the direction dual to |d| in a tile.
def dual(expr x,y,d) =
    (((2*tile[x][y]) + if d=0: 3 elseif d=1: 2 elseif d=2: 1 else: 0 fi) mod 4)
   enddef;

% This macro is true if a line goes outside the rectangle.
def last_tile(expr x,y,d) = 
   if (x=0) and (d=2) or 
      (x=Nx-1) and (d=0) or 
      (y=0) and (d=3) or 
      (y=Ny-1) and (d=1): true
   else: false
   fi;
  enddef;

def next_tile = 
   if     dd=0: xx:=xx+1;dd:=(1+2*tile[xx][yy]) mod 4;
   elseif dd=1: yy:=yy+1;dd:=(0+2*tile[xx][yy]) mod 4;
   elseif dd=2: xx:=xx-1;dd:=(3+2*tile[xx][yy]) mod 4;
   else:        yy:=yy-1;dd:=(2+2*tile[xx][yy]) mod 4;
   fi
  enddef;

%-----------------------------------------------------------------------------
% Computation of line colors: END
%-----------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Drawing of the colored lines: BEGINNING
%-----------------------------------------------------------------------------

% For each tile, we color the lines.
vardef draw_coloredlines(expr nx,ny) =
   save u;
   u=TilingUnit;
   pickup pencircle scaled TilingLineWidth;
   for i:=0 upto nx-1: 
      for j:=0 upto ny-1: 
        color_thetile(i,j); % here we draw the colored tiles.
      endfor; 
   endfor;  
  enddef;

% This macro just draws the left and right part of a tile.
def color_thetile(expr x,y) = 
    draw_upperleft(x,y,tile[x][y]*90,tilecolor[x][y][2]);
    draw_upperleft(x,y,180+90*tile[x][y],tilecolor[x][y][0]);
   enddef;

% The macro |draw_upperleft| draws the |upperleft| path, rotated by angle |a|,
% and with a color depending on |c|.

def draw_upperleft(expr x,y,a,c) =
   draw upperleft shifted (-.5u,-.5u) rotated a 
     shifted (.5u,.5u) shifted ((x,y)*u) 
     withcolor (linecolor(c));
   enddef;

% The kind of line color is chosen here; this may be changed.
def linecolor(expr c) = (c/nextcolor)[red,green] enddef;

%-----------------------------------------------------------------------------
% Drawing of the colored lines: END
%-----------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Computation of tile colors: BEGINNING
%-----------------------------------------------------------------------------

% In order to color the tiling, we need only two colors.
% These colors are numbered |0| and |1|. 
% The whole tiling can be performed at once.

def compute_partcolors = 
   init_partcolors;
   for i:=0 upto Nx-1: 
      for j:=0 upto Ny-1: 
          fill_tile(i,j);
      endfor; 
   endfor;
  enddef;

% This macro collects the colors of the neighbours (only down and left) 
% and updates the current tile, where possible.
%
def fill_tile(expr x,y) =
   init_neighbours(x,y); % get the color of the neighbouring tiles
   if tile[x][y]=0:
     handle_edges(7)(x,y,0);
     handle_edges(5,6)(x,y,1);
     handle_edges(4)(x,y,2);
   else:
     handle_edges(5,6)(x,y,2);
     handle_edges(4,7)(x,y,1);
   fi;
   complete_tile(x,y);
  enddef;

% Neighbours are initialized in an obvious way.
% The numbering of the neighbours is dual to the numbering
% of edges (see below).
% (commented lines are just given for sake of completeness;
%  they are not actually used)
%

def init_neighbours(expr x,y) =
   for i:=0 upto 7:neighbour_edgecolors[i]:=-1;endfor;
   if x>0: 
      neighbour_edgecolors[7]:=edge_color(x-1,y,2); 
      neighbour_edgecolors[6]:=edge_color(x-1,y,3); 
   fi;
%      |if x<Nx-1 : neighbour_edgecolors[2]:=edge_color(x+1,y,7);|
%                |neighbour_edgecolors[3]:=edge_color(x+1,y,6); fi;|
   if y>0: 
      neighbour_edgecolors[5]:=edge_color(x,y-1,0); 
      neighbour_edgecolors[4]:=edge_color(x,y-1,1); 
   fi;
%      |if y<Ny-1 : neighbour_edgecolors[0]:=edge_color(x,y+1,5);| 
%                |neighbour_edgecolors[1]:=edge_color(x,y+1,4); fi;|
  enddef;

% This macro spreads the colors of the neighbours in the list |e|
% onto the part |f| of tile |[x,y]|.
%
def handle_edges(text e)(expr x,y,f) =
   forsuffixes s:=e: 
      if neighbour_edgecolors[s]>-1 : 
         tilepartcolor[x][y][f]:=neighbour_edgecolors[s];
      fi;
   endfor;
  enddef;

% The macro |edge_color| gives the color of an edge, if any.
% There are eight edges, and they are numbered from |0| to |7|.
%
%
%{\os *0 0 0 1 1 1*
%  7           2
%  7           2
%  7           2
%  6           3
%  6           3
%  6           3
%  *5 5 5 4 4 4*}
%
% 
def edge_color(expr x,y,e) =
   if tile[x][y]=0:
     if (e=0) or (e=7):     tilepartcolor[x][y][0];
     elseif (e=3) or (e=4): tilepartcolor[x][y][2];
     else:                  tilepartcolor[x][y][1];
     fi;
   else:
     if (e=1) or (e=2):     tilepartcolor[x][y][0];
     elseif (e=5) or (e=6): tilepartcolor[x][y][2];
     else:                  tilepartcolor[x][y][1];
     fi;
   fi;
  enddef;

% Since two colors are enough, as soon as one part of a tile
% is colored, we can immediately color the others.
def complete_tile(expr x,y) =
   if tilepartcolor[x][y][0] > -1:
     tilepartcolor[x][y][1]:=1-tilepartcolor[x][y][0];
     tilepartcolor[x][y][2]:=tilepartcolor[x][y][0];
   fi;
   if tilepartcolor[x][y][1] > -1:
     tilepartcolor[x][y][0]:=1-tilepartcolor[x][y][1];
     tilepartcolor[x][y][2]:=1-tilepartcolor[x][y][1];
   fi;
   if tilepartcolor[x][y][2] > -1:
     tilepartcolor[x][y][1]:=1-tilepartcolor[x][y][2];
     tilepartcolor[x][y][0]:=tilepartcolor[x][y][2];
   fi;
   if tilepartcolor[x][y][0] = -1: % this part is only used at 
                                   % the very beginning of a tiling, and 
                                   % serves as initialization.
     tilepartcolor[x][y][0]:=0;
     tilepartcolor[x][y][1]:=1;
     tilepartcolor[x][y][2]:=0;
   fi;
  enddef;

%-----------------------------------------------------------------------------
% Computation of tile colors: END
%-----------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Drawing of tile colors: BEGINNING
%-----------------------------------------------------------------------------

% For each tile, we color the three parts.
vardef draw_coloredparts(expr nx,ny) =
   save u;
   u=TilingUnit;
   for i:=0 upto nx-1: 
      for j:=0 upto ny-1: 
           fill_tilepart(i,j,1);
           fill_tilepart(i,j,2);
           fill_tilepart(i,j,3);
      endfor;
   endfor;
  enddef;

% |fill_tilepart| fills part |part| at position |x|, |y|.
def fill_tilepart(expr x,y,part) =
   if part=1: 
      colorpart(x,y,0,-90*tile[x][y],partcolor(tilepartcolor[x][y][0]));
   elseif part=2: 
      colorpart(x,y,1,90*tile[x][y],partcolor(tilepartcolor[x][y][1]));
   else: 
      colorpart(x,y,0,180-90*tile[x][y],partcolor(tilepartcolor[x][y][2]));
   fi;
  enddef;

% |colorpart| colors a part |p| (0 is corner, 1 is middle) 
% at position |x|, |y|, using the fundamental
% |tilepart[p]| pattern, rotated by |a| degrees and colored according to |c|.

vardef colorpart(expr x,y,p,a,c) =
   fill (tilepart[p] shifted (-.5u,-.5u)
      rotated a 
      shifted (.5u,.5u)
      shifted ((x,y)*u)) withcolor (c);
  enddef;

%-----------------------------------------------------------------------------
% Drawing of tile colors: END
%-----------------------------------------------------------------------------
%\vfill\eject
%-----------------------------------------------------------------------------
% Main definition
%-----------------------------------------------------------------------------

% This is the main definition. 
% Two cases are considered: either the lines are colored, and the surfaces
% are not filled, or the surfaces are colored, but the lines are not.

vardef TruchetTiling(expr x,y) =
   save Nx,Ny;
   Nx=x;
   Ny=y;
   init_tiling(Nx,Ny);
   draw_boundaries(Nx,Ny);
   if not TruchetTilingFill:
      define_basetile(TilingUnit);
      numeric nextcolor,tilecolor[][][]; 
      nextcolor:=0;
      compute_linecolors; % the colors of the lines are computed here, 
                          % but not drawn;
      draw_coloredlines(Nx,Ny);
   else:
      define_basetilepart(TilingUnit);
      numeric tilepartcolor[][][],neighbour_edgecolors[];
      compute_partcolors;
      draw_coloredparts(Nx,Ny);
   fi;
  enddef;

%-----------------------------------------------------------------------------
% Global variables and default values
%-----------------------------------------------------------------------------

numeric tile[][];
boolean TruchetTilingFill;
TruchetTilingFill=false;
numeric TilingUnit,TilingLineWidth;
% default values
TilingUnit:=1cm;
TilingLineWidth:=1mm;

%-----------------------------------------------------------------------------
% End of file tiling.mp
%-----------------------------------------------------------------------------