#include <mpi.h>
#include <time.h>
#include <iostream.h>
#include <stdlib.h>
#include "team.h"
#include "common.h"
#include "maze.h"
#include "ghost.h"
#include "pacman.h"

extern const int NUM_PACMEN = 10;
extern int TURN_NUMBER = 0;
const int NUM_TEAMS = 25;
const int MAX_GENERATIONS = 250;
const int ROUNDS_PER_GENERATION = 40;
const int COPY_CHANCE = 20;

int NPES; // the number of cooperating PEs
int PE; // this processes PE number

int MAX_GAME_LENGTH = 150;
int DEADCOUNT;
int TOTAL_FITNESS;
bool DRAW_SCREEN = false;

Maze MAZE;
Pacman* PACMAN;
Team* TEAM;

extern void srand48(long);

void initProgram ();
void giveProgramInformation ();
void doGenerations (int numGenerations);
void initGeneration ();
void runGeneration ();
void doRound ();
void initGame (int teamNum);
void playGame(int teamNum);
void movePacmen();
void moveGhosts(int teamNum);
void checkPacmen();
void createNewGeneration ();
int fitnessMap (int fitness);
Team& chooseTeam();
int doFitnessCalculations ();
void displayBestTeam (bool verbose = false);
void generateDistributionData ();
void drawScreen ();
void endProgram ();


void main (int argc, char** argv)
//Initializes the parallel environment, then executes the main body of the program
{
	int ierr;
	ierr = MPI_Init(&argc, &argv);
	if (ierr)
	{
		cerr << "MPI_Init failed, ierr = " << ierr << endl;
		exit(1);
	}

	ierr = MPI_Comm_size (MPI_COMM_WORLD, &NPES);
	if (ierr)
	{
		cerr << "MPI_Comm_size failed, ierr = " << ierr << endl;
		MPI_Finalize();
		exit(1);
	}

	ierr = MPI_Comm_rank (MPI_COMM_WORLD, &PE);
	if (ierr)
	{
		cerr << "MPI_Comm_rank failed, ierr = " << ierr << endl;
		MPI_Finalize();
		exit(1);
	}

	initProgram();

	doGenerations(MAX_GENERATIONS);

	endProgram();
}

void initProgram()
//Spews out the program information and initializes some variables 
{
	if (PE == 0)
		giveProgramInformation();

	// These two lines will give each PE a different random number generator seed
	time_t t;
	srand48(PE * PE + time(&t));

	PACMAN = new Pacman[NUM_PACMEN];
	TEAM = new Team[NUM_TEAMS];

	Pacman::maze = &MAZE;
	Ghost::maze = &MAZE;
}

void giveProgramInformation ()
//Displays the set conditions of the game
{
	cout << "Pacman" << endl;
	cout << "Ghost evolving project" << endl;
	cout << "Compiled " << __DATE__ << " " << __TIME__ << endl;
	cout << endl;
	cout << "NUM_PACMEN = " << NUM_PACMEN << endl;
	cout << "GHOSTS_PER_TEAM = " << Team::GHOSTS_PER_TEAM << endl;
	cout << "NUM_TEAMS = " << NUM_TEAMS << endl;
	cout << "MAX_GENERATIONS = " << MAX_GENERATIONS << endl;
	cout << "ROUNDS_PER_GENERATION = " << ROUNDS_PER_GENERATION << endl;
	cout << "MAX_GAME_LENGTH = " << MAX_GAME_LENGTH << endl;
	cout << endl;
	cout << "XSIZE = " << Maze::XSIZE << endl;
	cout << "YSIZE = " << Maze::YSIZE << endl;
	cout << endl;

#ifdef ALLOW_SPECIALIZATION
	cout << "Specialization on" << endl;
#else
	cout << "Specialization off" << endl;
#endif


#ifdef PHEROMONES
	cout << "Pheromones on" << endl;
#else
	cout << "Pheromones off" << endl;
#endif

	cout << endl;
}	

void doGenerations (int numGenerations)
// Runs runGeneration a certain amount of times
// Also displays some data between generations
{
	initGeneration();

	for(; numGenerations > 0; numGenerations--)
	{
		runGeneration();

		if (PE == 0)
			cout << numGenerations << " left to go." << endl;

		displayBestTeam();
/*
		if (numGenerations % 50 == 1 || numGenerations == MAX_GENERATIONS)
			generateDistributionData (); */
	}
}

