#include <stdio.h>
#include <stdlib.h>
#include <curses.h>

#define made_quad 16

int U = 0;
int R = 1;
int D = 2;
int L = 3;

void initialize(int seed);
void camera_full();
void printboard();
void movem(int d);
void lookd(int d);
int setdn(int x, int y, int g);
void inc_combo();
void addst(int d);
void reduce(int x, int y);
int abs_dist(int x, int y);

char walls[made_quad][made_quad];											//Wall Map, Used to prevent
char dist[made_quad][made_quad];												//Distance Map, Used for Opt Path
char board[made_quad][made_quad];											//Random Generated Map, Used for simulated sensors
char backstack[made_quad * made_quad];										//Movement Stack, Top is Current, Bottom is START
int stack_depth = 0;

int start_x, start_y;
int end_x, end_y;
int mouse_x, mouse_y;

int stat_moves = 0;
int stat_discs = 0;

int main()
{
	int goal = 0;
	int count;
	int length = 0;
	int temp;
	int tempd;
	int i;
	int max_tri = (made_quad)*(made_quad);
	int seed = 0;
	char option;

	do {
		seed++;
		initialize(seed);
		printboard();
		printf("Continue With Seed %d? ", seed);
		scanf("%c",&option);
	} while ( option != 'y' && option != 'Y' );

	while ( stack_depth != 0 || goal == 0 )
	{
		if ( mouse_x == end_x && mouse_y == end_y )
		{
			max_tri = dist[end_x][end_y];
			printboard();
			printf("Goal! Start: %d %d, End: %d %d\n", start_x, start_y, end_x, end_y);
			goal = 1;
			getchar();
		}
		if ((walls[mouse_x][mouse_y]/1)%2 == 0 && dist[mouse_x][mouse_y-1] == -1 && abs_dist(mouse_x, mouse_y-1) < max_tri &&
			(goal == 0 || dist[mouse_x][mouse_y] + 1 < dist[end_x][end_y] * 2) )
		{
			movem(U);
			lookd(U);
			addst(D);
			max_tri = setdn(mouse_x,mouse_y,max_tri);
		}
		else if ((walls[mouse_x][mouse_y]/2)%2 == 0 && dist[mouse_x+1][mouse_y] == -1 && abs_dist(mouse_x+1, mouse_y) < max_tri &&
			(goal == 0 || dist[mouse_x][mouse_y] + 1 < dist[end_x][end_y] * 2) )
		{
			movem(R);
			lookd(R);
			addst(L);
			max_tri = setdn(mouse_x,mouse_y,max_tri);
		}
		else if ((walls[mouse_x][mouse_y]/4)%2 == 0 && dist[mouse_x][mouse_y+1] == -1 && abs_dist(mouse_x, mouse_y+1) < max_tri &&
			(goal == 0 || dist[mouse_x][mouse_y] + 1 < dist[end_x][end_y] * 2) )
		{
			movem(D);
			lookd(D);
			addst(U);
			max_tri = setdn(mouse_x,mouse_y,max_tri);
		}
		else if ((walls[mouse_x][mouse_y]/8)%2 == 0 && dist[mouse_x-1][mouse_y] == -1 && abs_dist(mouse_x-1, mouse_y) < max_tri &&
			(goal == 0 || dist[mouse_x][mouse_y] + 1 < dist[end_x][end_y] * 2) )
		{
			movem(L);
			lookd(L);
			addst(R);
			max_tri = setdn(mouse_x,mouse_y,max_tri);
		}
		else
		{
			printf("Checking BackStack: ");
			for ( i=0 ; i<stack_depth ; i++ )
				printf("[%d]", backstack[i]);
			printf(" --> %d cells\n",stack_depth);
			
			if (stack_depth > 0 )
			{
				movem(delst());
			}
			else
			{
				printboard();
				printf("~~~~~~~~~~~~~~~~~~~~~~~~~stack_exhausted~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
				getchar();
			}
		}


		printboard();
		printf("[Abs Dist: %d][Max Tri: %d]\n", abs_dist(mouse_x, mouse_y), max_tri);
		getchar();
		
	}

	printboard();
	printf("Made It Back!  Moves: %d  Discs: %d\n", stat_moves, stat_discs);
}
void initialize(int seed)
{
	int i,j;
	FILE *fpREAD;
	char filename[9];

	for (j=0;j<1000;j++)
	{
		backstack[j] = -1;
	}

	for (j=0;j<made_quad;j++)
	{
		for (i=0;i<made_quad;i++)
		{
			walls[i][j] = -1;
			dist[i][j] = -1;
		}
	}
	
	filename[0] = ( ( seed % 1000 ) / 100 ) + '0';
	filename[1] = ( ( seed % 100  ) / 10  ) + '0';
	filename[2] = ( ( seed % 10   ) / 1   ) + '0';
	filename[3] = '.';
	filename[4] = 'm';
	filename[5] = 'a';
	filename[6] = 'z';
	filename[7] = 'e';
	filename[8] = 0;

	if ( fpREAD = fopen( filename, "r") )
	{
		printf("File %s Openable!\n", filename);

		for (j=0;j<made_quad;j++)
		{
			for (i=0;i<made_quad;i++)
			{
				
				board[i][j] = fgetc(fpREAD);
				if (board[i][j] == '\n' || board[i][j] == '\r' )
					i--;
			}
		}
		fscanf(fpREAD, "\n\n%d %d\n%d %d\n", &start_x, &start_y, &end_x, &end_y);
	}
	else
	{
		printf("File %s Unopenable! Creating Random Maze (unverified)\n", filename);

		for ( i=0 ; i<seed ; i++ )
			rand();

		for (j=0;j<made_quad;j++)
			for (i=0;i<made_quad;i++)
				board[i][j] = (rand() % 2) + 1;

		start_x = rand() % made_quad;
		start_y = rand() % made_quad;

		end_x = rand() % made_quad;
		end_y = rand() % made_quad;
	}

	for (j=0;j<made_quad;j++)
	{
		for (i=0;i<made_quad;i++)
		{
			if ( i>0 && (board[i-1][j]/2)%2 == 1 && (board[i][j]/8)%2 == 0 )
				board[i][j] += 8;
			if ( i<made_quad && (board[i+1][j]/8)%2 == 1 && (board[i][j]/2)%2 == 0 )
				board[i][j] += 2;
			if ( j>0 && (board[i][j-1]/4)%2 == 1 && (board[i][j]/1)%2 == 0 )
				board[i][j] += 1;
			if ( j<made_quad && (board[i][j+1]/1)%2 == 1 && (board[i][j]/4)%2 == 0 )
				board[i][j] += 4;
		}
	}

	for (j=0;j<made_quad;j++)
	{
		for (i=0;i<made_quad;i++)
		{
			if ( i==0  && (board[i][j]/8)%2 == 0 )
				board[i][j] += 8;
			if ( j==made_quad-1 && (board[i][j]/4)%2 == 0 )
				board[i][j] += 4;
			if ( i==made_quad-1  && (board[i][j]/2)%2 == 0 )
				board[i][j] += 2;
			if ( j==0  && (board[i][j]/1)%2 == 0 )
				board[i][j] += 1;
		}
	}
	

	mouse_x = start_x;
	mouse_y = start_y;

	dist[start_x][start_y] = 0;

	camera_full();

}
void printboard()
{
	int i, j;
		printf("Board Reference:\n");
	for (i=0;i<made_quad; i++ )
	{
		printf("+---");
	}
	printf("+\n");

	for (j=0;j<made_quad; j++ )
	{
		printf(" ");
		for (i=0;i<made_quad;i++)
		{
			if ( (board[i][j]/8) % 2 )
				printf("\b|");

			if ( mouse_x == i && mouse_y == j )
				printf(">.<");
			else if ( start_x == i && start_y == j )
				printf("SSS");
			else if ( end_x == i && end_y == j )
				printf("EEE");
			else
			{
				if ( dist[i][j] == -1 )
					printf("   ");
				else
					printf("%3d",dist[i][j]);
			}

			if ( (board[i][j]/2) % 2 )
				printf("|");
			else
				printf(" ");
		}
		printf("\n");

		for (i=0;i<made_quad;i++)
		{
			if ( (board[i][j]/4) % 2 || (board[i][j+1]/1) % 2 )
				printf("+---");
			else
				printf("+   ");
		}
		printf("+\n");
	}
}

void camera_full()
{
	stat_discs++;
	walls[mouse_x][mouse_y] = board[mouse_x][mouse_y];
}
void movem(int d)
{
	stat_moves++;

	if ( d == U )
		mouse_y -= 1;
	else if ( d == R )
		mouse_x += 1;
	else if ( d == D )
		mouse_y += 1;
	else if ( d == L )
		mouse_x -= 1;
}
void lookd(int d)
{
	if ( walls[mouse_x][mouse_y] == -1 )
	{
		camera_full();
	}
}
int setdn(int x, int y, int g)
{
	int temp = (made_quad)*(made_quad);
	int i,j;
	int flag = 0;

	if ( y>0  && (walls[x][y]/1)%2 == 0 && dist[x  ][y-1] >= 0 && dist[x  ][y-1] < temp )
		temp = dist[x][y-1];
	if ( x<made_quad-1 && (walls[x][y]/2)%2 == 0 && dist[x+1][y  ] >= 0 && dist[x+1][y  ] < temp )
		temp = dist[x+1][y];
	if ( y<made_quad-1 && (walls[x][y]/4)%2 == 0 && dist[x  ][y+1] >= 0 && dist[x  ][y+1] < temp )
		temp = dist[x][y+1];
	if ( x>0  && (walls[x][y]/8)%2 == 0 && dist[x-1][y  ] >= 0 && dist[x-1][y  ] < temp )
		temp = dist[x-1][y];

	dist[x][y] = temp + 1;

	if ( y>0  && (walls[x][y]/1)%2 == 0 && dist[x  ][y-1] > temp + 2 )
	{
		printf("[Recalc 0]");
		reduce(x,y);
		flag = 1;
	}
	if ( x<made_quad-1 && (walls[x][y]/2)%2 == 0 && dist[x+1][y  ] > temp + 2 )
	{
		printf("[Recalc 1]");
		reduce(x,y);
		flag = 1;
	}
	if ( y<made_quad-1 && (walls[x][y]/4)%2 == 0 && dist[x  ][y+1] > temp + 2 )
	{
		printf("[Recalc 2]");
		reduce(x,y);
		flag = 1;
	}
	if ( x>0  && (walls[x][y]/8)%2 == 0 && dist[x-1][y  ] > temp + 2 )
	{
		printf("[Recalc 3]");
		reduce(x,y);
		flag = 1;
	}

	if ( flag && g < (made_quad)*(made_quad) )
		g = dist[end_x][end_y];

	return g;
}
void addst(int d)
{
	backstack[stack_depth] = d;
	stack_depth++;
}
int delst()
{
	int temp;

		stack_depth--;

		temp = backstack[stack_depth];

		backstack[stack_depth] = -1;
		return temp;
}
void reduce(int x, int y)
{
	int b_stack = stack_depth;
	int d;
	do
	{
		if ( y>0  && (walls[x][y]/1)%2 == 0 && dist[x  ][y-1] > dist[x][y] + 1 )
		{
			y--;
			setdn(x,y,(made_quad)*(made_quad));
			addst(D);
		}
		else if ( x<made_quad-1 && (walls[x][y]/2)%2 == 0 && dist[x+1][y  ] > dist[x][y] + 1 )
		{
			x++;
			setdn(x,y,(made_quad)*(made_quad));
			addst(L);
		}
		else if ( y<made_quad-1 && (walls[x][y]/4)%2 == 0 && dist[x  ][y+1] > dist[x][y] + 1 )
		{
			y++;
			setdn(x,y,(made_quad)*(made_quad));
			addst(U);
		}
		else if ( x>0  && (walls[x][y]/8)%2 == 0 && dist[x-1][y  ] > dist[x][y] + 1 )
		{
			x--;
			setdn(x,y,(made_quad)*(made_quad));
			addst(R);
		}
		else
		{
			d = delst();
			if ( d == U )
				y--;
			else if (d == R )
				x++;
			else if (d == D )
				y++;
			else //if (d == L )
				x--;
			
		}
	} while ( stack_depth > b_stack );
}
int abs_dist(int x, int y)
{
	int ax,ay,bx,by;

	ax = x - start_x;
	ay = y - start_y;

	bx = x - end_x;
	by = y - end_y;

	if ( ax < 0 )
		ax = -ax;

	if ( ay < 0 )
		ay = -ay;

	if ( bx < 0 )
		bx = -bx;

	if ( by < 0 )
		by = -by;

	return ax+ay+bx+by;
}