//////////////////////////////////////////////////
//////////////////////////////////////////////////
// ga.js
//////////////////////////////////////////////////
//////////////////////////////////////////////////

function Chromosone()
{
	this.Age = 0;
	this.Steps = 10;
	this.Data = new Array();
	this.Score = 0;
	this.Step = 0;
	this.Touched = false;
	
	this.EvolveType = "";
	
	var i;
	for (i=0;i<this.Steps;i++)
	{
		this.Data[i] = Math.floor(Math.random() * 8)+1;
	}

	this.Length = 3;

	this.PosX = new Array(this.Length);
	this.PosY = new Array(this.Length);

	this.PartsUI = new Array(this.Length);

	this.World = null;
}

Chromosone.prototype.New = function()
{
	var i;
	for (i=0;i<this.Steps;i++)
	{
		this.Data[i] = Math.floor(Math.random() * 8)+1;
	}
}
Chromosone.prototype.GetData = function()
{
	var ret;
	ret="";
	var i;
	for (i=0;i<this.Steps;i++)
	{
		ret = ret + this.Data[i] + '';;
	}
	return ret;
}

Chromosone.prototype.Mutate = function()
{
	var i;
	for (i=0;i<this.Steps;i++)
	{
		if (Math.random() > 0.7)
			this.Data[i] = Math.floor(Math.random() * 8)+1;
	}
}

Chromosone.prototype.CopyDataFrom = function(chromosone2)
{
	var i;
	for (i=0;i<this.Steps;i++)
	{
		this.Data[i] = chromosone2.Data[i];
	}
}

Chromosone.prototype.Equals = function(chromosone2)
{
	var i;
	for (i=0;i<this.Steps;i++)
	{
		if (this.Data[i] != chromosone2.Data[i])
			return false;
	}
	return true;
}

Chromosone.prototype.Crossover = function(chromosone2)
{
	var i,t;
	for (i=Math.floor(this.Steps/2);i<this.Steps;i++)
	{
		t=this.Data[i];
		this.Data[i] = chromosone2.Data[i];
		chromosone2.Data[i] = t;
	}
}

Chromosone.prototype.Reset = function()
{
	this.Score = 0;		
	this.Step = 0;
}

Chromosone.prototype.Step1 = function()
{
	// 812
	// 7 3
	// 654
	this.Step++;
	if (this.Step >= this.Steps)
		this.Step = 0;
	var i;
	for (i=this.Length-2;i>=0;i--)
	{
		this.PosX[i+1] = this.PosX[i];
		this.PosY[i+1] = this.PosY[i];
	}
	if (this.Data[this.Step]==1)	
	{
		this.DecY();
	}
	else if (this.Data[this.Step]==2)	
	{
		this.DecY();
		this.IncX();
	}
	else if (this.Data[this.Step]==3)	
	{
		this.IncX();
	}
	else if (this.Data[this.Step]==4)	
	{
		this.IncX();
		this.IncY();
	}
	else if (this.Data[this.Step]==5)	
	{
		this.IncY();
	}
	else if (this.Data[this.Step]==6)	
	{
		this.DecX();
		this.IncY();
	}
	else if (this.Data[this.Step]==7)	
	{
		this.DecX();
	}
	else if (this.Data[this.Step]==8)	
	{
		this.DecY();
		this.DecX();
	}
}

Chromosone.prototype.DecY = function()
{
		this.PosY[0]--;
		if (this.PosY[0]<0)
			this.PosY[0]+=this.World.Height;
}

Chromosone.prototype.IncY = function()
{
		this.PosY[0]++;
		if (this.PosY[0]>=this.World.Height)
			this.PosY[0]-=this.World.Height;
}
Chromosone.prototype.DecX = function()
{
		this.PosX[0]--;
		if (this.PosX[0]<0)
			this.PosX[0]+=this.World.Width;
}

Chromosone.prototype.IncX = function()
{
		this.PosX[0]++;
		if (this.PosX[0]>=this.World.Width)
			this.PosX[0]-=this.World.Width;
}

