path.cpp

决战帝王1.5武神降临对喜爱决战的玩家共享研究用

#include "stdafx.h"
#include "path.h"

CPath::CPath()
{
	m_NodePool = NULL;			// 货肺款 畴靛甫 檬扁拳茄促.
	m_NodePool = new POS[MAX_NODE];
	InitNodePool();

	m_pStrLink = (POS *)calloc(1,sizeof(POS));
	m_pEndLink = (POS *)calloc(1,sizeof(POS));

	m_pStrLink->prev = NULL;
	m_pStrLink->next = m_pEndLink;
	m_pEndLink->prev = m_pStrLink;
	m_pEndLink->next = NULL;

	m_PathListNum = 0;
	m_bConer		= FALSE;
	m_Ghost			= FALSE;
	m_Object		= FALSE;	
	m_bRect.bottom	= 0;
	m_bRect.left	= 0;
	m_bRect.right	= 0;
	m_bRect.top		= 0;
	m_StackNum = 0;
	m_BlockTileX = 0;
	m_BlockTileY = 0;
	m_pTile = NULL;
	SettingConer();

	for(int a = 0; a < 150; a++)
	{ 
		m_PathList[a].x = 0; 
		m_PathList[a].y = 0;
	}
}

void CPath::SettingConer()
{
	int i, j;
	for(i = 0; i < 9; i++)
	{
		for(j = 0; j < 9; j++)  m_ConerAtt[i][j] = 0;
	}

	m_ConerAtt[1][4] = m_ConerAtt[1][7] = m_ConerAtt[1][8] = 1;
	m_ConerAtt[2][1] = m_ConerAtt[2][5] = m_ConerAtt[2][8] = 1;
	m_ConerAtt[3][2] = m_ConerAtt[3][5] = m_ConerAtt[3][6] = 1;
	m_ConerAtt[4][3] = m_ConerAtt[4][6] = m_ConerAtt[4][7] = 1;
	m_ConerAtt[5][1] = m_ConerAtt[5][4] = m_ConerAtt[5][8] = 1;
	m_ConerAtt[6][1] = m_ConerAtt[6][2] = m_ConerAtt[6][5] = 1;
	m_ConerAtt[7][2] = m_ConerAtt[7][3] = m_ConerAtt[7][6] = 1;
	m_ConerAtt[8][3] = m_ConerAtt[8][4] = m_ConerAtt[8][7] = 1;
}

CPath::~CPath()
{
	free(m_pStrLink);
	free(m_pEndLink);
	DeleteNodePool();			// 且寸茄 畴靛甫 昏力茄促.
}

void CPath::SetTile(MapInfo **ppMap, int x, int y)
{
	m_pTile = ppMap;
	m_nSizeX = x;
	m_nSizeY = y;
}

void CPath:: Setting()
{
	int i;
	for(i = 0; i < STACKNUM; i += 4)
	{
		m_Stack[i] = 0;
		m_Stack[i+1] = 0;
		m_Stack[i+2] = 0;
		m_Stack[i+3] = 0;
	}
	for(i = 0; i < 8; i += 2)
	{
		m_PathConer[i].x = 0;
		m_PathConer[i].y = 0;
		m_PathConer[i].dist = 0;
		m_PathConer[i+1].x = 0;
		m_PathConer[i+1].y = 0;
		m_PathConer[i+1].dist = 0;
	}
	m_BlockTileX = 0;
	m_BlockTileY = 0;
	m_PathListNum = 0;
}


int CPath::CheckDirection(int x, int y)
{
	if(y > 0)
	{
		if(x > 0)		{ return ES; }	// 4
		else if(x < 0)	{ return SW; }	// 6
		else			{ return OS; }	// 5
	}
	else if(y < 0)
	{
		if(x > 0)		{ return NE; }	// 2
		else if(x < 0)	{ return WN; }	// 8
		else			{ return ON; }	// 1
	}
	else
	{
		if(x > 0)		{ return OE; }	// 3
		else			{ return OW; }	// 7
	}
}


