#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>
#include <stdio.h>

struct maze_info
{
	unsigned char value,top_wall,left_wall,visited;
} maze[16][16],load_maze[16][16];

unsigned char current_cell,top_cell,bottom_cell,right_cell,left_cell;

unsigned char x_current=0,y_current=0,dir_current=2,x_final=7,y_final=7,
	dir_final,x_initial=0,y_initial=0,dir_initial=0;
unsigned char i,j,k,tiny=255;
char str[3];

void display();
void initial_settings();
void floodfill();
void one_step();
void sensor();

//*------------------------------------------------------------------------
void display()
{
	int m,n;

	setcolor (BLACK);
	setfillstyle (0,0);
	setlinestyle(0,3,3);
	bar (10,30,300,350);

	settextstyle(2,0,2);

	for (m=0;m<=15;++m)
	{
		for (n=0;n<=15;++n)
		{
			if (maze[m][n].top_wall==0)
			{
				setlinestyle(0,0,1);
				setcolor (DARKGRAY);
			}
			else
			{
				setlinestyle(0,0,3);
				setcolor (RED);
			}
			line (10+m*18,40+n*18,28+m*18,40+n*18);

			if (maze[m][n].left_wall==0)
			{
				setlinestyle(0,0,1);
				setcolor (DARKGRAY);
			}
			else
			{
				setlinestyle(0,0,3);
				setcolor (RED);
			}
			line (10+m*18,40+n*18,10+m*18,58+n*18);

			if (maze[m][n].visited==1)
			{
				setcolor (DARKGRAY);
				setlinestyle (0,3,3);
				rectangle (330+m*18,45+n*18,338+m*18,53+n*18);
				rectangle (332+m*18,47+n*18,336+m*18,51+n*18);
			}

		}

	}
	setlinestyle(0,0,3);
	setcolor (RED);
	line (10+0*18,40+16*18,10+16*18,58+15*18);
	line (10+16*18,40+0*18,10+16*18,58+15*18);

//-------------------------------------------------------------+

setlinestyle(0,0,3);
setcolor (RED);
for (m=0;m<=15;++m)
{
	for (n=0;n<=15;++n)
	{
		if (load_maze[m][n].top_wall==1)
		line (325+m*18,40+n*18,343+m*18,40+n*18);

		if (load_maze[m][n].left_wall==1)
		line (325+m*18,40+n*18,325+m*18,58+n*18);
	}

}
line (325+0*18,40+16*18,325+16*18,58+15*18);
line (325+16*18,40+0*18,325+16*18,58+15*18);

//------------------------------------------------------------+

	setlinestyle(0,0,1);
	for (m=0;m<=15;m++)
	{
		for (n=0;n<=15;n++)
		{
		       itoa(maze[m][n].value,str,10);
		       if((n==y_current) && (m==x_current))
		       {
				setcolor (WHITE);
				circle(19+18*x_current,49+18*y_current,4);
				setlinestyle(0,0,2);
				switch (dir_current)
				{
					case 1:
						circle (19+18*x_current,45+18*y_current,2);
						line (19+18*x_current,52+18*y_current,19+18*x_current,57+18*y_current);
						break;
					case 2:
						circle (23+18*x_current,49+18*y_current,2);
						line (11+18*x_current,49+18*y_current,15+18*x_current,49+18*y_current);
						break;
					case 3:
						circle (19+18*x_current,53+18*y_current,2);
						line (19+18*x_current,40+18*y_current,19+18*x_current,45+18*y_current);
						break;
					case 4:
						circle (15+18*x_current,49+18*y_current,2);
						line (24+18*x_current,49+18*y_current,29+18*x_current,49+18*y_current);
						break;
				}
				setlinestyle(0,0,1);
		       }
		       else
		       {
				setcolor (GREEN);
				outtextxy (13+m*18,45+n*18,str);
		       }
		}
	}
}

//------------------------------------------------------------------------

void initial_settings()
{
	for (i=0;i<=15;i++)
	{
		for (j=0;j<=15;j++)
		{
			maze[i][j].left_wall=0;
			maze[i][j].top_wall=0;
			maze[i][j].value=0;
			maze[i][j].visited=0;
		}
	}
	for (i=0;i<=15;i++)
	{
		maze[0][i].left_wall=1;
		maze[i][0].top_wall=1;
	}
	maze[0][1].top_wall=1;
	current_cell=1;

}

//------------------------------------------------------------------------

