import java.awt.*;
import java.applet.*;
import java.util.*;
import java.io.*;
import java.awt.event.*;

/**
* THIS SOFTWARE IS PROVIDED AS-IS AND I CAN TAKE NO RESPONSIBILITY
* FOR ANY INDIRECT DAMAGE INCURRED ON ANY MACHINE THIS IS RUN ON. IT
* HAS BEEN FULLY TESTED TO ENSURE THAT NO SIDE EFFECTS WILL HARM YOUR
* MACHINE IN ANY WAY.
*
* THIS SOURCE CODE IS FREE TO DISTRIBUTE UNDER THE 'GNU' LICENSE SO LONG
* AS THIS HEADER IS ALWAYS ATTACHED TO IT AND YOU DONT MAKE ANY PROFIT
* FROM ITS DISTRIBUTION.
*
* TOBY SKINNER
* toby@hc2.co.uk
*/

public class Maze extends Applet implements Runnable
{
	/*GRID RELATED DATA*/
	private Point[][] grid = null;
	private Vector edges = new Vector (0,1);
	private Point start = null;
	private Point end = null;
	private AntSystem as = null;
	private Thread loop = null;

	/*MEASUREMENTS*/
	private int width = 400;
	private int height = 400;
	private int grid_width = 10;
	private int grid_height = 10;

	private Point current_node = null;
	public boolean selected = false;
	private int xinterval = 0;
	private int yinterval = 0;
	public int mx = 0;
	public int my = 0;

	/*GUI HANDLERS*/
	private EventHandler evt_hndlr = null;
	public Applet infopanel = null;
	boolean select_start = false;
	boolean select_end = false;
	Image buffer = null;
	Graphics bg = null;

	/*PARAMETERS*/
	public double alpha = 0.0;						//pheromone multiplier
	public double beta = 0.0;						//heuristic multiplier, local
	public double gamma = 0.0;						//heuristic multiplier, global
	public int tmax = 20;
	public int n = grid_width*grid_height;
	public int m = n/4;
	public double pmax = 0.05;						//max decay rate of pheromone
	public double p = pmax;							//decay rate of pheromone
	public double q = 100.0;
	public double t0 = 0.0000001;
	public Ant[] ants = null;
	public Vector T = new Vector(0,1);
	public Vector BT = new Vector(0,1);				//best tour
	public double L = 0.0;							//length of T
	public double BL = 0.0;							//length of BT

	public int epoch = 0;
	public int cntr = 0;
	public int alpha_div = 7;
	public int beta_div = 7;
	public int gamma_div = 7;
	public int[][] sarray = null;

	public File data = null;
	public FileWriter data_writer = null;
	public File success = null;
	public FileWriter success_writer = null; 

	public static final int LOCAL = 0;
	public static final int GLOBAL = 1;
	public static final int COMBINED = 2;

	public int nav_type = LOCAL;

	public void init() {
		while(infopanel == null) {
			infopanel = getAppletContext().getApplet("info");
		}

		((InfoPanel)infopanel).displayString("AS-RFP vers 0.1, 0.2, 0.3\n");
		((InfoPanel)infopanel).displayString("\n");
		((InfoPanel)infopanel).displayString("initGrid() @ "+new Date().toString()+"\n");
		initGrid();
		((InfoPanel)infopanel).displayString("initEdges() @ "+new Date().toString()+"\n");
		initEdges();

		buildHandlers();
		setBackground(Color.white);

		as = new AntSystem(this);
		loop = new Thread(this);

		((InfoPanel)infopanel).displayString("setStartNode() -> "+setStartNode()+"\n");
		((InfoPanel)infopanel).displayString("setEndNode() -> "+setEndNode()+"\n");
	}

	private void buildHandlers() {
		evt_hndlr = new EventHandler(this);
		this.addMouseMotionListener(evt_hndlr);
		this.addMouseListener(evt_hndlr);
	}