CPath::POS *CPath::InsertNode(POS *node, BOOL head)
{
	POS *temp = NULL;
	POS *old = NULL;

	temp = GetNodePool();
	if(temp == NULL) return NULL;

	old = node->next;
	old->prev = temp;
	node->next = temp;
	temp->prev = node;
	temp->next = old;

	return temp;
}

void CPath::DeleteNode(POS *now, POS *end)
{
	POS *Dnode;
	POS *temp = now->next;

	do
	{
		Dnode = temp;
		temp = temp->next;
		FreeNodePool(Dnode);	
		if(temp == end) break;		

	} while(1);

	now->next = end;
	end->prev = now;
}

//------------------------------------------------------------------------
//	Name :	FreeNode(POS *node, int num) 
//	Desc :	矫累登绰 畴靛客 秦寸 箭磊	
//	UpDate:	2000, 9, 17
//------------------------------------------------------------------------
void CPath::FreeNode(POS *node)
{
	InitNodePool();
	m_pStrLink->next = m_pEndLink;
	m_pEndLink->prev = m_pStrLink;
}

LIST_POINT* CPath::PathFinder(int starx, int stary, int destx, int desty)
{
//	bool exec = false;
//	bool search = true;-
	int sum = starx + stary;

	if(destx < 3 || desty < 3 || destx >= m_nSizeX-3 || desty >= m_nSizeY-3) return NULL;//search = false;

	if( starx == destx && stary == desty ) return NULL;//&& search) exec = true;

	int lMove = m_pTile[destx][desty].m_bMove;
	sum = destx + desty;
	if(m_Ghost) m_Object = FALSE;
	
	if(m_pTile[destx][desty].m_bMove != 0 && sum%2 != 0 ) return NULL;

	m_PathListNum = 0;
	m_pStrLink->x = starx;
	m_pStrLink->y = stary;
	m_pEndLink->x = destx;
	m_pEndLink->y = desty;
	m_pEndLink->prev = m_pStrLink;
	
	if( SearchBlock(m_pStrLink, m_pEndLink) )
	{
		Generate();
		FreeNode(m_pStrLink->next);
	}
	else
	{
		PutDistance();		
	}
	
	//return m_PathList;
	if (!m_PathListNum) return NULL;
	
	LIST_POINT*	pRoute = new LIST_POINT;
	//		TRACE("NewPath : ");
	
	CPoint ptPos;
	for (int i=0; i<m_PathListNum; i++) {
		ptPos.x = m_PathList[i].x;
		ptPos.y = m_PathList[i].y;
		
		//			TRACE("(%d,%d) ", ptPos.x, ptPos.y);
		pRoute->AddTail(ptPos);
	}
	//		TRACE("\n");
	
	return pRoute;
}


//------------------------------------------------------------------------
//	Name :	Generate() 
//	Desc :	函版 : 沤祸 裹困 力茄阑 滴瘤臼澜
//	UpDate:	2000, 12, 11
//------------------------------------------------------------------------
void CPath::Generate()
{
	int sx = m_pStrLink->x; 
	int sy = m_pStrLink->y; 
	int dx = m_pEndLink->x;
	int dy = m_pEndLink->y;
	
	POS *newNode=NULL, *Node = NULL;
	POS	*tempNode = NULL;

	Node = m_pStrLink;
	newNode = m_pEndLink;

	do
	{
		tempNode = NextNode(Node, newNode);
		if(tempNode == NULL) 
		{
			if( SearchBlock(Node, newNode) ) { Node = ChoiceNode(); break; }
			else
			{
				if(Node->prev == NULL) { Node = m_pEndLink; break; }
				Node = Node->prev;
				newNode = newNode->prev;
			}
		}
		else	Node = tempNode;
		
	} while(1);

	PathList(m_pStrLink, Node);
}

