#include <iostream>
#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

#define RIGHE 20
#define COLONNE 20

struct blocco{
	int x;
	int y;
	struct blocco * prossimo;
};

struct coordinata{
	int x;
	int y;
};

struct rete{
	int griglia[20][20];
	int punteggio=0;
	int mosse=0;
	float sinapsi_ps [20][20][20];
	float sinapsi_ss [20][4];
	float neuroni_ps [20];
	float neuroni_ss [4];
	struct blocco* snake;
	struct coordinata velocita;
	struct coordinata mela;
	bool game_over = false;

};

struct rete reti[100];

float RandomFloat(float a, float b) {

    float random = ((float) rand()) / (float) RAND_MAX;
    float diff = b - a;
    float r = random * diff;
    return a + r;
}

void iniz_reti_rand(struct rete reti[]){
	for(int i=0;i<100;i++){
		for(int t=0;t<20;t++)
			for(int k=0;k<20;k++)
				for(int j=0;j<20;j++)
					reti[i].sinapsi_ps[t][k][j] = RandomFloat(-1,1);

		for(int r=0;r<20;r++)
			for(int j=0;j<4;j++)
				reti[i].sinapsi_ss[r][j] = RandomFloat(-1,1);
	}
	return;
}

void iniz_neuroni(struct rete reti){
	for(int r=0;r<20;r++)
			reti.neuroni_ps[r]=0;
	for(int r=0;r<20;r++)
		reti.neuroni_ss[r]=0;
	return;
}

float abs_v(float v){
	if(v >=0)
		return v;
	else return (-v);
}

int find_max (float v[]){
	if(v[0]>=v[1] && v[0]>=v[2] && v[0]>=v[3])
		return 0;
	else if(v[1]>=v[0] && v[1]>=v[2] && v[1]>=v[3])
		return 1;
	else if(v[2]>=v[0] && v[2]>=v[1] && v[2]>=v[3])
		return 2;
	else if(v[3]>=v[0] && v[3]>=v[1] && v[3]>=v[2])
		return 3;
}

char mossa (struct rete reti){
	for(int i=0;i<20;i++)
		for(int k=0;k<20;k++)
			for(int j=0;j<20;j++)
				reti.neuroni_ps[j]+=reti.griglia[i][k]*reti.sinapsi_ps[i][k][j];
	for(int i=0;i<20;i++)
		if(reti.neuroni_ps[i]<0)
			reti.neuroni_ps[i] = reti.neuroni_ps[i]/(abs_v(reti.neuroni_ps[i])+1);

	for(int i=0;i<20;i++)
		for(int j=0;j<4;j++)
			reti.neuroni_ss[j]+= reti.neuroni_ps[i]*reti.sinapsi_ss[i][j];

	for(int i=0;i<4;i++)
		reti.neuroni_ss[i] = reti.neuroni_ss[i]/(abs_v(reti.neuroni_ss[i])+1);
	int max = find_max(reti.neuroni_ss);
	if(max==0)
		return 'w';
	else if(max==1)
		return 's';
	else if(max==2)
		return 'a';
	else if(max==3)
		return 'd';

}

void make_griglia(int griglia[][COLONNE],struct blocco* snake,int mela_x,int mela_y){
	griglia[mela_x][mela_y]=2;
	struct blocco* p = snake;
	while(p != NULL){
		if(p->prossimo != NULL)
			griglia[p->x][p->y]=1;
		else
			griglia[p->x][p->y]=3;
		p = p-> prossimo;
	}
	return;
}

bool death(struct blocco* snake){
	struct blocco* p = snake;
	struct blocco* q = snake;

	while(p != NULL){
		q=p;
		p = p-> prossimo;
	}
	//q punta alla testa
	if(q->x == 0 || q->y == 0 || q->x == COLONNE - 1 || q->y == RIGHE - 1)
		return true;
	p=snake;
	while(p != q){
		if(p->x == q->x && p->y == q->y)
				return true;
		p=p->prossimo;
	}
	return false;
}

void inizializza(int griglia[RIGHE][COLONNE]){
	for(int i=0;i<RIGHE;i++)
		for(int k=0;k<COLONNE;k++)
			griglia[i][k]=0;
	return;
}
void print(int griglia[RIGHE][COLONNE]){
	for(int i=0;i<RIGHE;i++){
		for(int k=0;k<COLONNE;k++)
			cout << griglia[i][k];
		cout << endl;
	}
	cout << endl;
	return;
}

void reti_migliori(int reti_vincenti[], struct rete reti[]){
	for (int k=0;k<10;k++){
		int m_score=0;
		int i;
		for(i=0;i<100;i++)
			if(reti[i].punteggio>=m_score){
				m_score = reti[i].punteggio;
				reti_vincenti[k] = i;
			}
		reti[reti_vincenti[k]].punteggio = -1000;
	}
	return;
}