	public void run() {
		try {
			for(int x=0;x<3;x++) {
				nav_type = x;
				cntr = 0;
				((InfoPanel)infopanel).displayString("Nav type = "+nav_type);
				//data = new File("variables["+nav_type+"]");
				//data_writer = new FileWriter(data);
				//success = new File("success["+nav_type+"]");
				//success_writer = new FileWriter(success);

				if(nav_type < 2) {
					((InfoPanel)infopanel).displayString("Constructing avg_earray...");
					int[][][] avg_earray = new int[10][(alpha_div+1)][(beta_div+1)];
					((InfoPanel)infopanel).displayString("done\n");
					for(int p=0;p<10;p++) {
						((InfoPanel)infopanel).displayString("Iteration "+p+"\n");
						sarray = new int[(alpha_div+1)*(beta_div+1)][tmax];
						int[][] earray = new int[(alpha_div+1)][(beta_div+1)];
						int in1 = 0;
						int in2 = 0;

						for(double i=0.0;i<=2.0;i+=(2.0/alpha_div)) {
							for(double j=0.0;j<=2.0;j+=(2.0/beta_div)) {
								alpha = i;
								beta = j;
								begin();
								earray[in1][in2] = acc(sarray[cntr]);
								cntr++;
								in2++;
							}
							in1++;
							in2=0;
						}

						for(int i=0;i<earray.length;i++) {
							for(int j=0;j<earray[i].length;j++) {
								avg_earray[p][i][j] = earray[i][j];
								earray[i][j] = 0;
							}
						}
						
						cntr = 0;
						in1 = 0;
						in2 = 0;

						//copy sarray to larger array, when needed later on
					}

					//average the results & write to file
					double avg = 0.0;
					for(int i=0;i<avg_earray[0][0].length;i++) {		//for all runs
						for(int j=0;j<avg_earray[0].length;j++) {		//index into avg_earray[0]
							for(int k=0;k<avg_earray.length;k++) {		//index to avg_earray
								avg+=avg_earray[k][j][i];
							}
							//data_writer.write(j+" "+i+" "+(avg/avg_earray.length)+"\n");
							//data_writer.flush();
							avg=0;
						}
					}
				}
				else {
					((InfoPanel)infopanel).displayString("Constructing avg_earray...");
					int[][][][] avg_earray = new int[10][(alpha_div+1)][(beta_div+1)][(gamma_div+1)];
					((InfoPanel)infopanel).displayString("done\n");
					for(int p=0;p<10;p++) {
						((InfoPanel)infopanel).displayString("Iteration "+p+"\n");
						sarray = new int[(alpha_div+1)*(beta_div+1)*(gamma_div+1)][tmax];
						int[][][] earray = new int[(alpha_div+1)][(beta_div+1)][(gamma_div+1)];
						int in1 = 0;
						int in2 = 0;
						int in3 = 0;

						for(double i=0.0;i<=2.0;i+=(2.0/alpha_div)) {
							for(double j=0.0;j<=2.0;j+=(2.0/beta_div)) {
								for(double k=0.0;k<=2.0;k+=(2.0/gamma_div)) {
									alpha = i;
									beta = j;
									gamma = k;
									begin();
									earray[in1][in2][in3] = acc(sarray[cntr]);
									cntr++;
									in3++;
								}
								in2++;
								in3=0;
							}
							in1++;
							in2=0;
						}

						for(int i=0;i<earray.length;i++) {
							for(int j=0;j<earray[i].length;j++) {
								for(int k=0;k<earray[i][j].length;k++) {
									avg_earray[p][i][j][k] = earray[i][j][k];
									earray[i][j][k] = 0;
								}
							}
						}
						
						cntr = 0;
						in1 = 0;
						in2 = 0;
						in3 = 0;

						//copy sarray to larger array, when needed later on
					}

					//average the results & write to file
					double avg = 0.0;
					for(int h=0;h<avg_earray[0][0][0].length;h++) {
						for(int i=0;i<avg_earray[0][0].length;i++) {
							for(int j=0;j<avg_earray[0].length;j++) {
								for(int k=0;k<avg_earray.length;k++) {
									avg+=avg_earray[k][j][i][h];
								}
								//data_writer.write(j+" "+i+" "+h+" "+(avg/avg_earray.length)+"\n");
								//data_writer.flush();
								avg=0;
							}
						}
					}

				}

				/*
				for(int i=0;i<sarray[0].length;i++) {
					for(int j=0;j<sarray.length;j++) {
						success_writer.write(sarray[j][i]+" ");
						success_writer.flush();
					}
					success_writer.write("\n");
					success_writer.flush();
				}
				*/
			}
		}
		catch(Exception ioe) {System.out.println(ioe.getMessage());}
	}

	private void initGrid() {
		int sx = (width/grid_width)/2;
		int sy = (height/grid_height)/2;

		xinterval = (width/grid_width);
		yinterval = (height/grid_height);

		grid = new Point[grid_width][grid_height];
		for(int i=0;i<grid_width;i++) {
			for(int j=0;j<grid_height;j++) {
				grid[i][j] = new Point(sx+((int)(width/grid_width)*i), sy+((int)(height/grid_height)*j));
				grid[i][j].setIIndex(i);
				grid[i][j].setJIndex(j);
			}
		}

		//uncomment the next loop to create a non-uniform graph
		for(int i=0;i<grid_width;i++) {
			for(int j=0;j<grid_height;j++) {
				grid[i][j].setX(grid[i][j].getX()+(int)((-xinterval/4)+Math.random()*(xinterval/2)));
				grid[i][j].setY(grid[i][j].getY()+(int)((-yinterval/4)+Math.random()*(yinterval/2)));
			}
		}
	}