//------------------------------------------------------------------------
//	Name :	NextNode(POS *str, POS *end) 
//	Desc :	林绢柳 滴痢荤捞俊辑 2俺 葛辑府甫 魄窜窍绊, 皋葛府甫..
//	UpDate:	2000, 9, 18
//------------------------------------------------------------------------
CPath::POS *CPath::NextNode(POS *str, POS *end)
{
	int num = 0;
	POS *temp = NULL;

	Setting();
	if( SearchBlock(str, end) )
	{
		num = SearchTile(str);
		if(num)
		{
			temp = GenerateSuccessors(str, end, num);
			if(!m_bConer && temp == NULL)
			{
				SearchBlock(end, str);
				num = SearchTile(str);
				if(num)	temp = GenerateSuccessors(str, end, num);
			}
		}

	}

	return temp;
}


//------------------------------------------------------------------------
//	Name :	GenerateSuccessors()
//	Desc :	畴靛甫 眠啊茄促.
//	UpDate:	2000, 9, 18
//------------------------------------------------------------------------
CPath::POS *CPath::GenerateSuccessors(POS *str, POS *end, int num)
{
	int  lean = 0, test = 0;
	BOOL bNode = false;
	int	 type = 0, i;
	int  tempx = 0, tempy = 0;
	int  dirOne = 0, dirTwo = 0;
	POS  *temp = NULL;
	m_bConer = false;

	QSort(m_PathConer, num);

	for(i = 0; i < num; i++)
	{
		if(m_bConer) break;
		tempx = m_PathConer[i].x - str->x;
		tempy = m_PathConer[i].y - str->y;
		dirOne = CheckDirection(tempx, tempy);
		tempx = end->x - m_PathConer[i].x;
		tempy = end->y - m_PathConer[i].y;
		dirTwo = CheckDirection(tempx, tempy);

		if( (dirOne == 6 && dirTwo == 8) || (dirOne == 8 && dirTwo == 6) || (dirOne == 6 && dirTwo == 6) || (dirOne == 5 && dirTwo == 5)) 
		{
			lean = (int)( abs(str->y - m_PathConer[i].y)/abs(str->x - m_PathConer[i].x) );
			test = (int)( abs(end->y - m_PathConer[i].y)/abs(end->x - m_PathConer[i].x) );
			if(test > lean) type = 1;
			else type = 0;
		}
		else if( (dirOne == 5 && dirTwo == 7) || (dirOne == 7 && dirTwo == 5) || (dirOne == 7 && dirTwo == 7) || (dirOne == 8 && dirTwo == 8))
		{
			lean = (int)( abs(str->y - m_PathConer[i].y)/abs(str->x - m_PathConer[i].x) );
			test = (int)( abs(end->y - m_PathConer[i].y)/abs(end->x - m_PathConer[i].x) );
			if(test > lean) type = 0;
			else type = 1;
		}
		else type = m_ConerAtt[dirOne][dirTwo];

		bNode = CompareNode(m_PathConer[i].x, m_PathConer[i].y);
		if( (str->Type == type || str == m_pStrLink) && !m_bConer && bNode) 
		{
			m_bConer = true;
			temp = InsertNode(str, true);
			temp->Type = type;
			temp->x = m_PathConer[i].x;
			temp->y = m_PathConer[i].y;
		}
	}

	return temp;
}


BOOL CPath::CompareNode(int x, int y)
{
	BOOL coner = TRUE;
	POS *temp = m_pStrLink;

	do
	{
		if((temp->x == x) && (temp->y == y))
		{
			coner = FALSE; 
			break;
		}
		temp = temp->next;
		if(temp == NULL) break;

	} while(1);

	return coner;
}

CPath::POS* CPath::ChoiceNode()
{
	int i = 0;
	POS *str = m_pStrLink;
	POS *end = m_pStrLink->next;

	do
	{
		if(SearchBlock(str, end)) 
		{
			if(str->next != m_pEndLink) DeleteNode(str, m_pEndLink);
			str->next = NULL;
			m_pEndLink->prev = NULL;
			break;
		}
		else
		{
			str = str->next;
			end = end->next;
		}
			
	} while(end != NULL);

	return str;
}

