///////////////////////////////////////////////////////////
// PathFinder.cpp
//
// Abin (abinn32@yahoo.com)
///////////////////////////////////////////////////////////

#include "PathFinder.h"
#include "D2HackIt.h"
#include "d2functions.h"
#include "Server20.h"
#include "Constants.h"

#define TP_RANGE		35		// Miximum teleport range
#define RANGE_INVALID	10000  // invalid range flag
#define DIM				1000 // maximum graph dimension(worst case only)

/////////////////////////////////////////////////////////////////////
// Path Finding Result
/////////////////////////////////////////////////////////////////////
enum {   PATH_FAIL = 0,     // Failed, error occurred or no available path
		 PATH_CONTINUE,	    // Path OK, destination not reached yet
		 PATH_REACHED };    // Path OK, destination reached(Path finding completed successfully)


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CPathFinder::CPathFinder()
{
	// Allocates memory
	m_graph = new short*[DIM];

	if (!m_graph)
		return;
	
	for (int i = 0; i < DIM; i++)
		m_graph[i] = new short[DIM];

	Reset();
}

CPathFinder::~CPathFinder()
{
	// Free heap
	if (m_graph)
	{
		for (int i = 0; i < DIM; i++)
		{
			if (m_graph[i])
				delete [] m_graph[i];
		}
		delete [] m_graph;
	}
}

void CPathFinder::Reset()
{
	if (VerifyMemory())
	{
		for (int i = 0; i < DIM; i++)
		{
			for (int j = 0; j < DIM; j++)
				m_graph[i][j] = 0;
		}
	}

	memset(&m_ptLevelLeftTop, 0, sizeof(POINT));
	memset(&m_ptAbsDest, 0, sizeof(POINT));
	memset(&m_ptRelDest, 0, sizeof(POINT));	
	memset(&m_rightBottom, 0, sizeof(POINT));
	m_lefttTop.x = DIM;
	m_lefttTop.y = DIM;
	m_aSearched.RemoveAll();
}

void CPathFinder::Search(RoomOther *ro, POINT ptPlayer)
{
	if (!ro)
		return;

	if(ro->ptDrlgLevel->LevelNo != GetCurrentMapID())
		return;

	if (m_aSearched.Find(ro) != -1)
		return;

	UnitPlayer* pPlayer = D2CLIENT_GetPlayerUnit();
	if (pPlayer == NULL)
		return;

	BOOL add_room=FALSE;
	if(!ro->pRoom)
	{
		add_room=TRUE;
		D2COMMON_AddRoomData(pPlayer->ptAct, GetCurrentMapID(), ro->xPos, ro->yPos, pPlayer);
	}

	m_aSearched.Add(ro);
	m_aSearched.Sort();	

	if (ro->pRoom)
		AddCollisionData((LPVOID)ro->pRoom->pColl, ptPlayer);
	//DumpCollisionMap((LPVOID)ro->pRoom->pColl);		
	
	
	RoomOther **n = ro->ptList;
	for(int i=0;i<ro->nRoomList;i++)
	{
		Search(n[i], ptPlayer);
	}
	
	if(add_room)
	{
		D2COMMON_RemoveRoomData(pPlayer->ptAct, GetCurrentMapID(), ro->xPos, ro->yPos, pPlayer);
	}
}

BOOL CPathFinder::Search()
{	
	UnitAny *pPlayer = D2CLIENT_GetPlayerUnit();
	if(!pPlayer)
		return FALSE;
	
	Room *pRoom1 = D2COMMON_GetRoomFromUnit(pPlayer);
	if(!pRoom1)
		return FALSE;	

	RoomOther *pRoom2 = pRoom1->ptRoomOther;
	if(!pRoom2) 
		return FALSE;

	DrlgLevel *pLevel = pRoom2->ptDrlgLevel;
	if(!pLevel)
		return FALSE;

	Reset();

	m_ptLevelLeftTop.x = pLevel->LevelX;
	m_ptLevelLeftTop.y = pLevel->LevelY;
	
	POINT ptPlayer = MapPos2Point(GetPosition());
	MapToGraph(ptPlayer);

	Search(pRoom2, ptPlayer);	
	return TRUE;
}

