import java.awt.Color;
import java.awt.event.KeyEvent;

class mazedragon extends mazebase
{
    public mazedragon(int bh, int mh, int mw) // don't change constructor
    { 
	super(bh,mh,mw); 
    }

public void digout(int y, int x)   // modify this function
 {
     // The following is a skeleton program that demonstrates the mechanics
     // needed for the completion of the program.

     // We always dig out two spaces at a time: we look two spaces ahead
     // in the direction we're trying to dig out, and if that space has
     // not already been dug out, we dig out that space as well as the
     // intermediate space.  This makes sure that there's always a wall
     // separating adjacent corridors.
     /*
     M[y][x] = 1;  // digout maze at coordinate y,x
     drawblock(y,x);  // change graphical display to reflect space dug out
     delay(40); // slows animation

     // But the following won't work (but will compile)

     // sample code that tries to digout one space to the left:
     if (x-1>=0) digout(y,x-1);
     // sample code that tries to digout TWO space to the right IF it's not
     // already dug out:
     if (x+2<mwidth && M[y][x+2]==0) // always check for maze boundaries
	 {
	     M[y][x+1] = 1;
	     drawblock(y,x+1);
	     digout(y,x+2);
	 }
     */
     //     pathcolor = Color.yellow;
     //     pencolor = Color.blue;
     int wgap=8; // maze block size
     int bgap = wgap+1;
     // dig out maze in 8x8 blocks.  translate coordinates
     for(int i=0;i<wgap;i++)
         for(int k=0;k<wgap;k++)
             {
                 M[y*bgap+i][x*bgap+k] = 1;
                 drawblock(y*bgap+i,x*bgap+k); // draw black squares
             }
     // directions n, e, s, w
     int[] DX = {0,1,0,-1};   // declared externally
     int[] DY = {-1,0,1,0};
     // scramble directions
     for(int i =0;i<DX.length-1;i++)
	 {
	     int k = i + (int)(Math.random()*(DX.length-i));
	     int tmp = DX[i]; DX[i]=DX[k]; DX[k] = tmp;
	     tmp = DY[i]; DY[i]=DY[k]; DY[k]=tmp;
	 }
     // dig out in EACH direction
     for(int dir =0;dir<DX.length;dir++)
	 {
	     int nx = x + DX[dir], ny = y+DY[dir];
	     if (nx*bgap>=0 && nx*bgap<mwidth && ny*bgap>=0 && ny*bgap<mheight && M[ny*bgap][nx*bgap]==0)
		 {
                   // dig out intermediate line:
                     if (DX[dir]>0)
                         for(int i=0;i<wgap;i++)
                           {
                             M[y*bgap+i][(x+DX[dir])*bgap-DX[dir]] = 1;
                             drawblock(y*bgap+i,(x+DX[dir])*bgap-DX[dir]);
                           }
                     else if (DX[dir]<0)
                         for(int i=0;i<wgap;i++)
                           {
                             M[y*bgap+i][x*bgap-1] = 1;
                             drawblock(y*bgap+i,x*bgap-1);
                           }                     
                     else if (DY[dir]>0)
                         for(int k=0;k<wgap;k++)
                           {
                             M[(y+DY[dir])*bgap-DY[dir]][x*bgap+k] = 1;
                             drawblock((y+DY[dir])*bgap-DY[dir],x*bgap+k);
                           }
                     else if (DY[dir]<0)
                         for(int k=0;k<wgap;k++)
                           {
                             M[y*bgap-1][x*bgap+k] = 1;
                             drawblock(y*bgap-1,x*bgap+k);
                           }
                     //delay(dtime*10);
                     digout(ny,nx);
		 }
	 }
 }//digout


    /////// mazedragon setup

protected int maxlength;
protected int minlength;
protected int px, py;  // position of player  (miner)
protected CircQueue<Integer> Dragon; 
protected int ddx, ddy; // dragon movement
protected CircQueue<Miner> Miners;
protected boolean dragonalive;    
protected int minersalive;
protected java.awt.Image dragongif;

    int encode(int base, int y, int x)
    {
        return (base/65356) + x*256 + y;
    }

    // determine if miner's movement is orthogonal to dragon's
    boolean orthogonal(int dy, int dx, int ddy, int ddx)
    {
        if (ddy==0 && ddx==0) return true;
        return ddy!=dy && ddx!=dx;
    }
    