void floodfill()
{
	unsigned char quit=245;

	for (i=0;i<16;i++)
	{
		for (j=0;j<16;j++) maze[i][j].value=255;
	}

	if (x_final==7)
	{
		maze[7][7].value=0;
		maze[7][8].value=0;
		maze[8][7].value=0;
		maze[8][8].value=0;
	}
	else
	{
		maze[0][0].value=0;
	}

	k=0;
	while (quit>0)
	{
		quit=quit-1;
		for (i=0;i<16;i++)
		{
			for (j=0;j<16;j++)
			{
				if (maze[i][j].value==k)
{
//	if (i==x_current &&  j==y_current) quit=2;

	current_cell=maze[i][j].value;
	left_cell=maze[i-1][j].value;
	right_cell=maze[i+1][j].value;
	top_cell=maze[i][j-1].value;
	bottom_cell=maze[i][j+1].value;

	tiny=255;
	if (maze[i-1][j].value<tiny && i>0 && maze[i][j].left_wall==0) tiny=maze[i-1][j].value;
	if (maze[i+1][j].value<tiny && i<15 && maze[i+1][j].left_wall==0) tiny=maze[i+1][j].value;
	if (maze[i][j-1].value<tiny && j>0 && maze[i][j].top_wall==0) tiny=maze[i][j-1].value;
	if (maze[i][j+1].value<tiny && j<15 && maze[i][j+1].top_wall==0) tiny=maze[i][j+1].value;

	if (left_cell>maze[i][j].value+2 && i>0 && maze[i][j].left_wall==0) maze[i-1][j].value=maze[i][j].value+2;
	if (left_cell>maze[i][j].value+1 && i>0 && maze[i][j].left_wall==0 && (right_cell==tiny && i<15 && maze[i+1][j].left_wall==0)) maze[i-1][j].value=maze[i][j].value+1;

	if (right_cell>maze[i][j].value+2 && i<15 && maze[i+1][j].left_wall==0) maze[i+1][j].value=maze[i][j].value+2;
	if (right_cell>maze[i][j].value+1 && i<15 && maze[i+1][j].left_wall==0 && (left_cell==tiny && i>0 && maze[i][j].left_wall==0)) maze[i+1][j].value=maze[i][j].value+1;

	if (top_cell>maze[i][j].value+2 && j>0 && maze[i][j].top_wall==0) maze[i][j-1].value=maze[i][j].value+2;
	if (top_cell>maze[i][j].value+1 && j>0 && maze[i][j].top_wall==0 && (bottom_cell==tiny && j<15 && maze[i][j+1].top_wall==0)) maze[i][j-1].value=maze[i][j].value+1;

	if (bottom_cell>maze[i][j].value+2 && j<15 && maze[i][j+1].top_wall==0) maze[i][j+1].value=maze[i][j].value+2;
	if (bottom_cell>maze[i][j].value+1 && j<15 && maze[i][j+1].top_wall==0 && (top_cell==tiny && j>0 && maze[i][j].top_wall==0)) maze[i][j+1].value=maze[i][j].value+1;
}
			}
		}
	k=k+1;
	}
}

//------------------------------------------------------------------------

void one_step()
{
	x_initial=x_current;
	y_initial=y_current;
	tiny=255;

	if (maze[x_current-1][y_current].value<tiny && x_current>0 && maze[x_current][y_current].left_wall==0) tiny=maze[x_current-1][y_current].value;
	if (maze[x_current+1][y_current].value<tiny && x_current<15 && maze[x_current+1][y_current].left_wall==0) tiny=maze[x_current+1][y_current].value;
	if (maze[x_current][y_current-1].value<tiny && y_current>0 && maze[x_current][y_current].top_wall==0) tiny=maze[x_current][y_current-1].value;
	if (maze[x_current][y_current+1].value<tiny && y_current<15 && maze[x_current][y_current+1].top_wall==0) tiny=maze[x_current][y_current+1].value;

	switch (dir_current)
	{
		case 4:
			if (maze[x_current-1][y_current].value==tiny && x_current>0 && maze[x_current][y_current].left_wall==0)	x_current=x_current-1;
			else if (maze[x_current][y_current+1].value==tiny && y_current<15 && maze[x_current][y_current+1].top_wall==0)
			{
				y_current=y_current+1;
				dir_current=3;
			}
			else if (maze[x_current][y_current-1].value==tiny && y_current>0 && maze[x_current][y_current].top_wall==0)
			{
				y_current=y_current-1;
				dir_current=1;
			}
			else
			{
				x_current=x_current+1;
				dir_current=2;
			}
			break;
		case 2:
			if (maze[x_current+1][y_current].value==tiny && x_current<15 && maze[x_current+1][y_current].left_wall==0) x_current=x_current+1;
			else if (maze[x_current][y_current+1].value==tiny && y_current<15 && maze[x_current][y_current+1].top_wall==0)
			{
				y_current=y_current+1;
				dir_current=3;
			}
			else if (maze[x_current][y_current-1].value==tiny && y_current>0 && maze[x_current][y_current].top_wall==0)
			{
				y_current=y_current-1;
				dir_current=1;
			}
			else
			{
				x_current=x_current-1;
				dir_current=4;
			}
			break;
		case 1:
			if (maze[x_current][y_current-1].value==tiny && y_current>0 && maze[x_current][y_current].top_wall==0) y_current=y_current-1;
			else if (maze[x_current+1][y_current].value==tiny && x_current<15 && maze[x_current+1][y_current].left_wall==0)
			{
				x_current=x_current+1;
				dir_current=2;
			}
			else if (maze[x_current-1][y_current].value==tiny && x_current>0 && maze[x_current][y_current].left_wall==0)
			{
				x_current=x_current-1;
				dir_current=4;
			}
			else
			{
				y_current=y_current+1;
				dir_current=3;
			}
			break;
		case 3:
			if (maze[x_current][y_current+1].value==tiny && y_current<15 && maze[x_current][y_current+1].top_wall==0) y_current=y_current+1;
			else if (maze[x_current+1][y_current].value==tiny && x_current<15 && maze[x_current+1][y_current].left_wall==0)
			{
				x_current=x_current+1;
				dir_current=2;
			}
			else if (maze[x_current-1][y_current].value==tiny && x_current>0 && maze[x_current][y_current].left_wall==0)
			{
				x_current=x_current-1;
				dir_current=4;
			}
			else
			{
				y_current=y_current-1;
				dir_current=1;
			}
			break;
	}

	maze[x_initial][y_initial].visited=1;
}