void CPathFinder::DumpMap1(LPCPATH lpPath) const
{	
	FILE *fp = fopen( "c:\\map1.txt", "w+" );
	if(fp == NULL )
		return;

	fprintf(fp, "LeftTop %d, %d      RightBottom %d, %d\n-----------------------------------\n",
		m_lefttTop.x, m_lefttTop.y, m_rightBottom.x, m_rightBottom.y);


	MAPPOS mp = GetPosition();
	mp.x -= m_ptLevelLeftTop.x * 5;
	mp.y -= m_ptLevelLeftTop.y * 5;

	POINT pt1 = m_lefttTop;
	POINT pt2 = m_rightBottom;

	// make the picture border
	if (pt1.x)
		pt1.x--;
	if (pt1.y)
		pt1.y--;

	if (pt2.x < DIM - 1)
		pt2.x++;
	if (pt2.y < DIM - 1)
		pt2.y++;
	
	for (int y = pt1.y; y < pt2.y; y++)
	{			
		for (int x = pt1.x; x < pt2.x; x++)
		{
			BOOL bOccupied = FALSE;
			if (m_ptRelDest.x == x && m_ptRelDest.y == y)
			{
				fprintf(fp, "%C", 'E'); // E - destination
				bOccupied = TRUE;
			}
			else if (mp.x == x && mp.y == y)
			{
				fprintf(fp, "%C", 'P'); // P - player
				bOccupied = TRUE;
			}
			else if (lpPath && lpPath->iNodeCount)
			{
				for (BYTE i = 0; i < lpPath->iNodeCount; i++)
				{
					POINT pos;
					pos.x = lpPath->aPathNodes[i].x;
					pos.y = lpPath->aPathNodes[i].y;
					MapToGraph(pos);
					if (pos.x == x && pos.y == y)
					{
						fprintf(fp, "%C", '*'); // * - path nodes
						bOccupied = TRUE;
						break;
					}
				}
			}

			if (!bOccupied)
			{
				fprintf(fp, "%C", m_graph[x][y] ? ' ' : 'X'); // X - unreachable
			}
		}

		fprintf(fp, "%c", '\n');
	}	
	
	fclose(fp);
}

void CPathFinder::MakeMap2()
{
	// convert the graph into a distance table
	for (int j = m_lefttTop.y; j < m_rightBottom.y; j++)	
	{
		for (int i = m_lefttTop.x; i < m_rightBottom.x; i++)
		{
			if (m_graph[i][j])
				m_graph[i][j] = GetDistance(i, j, m_ptRelDest.x, m_ptRelDest.y);
			else
				m_graph[i][j] = RANGE_INVALID;
		}
	}

	//AdjustWalls();
	
	if (IsValidPos(m_ptRelDest))
	{
		//m_graph[m_ptRelDest.x][m_ptRelDest.y] = 1;
		m_graph[m_ptRelDest.x][m_ptRelDest.y] = 1;
	}	
/*
	// original Niren7's code, not working properly
	BOOL over=FALSE;
	int cur=1;
	while(!over)
	{
		over=TRUE;
		int i,j;
		for(i=0;i<DIM;i++)
		for(j=0;j<DIM;j++)
		{
			if(map[i][j] && m_disTable[i][j]==cur)
			{
				int x,y;
				for(x=i-1;x<=i+1;x++)
				for(y=j-1;y<=j+1;y++)
				{
					if(x<0||y<0||x>=DIM||y>=DIM) continue;
					if(!map[x][y]) continue;
					if(m_disTable[x][y]>0) continue;
					m_disTable[x][y]=cur+1;
				}
				over=FALSE;
			}
		}
		cur++;
	}
	
	for(i=0;i<DIM;i++)
	for(j=0;j<DIM;j++)
	{
		if(m_graph[i][j]==1)
		{
			int x,y;
			int d=5;
			for(x=i-5;x<=i+5;x++)
			for(y=j-5;y<=j+5;y++)
			{
				if(x<0||y<0||x>=DIM||y>=DIM) continue;
				if(m_graph[x][y]==0)
				{
					int d1=abs(x-i)+abs(y-j);
					if(d1<d)d=d1;
				}
			}
			m_disTable[i][j]+=5-d;
		}
	}
	//*/
}