//------------------------------------------------------------------------
//	Name :	SearchTile()
//	Desc :	
//	UpDate:	2000, 9, 18
//------------------------------------------------------------------------
int CPath::SearchTile(POS *str)
{
	char    tes = 0;//, dir = 0;
	int		ConerNum = 0;
	int		TileValue = 0;
	int		tempX = m_BlockTileX;
	int		tempY = m_BlockTileY;
	BOOL	ConerTile = FALSE; 

	do
	{
		if(tempY <= 0 || tempX >= m_nSizeX) break;
		TileValue = m_pTile[tempX][tempY].m_bMove;				//	NE
		if(!TileValue) 
		{
			if( IsConer(tempX-1, tempY+1) )
			{
				if((tempX-1 == m_BlockTileX) && (tempY+1 == m_BlockTileY) && ( abs(str->x - tempX-1) == abs(str->y - tempY+1) )) tes = 3;
				m_PathConer[ConerNum].x = tempX; m_PathConer[ConerNum].y = tempY;
				m_PathConer[ConerNum].dist = abs(tempX - m_BlockTileX) + tes + ( abs(tempX - str->x)+abs(tempY - str->y) )/2;
				ConerTile = TRUE; ConerNum++; 
			}
		}
		else	{ tempX++; tempY--; }
	} while(TileValue && (tempX%2 == tempY%2));

	tes = 0;
	tempX = m_BlockTileX;
	tempY = m_BlockTileY;

	do
	{
		if(tempX >= m_nSizeX || tempY >= m_nSizeY) break;
		TileValue = m_pTile[tempX][tempY].m_bMove;				//	ES
		if(!TileValue) 
		{
			if( IsConer(tempX-1, tempY-1) )
			{
				if((tempX-1 == m_BlockTileX) && (tempY-1 == m_BlockTileY) && ( abs(str->x - tempX-1) == abs(str->y - tempY-1) )) tes = 3;
				m_PathConer[ConerNum].x = tempX; m_PathConer[ConerNum].y = tempY;
				m_PathConer[ConerNum].dist = abs(tempX - m_BlockTileX) + tes +( abs(tempX - str->x)+abs(tempY - str->y) )/2;
				ConerTile = TRUE; ConerNum++; 
			}
		}
		else	{ tempX++; tempY++; }
	} while(TileValue && (tempX%2 == tempY%2));

	tes = 0;
	tempX = m_BlockTileX;
	tempY = m_BlockTileY;

	do
	{		
		if(tempX <= 0 || tempY >= m_nSizeY) break;
		TileValue = m_pTile[tempX][tempY].m_bMove;				//	SW
		if(!TileValue) 
		{
			if( IsConer(tempX+1, tempY-1) )
			{
				if((tempX+1 == m_BlockTileX) && (tempY-1 == m_BlockTileY) && ( abs(str->x - tempX+1) == abs(str->y - tempY-1) )) tes = 3;
				m_PathConer[ConerNum].x = tempX; m_PathConer[ConerNum].y = tempY;
				m_PathConer[ConerNum].dist = abs(tempX - m_BlockTileX) + tes +( abs(tempX - str->x)+abs(tempY - str->y) )/2;	
				ConerTile = TRUE; ConerNum++; 
			}
		}
		else	{ tempX--; tempY++; }
	} while(TileValue && (tempX%2 == tempY%2));

	tes = 0;
	tempX = m_BlockTileX;
	tempY = m_BlockTileY;

	do
	{		
		if(tempX < 0 || tempY < 0) break;
		TileValue = m_pTile[tempX][tempY].m_bMove;				//	WN
		if(!TileValue) 
		{
			if( IsConer(tempX+1, tempY+1) )
			{
				if((tempX+1 == m_BlockTileX) && (tempY+1 == m_BlockTileY) && ( abs(str->x - tempX+1) == abs(str->y - tempY+1) )) tes = 3;
				m_PathConer[ConerNum].x = tempX; m_PathConer[ConerNum].y = tempY;
				m_PathConer[ConerNum].dist = abs(tempX - m_BlockTileX) + tes + ( abs(tempX - str->x)+abs(tempY - str->y) )/2;	
				ConerTile = TRUE; ConerNum++; 
			}
		}
		else	{ tempX--; tempY--; }
	} while(TileValue && (tempX%2 == tempY%2));

	if(!ConerTile)
	{
		tempX = m_BlockTileX;
		tempY = m_BlockTileY;