void initGeneration ()
//Initializes a new generation
{
	int i;
	for(i = 0; i < NUM_TEAMS; i++)
	{
		TEAM[i].newGeneration();
	}

	for(i = 0; i < NUM_PACMEN; i++)
	{
		PACMAN[i].newGeneration();
	}
}

void runGeneration ()
//Initializes a new generation and runs a defined number of rounds with it
{
	MPI_Barrier(MPI_COMM_WORLD);

	initGeneration ();

	int i;
	for(i = 0; i < ROUNDS_PER_GENERATION; i++)
	{
		doRound();
	}

	createNewGeneration ();
}

void doRound ()
//Starts and runs a round for each team
{
	MAZE.newRound();
	int i;

	for(i=0; i<NUM_TEAMS; i++)
	{
		initGame(i);
		playGame(i);
	}
}

void initGame(int teamNum)
//Sets the initial conditions of a game
{
	int i;

	MAZE.newGame();
	DEADCOUNT=0;

	for (i=0; i< NUM_PACMEN; i++)
		PACMAN[i].newGame();

	TEAM[teamNum].newGame();
}

void playGame(int teamNum)
// Keeps running the round until either all pacmen are caught, or time runs out
{
	TURN_NUMBER = 0;

	do
	{
		movePacmen();

		moveGhosts(teamNum);

		if (DRAW_SCREEN)
			drawScreen();

	} while (DEADCOUNT < NUM_PACMEN && ++TURN_NUMBER < MAX_GAME_LENGTH);
//	if (turns < MAX_GAME_LENGTH)
//		MAX_GAME_LENGTH--;

	TEAM[teamNum].increaseFitness(DEADCOUNT);
}

void movePacmen()
// Moves each pacman if it isn't dead
{
	int i;

	MAZE.pacmenMoving();

	for(i = 0; i < NUM_PACMEN; i++)
		if (PACMAN[i].isAlive())
			// Is this more efficient?
			if (!PACMAN[i].move())
				DEADCOUNT++;

	MAZE.pacmenDone ();
}

void moveGhosts(int teamNum)
// Moves the ghosts
{
	MAZE.ghostsMoving();

	TEAM[teamNum].moveTeam();

	MAZE.ghostsDone();

	checkPacmen();
}

void checkPacmen()
// Keeps track of the number of pacmen caught
{
	int i;

	for(i = 0; i < NUM_PACMEN; i++)
		if (PACMAN[i].isAlive())
			if (PACMAN[i].deathCheck())
				DEADCOUNT++;
}

void createNewGeneration ()
/*Crosses over generations first within a processor and then among the
group of processors*/
//Intra-processor crossover
{
	static int fromPE = PE, toPE = PE;
	MPI_Status status;
	int i, ierr;
	int bestTeam = doFitnessCalculations ();

	do
	{
		fromPE = (fromPE + 1) % NPES;
		toPE = (toPE + NPES - 1) % NPES;
	} while (fromPE == PE);

	for (i=1; i < NUM_TEAMS; i++)
	{
		if (int(drand48() * COPY_CHANCE) == 0)
		{
			TEAM[i].copy(chooseTeam());
		}
		else
		{
			TEAM[i].crossover(chooseTeam(), chooseTeam());
		}
	}
//Inter-processor crossover
#ifdef ALLOW_SPECIALIZATION
	ierr =
	MPI_Sendrecv (	TEAM[bestTeam].teamProgram,
			Ghost::MAX_PROGRAM_LENGTH * Team::GHOSTS_PER_TEAM,
			MPI_CHAR,
			toPE,
			1,
			TEAM[0].teamNewProgram,
			Ghost::MAX_PROGRAM_LENGTH * Team::GHOSTS_PER_TEAM,
			MPI_CHAR,
			fromPE,
			1,
			MPI_COMM_WORLD,
			&status);
#else
	ierr =
	MPI_Sendrecv (	TEAM[bestTeam].teamProgram,
			Ghost::MAX_PROGRAM_LENGTH,
			MPI_CHAR,
			toPE,
			1,
			TEAM[0].teamNewProgram,
			Ghost::MAX_PROGRAM_LENGTH,
			MPI_CHAR,
			fromPE,
			1,
			MPI_COMM_WORLD,
			&status);
#endif

	if (ierr)
	{
		cerr << "First MPI_Sendrecv failed on PE " << PE << ", ierr = " << ierr << endl;
		MPI_Finalize ();
		exit(1);
	}

#ifdef ALLOW_SPECIALIZATION
	ierr =
	MPI_Sendrecv (	TEAM[bestTeam].teamProgramLength,
			Team::GHOSTS_PER_TEAM,
			MPI_INT,
			toPE,
			2,
			TEAM[0].teamNewProgramLength,
			Team::GHOSTS_PER_TEAM,
			MPI_INT,
			fromPE,
			2,
			MPI_COMM_WORLD,
			&status);
#else
	ierr =
	MPI_Sendrecv (	TEAM[bestTeam].teamProgramLength,
			1,
			MPI_INT,
			toPE,
			2,
			TEAM[0].teamNewProgramLength,
			1,
			MPI_INT,
			fromPE,
			2,
			MPI_COMM_WORLD,
			&status);
#endif

	if (ierr)
	{
		cerr << "Second MPI_Sendrecv failed on PE " << PE << ", ierr = " << ierr << endl;
		MPI_Finalize ();
		exit(1);
	}

	TEAM[0].checkProgramLengths();
}