/////////////////////////////////////////////////////////////////////
// The "Get Best Move" Algorithm
//
// Originally developed by Niren7, Modified by Abin
/////////////////////////////////////////////////////////////////////
BOOL CPathFinder::GetBestMove(POINT& pos, int nAdjust)
{	
	if(Distance(m_ptAbsDest,pos) <= TP_RANGE)
	{
		pos = m_ptAbsDest;
		return PATH_REACHED; // we reached the destination
	}

	MapToGraph(pos);
	if (!IsValidPos(pos))
		return PATH_FAIL; // fail

	Block(pos, nAdjust);

	POINT p, best;
	int value = RANGE_INVALID;

	for (p.x = pos.x - TP_RANGE; p.x <= pos.x + TP_RANGE; p.x++)
	{
		for (p.y = pos.y - TP_RANGE; p.y <= pos.y + TP_RANGE; p.y++)
		{			
			if (!IsValidPos(p))
				continue;
			
			if (m_graph[p.x][p.y] < value && Distance(p, pos) <= TP_RANGE)
			{
				value = m_graph[p.x][p.y];
				best = p;					
			}			
		}
	}

	if (value >= RANGE_INVALID)
		return PATH_FAIL; // no path at all	
	
	pos = best;
	Block(pos, nAdjust);	
	GraphToMap(pos);
	return PATH_CONTINUE; // ok but not reached yet
}

int CPathFinder::Distance(const POINT &p1, const POINT &p2)
{
	return GetDistance(p1.x, p1.y, p2.x, p2.y);
}

BYTE CPathFinder::CalculatePathTo(WORD x, WORD y, LPPATH lpBuffer, int nAdjust)
{
	if (lpBuffer == NULL || x == 0 || y == 0 || !VerifyMemory())
		return 0;

	memset(lpBuffer, 0, sizeof(PATH));
	lpBuffer->posStart = GetPosition();
	if (lpBuffer->posStart.x == 0 || lpBuffer->posStart.y == 0)
		return 0;
	
	if (!Search())
		return 0;

	GameInfof("Mapsize %d, %d", m_rightBottom.x - m_lefttTop.x, m_rightBottom.y - m_lefttTop.y);

	m_ptAbsDest.x = x;
	m_ptAbsDest.y = y;

	m_ptRelDest = m_ptAbsDest;
	MapToGraph(m_ptRelDest);

	GameInfof("des %d, %d", m_ptRelDest.x, m_ptRelDest.y);

	// verify destination, see if it's in our map
	if (!IsValidPos(m_ptRelDest))
		return 0;

	MakeMap2();	
	//DumpMap2();

	POINT pos;
	pos.x = (short)lpBuffer->posStart.x;
	pos.y = (short)lpBuffer->posStart.y;

	lpBuffer->iNodeCount = 0;

	BOOL bOK = FALSE;
	int nRes = GetBestMove(pos, nAdjust);
	while (nRes != PATH_FAIL && lpBuffer->iNodeCount < 255)
	{
		// Reached?
		if (nRes == PATH_REACHED)
		{
			bOK = TRUE;
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].x = x;
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].y = y;
			lpBuffer->iNodeCount++;
			break; // Finished
		}

		// Perform a redundancy check
		int nRedundancy = GetRedundancy(lpBuffer, pos);
		if (nRedundancy == -1)
		{
			// no redundancy
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].x = (WORD)pos.x;
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].y = (WORD)pos.y;
			lpBuffer->iNodeCount++;
		}
		else
		{
			// redundancy found, discard all redundant steps
			lpBuffer->iNodeCount = nRedundancy + 1;
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].x = (WORD)pos.x;
			lpBuffer->aPathNodes[lpBuffer->iNodeCount].y = (WORD)pos.y;
		}	

		nRes = GetBestMove(pos, nAdjust);
	}	

	if (!bOK)
	{
		lpBuffer->iNodeCount = 0;
	}
	else
	{
		lpBuffer->posEnd.x = x;
		lpBuffer->posEnd.y = y;
	}
	
	//DumpMap1(lpBuffer);	// debug pictures
	return lpBuffer->iNodeCount;	
}

void CPathFinder::DumpCollisionMap(LPVOID lpCol) const
{
	DrlgColl* pCol = (DrlgColl*)lpCol;
	if (pCol == NULL)
		return;

	char szFile[MAX_PATH + 1] = "";
	sprintf(szFile, "c:\\col\\%03d%03d.txt", pCol->nPosGameX - m_ptLevelLeftTop.x * 5, pCol->nPosGameY - m_ptLevelLeftTop.y * 5);
	if (::GetFileAttributes(szFile) != -1)
		return;

	FILE* fp = fopen(szFile, "w");
	if (!fp)
	{
		GameErrorf("Fail %s", szFile);
		return;
	}

	int cx = pCol->nSizeGameX;
	int cy = pCol->nSizeGameY;
	fprintf(fp, "XY %d, %d, Size %d, %d\n\n", pCol->nPosGameX - m_ptLevelLeftTop.x * 5,
		pCol->nPosGameY - m_ptLevelLeftTop.y * 5, cx, cy);

	WORD* currentloc = pCol->pMapStart;

	int i,j;
		
	for(i=0; i < cx; i++)		
	{
		char sz[256] = "";
		for(j=0; j < cy; j++)
		{
			sprintf(sz, "%s%C", sz, *currentloc ? 'X' : ' ');
			currentloc++;
		}

		fprintf(fp, "%s\n", sz);
	}
	fclose(fp);
}