	private void initEdges() {
		int x = 0;
		int y = 0;
		int offx = 0;
		int offy = 0;
		boolean already_there = false;

		for(int i=0;i<grid_width;i++) {
			for(int j=0;j<grid_height;j++) {
				x = i;
				y = j;

				Point p1 = grid[x][y];

				for(int k=0;k<3;k++) {
					for(int l=0;l<3;l++) {
						offx = k;
						offy = l;

						try {
							Point p2 = grid[(i-1)+offx][(j-1)+offy];

							if(p1 != p2) {
								for(int m=0;m<edges.size();m++) {
									Edge e = (Edge)edges.elementAt(m);
									if(e.contains(p1,p2) || p1 == p2) {
										already_there = true;
										break;
									}
								}

								if(!already_there) {
									Edge e2 = new Edge(p1,p2);
									float[] rgba = {0.5f,0.5f,0.5f,0.5f};
									e2.setColor(rgba);
									edges.addElement(e2);
								}
								else {
									already_there = false;
									throw new ArrayIndexOutOfBoundsException();
								}
							}
						}
						catch(ArrayIndexOutOfBoundsException aaiobe) {}
					}
				}
			}
		}
		BL = width*height;
	}

	public Point getNode() {
		return(current_node);
	}

	public Point setStartNode() {
		start = grid[(int)Math.floor(Math.random()*grid_width)][(int)Math.floor(Math.random()*grid_height)];
		start.setColor(Color.green);
		start.setSpecial(true);
		return(start);
	}

	public Point setEndNode() {
		end = grid[(int)Math.floor(Math.random()*grid_width)][(int)Math.floor(Math.random()*grid_height)];;
		end.setColor(Color.red);
		end.setSpecial(true);
		loop.start();
		return(end);
	}

