// Randomly generates a 256x256 world map

import java.util.*;
import java.awt.*;

public class worldgen {

 public int alti[]=new int[65536];
 public int water[]=new int[65536];


 public static final int STEPSIZE=32;
 public static final int BUMPMAX=157<<16;

 public void makeWorld() {

  int seed=(int)Math.round(Math.random()*987654321);
  int[][] za = new int[256][256];
  IJKPlasma.noise(za,STEPSIZE,BUMPMAX,seed);
  for(int x=0;x<256;x+=STEPSIZE)
   za[x][0]= -BUMPMAX;
/*  for(int x=STEPSIZE;x<256-(STEPSIZE<<1);x+=(STEPSIZE<<1))
   for(int y=STEPSIZE;y<256-(STEPSIZE<<1);y+=(STEPSIZE<<1)) {
    za[x][y]=(za[x-STEPSIZE][y]+za[x+STEPSIZE][y]
             +za[x][y-STEPSIZE]+za[x][y+STEPSIZE]+2)>>2;
    za[x+STEPSIZE][y+STEPSIZE]=
             (za[x+STEPSIZE][y]+za[x][y+STEPSIZE]
             +za[x+STEPSIZE][y+(STEPSIZE<<1)]
             +za[x+(STEPSIZE<<1)][y+STEPSIZE]+2)>>2;
   }
  for(int x=STEPSIZE;x<256-(STEPSIZE<<1);x+=(STEPSIZE<<1))
   for(int y=STEPSIZE;y<256-(STEPSIZE<<1);y+=(STEPSIZE<<1)) {
    za[x+STEPSIZE][y]=(za[x][y]+za[x+STEPSIZE][y+STEPSIZE]
         +za[x+STEPSIZE][y-STEPSIZE]+za[x+(STEPSIZE<<1)][y]+2)>>2;
    za[x][y+STEPSIZE]=(za[x][y]+za[x+STEPSIZE][y+STEPSIZE]
         +za[x-STEPSIZE][y+STEPSIZE]+za[x][y+(STEPSIZE<<1)]+2)>>2;
   } */
  IJKPlasma.plasma(za,STEPSIZE,BUMPMAX,seed);

  for(int x=0;x<256;x++)
   for(int y=0;y<256;y++)
    alti[x+(y<<8)]=((za[x][y]<<2)
                    +((za[(x+1)&255][y]+za[(x-1)&255][y]
                       +za[x][(y+1)&255]+za[x][(y-1)&255])<<1)
                    +za[(x+1)&255][(y+1)&255]
                    +za[(x+1)&255][(y-1)&255]
                    +za[(x-1)&255][(y+1)&255]
                    +za[(x-1)&255][(y-1)&255])>>4;
  normalize();
  for(int xy=0;xy<256;xy++) alti[xy]=-BUMPMAX;
  for(int xy=65536-256;xy<65536;xy++) alti[xy]=-BUMPMAX;

  rainfall(seed+1);
 } //end of makeworld


 public int down[]=new int[65536];
 public int basin[]=new int[65536];
 public int cloud[]=new int[65536];
 public int wetness[]=new int[65536];
 public boolean river[]=new boolean[65536];