void CPathFinder::AddCollisionData(LPVOID lpCol, POINT ptPlayer)
{
	DrlgColl* pCol = (DrlgColl*)lpCol;
	if (pCol == NULL)
		return;

	int x = pCol->nPosGameX - m_ptLevelLeftTop.x * 5;
	int y = pCol->nPosGameY - m_ptLevelLeftTop.y * 5;
	int cx = pCol->nSizeGameX;
	int cy = pCol->nSizeGameY;

	if (x < 0 || x + cx > DIM || y < 0 || y + cy > DIM)
	{
		//GamePrintError("invalid col");
		return;
	}	
	
	WORD* currentloc = pCol->pMapStart;
	int nLimitX = x + cx;
	int nLimitY = y + cy;
	
	for (int j = y; j < nLimitY; j++)		
	{
		for (int i = x; i < nLimitX; i++)
		{
			if ((*currentloc % 2) == 0)
			{
				m_graph[i][j] = 1;

				// record reach-able area edges
				if (m_lefttTop.x > i)
					m_lefttTop.x = i;
				if (m_lefttTop.y > j)
					m_lefttTop.y = j;

				if (m_rightBottom.x < i + 1)
					m_rightBottom.x = i + 1;
				if (m_rightBottom.y < j + 1)
					m_rightBottom.y = j + 1;
			}
			
			currentloc++;
		}
	}
}

BOOL CPathFinder::IsValidPos(POINT pos) const
{
	return pos.x >= m_lefttTop.x && pos.x >= 0
		&& pos.y >= m_lefttTop.y && pos.y >= 0
		&& pos.x < m_rightBottom.x && pos.x < DIM
		&& pos.y < m_rightBottom.y && pos.y < DIM;
}

void CPathFinder::MapToGraph(POINT &pos) const
{
	pos.x -= m_ptLevelLeftTop.x * 5;
	pos.y -= m_ptLevelLeftTop.y * 5;
}

void CPathFinder::GraphToMap(POINT &pos) const
{
	pos.x += m_ptLevelLeftTop.x * 5;
	pos.y += m_ptLevelLeftTop.y * 5;
}

BOOL CPathFinder::VerifyMemory() const
{
	if (m_graph == NULL)
		return FALSE;

	for (int i = 0; i < DIM; i++)
	{
		if (m_graph[i] == NULL)
			return FALSE;
	}
	return TRUE;
}

POINT CPathFinder::MapPos2Point(MAPPOS pos)
{
	POINT pt;
	pt.x = (long)pos.x;
	pt.y = (long)pos.y;
	return pt;
}

void CPathFinder::DumpMap2() const
{
	FILE *fp = fopen( "c:\\map2.txt", "w+" );
	if(fp == NULL )
		return;

	for (int y = m_lefttTop.y; y < m_rightBottom.y; y++)
	{			
		for (int x = m_lefttTop.x; x < m_rightBottom.x; x++)
		{
			if (!m_graph[x][y])
			{
				fprintf(fp, "%s ", "  ");
			}
			else
			{
				if (m_graph[x][y] < 256)
					fprintf(fp, "%02x ", m_graph[x][y]);
				else
					fprintf(fp, "%s ", "??");
			}
		}

		fprintf(fp, "%c", '\n');
	}

	fclose(fp);
}

void CPathFinder::Block(POINT pos, int nRange)
{
	for (int i = pos.x - nRange; i < pos.x + nRange; i++)
	{
		for (int j = pos.y - nRange; j < pos.y + nRange; j++)
		{
			if (i >= 0 && i < DIM && j >= 0 && j < DIM)
				m_graph[i][j] = RANGE_INVALID;
		}
	}
}

int CPathFinder::GetRedundancy(LPPATH lpPath, const POINT &pos)
{
	// step redundancy check
	if (lpPath == NULL || lpPath->iNodeCount == 0)
		return -1;

	for (BYTE i = 0; i < lpPath->iNodeCount; i++)
	{
		if (GetDistance(lpPath->aPathNodes[i].x, lpPath->aPathNodes[i].y, pos.x, pos.y) <= TP_RANGE / 2)
			return i;
	}

	return -1;
}