void create_seed(float seed_sinapsi_ps [10][20][20][20],float seed_sinapsi_ss [10][20][4],struct rete reti[],int reti_vincenti[]){
	for(int i=0;i<10;i++)
		for(int k=0;k<20;k++)
			for(int j=0;j<20;j++)
				for(int y=0;y<20;y++)
					seed_sinapsi_ps[i][k][j][y] = reti[reti_vincenti[i]].sinapsi_ps[k][j][y];

	for(int i=0;i<10;i++)
		for(int k=0;k<20;k++)
			for(int j=0;j<4;j++)
				seed_sinapsi_ss[i][k][j] = reti[reti_vincenti[i]].sinapsi_ss[k][j];
	return;
}

void iniz_reti_everything(struct rete reti[]){
	for(int i=0;i<100;i++){
		reti[i].snake = new struct blocco;
		reti[i].snake->x = RIGHE/2;
		reti[i].snake->y = COLONNE/2;
		reti[i].snake->prossimo = NULL;

		struct blocco* p = new struct blocco;
		p->x = RIGHE/2-1;
		p->y = COLONNE/2;
		p->prossimo = reti[i].snake;
		reti[i].snake = p;

		p = new struct blocco;
		p->x = RIGHE/2-2;
		p->y = COLONNE/2;
		p->prossimo = reti[i].snake;
		reti[i].snake = p;

		reti[i].mela.x = rand() % (RIGHE-2) +1;
		reti[i].mela.y = rand() % (COLONNE-2) +1;

		reti[i].velocita.x=1;
		reti[i].velocita.y=0;

		reti[i].mosse = 0;
		reti[i].punteggio = 0;
		reti[i].game_over = false;

		inizializza(reti[i].griglia);
	}
	return;
}

void create_reti_from_seed(struct rete reti[],float seed_sinapsi_ps [10][20][20][20],float seed_sinapsi_ss [10][20][4]){
	for(int i=0;i<100;i++){
		int r = i%10;

		for(int x=0;x<20;x++)
			for(int y=0;y<20;y++)
				for(int z=0;z<20;z++)
					reti[i].sinapsi_ps[x][y][z] =  (seed_sinapsi_ps [r][x][y][z])*RandomFloat(0.99,1.01);
		for(int x=0;x<20;x++)
			for(int y=0;y<4;y++)
				reti[i].sinapsi_ss[x][y] = seed_sinapsi_ss [r][x][y]*RandomFloat(0.99,1.01);
	}
	return;
}

int main(){
	iniz_reti_rand(reti);
	iniz_reti_everything(reti);
	int reti_vincenti[10];
	float seed_sinapsi_ss [10][20][4];
	float seed_sinapsi_ps [10][20][20][20];

	while(1){
		int punti_generazione = 0;
		for(int i=0;i<100;i++){
			while(reti[i].game_over == false){
				make_griglia(reti[i].griglia,reti[i].snake,reti[i].mela.x,reti[i].mela.y);
				char move;
				iniz_neuroni(reti[i]);
				move = mossa(reti[i]);
				if(move == 's'){
					if(reti[i].velocita.x != -1)
						reti[i].velocita.x = 1;
					reti[i].velocita.y = 0;
				}
				if(move == 'w'){
					if(reti[i].velocita.x != 1)
						reti[i].velocita.x = -1;
					reti[i].velocita.y = 0;
				}
				if(move == 'a'){
					reti[i].velocita.x = 0;
					if(reti[i].velocita.y != 1)
						reti[i].velocita.y = -1;
				}
				if(move == 'd'){
					reti[i].velocita.x = 0;
					if(reti[i].velocita.y != -1)
						reti[i].velocita.y = 1;
				}

				struct blocco* old_head = reti[i].snake;
				while(old_head -> prossimo != NULL)
					old_head = old_head -> prossimo;

				struct blocco* n_head = new struct blocco;
				n_head -> x =  old_head -> x + reti[i].velocita.x;
				n_head -> y =  old_head -> y + reti[i].velocita.y;
				n_head -> prossimo = NULL;

				old_head -> prossimo = n_head;
				if(n_head -> x == reti[i].mela.x && n_head -> y == reti[i].mela.y){
					reti[i].mela.x = rand() % (RIGHE-2) +1;
					reti[i].mela.y = rand() % (COLONNE-2) +1;
					reti[i].punteggio += 10;
				}
				else{
					struct blocco* temp = reti[i].snake;
					reti[i].snake = reti[i].snake -> prossimo;
					delete temp;
				}

				reti[i].game_over =  death(reti[i].snake);
				inizializza(reti[i].griglia);

				reti[i].mosse++;
					if(reti[i].mosse > 1000 + reti[i].punteggio*100)
						reti[i].game_over = true;
			}
			punti_generazione += reti[i].punteggio;

		}
		cout << "La generazione " << " ha realizzato " << punti_generazione << " punti" << endl;
		reti_migliori(reti_vincenti,reti);
		create_seed(seed_sinapsi_ps,seed_sinapsi_ss,reti,reti_vincenti);
		create_reti_from_seed(reti,seed_sinapsi_ps,seed_sinapsi_ss);
		iniz_reti_everything(reti);
	}
}