 public void rainfall(int seed) {
  //determine favored
  //downward flow at each point
  int a; int d; int q;
  for(int xy=0;xy<257;xy++) down[xy]=0;
  for(int xy=65536-257;xy<65536;xy++) down[xy]=0;
  for(int xy=257;xy<65536-257;xy++) {
   d=xy; a=alti[d];
   if(alti[xy-256]<a) {d=xy-256; a=alti[d];}
   if(alti[xy+256]<a) {d=xy+256; a=alti[d];}
   if(alti[xy+1]<a) {d=xy+1; a=alti[d];}
   if(alti[xy-1]<a) d=xy-1;

   if(0==(a&32)) { //try to wind 1/2 of the time
    if(1==((xy-d)&1)) { //try up or down
     q=(0==(a&8))?256:-256;
    }
    else { //try left or right
     q=(0==(a&8))?1:-1;
    }
    if(alti[xy+q]<a) d=xy+q;
    else if(alti[xy-q]<a) d=xy-q;
   }

   if(0==(a&17)) { //try diagonal 1/4 of the time
    if(1==((xy-d)&1)) { //try up or down
     q=(0==(a&4))?256:-256;
    }
    else { //try left or right
     q=(0==(a&4))?1:-1;
    }
    if(alti[d+q]<a) d=d+q;
    else if(alti[d-q]<a) d=d-q;
   }

   down[xy]=d;
  }

  //next build basins

  for(int xy=0;xy<65536;xy++)
   basin[xy]=(alti[xy]<0)?0:down[xy];

  //now flood the basins to ultimate
  //destinations
  int bxy;
  boolean flag=true;
  while(flag) {
   flag=false;
   for(int xy=0;xy<65536;xy++) {
    bxy=basin[xy];
    if(bxy!=basin[bxy]) {
     basin[xy]=basin[bxy];
     flag=true;
    }
   }
   for(int xy=65535;xy>=0;xy--) {
    bxy=basin[xy];
    if(bxy!=basin[bxy]) {
     basin[xy]=basin[bxy];
     flag=true;
    }
   }
  } // end of while for flooding basins

  // now add lots and lots of rain
  for(int xy=1;xy<65536;xy++)water[xy]=987654321;
  water[0]=0;

  // drain basins as possible
  int lev;
  flag=true;
  while(flag) {
   flag=false;
   for(int xy=256;xy<65536;xy++) {
    lev=Math.min(Math.max(alti[xy-1],water[basin[xy-1]]),
                 Math.max(alti[xy-256],water[basin[xy-256]])
                );
    lev=Math.max(lev,alti[xy]);
    if(lev<water[basin[xy]]) {
     water[basin[xy]]=lev;
     flag=true;
    }
   }
   for(int xy=65535-256;xy>=0;xy--) {
    lev=Math.min(Math.max(alti[xy+1],water[basin[xy+1]]),
                 Math.max(alti[xy+256],water[basin[xy+256]])
                );
    lev=Math.max(lev,alti[xy]);
    if(lev<water[basin[xy]]) {
     water[basin[xy]]=lev;
     flag=true;
    }
   }
  } // end of while draining basins

  // fill basins
  for(int xy=1;xy<65536;xy++)
   water[xy]=water[basin[xy]];

  // build rivers from each basin downward
  for(int xy=0;xy<65536;xy++)river[xy]=false;
  for(int xy=256;xy<65536-256;xy++) 
   if (water[xy]>=alti[xy]) {
    bxy=basin[xy];
    if(bxy!=basin[xy-256]) makeriver(xy,xy-256);
    if(bxy!=basin[xy+256]) makeriver(xy,xy+256);
    if(bxy!=basin[xy-1]) makeriver(xy,xy-1);
    if(bxy!=basin[xy+1]) makeriver(xy,xy+1);
   }

  //create cloud of rainfall levels
  int[][] za = new int[256][256];
  IJKPlasma.noisePos(za,STEPSIZE>>1,750<<16,seed);
  IJKPlasma.plasma(za,STEPSIZE>>1,750<<16,seed);
  for(int x=0;x<256;x++)
   for(int y=0;y<256;y++)
    cloud[x+(y<<8)]=za[x][y];

  //accumulate wetness values from rainfall
  int rain; int absorbed; int wxy;
  for(int xy=0;xy<65536;xy++) wetness[xy]=0;
  for(int source=0;source<65536;source++) {
   rain=cloud[source];
   int xy=source;
   while(water[xy]<alti[xy]) { //stop in oceans+lakes
    wxy=water[xy];
    //absorb at most 1/2 of the way to 256<<16
    //absorb at most 1/4 of the rain
    absorbed=Math.min((256<<16-wxy)>>1,rain>>2);
    wetness[xy]+=absorbed;
    rain-=absorbed;
    xy=(river[xy])?basin[xy]:down[xy]; //stop in river
   }
   wetness[xy]+=rain; //stuff the remaining wetness in water;
  }

 } // end of rainfall routine

 public void makeriver(int source,int xy) {
  if(alti[xy]<=water[source] && alti[source]<=water[source]) {
   river[source]=true;   //paint starting point
   while(water[xy]<=alti[xy]) {
    river[xy]=true;      //paint midpoint
    xy=down[xy];        //flow river downward
   }
   river[xy]=true;   //paint endpoint
  }
 }