//------------------------------------------------------------------------

void sensor()
{
	maze[x_current][y_current].left_wall=load_maze[x_current][y_current].left_wall;
	if (x_current<15) maze[x_current+1][y_current].left_wall=load_maze[x_current+1][y_current].left_wall;
	maze[x_current][y_current].top_wall=load_maze[x_current][y_current].top_wall;
	if (y_current<15) maze[x_current][y_current+1].top_wall=load_maze[x_current][y_current+1].top_wall;
}

//------------------------------------------------------------------------

void main()
{
unsigned char top_wall[16][16]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
				1,1,1,1,0,0,1,1,0,0,1,1,1,1,1,0,
				0,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0,
				0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,0,
				0,1,0,1,1,0,0,0,0,1,0,1,0,1,0,0,
				1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
				0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,
				0,0,0,0,0,0,0,1,1,1,1,0,0,0,1,0,
				0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,
				0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,
				0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,
				0,1,1,1,0,1,0,0,1,0,0,0,0,0,0,0,
				0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
				0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
				0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
				0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0},
// top_wall             1=wall present   , 0=wall missing
//      - - - - - - - - - - - - - - - -
//      - - - -     - -     - - - - -
//        - - - - - -     -   -
//          - - - -   etc...


	left_wall[16][16]={	1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,
				1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,
				1,1,0,0,0,0,0,1,1,1,0,0,1,0,1,0,
				1,1,0,0,0,0,1,1,1,1,1,0,1,0,0,0,
				1,0,1,1,0,1,1,1,1,1,0,1,0,0,1,1,
				1,0,1,1,1,1,1,0,1,0,1,1,1,0,0,1,
				1,1,1,1,1,1,0,1,0,0,1,0,0,1,0,0,
				1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,
				1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,
				1,1,0,1,1,1,1,0,0,0,1,1,1,0,1,1,
				1,0,0,0,1,0,1,0,0,0,1,1,1,1,1,1,
				1,0,1,0,1,1,0,1,1,0,1,1,1,1,1,1,
				1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,
				1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,
				1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,
				1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
// left_wall
//     l        l      l
//     l            l        l   l
//     l l        l l l    l   l
//     l l .. etc...


	clrscr();
	int gd=DETECT,gm,speed;
	initgraph (&gd,&gm,"c:\\tc\\bgi");

	char ans='y';
	long int delay;
	unsigned int step=0;

	gotoxy(21,2);
	cout<<"-------- MICROMOUSE SIMULATION ---------";
	gotoxy(1,22);
	cout<<"Simulation Speed : <1-9> ";
	cin>>speed;
	speed = 10 - speed;

		for(i=0;i<16;i++)
		{
			for(j=0;j<16;j++)
			{
				load_maze[j][i].top_wall=top_wall[i][j];
			}
		}
		for(i=0;i<16;i++)
		{
			for(j=0;j<16;j++)
			{
				load_maze[j][i].left_wall=left_wall[i][j];
			}
		}

	initial_settings();

	while (ans=='y' || ans=='Y')
	{
		floodfill();
		display();
		step=0;

		while (maze[x_current][y_current].value>0)
		{
			sensor();
			if (maze[x_current][y_current].visited==0) floodfill();
			display();
			for(delay=1;delay<speed*speed*speed*50000;delay++);

			one_step();
			step++;

			display();
			for(delay=1;delay<speed*speed*speed*1000;delay++);
		}

		if (x_final==7 ) x_final=0;
		else x_final=7;

		gotoxy(1,24);
		cout<<"Number of steps : "<<step<<"                "<<endl<<"Continue... ?? <y/n> : ";
		ans=getch();
		gotoxy(1,24);
		cout<<"Number of steps : ----"<<step<<"-----"<<endl<<"--------------------------------- ";
	}
}