bool PathFinder::CalculatePath3(RTSUnit *pUnit,WORD destX,WORD destY)
{
	//if this unit is a user of any other paths, unregister it from them
	Cancel(pUnit);

	WORD startX = pUnit->Pos().x, startY = pUnit->Pos().y;
	m_Open.clear();
	m_Closed.clear();
	
	PathSearchNode N,Nnew,*pN;
	
	m_Open.push_front(PathSearchNode(0,startX,startY,destX,destY));
	while(!m_Open.empty())
	{
		N = m_Open.front();
		m_Open.pop_front();
		if(N.m_X == destX && N.m_Y == destY)
		{
			//found a route - genreate the list of tiles
			PathDataTileList *pPath = new PathDataTileList(this);
			
			for(pN = &N; pN; pN=pN->m_pParent) 
			{
				pPath->AddPoint(pN->m_X,pN->m_Y);
			}
			m_Paths.push_back(pPath);
			m_PathLocations.push_back(new PathLocation(pPath,pUnit));
			return true;
		}

		//push N onto closed and remember it's address for setting it as a parent to the new nodes
		m_Closed.push_back(N);
		pN = &m_Closed.back();

		//find the 8 surrounding nodes
		for(WORD y = max(N.m_Y,1)-1; y<= N.m_Y+1; ++y)
		for(WORD x = max(N.m_X,1)-1; x<= N.m_X+1; ++x)
		if(y!=N.m_Y || x!=N.m_X)	//don't select current node again!
		{
			Nnew.Set(pN,x,y,destX,destY);
			
			bool skip =false;
			// check - if Nnew in closed or open, and existing version has lower G, then skip this one
			for(std::list<PathSearchNode>::iterator Iopen = m_Open.begin(); Iopen!= m_Open.end(); ++Iopen)
				if((*Iopen) == Nnew && (*Iopen).m_G <= Nnew.m_G)
				{	skip =true;		break;	}
			for(std::list<PathSearchNode>::iterator Iclosed = m_Closed.begin(); Iclosed!= m_Closed.end(); ++Iclosed)
				if((*Iclosed) == Nnew && (*Iclosed).m_G <= Nnew.m_G)
				{	skip =true;		break;	}
			if(skip)
				continue;

			//if in closed, remove it
			if(Iclosed != m_Closed.end())
				m_Closed.erase(Iclosed);

			//add to open
			if(Iopen == m_Open.end())
				m_Open.push_front(Nnew);
		}
		//sort all nodes by ascending F.
		m_Open.sort();
	}
	return false;
}

class PathSearchNode
{
public:
	PathSearchNode *m_pParent;
	float m_F,m_G,m_H;	//G is cost to this node, H heuristic estimate from here to end, F node cost G+H
	WORD m_X,m_Y;		//the tile this node is located at

	PathSearchNode(){}
	PathSearchNode(PathSearchNode *pParent,WORD X,WORD Y,WORD destX,WORD destY)
	{
		Set(pParent,X,Y,destX,destY);
	}
	void Set(PathSearchNode *pParent,WORD X,WORD Y,WORD destX,WORD destY)
	{
		m_pParent = pParent;
		m_X = X;	m_Y = Y;
		//no parent - start point
		if(!m_pParent)
			m_G=0;
		else if(m_pParent->m_X != m_X && m_pParent->m_Y != m_Y)
			m_G = m_pParent->m_G + 1.4f;	//extra cost for diagonal movement
		else
			m_G = m_pParent->m_G + 1.0f;
		m_H = EstimateGoalDistance(destX,destY);
		m_F = m_G + m_H;
	}

	bool operator<(const PathSearchNode &comp)
	{	return (m_F < comp.m_F);	}
	bool operator>(const PathSearchNode &comp)
	{	return (m_F > comp.m_F);	}
	bool operator==(const PathSearchNode &comp)
	{	return (m_X==comp.m_X && m_Y==comp.m_Y);	}

	int EstimateGoalDistance(WORD destX,WORD destY)
	{
		int dx = max(m_X,destX) - min(m_X,destX);
		int dy = max(m_Y,destY) - min(m_Y,destY);
		return max(dx,dy);
	}
};