Chromosone.prototype.StepFull = function()
{
	for (i=0; i<this.Steps; i++)
		this.Step1();
}

Chromosone.prototype.MoveToRandomSpot = function()
{
	var i;
	var x,y;
	x = Math.floor(Math.random() * (this.World.Width - 1));
	y = Math.floor(Math.random() * (this.World.Height - 1));
	for(i=0;i<this.Length;i++)
	{
		this.PosX[i] = x;
		this.PosY[i] = y;
	}
}
Chromosone.prototype.ToString = function()
{
	var temp = this.GetData() + " Score " + this.Score + " (" + this.EvolveType + ")";
	return temp;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////

function World(w,h)
{
	this.Width = w;
	this.Height = h;

	this.BestEver = "";
	this.BestEverScore = 0;

	this.PopulationSize = 0;
	this.Population = new Array();

	this.Data = new Array(h);
	this.DataUI = new Array(h);
	for (i=0; i<h; i++)
	{
		this.Data[i] = new Array(w);
		this.DataUI[i] = new Array(w);
	}
	this.Clear();
}

World.prototype.Clear = function()
{
	for (j=0; j<this.Width; j++)
		for (i=0; i<this.Height; i++)
		{
			this.Data[i][j] = 0;
			this.DataUI[i][j] = null;
		}
}
World.prototype.AddFood = function(foodcount)
{
	var i;
	for (i=0; i<foodcount; i++)
	{
		x = Math.floor(Math.random() * (this.Width - 1));
		y = Math.floor(Math.random() * (this.Height - 1));
		if (this.Data[y][x]==0)
			this.Data[y][x] = 1;
	}
}

World.prototype.AddPopulation = function(populationcount)
{
	var i;
	this.PopulationSize = populationcount;
	this.Population = new Array(populationcount);
	for (i=0; i<populationcount; i++)
	{
		this.Population[i] = new Chromosone();
		this.Population[i].World = _world;
		this.Population[i].MoveToRandomSpot();
	}
}

World.prototype.CheckIfFoundFood = function(chromo)
{
	var x,y;
	var nx,ny;
	var ret=false;
	x=chromo.PosX[0];
	y=chromo.PosY[0];
	if (this.Data[y][x]==1)
	{
		nx=x;
		ny=y;
		while(this.Data[ny][nx]==1)
		{
			nx = Math.floor(Math.random() * (this.Width - 1));
			ny = Math.floor(Math.random() * (this.Height - 1));
		}
		this.Data[ny][nx]=1;
		this.DataUI[ny][nx]=this.DataUI[y][x];
		this.DataUI[y][x]=null;
		this.Data[y][x]=0;
		ret=true;
	}
	return ret;
}

World.prototype.SortPopulation = function()
{
	var temp;
	var swapped = true;
	var i;
	while (swapped)
	{
		swapped=false;
		for (i=0;i<this.PopulationSize-1;i++)
		{
			if (this.Population[i].Score < this.Population[i+1].Score)
			{
				swapped=true;
				temp=this.Population[i];
				this.Population[i] = this.Population[i+1];
				this.Population[i+1] = temp;
				temp=null;
			}
		}
	}
}

World.prototype.EvolvePopulation = function(showinfo)
{
	var before,after;
	var i,rand,j;
	var totalrank=0;
	var thisrank;
	this.SortPopulation();
	
	if (this.Population[0].Score > this.BestEverScore)
	{
		this.BestEverScore = this.Population[0].Score;
		this.BestEver = this.Population[0].GetData();
	}
	
	before=this.PrintPopulation("Before Evolve");
	for (i=0;i<this.PopulationSize;i++)
	{
		this.Population[i].Touched = false;
		//alert(i+ ' ' + this.Population[i].Score);
		this.Population[i].Score=this.PopulationSize-i;
		totalrank = totalrank + this.Population[i].Score;
		this.Population[i].EvolveType="";
	}
	this.Population[0].Touched = true;
	this.Population[1].Touched = true;
	this.Population[2].Touched = true;
	this.Population[3].Touched = true;
	
  this.Population[0].EvolveType="Elite ";
  this.Population[1].EvolveType="Elite ";
  this.Population[2].EvolveType="Elite ";
  this.Population[3].EvolveType="Elite ";

	//Keep the best
	this.Population[this.PopulationSize-1].CopyDataFrom(this.Population[0]);
	this.Population[this.PopulationSize-1].Touched = true;
  this.Population[this.PopulationSize-1].EvolveType="Elite ";
	
	//Copy the best and mutate
	this.Population[this.PopulationSize-2].CopyDataFrom(this.Population[0]);
	this.Population[this.PopulationSize-2].Touched = true;
  this.Population[this.PopulationSize-2].EvolveType="Elite ";
	this.Population[this.PopulationSize-2].Mutate();
	this.Population[this.PopulationSize-2].EvolveType+="Mutate ";

	//Crossover - rank selection
	var r1=null;
	var r2=null;
	var ii;
	for (i=0;i<3;i++)
	{
		r1=-1;
		r2=-1;
		rand = Math.floor(Math.random() * totalrank);
		thisrank=0;
		for (ii=0;ii<this.PopulationSize;ii++)
		{
			thisrank = thisrank + this.Population[ii].Score;
			if (thisrank>rand)
			{
				r1=ii;
				break;
			}
		}
		rand = Math.floor(Math.random() * totalrank);
		thisrank=0;
		for (ii=0;ii<this.PopulationSize;ii++)
		{
			thisrank = thisrank + this.Population[ii].Score;
			if (thisrank>rand)
			{
				r2=ii;
				break;
			}
		}
		if (r1!=-1 && r2!=-1 && r1!=r2)
		{
			this.Population[r1].Touched=true;
			this.Population[r2].Touched=true;
			this.Population[r1].Crossover(this.Population[r2]);
		  this.Population[r1].EvolveType+="CrossOver"+i+" ";
		  this.Population[r2].EvolveType+="CrossOver"+i+" ";

		}
	}
	//Mutate
	for (i=0;i<this.PopulationSize;i++)
	{
		if (Math.random() > 0.80 && !this.Population[i].Touched)
		{
			this.Population[i].Touched = true;
			this.Population[i].Mutate();
		  this.Population[i].EvolveType+="Mutate ";
		}
	}
	//Mutate
	for (i=0;i<this.PopulationSize;i++)
	{
		if (!this.Population[i].Touched)
		{
			this.Population[i].New();
		  this.Population[i].EvolveType+="New ";
		}
	}
	this.EliminateDuplicates();
	after=this.PrintPopulation("After Evolve");
	if (showinfo)
		alert(before+after+"Best Ever: " + this.BestEver + " ("+this.BestEverScore+")");
}

World.prototype.EliminateDuplicates = function()
{
	var a,b;
	for (a=0;a<this.PopulationSize;a++)
	{
		for (b=0;b<this.PopulationSize;b++)
		{
			if (a!=b)
			{
				if (this.Population[a].Equals(this.Population[b]))
				{
					this.Population[b].New();
				  this.Population[b].EvolveType="New(d) ";
				}				
			}
		}
	}
}

World.prototype.PrintPopulation = function(title)
{
	var temp=title+":\r\n";
	for (i=0;i<this.PopulationSize;i++)
	{
		temp=temp+this.Population[i].ToString() + "\r\n";
	}
	temp=temp+"\r\n";
	return temp;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
/*
var WIDTH = 50;
var HEIGHT = 50;
var POPSIZE = 30;
var FOODCOUNT = 30;
var _world = new World(WIDTH,HEIGHT);
_world.Clear();
var _population = new Array();
for (i=0;i<POPSIZE;i++)
{
	_population[i] = new Chromosone();
	_population[i].World = _world;
	_population[i].MoveToRandomSpot();
}
_world.AddFood(FOODCOUNT);
*/

/*
Best: 4754455454
3566724364
*/