import java.awt.*;
   import java.awt.image.*;
   import java.awt.event.*;
   import javax.swing.*;
   import java.io.*;
   import java.util.*;

class GeneticPanel extends JPanel
{
	int xwidth = 800, ywidth = 600, tilewidth = 20;
	BufferedImage img = new BufferedImage(xwidth, ywidth, BufferedImage.TYPE_INT_RGB);
   Graphics buffer = img.getGraphics();
	javax.swing.Timer timer = new javax.swing.Timer(0, new Listener());
	
	int comps = 5;
	int rmax= 20; int cmax = 30;
	int grid[][] = new int[rmax][cmax];
	int rcomp[]=new int[comps], ccomp[]=new int[comps];
	Color color[] = new Color[comps];
	int totalalgs = 3;
	double alg[][] = new double[comps][totalalgs];
	int score[] = new int[comps];
	boolean done[] = new boolean[comps];
	int rend, cend;
	int rman, cman;
	
	double mutspeed = 0.1;
	double wallprob = 0.55;
	int turn=-1;
	int totalrounds = 0;
	int totalscore[] = new int[comps];
	boolean paused = false;
	boolean player = false;
	boolean mandone = false;
	int manscore = -1;
	
	public void move(int comp)
	{
		int bestrch=0, bestcch=0; 
		double bestfit=calcFit(rcomp[comp],ccomp[comp],alg[comp]);
		for(int rchange=-1; rchange<=1; rchange++) for(int cchange=-1; cchange<=1; cchange++)
		{
			if(rchange==0&&cchange==0) continue;
			int rnew = rcomp[comp]+rchange, cnew = ccomp[comp]+cchange;
			if(rnew<0||rnew>=rmax||cnew<0||cnew>=cmax||grid[rnew][cnew]/10==0) continue;
			double fit = calcFit(rnew, cnew, alg[comp]);
			if(fit>bestfit){bestfit=fit;bestrch=rchange;bestcch=cchange;}
		}
		rcomp[comp]+=bestrch; ccomp[comp]+=bestcch;
		return; 
		
	}
	public double calcFit(int r, int c, double[] alg)
	{
		double fit = 0;
		for(int n=0; n<totalalgs; n++) fit+=calcFitAlg(r,c,n)*alg[n];
		return fit;
	}
	public double calcFitAlg(int r, int c, int algnumber)
	{
		switch(algnumber)
		{
			case 0: return calcFitDijkstra(r,c);
			case 1: return calcFitGreedy(r,c);
			case 2: return calcFitInterdijk(r,c);
			default: break;
		}		
		return 0;
	}
	
	
	public double calcFitGreedy(int r, int c)
	{
		return -Math.sqrt(Math.sqrt(Math.pow(r-rend,4)+Math.pow(c-cend,4)));
	}
	public double calcFitDijkstra(int r, int c)
	{
		return -runDijkstra(r, c, rend, cend);
	}
	public double calcFitInterdijk(int r, int c)
	{
		int tries = (int)Math.sqrt(Math.sqrt(rmax*cmax));
		double fit = 0;
		for(int n=0; n<tries; n++)
		{
			int rinter = (int)(Math.random()*rmax);
			int cinter = (int)(Math.random()*rmax);
			fit-=runDijkstra(r,c,rinter,cinter)+runDijkstra(rinter,cinter,rend,cend);
		}
		return fit;
	}
	public double runDijkstra(int rstart, int cstart, int rfinish, int cfinish)
	{
		PriorityQueue pq = new PriorityQueue();
		double[][] value = new double[rmax][cmax];
		boolean[][] visited = new boolean[rmax][cmax];
		double[][] cost = new double[rmax][cmax];
		Node[][] nodemat = new Node[rmax][cmax];
		nodemat[rstart][cstart] = new Node(rstart, cstart, 0);
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) if(!(r==rstart&&c==cstart)) nodemat[r][c] = new Node(r,c,Double.MAX_VALUE);
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) pq.add(nodemat[r][c]);
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) 
		{
			value[r][c] = Double.MAX_VALUE; 
			visited[r][c] = false;
			//cost[r][c] = 1.0/Math.sqrt(Math.pow(rbegin-r,2)+Math.pow(cbegin-c,2));
			cost[r][c] = 1;
			if(grid[r][c]/10==0) cost[r][c]=1/mutspeed;
		}
		value[rstart][cstart] = 0;
		while(!visited[rfinish][cfinish])
		{
			Node next = (Node)pq.poll();
			int rnext = next.getR(), cnext = next.getC();
			for(int r=Math.max(0,rnext-1); r<=Math.min(rmax-1,rnext+1); r++) for(int c=Math.max(0,cnext-1); c<=Math.min(cmax-1,cnext+1); c++) 
				if(!visited[r][c] && Math.abs(r-rnext)<=1&&Math.abs(c-cnext)<=1&&(r!=rnext||c!=cnext) && value[rnext][cnext]+cost[r][c]<value[r][c])
				{
					value[r][c] = value[rnext][cnext]+cost[r][c];
					pq.remove(nodemat[r][c]);
					nodemat[r][c].setValue(value[r][c]);
					pq.add(nodemat[r][c]);
				}
			visited[rnext][cnext] = true;				
		}
		return value[rfinish][cfinish];
	}
	public boolean checkDone()
	{
		for(int n=0; n<comps; n++) if((rcomp[n]==rend&&ccomp[n]==cend)&&!done[n]) {done[n] = true; score[n] = turn;}
		if((rman==rend&&cman==cend) && !mandone) {mandone = true; manscore = turn;}
		
		boolean flag = true;
		for(int n=0; n<comps; n++) if(!done[n]) flag = false;
		//if((rman==rend&&cman==cend)) flag = true;
		
		if(flag) roundEnd();
		return flag;
	}
	public void roundEnd()
	{
		System.out.println("Search Ended!");
		for(int n=0; n<comps; n++) System.out.println("Comp#"+n+" score:   " + score[n]);
		System.out.println(                           "Your score:     " + manscore);
		System.out.println();
		totalrounds++;
		for(int n=0; n<comps; n++) totalscore[n]+=score[n];
		init();
	}
	public void init()
	{
		color[0] = (Color.YELLOW);
		color[1] = (Color.ORANGE);
		color[2] = (Color.MAGENTA);
		color[3] = (Color.GRAY);
		color[4] = (Color.CYAN);
		alg[0] = new double[] {1,0,0};
		alg[1] = new double[] {0,1,0};
		alg[2] = new double[] {1,0.1,0.01};
		alg[3] = new double[] {1,0.75,0};
		alg[4] = new double[] {1,0.5,0.1};
		
		for(int n=0; n<comps; n++) {done[n] = false; score[n] = -1;}
		mandone = false; manscore = -1;
	
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) 
			{ grid[r][c] = 10; if(Math.random()<wallprob) grid[r][c] = 0;}
		int rstart = (int)(rmax*Math.random()/3), cstart = (int)(cmax*Math.random()/3);
		rman=rstart; cman=cstart;
		for(int n=0; n<comps; n++) {rcomp[n] = rstart; ccomp[n] = cstart;}
		rend = (int)(rmax*(2+Math.random())/3); cend = (int)(cmax*(2+Math.random())/3);
		grid[rstart][cstart] = 10;
		grid[rend][cend] = 10;
		turn = 0;
		System.out.println("Graph initialized");
	}
	public void endTurn()
	{
		for(int n=0; n<comps; n++)	move(n);
		
		turn++;
		checkDone();
		changeLand();
		moveEnd();
		checkDone();
	}
	public void changeLand()
	{
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) 
			if(Math.random()<mutspeed) { grid[r][c] = 10; if(Math.random()<wallprob) grid[r][c] = 0;}
		for(int n=0; n<comps; n++)	grid[rcomp[n]][ccomp[n]] = 10;
		grid[rman][cman] = 10;
		grid[rend][cend] = 10;
	}
	public boolean moveEnd()
	{
		boolean moved = false;
		boolean movable = false;
		for(int rchange=-1; rchange<=1; rchange++) for(int cchange=-1; cchange<=1; cchange++)
		{
			int rnew = rend+rchange, cnew = cend+cchange;
			if(rnew<0||rnew>=rmax||cnew<0||cnew>=cmax) continue;
			if(grid[rnew][cnew]/10!=0) 
				movable = true;
		}
		if(!movable) return false;
		for(int n=0; n<100; n++)
		{
			int rchange = (int)(Math.random()*3)-1;
			int cchange = (int)(Math.random()*3)-1;
			int rnew = rend+rchange, cnew = cend+cchange;
			if(rnew<0||rnew>=rmax||cnew<0||cnew>=cmax) continue;
			if(grid[rnew][cnew]/10!=0) 
			{
				//moveAlgorithm here
				moveEndTo(rnew, cnew); //always move
				return true;
			}
		}
		return false;
	}
	public boolean moveEndTo(int r, int c)
	{
		if(r<0||r>=rmax||c<0||c>=cmax) return false;
		rend = r; cend = c;
		return true;
	}
	public boolean manMove(int rchange, int cchange)
	{
		int rnew = rman+rchange, cnew = cman+cchange;
		if(rnew<0||rnew>=rmax||cnew<0||cnew>=cmax) return false;
		if(grid[rnew][cnew]/10==0) return false;
		
		rman = rnew; cman = cnew;
		endTurn();
		return true;
	}
	public void drawAll()
	{
		buffer.setColor(Color.GREEN);
		buffer.fillRect(90,90, Math.max(0,xwidth-180), Math.max(0,ywidth-180));
		for(int r=0; r<rmax; r++) for(int c=0; c<cmax; c++) 
		{
			if(grid[r][c]==10)
			buffer.setColor(Color.WHITE);
			if(grid[r][c]==0)
			buffer.setColor(Color.BLACK);
			if(grid[r][c]>=20||grid[r][c]<0)
			buffer.setColor(Color.GREEN);
			buffer.fillRect(100+tilewidth*c, 100+tilewidth*r, tilewidth, tilewidth);
		}
		for(int n=0; n<comps; n++)
		{
			buffer.setColor(color[n]);
			buffer.fillRect(100+tilewidth*ccomp[n]+tilewidth/4-tilewidth/8+(n*tilewidth/5)%(tilewidth/4+1), 100+tilewidth*rcomp[n]+tilewidth/4-tilewidth/8+(n*tilewidth/6)%(tilewidth/4+1), tilewidth/2, tilewidth/2);
		}
		buffer.setColor(Color.RED);
		buffer.fillRect(100+tilewidth*cman+tilewidth/4+tilewidth/8, 100+tilewidth*rman+tilewidth/4+tilewidth/8, tilewidth/2, tilewidth/2);
		buffer.setColor(Color.BLUE);
		buffer.fillRect(100+tilewidth*cend+tilewidth/4, 100+tilewidth*rend+tilewidth/4, tilewidth/2, tilewidth/2);
	}
	
	public void paint(Graphics g1)
   {
      Graphics2D g2 = (Graphics2D)g1;
      g2.drawImage(img, 0, 0, getWidth(), getHeight(), null);
   }
	
	public class Listener implements ActionListener
   {
      public void actionPerformed(ActionEvent e)
      {     
           
      	if((!player||mandone) && !paused) 
      	{
      		endTurn();
      	}
         drawAll();       
         repaint();
         
      }
   }
   public class KeyListener extends KeyAdapter
   {
      public void keyPressed(KeyEvent e) 
      {
      	int key = e.getKeyCode();
      	//System.out.println(key);
      	if(key==10) {paused=!paused;}
      	if(key==32) {
      		System.out.println("---------------------CURRENT SUMMARY----------------------");
      		System.out.println("Total rounds:     "+totalrounds);
      		for(int n=0; n<comps; n++) System.out.println("Comp#"+n+" average score:    "+(double)totalscore[n]/totalrounds);
      		System.out.println("----------------------------------------------------------");
      	}
      	if((player&&!mandone) && key>=97 && key<=105 && player) manMove(1-(key-97)/3, (key-97)%3-1);
      }
   }
   public GeneticPanel() throws IOException // Constructor
   {
   	init();
   	for(int n=0; n<comps; n++) totalscore[n] = 0;
		timer.start();
     
      addKeyListener(new KeyListener());
      setFocusable(true);      
   }
}

class Node implements Comparable
{
	int nr, nc;
	double nvalue;
	Node(int r, int c, double value)
	{
		nr=r; nc=c;
		nvalue=value;
	}
	int getR()
	{
		return nr;
	}
	int getC()
	{
		return nc;
	}
	double getValue()
	{
		return nvalue;
	}
	void setValue(double value)
	{
		nvalue = value;
	}
	public int compareTo(Object rhs)
	{
		double s = ((Node)rhs).getValue()-nvalue;
		if(s>0) return -1;
		if(s<0) return 1;
		return 0;
	}
}

public class simple
{
		public static void main(String args[]) throws IOException
      {
         JFrame frame = new JFrame("Genetic");
         frame.setBackground(Color.BLACK);
         frame.setForeground(Color.WHITE);
         frame.setSize(800, 600);
         frame.setLocation(0, 0);
         frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
         GeneticPanel app = new GeneticPanel();
         frame.setContentPane(app);
         frame.setVisible(true);
      } // end of main
}