import java.awt.*;

public class OverlappingMaze extends java.applet.Applet implements Runnable {

  int[][]
  cell,   //  0 = untouched, 1 = crumb trail back to start, 2 = used and de-trailed
  L   ,   //  connects left  0, 1, or 2
  U   ,   //  connects up    0, 1, or 2
  R   ,   //  connects right 0, 1, or 2 
  D   ;   //  connects down  0, 1, or 2

  int       X, Y, W=0, H=0 ;
  Thread    thread ;
  boolean   done   ;
  Graphics  gfx    ;

  char  direc[]=new char[4] ;
  int   dist []=new  int[4], options ;

 

  private void fillCorner(Graphics g, int centerX, int centerY, int A, int B, int RAD, boolean isBLACK) {
    double rad2INNER=(RAD-.5)*(RAD-.5);
    double rad2OUTER=(RAD+.5)*(RAD+.5);
    double radDIFF  =rad2OUTER-rad2INNER; 
    for   (int j=B; j<B+RAD; j++) {
      for (int i=A; i<A+RAD; i++) {
        double   dist2=(centerX-i-.5)*(centerX-i-.5)+(centerY-j-.5)*(centerY-j-.5);
        if (dist2>rad2INNER) {
          int greyLEVEL=255; if (dist2<rad2OUTER) greyLEVEL=(int) (255.*(dist2-rad2INNER)/radDIFF); 
          if (isBLACK) greyLEVEL=255-greyLEVEL;
          Color c=new Color(greyLEVEL,greyLEVEL,greyLEVEL); g.setColor(c);
          g.fillRect(i,j,1,1); }}}
    Color c=new Color(0,0,0); g.setColor(c); }

 

  private void clearCornerNW     (Graphics g, int E, int F) {
    fillCorner(g, 9+20*E-4, 9+20*F-4, 9+20*E-4, 9+20*F-4, 4,false); }
  private void clearCornerNE     (Graphics g, int E, int F) {
    fillCorner(g,21+20*E+4, 9+20*F-4,21+20*E  , 9+20*F-4, 4,false); } 
  private void clearCornerSW     (Graphics g, int E, int F) {
    fillCorner(g, 9+20*E-4,21+20*F+4, 9+20*E-4,21+20*F  , 4,false); }
  private void clearCornerSE     (Graphics g, int E, int F) {
    fillCorner(g,21+20*E+4,21+20*F+4,21+20*E  ,21+20*F  , 4,false); }