 public void NEWmakeriver(int source,int xy) {
  int bxy=basin[xy]; int dxy; int q;
  if(alti[xy]<=water[source] && alti[source]<=water[source]) {
   river[source]=true;   //paint starting point
   while(water[xy]<=alti[xy]) {
    river[xy]=true;      //paint midpoint
    //flow river downward
    dxy=down[xy];
    if (dxy-xy==xy-source && 0<(hash(xy&255,xy>>8,bxy)&6)) { //try to wind
     if(1==((xy-source)&1)) { //try up or down
      q=(1==hash(xy&255,xy>>8,bxy))?256:-256;
     }
     else { //try left or right
      q=(1==hash(xy&255,xy>>8,bxy))?1:-1;
     }
     if(alti[xy+q]<alti[xy] && basin[xy+q]==bxy) dxy=xy+q;
     else if(alti[xy-q]<alti[xy] && basin[xy-q]==bxy) dxy=xy-q;
    }
    // make the move, first saving old xy to source
    source=xy; xy=dxy;
   }
   river[xy]=true;   //paint endpoint
  }
 }

 public long hash(int x,int y,int seed) {
  return (int)Math.round(Math.random()*95213443212345621L);
 }

 public void drawMap(Graphics g) {
  int afac; int wfac; int cfac;
  int xy; int a; int w; int c;
  for(int y=0;y<256;y++)
   for(int x=0;x<256;x++) {
    xy=x+(y<<8);

    a=alti[xy];
    w=water[xy]-alti[xy];
    c=wetness[xy];

    afac=bra((a>>16)+32);
    wfac=(w>=0)?bra((w>>16)+137):((river[xy])?135:0);
    cfac=256-bra(c>>16);
    g.setColor(new Color((afac*cfac)>>8,afac,wfac));
    g.fillRect(x,y,1,1);

    if(w>=0 || river[xy]) g.setColor(Color.blue);
    else if(afac>150) g.setColor(Color.white);
    else if(cfac<25) g.setColor(Color.green);
    else if(cfac<225) g.setColor(Color.gray);
    else g.setColor(Color.yellow);

    g.fillRect(x+256,y,1,1);
   }
 } // end of drawMap

 public void worldgen() {
 } // end of initialization

 public final static int BELOWSEA=44<<10;
 public void normalize() {
  // shift the altitudes up or down to get a sea level
  // with about 1/3 land above water.
  int hist[]=new int[256];
  int sea=0;
  int i;
  int total;

  sea=(-128)<<16;

  for(i=0;i<256;i++) hist[i]=0;
  for(i=0;i<65536;i++) hist[bra((alti[i]-sea)>>16)]++;
  i=0; total=hist[0];
  while(total<BELOWSEA) {
   i++;
   total+=hist[i];
  }
  sea+=(i<<16);

  for(i=0;i<256;i++) hist[i]=0;
  for(i=0;i<65536;i++) hist[bra((alti[i]-sea)>>8)]++;
  i=0; total=hist[0];
  while(total<BELOWSEA) {
   i++;
   total+=hist[i];
  }
  sea+=(i<<8);

  for(i=0;i<256;i++) hist[i]=0;
  for(i=0;i<65536;i++) hist[bra((alti[i]-sea))]++;
  i=0; total=hist[0];
  while(total<BELOWSEA) {
   i++;
   total+=hist[i];
  }
  sea+=(i);

  for(i=0;i<65536;i++) alti[i]-=sea;
 } // end of normalize()

 public final static double EXPO=Math.log(2)/Math.log(1.5);
 public final static double INVEXPO=1/EXPO;
 public static int dt[]=new int[8192];
 static {
  for(int DXY=-4096;DXY<4096;DXY++) {
   int dx=((DXY+128)&255)-128;
   int dy=(DXY-dx)>>8;
   dt[DXY+4096]=dist(DXY);
  }
 }
 public static double distd(double dx,double dy) {
  return Math.pow(Math.pow(Math.abs(dx),EXPO)
                  +Math.pow(Math.abs(dy),EXPO),
                 INVEXPO);
 }
 public static int dist(int dx, int dy) {
  return (int)Math.round(distd((double)dx,(double)dy)-0.25);
 }
 public static int dist(int DXY) {
  int dx=((DXY+128)&255)-128;
  int dy=(DXY-dx)>>8;
  return dist(dx,dy);
 }