 public void play()
 {
     try {
       dragongif = java.awt.Toolkit.getDefaultToolkit().getImage("head1.gif");
       prepareImage(dragongif,this);
       Thread.sleep(50);
     }
     catch (Exception ee) {dragongif=null;}
     
     maxlength=16;
     minlength=3;
     Dragon = new CircQueue<Integer>(maxlength);
     // set initial position of dragon
     Dragon.push(encode(0,0,0));
     Dragon.push(encode(0,0,1));
     Dragon.push(encode(0,0,2));
     Dragon.push(encode(0,0,3));
     Dragon.push(encode(0,1,3));
     //     Dragon.push(encode(0,2,3));
     //     Dragon.push(encode(0,2,4));
     //     Dragon.push(encode(0,2,5));
     dragonalive=true;

     // miner positions
     Miners = new CircQueue<Miner>(maxlength/2);
     for (int i=0;i<Miners.capacity();i++)
         {
             int my = (int)(Math.random()*(mheight-16))+16;
             int mx = (int)(Math.random()*mwidth);
             Miners.enqueue(new Miner(my,mx));
         }
     minersalive = Miners.size();
     redraw();
     int[] DX = {0,1,0,-1};
     int[] DY = {-1,0,1,0};     

     while (dragonalive && minersalive>0)
         {
             /*
             int coord = Dragon.peek();
             int y = coord%256, x = (coord/256)%256;
             int dy = y-py, dx =x-px;
             if (Math.abs(dy)!=0 && Math.abs(dx)!=0)
                 {
                     if (Math.random()<.5)
                         {
                             ddy = -1 * (dy/Math.abs(dy));
                             ddx = 0;
                         }
                     else 
                         {
                             ddx = -1 * (dx/Math.abs(dx));
                             ddy = 0;
                         }
                 }
             else if (Math.abs(dy)!=0)
                 {
                             ddy = -1 * (dy/Math.abs(dy));
                             ddx = 0;                     
                 }
             else if (Math.abs(dx)!=0)
                         {
                             ddx = -1 * (dx/Math.abs(dx));
                             ddy = 0;
                         }                 
             */

             for (Miner m:Miners)
                 {
                     if (m.alive && Math.random()<.2)
                         {
                             int dd = (int)(Math.random()*4);
                             m.dy = DY[dd];
                             m.dx = DX[dd];
                         }
                 }
             
             moveto(0,0);
             delay(dtime*2);
         }
 }//play - setup only

    
 protected void moveto(int dy,int dx)
 {
     int coord = Dragon.peek();
     int cy = coord%256;
     int cx = (coord/256)%256;
     int ny = cy + ddy;
     int nx = cx + ddx;
     if (ny>=0 && ny<mheight && nx>=0 && nx<mwidth && M[ny][nx]!=0 && (ddx!=0 || ddy!=0))
         {
             Dragon.push(encode(coord,ny,nx));
             //M[ny][nx] = 2; //value written by redraw
             // did dragon eat something?
             if (M[ny][nx] < -1)
                 {
                     Miner m = Miners.getnth(-M[ny][nx]-2);
                     m.alive=false;
                     minersalive--;
System.out.printf("dragon eat M[%d][%d]==%d, dy,dx:%d,%d, ddy,ddx:%d,%d\n",ny,nx,M[ny][nx],m.dy,m.dx,ddy,ddx); // trace                     
                     // length extended because tail move skipped.
                 }
             else    // tail moves
                 {
                     int last = Dragon.dequeue();
                     int ly = last%256, lx = (last/256)%256;
                     M[ly][lx] = 1; // clear cell
                 }
             M[ny][nx]=2;
         }
     // move miners
     for(Miner m:Miners)
         {
             ny = m.y+m.dy;
             nx = m.x+m.dx;
             if (m.alive && ny>=0 && ny<mheight && nx>=0 && nx<mwidth && M[ny][nx]!=0)
                 {
                     if (M[ny][nx]==2) // got eaten?
                         {
                             m.alive=false;
                             minersalive--;
                             Dragon.push(encode(coord,m.y,m.x));
System.out.printf("dragon eat head-on M[%d][%d]==%d, dy,dx:%d,%d, ddy,ddx:%d,%d\n",ny,nx,M[ny][nx],m.dy,m.dx,ddy,ddx); // trace                                                  
                         }
                     // did it cut off dragon?
                     else if (M[ny][nx]>2 && M[ny][nx]<4 && orthogonal(m.dy,m.dx,ddy,ddx))
                         {
                             // cut of dragon's head
                             dragonalive = false;
System.out.printf("dragon dead M[%d][%d]==%d, dy,dx:%d,%d, ddy,ddx:%d,%d\n",ny,nx,M[ny][nx],m.dy,m.dx,ddy,ddx); // trace                     
                             ddx = 0;  ddy = 0;
                         }
                     else if (M[ny][nx]>=4) // cut off tail
                         {
                             int tailsize = Dragon.size()-M[ny][nx]+2;
System.out.printf("dragon cut off M[%d][%d]==%d, dy,dx:%d,%d, ddy,ddx:%d,%d\n",ny,nx,M[ny][nx],m.dy,m.dx,ddy,ddx); // trace                     
                             while (tailsize-->0)
                                 {
                                     int last = Dragon.dequeue();
                                     int ly = last%256, lx = (last/256)%256;
                                     M[ly][lx] = 1; // clear cell                                         
                                 }
                         }

                     M[m.y][m.x] = 1;
                     m.y = ny;  m.x = nx;
                     // value won't be written to M until redraw
                 }//m.alive and within bounds
         }//for each miner
     redraw();
 }//moveto

    
 protected void redraw()
 {
     clear();
     int coord = Dragon.getnth(0);
     int y = coord%256;
     int x = (coord/256) % 256;     
     // draw dragon head
     if (dragongif!=null) drawgif(g2,dragongif,y,x);
     else drawdot(g2,y,x);
     M[y][x]=2;
     for (int i=1;i<Dragon.size();i++) // draw dragon's body
         {
             coord = Dragon.getnth(i);
             y = coord%256;
             x = (coord/256) % 256;
             M[y][x] = i+2;
             drawdot(g2,y,x);
         }
     // draw miners
     for (int i=0;i<Miners.size();i++)
         {
             Miner m = Miners.getnth(i);
             if (m.alive)
                 {
                     drawgif(g2,animatedgif,m.y,m.x);
                     M[m.y][m.x] = -i-2;
                 }
         }
     refresh();
 }//redraw