  private void  fillCornerSmallNW(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E+6, 9+20*F+6, 9+20*E  , 9+20*F  , 6, true); }
  private void  fillCornerSmallNE(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E+6, 9+20*F+6, 9+20*E+6, 9+20*F  , 6, true); } 
  private void  fillCornerSmallSW(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E+6, 9+20*F+6, 9+20*E  , 9+20*F+6, 6, true); }
  private void  fillCornerSmallSE(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E+6, 9+20*F+6, 9+20*E+6, 9+20*F+6, 6, true); }

  private void  fillCornerLargeNW(Graphics g, int E, int F) {
    fillCorner(g,21+20*E+4,21+20*F+4, 9+20*E  , 9+20*F  ,16, true); }
  private void  fillCornerLargeNE(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E-4,21+20*F+4, 9+20*E-4, 9+20*F  ,16, true); } 
  private void  fillCornerLargeSW(Graphics g, int E, int F) {
    fillCorner(g,21+20*E+4, 9+20*F-4, 9+20*E  , 9+20*F-4,16, true); }
  private void  fillCornerLargeSE(Graphics g, int E, int F) {
    fillCorner(g, 9+20*E-4, 9+20*F-4, 9+20*E-4, 9+20*F-4,16, true); }

 

  private void  drawCrumb(Graphics g, int X, int Y) {
    g. fillRect(X*20+15-2,Y*20+15-2,4,4); }

  private void clearCrumb(Graphics g, int X, int Y) {
    g.clearRect(X*20+15-2,Y*20+15-2,4,4); }

 

  private void   crumb() {
    cell[X][Y]=1;  drawCrumb(gfx,X,Y); }

  private void noCrumb() {
    cell[X][Y]=2; clearCrumb(gfx,X,Y); }

 

  private void drawBridge(Graphics g, int M, int N) {
    if (((M+N)&1)==0) {   //  horizontal path is on top
      for (int G=0; G<4; G++) {
        Color c=new Color(64*G,64*G,64*G); g.setColor(c);
        g.fillRect(10*(M+M+1)-1,10*(N+N+1)-2-G,12, 1);
        g.fillRect(10*(M+M+1)-1,10*(N+N+2)+1+G,12, 1); }}
    else {                //    vertical path is on top
      for (int G=0; G<4; G++) {
        Color c=new Color(64*G,64*G,64*G); g.setColor(c);
        g.fillRect(10*(M+M+1)-2-G,10*(N+N+1)-1, 1,12);
        g.fillRect(10*(M+M+2)+1+G,10*(N+N+1)-1, 1,12); }}
    Color c=new Color(0,0,0); g.setColor(c); }

 

  private void drawPath(int A, int B, int C, int D) {
    if (C>A) {   //  horizontal path
      gfx           .clearRect(21+20*A, 9+20*B, 8,12);
      if (C-A>1) gfx.clearRect(41+20*A, 9+20*B, 8,12); } 
    else {       //    vertical path
      gfx           .clearRect( 9+20*A,21+20*B,12, 8);
      if (D-B>1) gfx.clearRect( 9+20*A,41+20*B,12, 8); }
    if (C-A>1 || D-B>1) drawBridge(gfx,(A+C)/2,(B+D)/2); }

 

  public void paint(Graphics g) {   //  Draw the entire maze in its current state.
    if (W<1 || H<1) return;   //  <-- Sometimes, paint() can be called before first call to run().
    for   (int y=0; y<H; y++) { 
      for (int x=0; x<W; x++) {
        g                                 .fillRect(20*x+1,20*y+1, 8, 8);
        if (L[x][y]==0 && L[x+1][y  ]<2) g.fillRect(20*x+1,20*y+9, 8,12);
        if (U[x][y]==0 && U[x  ][y+1]<2) g.fillRect(20*x+9,20*y+1,12, 8);
        if (cell[x][y]==1) drawCrumb(g,x,y);
        if (x>0 && x<W-1 && y>0 && y<H-1 && (L[x+1][y]==2 || U[x][y+1]==2)) drawBridge(g,x,y); }} 
    g.fillRect(1,20*H+1,    8+20*W,8);
    g.fillRect(  20*W+1,1,8,8+20*H  );
    if (done) {   //  (fancy frills that are drawn only when the maze is completed)
      //  Rounded corners.
      for   (int y=0; y<H; y++) { 
        for (int x=0; x<W; x++) {
          if (U[x][y]!=0 && L[x][y]!=0) clearCornerNW(g,x,y);
          if (U[x][y]!=0 && R[x][y]!=0) clearCornerNE(g,x,y);
          if (D[x][y]!=0 && L[x][y]!=0) clearCornerSW(g,x,y); 
          if (D[x][y]!=0 && R[x][y]!=0) clearCornerSE(g,x,y);
          if (L[x][y]==0 && U[x][y]==0 && (R[x][y]==0 && D[x][y]!=0 || R[x][y]!=0 && D[x][y]==0)) fillCornerSmallNW(g,x,y); 
          if (R[x][y]==0 && U[x][y]==0 && (L[x][y]==0 && D[x][y]!=0 || L[x][y]!=0 && D[x][y]==0)) fillCornerSmallNE(g,x,y);
          if (L[x][y]==0 && D[x][y]==0 && (R[x][y]==0 && U[x][y]!=0 || R[x][y]!=0 && U[x][y]==0)) fillCornerSmallSW(g,x,y); 
          if (R[x][y]==0 && D[x][y]==0 && (L[x][y]==0 && U[x][y]!=0 || L[x][y]!=0 && U[x][y]==0)) fillCornerSmallSE(g,x,y);
          if (L[x][y]==0 && U[x][y]==0 &&  R[x][y]!=0 && D[x][y]!=0) fillCornerLargeNW(g,x,y); 
          if (L[x][y]!=0 && U[x][y]==0 &&  R[x][y]==0 && D[x][y]!=0) fillCornerLargeNE(g,x,y);
          if (L[x][y]==0 && U[x][y]!=0 &&  R[x][y]!=0 && D[x][y]==0) fillCornerLargeSW(g,x,y); 
          if (L[x][y]!=0 && U[x][y]!=0 &&  R[x][y]==0 && D[x][y]==0) fillCornerLargeSE(g,x,y); }}
      //  Bottom opening of maze.  (Top opening appears automatically.)
      g.clearRect(20*W-11,20*H+1,12,8);
      //  Rounded corners for exterior edge of maze. 
      clearCornerSW(g,  0,-1);
      clearCornerSE(g,  0,-1);
      clearCornerNW(g,W-1, H);
      clearCornerNE(g,W-1, H);
      clearCornerSE(g, -1,-1);
      clearCornerSW(g,W  ,-1);
      clearCornerNW(g,W  , H); 
      clearCornerNE(g, -1, H); }}

 

  public void start() {
    Color
    c=new Color(255,255,255); setBackground(c);
    c=new Color(  0,  0,  0); setForeground(c);
    thread=new Thread(this); thread.start(); }

 

  private void snooze() {
    try {
      thread.sleep(50); }   //  1/20 of a second
    catch (InterruptedException e) {
      }}

 

  public void run() {

    //  Initialize globals.
    W=(size().width -10)/20; gfx =getGraphics();
    H=(size().height-10)/20; done=false;

    //  Exit if graphics area is too small.
    if (W<1 || H<1) return;

    //  Set up the starting grid data.
    cell=new int[W+1][H+1];
    L   =new int[W+1][H+1];
    U   =new int[W+1][H+1];
    R   =new int[W+1][H+1];
    D   =new int[W+1][H+1];
    for   (int i=0; i<=W; i++) { 
      for (int j=0; j<=H; j++) {
        cell[i][j]=0;
        L   [i][j]=0;
        U   [i][j]=0;
        R   [i][j]=0;
        D   [i][j]=0; }}

    //  Initialize the maze-generating conditions.
    X=W/2; Y=H/2; crumb(); repaint();

    //  Main, maze-generation loop.
    while (!done) {

      //  Govern the speed of execution, and give paint events a chance to occur.
      snooze();

      //  Make a list of up to four ways that the trail can be extended.
      options=0;
      if (X>0   && cell[X-1][Y  ]==0) {
        direc[options]='L'; dist[options]=1; options++; }
      if (Y>0   && cell[X  ][Y-1]==0) { 
        direc[options]='U'; dist[options]=1; options++; }
      if (X<W-1 && cell[X+1][Y  ]==0) {
        direc[options]='R'; dist[options]=1; options++; }
      if (Y<H-1 && cell[X  ][Y+1]==0) { 
        direc[options]='D'; dist[options]=1; options++; }
      if (X>1   && cell[X-1][Y  ]!=0 && L[X-1][Y  ]==0 && U[X-1][Y  ]!=0 && R[X-1][Y  ]==0 && D[X-1][Y  ]!=0 && cell[X-2][Y  ]==0) { 
        direc[options]='L'; dist[options]=2; options++; }
      if (Y>1   && cell[X  ][Y-1]!=0 && L[X  ][Y-1]!=0 && U[X  ][Y-1]==0 && R[X  ][Y-1]!=0 && D[X  ][Y-1]==0 && cell[X  ][Y-2]==0) { 
        direc[options]='U'; dist[options]=2; options++; }
      if (X<W-2 && cell[X+1][Y  ]!=0 && L[X+1][Y  ]==0 && U[X+1][Y  ]!=0 && R[X+1][Y  ]==0 && D[X+1][Y  ]!=0 && cell[X+2][Y  ]==0) { 
        direc[options]='R'; dist[options]=2; options++; }
      if (Y<H-2 && cell[X  ][Y+1]!=0 && L[X  ][Y+1]!=0 && U[X  ][Y+1]==0 && R[X  ][Y+1]!=0 && D[X  ][Y+1]==0 && cell[X  ][Y+2]==0) { 
        direc[options]='D'; dist[options]=2; options++; }

      if (options>0) {   //   Extend the path.
        int i=(int) (Math.random()*options);
        if (direc[i]=='L') {
          L[X][Y]=dist[i]; drawPath(X-dist[i],Y,X,Y); X-=dist[i]; R[X][Y]=dist[i]; } 
        if (direc[i]=='U') {
          U[X][Y]=dist[i]; drawPath(X,Y-dist[i],X,Y); Y-=dist[i]; D[X][Y]=dist[i]; }
        if (direc[i]=='R') {
          R[X][Y]=dist[i]; drawPath(X,Y,X+dist[i],Y); X+=dist[i]; L[X][Y]=dist[i]; } 
        if (direc[i]=='D') {
          D[X][Y]=dist[i]; drawPath(X,Y,X,Y+dist[i]); Y+=dist[i]; U[X][Y]=dist[i]; }
        crumb(); }

      else {   //  Retreat the path.
        noCrumb();
        if      (cell[X-L[X][Y]][Y        ]==1) X-=L[X][Y];
        else if (cell[X        ][Y-U[X][Y]]==1) Y-=U[X][Y];
        else if (cell[X+R[X][Y]][Y        ]==1) X+=R[X][Y]; 
        else if (cell[X        ][Y+D[X][Y]]==1) Y+=D[X][Y];
        else                                    done=true; }}

    //  Open up the start and end of the maze.
    U[0][0]=1; D[W-1][H-1]=1;

    //  Redraw the entire maze to open up the start and end, and to perform other pretty touch-ups.
    repaint(); }}