#include <solver.h>
#include <stdbran.h>


Node *CurrentBaseNode;		/* base from which path is calculated */
Path *PathFromBase;		/* path from base node */
int X;
int Y;				/* Current co-ords */

int SearchX;
int SearchY; 			/* Coordinates to aim for */

Maze *TheMaze;			/* Store for all maze info */
int FactorToFinish;		/* Current Inconvenience Factor to Finish */
Node *FinishNode;		/* Finish node or NULL if not found */
int MazeCompleted; 
Exits CurExits;





void Solver_Go() {
	X=0;
	Y=0;
	Maze_MAKE(&TheMaze);
	Maze_SetFirstNode(TheMaze,0,0,EXIT_N);

	CurrentBaseNode=Maze_NodePtr(TheMaze,0,0);
	FinishNode=NULL;
	FactorToFinish=IF_VERY_FAR;
	MazeCompleted=0;
	Maze_BeenAt(TheMaze,0,0,EXIT_N);
	SearchX=7;
	SearchY=7;


	while (!MazeCompleted) {
		int OldFactor;
		Path *P;
		OldFactor=FactorToFinish;
		while (((OldFactor-FactorToFinish)<=(FactorToFinish >> 5))&&
				!MazeCompleted)
			Solver_Explore();
		P=Maze_BestPathBetween(TheMaze,CurrentBaseNode,Maze_NodePtr(TheMaze,0,0));
		Solver_MovePath(P);
		Path_KILL(&P);
		/* cout << "Making Run:" << endl; */
		P=Maze_BestPathBetween(TheMaze,Maze_NodePtr(TheMaze,0,0),FinishNode);
		Solver_MovePath(P);
		Path_KILL(&P);
		/* cout << "(Factor = " << FactorToFinish << " )" << endl; */
		CurrentBaseNode=FinishNode;
	}	


	Maze_KILL(&TheMaze);
}

Exits Solver_ExitDirs(){
	return CurExits;

}


void Solver_Move(Dir d) {
	Path *P;
	P=Path_PathOf(d);
	Solver_MovePath(P);
	Path_KILL(&P);
}



void Solver_MovePath(Path *P) {
	Path *P1;
	int i;

	CurExits=MC_Move(P);

	P1=Path_ADD(PathFromBase,P);
	Path_KILL(&PathFromBase);
	PathFromBase=P1;

	for (i=0;i<Path_NumberOfMoves(P);i++) {
		Move M;
		M=Path_MoveNo(P,i);
		X+=DX[DIRNUM(M)]*(M&MOVE_LENMASK);
		Y+=DY[DIRNUM(M)]*(M&MOVE_LENMASK);
	}

    Maze_BeenAt(TheMaze,X,Y,Solver_ExitDirs());
}

void DumpMaze(Maze *);


