import java.awt.*;

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

  //  Constants.
  final int INNER_SECTORS_PER_QUADRANT= 4;
  final int WALL_THICKNESS            = 6;
  final int TRACK_WIDTH               =18;

  int[][]   //  first param = inner circle to outer; second param = position in the circle
  cell,     //  0 = untouched, 1 = crumb trail back to start, 2 = used and de-trailed
  L   ,     //  connects left  0 or 1  (counter-clockwise)
  U   ,     //  connects up    0 or 1  (toward center)
  R   ,     //  connects right 0 or 1  (clockwise)
  D   ;     //  connects down  0 or 1  (away from center)

  int       X, Y, tracks=0, center, roomRad, sectorsPerTrack[], inPaintMaze=0;
  Thread    thread ;
  boolean   done   ;
  Graphics  gfx    ;

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



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

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



  public void drawCell(Graphics g, int track, int sector) {

    //  Determine the smallest rectangular area that includes the desired cell.
    int rectA=size().width, rectB=size().height, rectC=0, rectD=0;
    double x, y;
    x=center+(roomRad+TRACK_WIDTH* track   )*Math.cos(6.2831853* sector   /(double) sectorsPerTrack[track]);
    if (rectA>x) rectA=(int) x  ;
    if (rectC<x) rectC=(int) x+1;
    x=center+(roomRad+TRACK_WIDTH* track   )*Math.cos(6.2831853*(sector+1)/(double) sectorsPerTrack[track]);
    if (rectA>x) rectA=(int) x  ;
    if (rectC<x) rectC=(int) x+1;
    x=center+(roomRad+TRACK_WIDTH*(track+1))*Math.cos(6.2831853* sector   /(double) sectorsPerTrack[track]);
    if (rectA>x) rectA=(int) x  ;
    if (rectC<x) rectC=(int) x+1;
    x=center+(roomRad+TRACK_WIDTH*(track+1))*Math.cos(6.2831853*(sector+1)/(double) sectorsPerTrack[track]);
    if (rectA>x) rectA=(int) x  ;
    if (rectC<x) rectC=(int) x+1;
    y=center+(roomRad+TRACK_WIDTH* track   )*Math.sin(6.2831853* sector   /(double) sectorsPerTrack[track]);
    if (rectB>y) rectB=(int) y  ;
    if (rectD<y) rectD=(int) y+1;
    y=center+(roomRad+TRACK_WIDTH* track   )*Math.sin(6.2831853*(sector+1)/(double) sectorsPerTrack[track]);
    if (rectB>y) rectB=(int) y  ;
    if (rectD<y) rectD=(int) y+1;
    y=center+(roomRad+TRACK_WIDTH*(track+1))*Math.sin(6.2831853* sector   /(double) sectorsPerTrack[track]);
    if (rectB>y) rectB=(int) y  ;
    if (rectD<y) rectD=(int) y+1;
    y=center+(roomRad+TRACK_WIDTH*(track+1))*Math.sin(6.2831853*(sector+1)/(double) sectorsPerTrack[track]);
    if (rectB>y) rectB=(int) y  ;
    if (rectD<y) rectD=(int) y+1;

    //  Draw the cell.
    paintMaze(g,rectA,rectB,rectC,rectD,1); }



  private void paintMaze(Graphics g, int rectL, int rectT, int rectR, int rectB, int subPixels) {

    double   tX, tY, tDIST, dist2, distA, distB, distC, slopeA, slopeB, slopeC, slope, sectorSin[], sectorCos[] ;
    int      pixSum, track, grey, sectorSkip[], sectorIndex, i, j, ii, jj ;
    double   radA , radB , radC , radD  ;
    double   radA2, radB2, radC2, radD2 ;
    double   cosA, cosB, cosC ;
    double   sinA, sinB, sinC ;
    boolean  crumbShade ;
    Color    c ;

    inPaintMaze++;

    //  Set up sine/cosine tables to avoid having to constantly recalculate them during bulk image processing.
    sectorSin=new double[sectorsPerTrack[tracks-1]*2+1];
    sectorCos=new double[sectorsPerTrack[tracks-1]*2+1];
    for (i=0; i<=sectorsPerTrack[tracks-1]*2; i++) {
      sectorCos[i]=Math.cos(6.2831853*i/(double) sectorsPerTrack[tracks-1]/2.);
      sectorSin[i]=Math.sin(6.2831853*i/(double) sectorsPerTrack[tracks-1]/2.); }
    sectorSkip=new int[tracks]; for (i=0; i<tracks; i++) sectorSkip[i]=sectorsPerTrack[tracks-1]/sectorsPerTrack[i];

    //  Main loops to generate the maze image.
    for   (j=rectT;  j<rectB;  j++) {
      for (i=rectL;  i<rectR;  i++) {
        pixSum=0; crumbShade=false;
        for   (jj=0; jj<subPixels; jj++) {
          tY  =j+(jj+.5)/(double) subPixels-center;
          for (ii=0; ii<subPixels; ii++) {
            tX=i+(ii+.5)/(double) subPixels-center;
            tDIST=Math.sqrt(tX*tX+tY*tY);
            track=(int) ((tDIST-roomRad)/(double) TRACK_WIDTH);

            //  Exterior region.
            if (track>=tracks) {
              if ( tDIST<roomRad+TRACK_WIDTH*tracks+WALL_THICKNESS/2
              &&  (!done || tX>=0. || tY<=0. || tY/tX>=
              sectorSin[(sectorsPerTrack[tracks-1]*2)/4+2]/
              sectorCos[(sectorsPerTrack[tracks-1]*2)/4+2]
              ||   ((tX-sectorCos[(sectorsPerTrack[tracks-1]*2)/4+2]*(roomRad+TRACK_WIDTH*tracks))
              *     (tX-sectorCos[(sectorsPerTrack[tracks-1]*2)/4+2]*(roomRad+TRACK_WIDTH*tracks))
              +     (tY-sectorSin[(sectorsPerTrack[tracks-1]*2)/4+2]*(roomRad+TRACK_WIDTH*tracks))
              *     (tY-sectorSin[(sectorsPerTrack[tracks-1]*2)/4+2]*(roomRad+TRACK_WIDTH*tracks))<
              WALL_THICKNESS/2*WALL_THICKNESS/2)
              ||   ( tX*tX
              +     (tY-(roomRad+TRACK_WIDTH*tracks))
              *     (tY-(roomRad+TRACK_WIDTH*tracks))<
              WALL_THICKNESS/2*WALL_THICKNESS/2))) {
                pixSum++; }}

            //  Interior region.
            else if (tDIST<roomRad) {
              if ( tDIST>=roomRad-WALL_THICKNESS/2
              &&  (!done || tX<=0. || tY>=0. || tY/tX>=
              sectorSin[((sectorsPerTrack[0]*2)/4+2)*sectorSkip[0]]/
              sectorCos[((sectorsPerTrack[0]*2)/4+2)*sectorSkip[0]]
              ||   ((tX-sectorCos[((sectorsPerTrack[0]*2)*3/4+2)*sectorSkip[0]]*roomRad)
              *     (tX-sectorCos[((sectorsPerTrack[0]*2)*3/4+2)*sectorSkip[0]]*roomRad)
              +     (tY-sectorSin[((sectorsPerTrack[0]*2)*3/4+2)*sectorSkip[0]]*roomRad)
              *     (tY-sectorSin[((sectorsPerTrack[0]*2)*3/4+2)*sectorSkip[0]]*roomRad)<
              WALL_THICKNESS/2*WALL_THICKNESS/2)
              ||   ( tX*tX
              +     (tY+roomRad)
              *     (tY+roomRad)<
              WALL_THICKNESS/2*WALL_THICKNESS/2))
              || (done && tX*tX+tY*tY<(WALL_THICKNESS/2*WALL_THICKNESS/2))) {
                pixSum++; }}

            //  Cells of the maze.
            else {
              radA=roomRad+ track   *TRACK_WIDTH                 ; radA2=radA*radA;
              radB=roomRad+ track   *TRACK_WIDTH+WALL_THICKNESS/2; radB2=radB*radB;
              radC=roomRad+(track+1)*TRACK_WIDTH-WALL_THICKNESS/2; radC2=radC*radC;
              radD=roomRad+(track+1)*TRACK_WIDTH                 ; radD2=radD*radD;
              for (int sector=0; sector<sectorsPerTrack[track]; sector++) {
                sectorIndex=sector*2*sectorSkip[track];
                cosA=sectorCos[sectorIndex];
                sinA=sectorSin[sectorIndex]; sectorIndex+=sectorSkip[track];
                cosB=sectorCos[sectorIndex];
                sinB=sectorSin[sectorIndex]; sectorIndex+=sectorSkip[track];
                cosC=sectorCos[sectorIndex];
                sinC=sectorSin[sectorIndex];
                if (cosA>-.00001 && cosA<.0001) {
                  cosA=-.0000001; if (sinA<0.) cosA*=-1.; }
                if (cosC>-.00001 && cosC<.0001) {
                  cosC= .0000001; if (sinC<0.) cosC*=-1.; }
                slopeA=sinA/cosA;
                slopeB=sinB/cosB;
                slopeC=sinC/cosC;
                dist2=tX*tX+tY*tY; slope=tY/tX;
                if (slope>=slopeA && tX*cosB>0
                &&  slope< slopeC && tY*sinB>0
                &&  dist2>=radA2
                &&  dist2< radD2) {   //  Pixel is governed by this cell.
                  distA=Math.abs(tY*cosA-tX*sinA); if (cell[track][sector]==1) crumbShade=true;
                  distB=Math.abs(tY*cosB-tX*sinB);
                  distC=Math.abs(tY*cosC-tX*sinC);
                  //  Corner posts.
                  if ((dist2< radB2
                  ||   dist2>=radC2)
                  &&  (distA<WALL_THICKNESS/2
                  ||   distB<WALL_THICKNESS/2 && track<tracks-1 && sectorsPerTrack[track]<sectorsPerTrack[track+1] && dist2>=radC2
                  ||   distC<WALL_THICKNESS/2)
                  //  (The rest of this "if" condition rounds off the exterior corners of the walls.)
                  &&  (!done
                  ||   (tX-sectorCos[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tX-sectorCos[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  +    (tY-sectorSin[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tY-sectorSin[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))<
                  WALL_THICKNESS/2*WALL_THICKNESS/2
                  ||   (tX-sectorCos[(sector*2+1)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tX-sectorCos[(sector*2+1)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  +    (tY-sectorSin[(sector*2+1)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tY-sectorSin[(sector*2+1)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))<
                  WALL_THICKNESS/2*WALL_THICKNESS/2
                  ||   (tX-sectorCos[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tX-sectorCos[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  +    (tY-sectorSin[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))
                  *    (tY-sectorSin[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track+TRACK_WIDTH))<
                  WALL_THICKNESS/2*WALL_THICKNESS/2
                  ||   (tX-sectorCos[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  *    (tX-sectorCos[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  +    (tY-sectorSin[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  *    (tY-sectorSin[ sector*2   *sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))<
                  WALL_THICKNESS/2*WALL_THICKNESS/2
                  ||   (tX-sectorCos[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  *    (tX-sectorCos[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  +    (tY-sectorSin[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))
                  *    (tY-sectorSin[(sector*2+2)*sectorSkip[track]]*(roomRad+TRACK_WIDTH*track            ))<
                  WALL_THICKNESS/2*WALL_THICKNESS/2)) {
                    pixSum++; break; }
                  //  Concentric walls of the cell.
                  else if (dist2< radB2 &&  U[track  ][sector    ]==0
                  ||       dist2>=radC2 &&  D[track  ][sector    ]==0
                  ||       track<tracks-1 && sectorsPerTrack[track]<sectorsPerTrack[track+1]
                  &&       dist2>=radC2 && (U[track+1][sector*2  ]==0 && slope< slopeB
                  ||                        U[track+1][sector*2+1]==0 && slope>=slopeB)) {
                    pixSum++; break; }
                  //  Radial walls of the cell.
                  else if (distA<WALL_THICKNESS/2 && L[track][sector]==0) {
                    pixSum++; break; }
                  else if (distC<WALL_THICKNESS/2 && R[track][sector]==0) {
                    pixSum++; break; }}}}}}
        grey=255-255*pixSum/(subPixels*subPixels); if (!done) grey=grey*4/5;
        if (!crumbShade) c=new Color(grey,grey,grey  );
        else             c=new Color(grey,grey,grey/4);
        g.setColor(c); g.fillRect(i,j,1,1); }}
    c=new Color(0,0,0); g.setColor(c);

    inPaintMaze--; }



  public void paint(Graphics g) {
    if (tracks<1) return;   //  <-- Sometimes paint() can get called before run().
    paintMaze          (g,0,0,size().width,size().height,1);
    if (done) paintMaze(g,0,0,size().width,size().height,4); }



  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(double snoozeSeconds) {
    try {
      thread.sleep((int) (1000.*snoozeSeconds)); }
    catch (InterruptedException e) {
      }}



  public void run() {

    //  Initialize globals.
    roomRad=2*TRACK_WIDTH;
    int screenSize=size().width; if (screenSize>size().height) screenSize=size().height;
    center=screenSize/2; tracks=(screenSize-10-2*roomRad)/TRACK_WIDTH/2; gfx=getGraphics(); done=false;

    //  Exit if graphics area is too small.
    if (tracks<1) return;

    //  Set up the starting grid data.
    sectorsPerTrack=new int[tracks];
    int trackCount=roomRad/TRACK_WIDTH, newTrackCount=trackCount, sectors=4*INNER_SECTORS_PER_QUADRANT;
    for (int i=0; i<tracks; i++) {
      sectorsPerTrack[i]=sectors; newTrackCount++;
      if (newTrackCount>=trackCount*2) {
        trackCount=newTrackCount; sectors*=2; }}
    cell=new int[tracks][sectorsPerTrack[tracks-1]];
    L   =new int[tracks][sectorsPerTrack[tracks-1]];
    U   =new int[tracks][sectorsPerTrack[tracks-1]];
    R   =new int[tracks][sectorsPerTrack[tracks-1]];
    D   =new int[tracks][sectorsPerTrack[tracks-1]];
    for   (int i=0; i<                tracks   ; i++) {
      for (int j=0; j<sectorsPerTrack[tracks-1]; 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=0; Y=tracks/2; crumb(); repaint();

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

      //  Govern the speed of execution, and give paint events a chance to occur.
      snooze(1./50.); while (inPaintMaze>0) snooze(1./50.);

      //  Make a list of up to 5 ways that the path can be extended.
      options=0;
      if (X> 0 && cell[Y][X-1                   ]==0
      ||  X==0 && cell[Y][X-1+sectorsPerTrack[Y]]==0) {
        direc[options]='L'; dist[options]=1; options++; }
      if (Y>0) {
        if (sectorsPerTrack[Y]==sectorsPerTrack[Y-1]) {
          if (cell[Y-1][X  ]==0) {
            direc[options]='U'; dist[options]=1; options++; }}
        else {
          if (cell[Y-1][X/2]==0) {
            direc[options]='U'; dist[options]=1; options++; }}}
      if (X< sectorsPerTrack[Y]-1 && cell[Y][X+1                   ]==0
      ||  X==sectorsPerTrack[Y]-1 && cell[Y][X+1-sectorsPerTrack[Y]]==0) {
        direc[options]='R'; dist[options]=1; options++; }
      if (Y<tracks-1) {
        if (sectorsPerTrack[Y]==sectorsPerTrack[Y+1]) {
          if (cell[Y+1][X    ]==0) {
            direc[options]='D'; dist[options]=1; options++; }}
        else {
          if (cell[Y+1][X*2  ]==0) {
            direc[options]='D'; dist[options]=1; options++; }
          if (cell[Y+1][X*2+1]==0) {
            direc[options]='E'; dist[options]=1; options++; }}}

      if (options>0) {   //   Extend the path.
        int i=(int) (Math.random()*options), oldX, oldY;
        if (direc[i]=='L') {
          L[Y][X]=dist[i]; oldX=X; oldY=Y; X-=dist[i]; if (X<0) X+=sectorsPerTrack[Y];
          R[Y][X]=dist[i]; drawCell(gfx,oldY,oldX); crumb(); }
        if (direc[i]=='U') {
          U[Y][X]=dist[i]; oldX=X; oldY=Y; Y-=dist[i]; if (sectorsPerTrack[Y]<sectorsPerTrack[Y+1]) X/=2;
          D[Y][X]=dist[i]; drawCell(gfx,oldY,oldX); crumb(); }
        if (direc[i]=='R') {
          R[Y][X]=dist[i]; oldX=X; oldY=Y; X+=dist[i]; if (X>=sectorsPerTrack[Y]) X-=sectorsPerTrack[Y];
          L[Y][X]=dist[i]; drawCell(gfx,oldY,oldX); crumb(); }
        if (direc[i]=='D'
        ||  direc[i]=='E') {
          D[Y][X]=dist[i]; oldX=X; oldY=Y; Y+=dist[i];
          if (sectorsPerTrack[Y]>sectorsPerTrack[Y-1]) {
            X*=2; if (direc[i]=='E') X++; }
          U[Y][X]=dist[i]; drawCell(gfx,oldY,oldX); crumb(); }}

      else {   //  Retreat the path.
        noCrumb(); done=true;
        if (L[Y][X]>0) {
          if  (X> 0 && cell[Y][X-L[Y][X]                   ]==1
          ||   X==0 && cell[Y][X-L[Y][X]+sectorsPerTrack[Y]]==1) {
            done=false; X-=L[Y][X]; if (X<0) X+=sectorsPerTrack[Y]; }}
        if (done && U[Y][X]>0) {
          if (sectorsPerTrack[Y]==sectorsPerTrack[Y-1]) {
            if (cell[Y-U[Y][X]][X  ]==1) {
              done=false; Y-=U[Y][X]; }}
          else {
            if (cell[Y-U[Y][X]][X/2]==1) {
              done=false; Y-=U[Y][X]; X/=2; }}}
        if (done && R[Y][X]>0) {
          if (X< sectorsPerTrack[Y]-1 && cell[Y][X+R[Y][X]                   ]==1
          ||  X==sectorsPerTrack[Y]-1 && cell[Y][X+R[Y][X]-sectorsPerTrack[Y]]==1) {
            done=false; X+=R[Y][X]; if (X>=sectorsPerTrack[Y]) X-=sectorsPerTrack[Y]; }}
        if (done && D[Y][X]>0) {
          if (sectorsPerTrack[Y]==sectorsPerTrack[Y+1]) {
            if (cell[Y+1][X    ]==1) {
              done=false; Y+=D[Y][X]; }}
          else {
            if      (cell[Y+1][X*2  ]==1 && U[Y+1][X*2  ]>0) {
              done=false; Y++; X*=2; }
            else if (cell[Y+1][X*2+1]==1 && U[Y+1][X*2+1]>0) {
              done=false; Y++; X*=2; X++; }}}}}

    //  Open up the start and end of the maze.
    D[tracks-1][sectorsPerTrack[tracks-1]  /4]=1;
    U[       0][sectorsPerTrack[       0]*3/4]=1;

    //  Redraw the entire maze to open up the start and end, and to perform other pretty touch-ups.
    paintMaze(gfx,0,0,size().width,size().height,4); }}