 public static int bra(int v) {
  // returns v bracketed by 0 and 255
  return (v==(v&255))?v:((v<0)?0:255);
 }





 public static final int VOLSLOPE=65536*15;
 public static int volcone[]=new int[8192];
 static {
  for(int DXY=-4096;DXY<4096;DXY++) {
   int dx=((DXY+128)&255)-128;
   int dy=(DXY-dx)>>8;
   volcone[DXY+4096]=(int)Math.round(VOLSLOPE
           *distd((double)dx,(double)dy));
  }
 }
 public void volcano(int volXY,int volA) {
  int xy;
  for(int vertXY=volXY-3840; vertXY<=volXY+3840; vertXY+=256)
   for(xy=vertXY-15;xy<=vertXY+15;xy++)
    if(xy==(xy&65535))
     alti[xy]=Math.max(alti[xy],volA-volcone[volXY+4096-xy]);
 } // end of volcano

 public void volcanos(int height,int decay) {
  int xy;
  int h=height;
  int dec=decay;
  if (dec!=(dec&65535)) dec=65000;
  while (h>65536) {
   xy=65535&(int)Math.round(Math.random()*524288);
   volcano(xy,Math.min(alti[xy]+h,250<<16));
   h=(((h>>10)*dec)>>6);
  }
 } // end of volcanos

} // end of worldgen class



/*
////////////////////////////////////////////////////////////////////////

 public static final int DMAX=32;
 public static final int HEIGHTFACT=63<<16;

 public void oldmakeWorld() {
  { // plasma in the 40 watt range
   int fact; int halfact;
   fact=DMAX*HEIGHTFACT; halfact=fact>>1;
   for(int x=0;x<256;x+=DMAX) {
    alti[x]=(-halfact)>>2;
    for(int y=DMAX;y<256;y+=DMAX)
     alti[x+(y<<8)]=((int)Math.round(Math.random()*fact)-halfact)>>2;
   }
   for(int d=DMAX>>1;d>0;d=d>>1) {
    fact=d*HEIGHTFACT; halfact=fact>>1;
    for(int x=0;x<256;x+=(d<<1))
     for(int y=0;y<256;y+=(d<<1)) {
      alti[(x+d)+((y+d)<<8)]=
       (alti[x+(y<<8)]+alti[((x+d+d)&255)+(y<<8)]
        +alti[x+(((y+d+d)&255)<<8)]
        +alti[((x+d+d)&255)+(((y+d+d)&255)<<8)]
        +(int)Math.round(Math.random()*fact)-halfact
       )>>2;
     }
    fact=(((d*92682)>>8)*HEIGHTFACT)>>8; halfact=fact>>1;
    for(int x=0;x<256;x+=(d<<1))
     for(int y=0;y<256;y+=(d<<1)) {
      alti[(x+d)+(y<<8)]=
       (alti[x+(y<<8)]+alti[((x+d+d)&255)+(y<<8)]
        +alti[(x+d)+(((y+d)&255)<<8)]
        +alti[(x+d)+(((y-d)&255)<<8)]
        +(int)Math.round(Math.random()*fact)-halfact
       )>>2;
      alti[x+((y+d)<<8)]=
       (alti[x+(y<<8)]+alti[x+(((y+d+d)&255)<<8)]
        +alti[(x+d)+(((y+d)&255)<<8)]
        +alti[(x-d)+(((y+d)&255)<<8)]
        +(int)Math.round(Math.random()*fact)-halfact
       )>>2;
     }
   }
  } // end of plasma in the 40 watt range

//  volcanos(100<<16,65000);
//  for(int n=0;n<5;n++)
//   for(int i=5+n;i<20+n;i++)
//    volcanos(i<<16,65000);

  normalize();
  rainfall(15);
 }

////////////////////////////////////////////////////////////////////////
*/