	public void begin() {
		/*Initialise pheromone strengths*/
		((InfoPanel)infopanel).displayString("Initialising pheromone on edges...");
		for(int i=0;i<edges.size();i++) {
			Edge e = (Edge)edges.elementAt(i);
			e.setPheromone(t0);
		}
		((InfoPanel)infopanel).displayString("done\n");

		((InfoPanel)infopanel).displayString("Initialising ants...");
		/*Initialise ants*/
		ants = new Ant[m];
		for(int i=0;i<ants.length;i++)
			ants[i] = new Ant(start);
		((InfoPanel)infopanel).displayString("done\n");

		int success = 0;

		/*Main loop*/
		for(int t=0;t<tmax;t++) {
			success=0;
			for(int k=0;k<m;k++) {
				Ant ant = ants[k];

				/*Tour the maze for n-1 steps*/
				for(int j=0;j<n-1;j++) {
					Vector e = getEdges(ant.getCurrentNode(), ant.visited);

					if(e.size() == 0) {
						break;
					}

					double[] prob = new double[e.size()];
					double sum_prob = 0.0;
					double sum = 0.0;

					for(int i=0;i<e.size();i++) {
						Edge edge = (Edge)e.elementAt(i);

						if(nav_type == Maze.LOCAL) {
							//LOCAL INVERSE DISTANCES
							sum_prob += Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getStartPoint().getX(), edge.getStartPoint().getY(), edge.getEndPoint().getX(), edge.getEndPoint().getY())),beta);
						}
						else if(nav_type == Maze.GLOBAL) {
							//GLOBAL INVERSE DISANCES
							sum_prob += Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getOther(ant.getCurrentNode()).getX(), edge.getOther(ant.getCurrentNode()).getY(), end.getX(), end.getY())),gamma);
						}
						else if(nav_type == Maze.COMBINED) {
							//LOCAL * GLOBAL INVERSE DISTANCES
							sum_prob += Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getStartPoint().getX(), edge.getStartPoint().getY(), edge.getEndPoint().getX(), edge.getEndPoint().getY())),beta) * Math.pow(1/(cud(edge.getOther(ant.getCurrentNode()).getX(), edge.getOther(ant.getCurrentNode()).getY(), end.getX(), end.getY())),gamma);
						}
					}
					sum = sum_prob;

					for(int i=0;i<e.size();i++) {
						Edge edge = (Edge)e.elementAt(i);

						if(nav_type == Maze.LOCAL) {
							//LOCAL INVERSE DISTANCES
							prob[i] = (Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getStartPoint().getX(), edge.getStartPoint().getY(), edge.getEndPoint().getX(), edge.getEndPoint().getY())),beta))/sum_prob;
						}
						else if(nav_type == Maze.GLOBAL) {
							//GLOBAL INVERSE DISANCES
							prob[i] = (Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getOther(ant.getCurrentNode()).getX(), edge.getOther(ant.getCurrentNode()).getY(), end.getX(), end.getY())),gamma))/sum_prob;
						}
						else if(nav_type == Maze.COMBINED) {
							//LOCAL * GLOBAL INVERSE DISTANCES
							prob[i] = (Math.pow(edge.getPheromone(), alpha) * Math.pow(1/(cud(edge.getStartPoint().getX(), edge.getStartPoint().getY(), edge.getEndPoint().getX(), edge.getEndPoint().getY())),beta) * Math.pow(1/(cud(edge.getOther(ant.getCurrentNode()).getX(), edge.getOther(ant.getCurrentNode()).getY(), end.getX(), end.getY())),gamma))/sum_prob;
						}
					}
					
					//deterministic selection
					/*
					Edge best = (Edge)e.elementAt((int)(Math.random()*e.size()));
					double max = prob[0];
					double current = 0;
					int id = 0;

					for(int i=0;i<prob.length;i++) {
						current=prob[i];
						if(current > max) {
							id = i;
							max = current;
						}
					}

					best = (Edge)e.elementAt(id);
					*/

					//probabilistic selection
					Edge best = (Edge)e.elementAt((int)(Math.random()*e.size()));
					double p = prob[0];
					double r = Math.random()*acc(prob);
					double s = 0.0;

					for(int i=0;i<prob.length;i++) {
						p=prob[(int)(Math.random()*prob.length)];
						if(s+p >= r) {
							best = (Edge)e.elementAt(i);
							break;
						}
						else {
							s+=p;
						}
					}

					ant.addEdge(best, cud(best.getStartPoint().getX(), best.getStartPoint().getY(), best.getEndPoint().getX(), best.getEndPoint().getY()));
					ant.setCurrentNode(best.getOther(ant.getCurrentNode()));

					ant.getCurrentNode().setColor(Color.blue);
					ant.getCurrentNode().setSpecial(true);

					if(ant.getCurrentNode() == end) {
						success++;
						break;
					}

					try {Thread.sleep(50);}catch(Exception exc) {}

					repaint();
				}

				for(int i=0;i<grid_width;i++) {
					for(int j=0;j<grid_height;j++) {
						if(grid[i][j] != start && grid[i][j] != end) {
							grid[i][j].setSpecial(false);
							grid[i][j].setColor(Color.black);
						}
					}
				}

				/*remove all non-complete tours*/
				if(ant.getCurrentNode() != end) {
					ant.setTour(new Vector());
					ant.setTourLength((double)(width*height));
				}
				else {
					sarray[cntr][epoch]++;
				}

				/*update best tour & length here*/
				if(ant.getCurrentNode() == end && ant.getTourLength() < BL) {
					BT = ant.getTour();
					BL = ant.getTourLength();
				}
			}

			/*Update pheromone trails*/
			for(int j=0;j<edges.size();j++) { 
				Edge e = (Edge)edges.elementAt(j);
				double gdelta_pe = 0.0;

				for(int i=0;i<ants.length;i++) {
					T = ants[i].getTour();
					L = ants[i].getTourLength();
					double delta_p = 0.0;

					if(memberObj(T,e)) {
						delta_p = q/L;
					}

					gdelta_pe+=delta_p;
				}
				e.setPheromone(((1.0-p)*e.getPheromone())+gdelta_pe);
			}

			epoch++;

			ants = new Ant[m];
			for(int i=0;i<ants.length;i++)
				ants[i] = new Ant(start);

			/*Lower decay rate over time to solidify average routes*/
			p-=((pmax/(double)tmax));
			repaint();
		}

		/*Paint the final path in red*/
		for(int i=0;i<BT.size();i++) {
			Edge e = (Edge)BT.elementAt(i);
			float[] rgba = {1.0f, 0.0f, 0.0f, 1.0f};
			e.setColor(rgba);
		}
		repaint();

		T = new Vector(0,1);
		L = 0.0;
		BT = new Vector(0,1);
		BL = width*height;
		epoch = 0;
	}

	public double acc(double[] ar) {
		double s = 0.0;
		for(int i=0;i<ar.length;i++)
			s+=ar[i];
		return(s);
	}

	public int acc(int[] ar) {
		int s = 0;
		for(int i=0;i<ar.length;i++)
			s+=ar[i];
		return(s);
	}

	public double cud(int x1, int y1, int x2, int y2) {
		double xdelta_alpha = Math.abs((x1-x2)*(x1-x2));
		double ydelta_alpha = Math.abs((y1-y2)*(y1-y2));
		return(Math.sqrt(xdelta_alpha+ydelta_alpha));
	}

	public Vector getNodes(Point p) {
		Vector v = new Vector(0,1);

		for(int i=p.getIIndex()-1;i<3;i++) {
			for(int j=p.getJIndex()-1;j<3;j++) {
				try {
					if(grid[i][j] != p)
						v.addElement(grid[i][j]);
				}
				catch(ArrayIndexOutOfBoundsException e) {System.out.println(e.getMessage());}
			}
		}

		return(v);
	}

	public Vector getEdges(Point p, Vector visited) {
		Vector v = new Vector(0,1);

		for(int i=0;i<edges.size();i++) {
			Edge e = (Edge)edges.elementAt(i);

			if(e.isStartOrEnd(p) && (!member(visited,e.getOther(p))))
				v.addElement(e);
		}

		return(v);
	}

	public boolean member(Vector v, Point p) {
		for(int i=0;i<v.size();i++) {
			if(p == (Point)v.elementAt(i))
				return(true);
		}
		return(false);
	}

	public boolean memberObj(Vector v, Object o) {
		for(int i=0;i<v.size();i++) {
			if(o == v.elementAt(i))
				return(true);
		}
		return(false);
	}

	public void update(Graphics g) {
		paint(g);
	}

	public void paint(Graphics g) {
		if(buffer == null) {
			buffer = createImage(width, height);
			bg = buffer.getGraphics();
		}
		
		bg.setColor(Color.white);
		bg.fillRect(0,0,width,height);

		//draw edges
		for(int i=0;i<edges.size();i++) {
			Edge e = (Edge)edges.elementAt(i);
			e.paint(bg);
		}

		//draw grid points
		for(int i=0;i<grid_width;i++) {
			for(int j=0;j<grid_height;j++) {
				if((grid[i][j].getX() > (mx-(xinterval/2))) && (grid[i][j].getX() < (mx-(xinterval/2)+xinterval))) {
					if((grid[i][j].getY() > (my-(yinterval/2))) && (grid[i][j].getY() < (my-(yinterval/2)+yinterval))) {
						selected=true;
						current_node = grid[i][j];
					}
					else selected = false;
				}
				else selected = false;

				if(selected) {
					grid[i][j].setSelected(true);
				}
				else {
					grid[i][j].setSelected(false);
				}

				if(end != null) {
					grid[i][j].str = (int)cud(grid[i][j].getX(), grid[i][j].getY(), end.getX(), end.getY());
				}
				grid[i][j].paint(bg);
			}
		}

		//draw mouse area
		bg.setColor(Color.blue);
		bg.drawRect(mx-(xinterval/2), my-(yinterval/2), xinterval, yinterval);

		g.drawImage(buffer, 0, 0, width, height, this);
	}
}