void Solver_Explore() {
    if (Debug)
        DumpMaze(TheMaze);
	Maze_LinkNeighbours(TheMaze);
	if (PathFromBase) {
		Path_KILL(&PathFromBase);
		Path_MAKE(&PathFromBase);
	}
	switch (Node_Status(CurrentBaseNode)) {
		case NODE_FINISH: {
            Maze_KillUseless(TheMaze,NULL);
			if (!FinishNode) {
				FinishNode=CurrentBaseNode;
				SearchX=4;
				SearchY=4;
			}
			else {
				Path *P;
				P=Solver_PathToNode(); 
                if (Path_NumberOfMoves(P))
					Solver_MovePath(P);
				else
					MazeCompleted=1;
				Path_KILL(&P);
			}
			break;
		}
		case NODE_TERMINAL: {
			Path *P;
			P=PathFromBase;
			PathFromBase=Path_REVCOPY(Node_ExploredPath(CurrentBaseNode));
			Path_KILL(&P);
			Maze_KillNodeAt(TheMaze,X,Y);
			P=Path_REVCOPY(PathFromBase);
			Solver_MovePath(P);
			Path_KILL(&P);
			break;
		}

		case NODE_DEAD: {
			Path *P1;
			Path *P2;
			Dir D;

			P1=PathFromBase;
			P2=Path_REVCOPY(Node_ExploredPath(CurrentBaseNode));
			PathFromBase=Path_ADD(P1,P2);
			Path_KILL(&P1);
			Path_KILL(&P2);
			D=Node_UnexploredDir(CurrentBaseNode);
			CurrentBaseNode=Node_AGoodLink(CurrentBaseNode);
			Maze_KillNodeAt(TheMaze,X,Y);
			Solver_Wander(D);
			break;
		}
		case NODE_COMPLETED: {
			Path *P;
			P=Solver_PathToNode();
            if (Path_NumberOfMoves(P))
				Solver_MovePath(P); /* move to chosen uncompleted node */
			else
				MazeCompleted=1;
			Path_KILL(&P);
			break;
		}
		case NODE_UNCOMPLETED: {
			int dx;
			int dy;
			Dir d1;
			Dir d2;
			/* perform maze simplification if possible */
			while (Maze_Simplify(TheMaze,FinishNode));
			/* find an unexplored direction + go that way */
			dx=(X<8 ? 8 : 7)-X;
			dy=(Y<8 ? 8 : 7)-Y;
			if ((dx<0 ? -dx : dx)>(dy<0 ? -dy : dy)) {
				d1=(dx<0 ? DIR_W : DIR_E);
				d2=(dy<0 ? DIR_S : DIR_N);
			}
			else {
				d1=(dy<0 ? DIR_S : DIR_N);
				d2=(dx<0 ? DIR_W : DIR_E);
			}
			if (!Node_IsUnexplored(CurrentBaseNode,d1))
				d1=d2;
			if (!Node_IsUnexplored(CurrentBaseNode,d1))
				d1=Node_UnexploredDir(CurrentBaseNode);
			Solver_Wander(d1);
		}
	}
	CurrentBaseNode=Maze_NodePtr(TheMaze,X,Y);
	if (FinishNode) {
		Path *P;
		P=Maze_BestPathBetween(TheMaze,Maze_NodePtr(TheMaze,0,0),FinishNode);
		FactorToFinish=Path_IncFactor(P);
		Path_KILL(&P);
	}
}

void Solver_Wander(Dir StartDir) {
	Dir D;
	Path *P;
    Exits E;

	Solver_Move(StartDir);
	/* continue until node or dead end */
    D=StartDir;
    while (Exits_NumExits(E=Solver_ExitDirs())==2) {
        Dir d1,d2;
        FOREACH_DIR(d1)
            if ( d1!=(D^DIR_REVERSE) && Exits_IsExitTo(E,d1) ) {
                d2=d1;
            }
        D=d2;
		Solver_Move(D);
	}
	
	P=Path_REVCOPY(PathFromBase);

	if (!Maze_IsNode(TheMaze,X,Y)) {
		/* unseen node */
        Maze_AddNode(TheMaze,X,Y,Solver_ExitDirs(),CurrentBaseNode,P);
	}
	else {
        Node_LinkTo(Maze_NodePtr(TheMaze,X,Y),CurrentBaseNode,P);
	}
	Path_KILL(&P);
}

Path *Solver_PathToNode() { /*
	Looks in a spiral path for the nearest uncompleted node
	to SearchX,SearchY */
	Path *P;
	Node *N;
	int x;
	int y;
	int dx;
	int dy;

    x=SearchX;
    y=SearchY;
	dx=0;
	dy=1;
	P=NULL;

	while ((dx<=16)&&!P) {
		if (x>=0&&x<=15&&y>=0&&y<=15) 
			N=Maze_NodePtr(TheMaze,x,y);
		x+=dx;
		y+=dy;
		if (!dx) {
			dx=dy;
			dy=0;
		} else {
			dy=(dx<0?1-dx:-1-dx);
			dx=0;
		}
	}
	if (N) 
		P=Maze_BestPathBetween(TheMaze,CurrentBaseNode,N);
	return P;
}