int fitnessMap (int fitness)
// This computes some function of the fitness and returns a modified version
{
	return fitness * fitness;
}

Team& chooseTeam()
// Chooses a team in proportion to the fitness modified by fitnessMap
{
	int targetFitness = int(drand48() * TOTAL_FITNESS);
	int i = -1;

	do
	{
		i++;
		targetFitness -= fitnessMap(TEAM[i].getFitness());
	} while (targetFitness > 0);

	return TEAM[i];
}

int doFitnessCalculations ()
// Calculates the most fit team and the total fitness of all the teams on each // processor
{
	TOTAL_FITNESS = 0;
	int i, bestTeam = 0, bestFitness = 0, fitness;

	for(i=0; i < NUM_TEAMS; i++)
	{
		fitness = TEAM[i].getFitness();

		if (fitness > bestFitness)
		{
			bestFitness = fitness;
			bestTeam = i;
		}

		TOTAL_FITNESS += fitnessMap(fitness);
	}

	return bestTeam;
}


void displayBestTeam (bool verbose /* = false */)
/* Returns the fitness score of the best fit team and allows user to view a
sample round using the best team */
{
	int i, bestFitness = 0, bestTeam = 0, bestPE = 0;
	MPI_Status status;

	for (i=0; i < NUM_TEAMS; i++)
	{
		if (TEAM[i].getFitness() > bestFitness)
		{
			bestTeam = i;
			bestFitness = TEAM[i].getFitness();
		}
	}

	if (PE == 0)
	{
		int buffer;
		for (i=1; i < NPES; i++)
		{
			MPI_Recv (&buffer, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &status);
			if (buffer > bestFitness)
				bestPE = i;
		}
	}	
	else
	{
		MPI_Send (&bestFitness, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
	}

	MPI_Bcast (&bestPE, 1, MPI_INT, 0, MPI_COMM_WORLD);

	if (bestPE == PE)
	{
		cout << "Best team (fitness/game = " << bestFitness/float(ROUNDS_PER_GENERATION) << ")" << endl;

		if (verbose)
		{
			TEAM[bestTeam].outputPrograms();

			bool oldDrawScreen = DRAW_SCREEN;
			DRAW_SCREEN = true;

			initGame(bestTeam);
			playGame(bestTeam);
			cout << "Deadcount: " << DEADCOUNT << endl;

			DRAW_SCREEN = oldDrawScreen;
		}
	}
}

void generateDistributionData ()
// Prints out the fitness number for every team on every processor
{
	MPI_Barrier (MPI_COMM_WORLD);

	if (PE == 0)
	{
		cout << "Distribution data: " << endl;
		cout << "*--------------" << endl;
	}

	MPI_Barrier (MPI_COMM_WORLD);

	int i;
	for (i=0; i < NUM_TEAMS; i++)
	{
		cout << TEAM[i].getFitness() << endl;
	}

	MPI_Barrier (MPI_COMM_WORLD);

	if (PE == 0)
		cout << "--------------*" << endl;
}


void drawScreen ()
// Displays the maze on the screen
{
	MAZE.display();
}

void endProgram ()
// Gives best team and frees up resources
{
	displayBestTeam (true);

	delete [] PACMAN;
	delete [] TEAM;

	MPI_Finalize();
}