class EventHandler implements MouseListener, MouseMotionListener
{
	Maze master = null;

	public EventHandler(Maze env) {
		master = env;
	}

	public void mouseMoved(MouseEvent evt) {
		int mx = evt.getX();
		int my = evt.getY();
		master.mx = mx;
		master.my = my;
		master.repaint();
	}

	public void mouseDragged(MouseEvent evt) {
		int mx = evt.getX();
		int my = evt.getY();
	}

	public void mouseEntered(MouseEvent evt) {

	}

	public void mouseExited(MouseEvent evt) {

	}

	public void mousePressed(MouseEvent evt) {
		int mx = evt.getX();
		int my = evt.getY();
		master.mx = mx;
		master.my = my;
		master.repaint();
		if(master.select_start) {
			master.setStartNode();
		}
		else if(master.select_end) {
			master.setEndNode();
		}
	}

	public void mouseReleased(MouseEvent evt) {
		int mx = evt.getX();
		int my = evt.getY();
	}

	public void mouseClicked(MouseEvent evt) {

	}
}

class AntSystem extends Thread 
{
	private Maze master = null;

	public AntSystem(Maze m) {
		master = m;
	}

	public void run() {
		while(true) {
			try {
				Thread.sleep(100);
				master.repaint();
			}
			catch(InterruptedException ie) {}
		}
	}
}