 public void keyPressed(KeyEvent e) // override for key event handling
 {
	int key = e.getKeyCode();       // code for key pressed      
	//System.out.println("YOU JUST PRESSED KEY "+key);
	int dx = ddx, dy = ddy;
	switch (key)
	    {
	    case 37: // left
		dx = -1; dy=0; break;
	    case 38: // up
		dy = -1;  dx=0; break;
	    case 39: // right
		dx = 1; dy=0; break;
	    case 40: // down
		dy = 1; dx=0; break;
            case 32: // stop
                dy = 0;  dx = 0;
	    default:
		break;
	    }; //switch
        if (dx!=-ddx  || dy!=-ddy) // can't go backwards
            { ddx = dx;  ddy = dy; }
	//moveto(dy,dx);
 }//keyPressed

    
    /* miner moves
 public void keyPressed1(KeyEvent e) // override for key event handling
 {
	int key = e.getKeyCode();       // code for key pressed      
	//System.out.println("YOU JUST PRESSED KEY "+key);
	int dx = pdx, dy = pdy;
	switch (key)
	    {
	    case 37: // left
		dx = -1; dy=0; break;
	    case 38: // up
		dy = -1;  dx=0; break;
	    case 39: // right
		dx = 1; dy=0; break;
	    case 40: // down
		dy = 1; dx=0; break;
	    default:
		break;
	    }; //switch
        pdx = dx;  pdy = dy;
	//moveto(dy,dx);
 }//keyPressed
    */

  public static void main(String[] args) throws Exception
  {
      mazebase.main(args);
  }
}//mazedragon subclass


class Miner
{
    int y, x;
    int dy, dx;
    boolean alive;
    public Miner(int y0, int x0)
    {y=y0;  x=x0;  alive=true; }
}

////// 
// java mazedragon 53 53 24  -- dimensions should be n8-3 x n8-3 (56-3)
// java mazedragon 45 45 24  -- dimensions should be n8-3 x n8-3 (56-3)
// java mazedragon 27 27 32