//此處代碼源自CSDN，地址不記得了。。。。。。。
#include?
#include?“Astar.h“
#include?

int?CAStar::m_moveCostHorizontal?=?5;
int?CAStar::m_moveCostDiagonal?=?7;

DIRECTION?g_direct[]?=?{
	//{-1?-1}?//left?up
	//{-1?+1}?//left?down
	//{+1?-1}?//right?up
	//{+1?+1}?//right?down
	{?-1?0?}?//left
	{?+1?0?}?//right
	{?0?-1?}?//up
	{?0?+1?}?//down
};

CAStar::CAStar（）?:m_startNode（0?0）?m_endNode（0?0）
{
	m_CallBack?=?NULL;
}

CAStar::CAStar（int?nColumn?int?nRow）?:?m_startNode（0?0）?m_endNode（0?0）
{
	m_nColumn?=?nColumn;
	m_nRow?=?nRow;
	m_CallBack?=?NULL;
}

CAStar::~CAStar（void）
{
}

void?CAStar::SetRange（int?nColumn?int?nRow）
{
	m_nColumn?=?nColumn;
	m_nRow?=?nRow;
}

void?CAStar::SetBlock（vector?&vecBlock）
{
	m_barrier.clear（）;
	for?（unsigned?int?i?=?0;?i?	{
		m_barrier.push_back（vecBlock[i]）;
	}
}

void?CAStar::SetStartAndEnd（NODE?startNode?NODE?endNode）
{
	m_startNode?=?startNode;
	m_endNode?=?endNode;
	m_open.clear（）;
	m_close.clear（）;
	CalcValue（startNode）;
	m_open.push_back（startNode）;
}

void?CAStar::GetMinFromOpen（vector?&minVec）
{
	minVec.clear（）;
	vector::iterator?it?=?m_open.begin（）;
	int?fMin?=?INT_MAX;
	for?（;?it?!=?m_open.end（）;?it++）
	{
		if?（it->f?			fMin?=?it->f;
	}
	for?（it?=?m_open.begin（）;?it?!=?m_open.end（）;?）
	{
		if?（it->f?==?fMin）
		{
			minVec.push_back（*it）;
			it?=?m_open.erase（it）;
			continue;
		}
		it++;
	}
}

int?CAStar::SetCallBack（int（*pFun）（void?*）?void?*pThis）
{
	m_CallBack?=?pFun;
	m_pArg?=?pThis;
	return?1;
}

bool?CAStar::IsFindPath（）
{
	return?m_bFind;
}

void?CAStar::FindPath（）
{
	m_bFind?=?false;
	vector?minVec;
	while?（!m_bFind）
	{
		minVec.clear（）;
		GetMinFromOpen（minVec）;
		if?（minVec.empty（））
			break;
		m_close.insert（m_close.end（）?minVec.begin（）?minVec.end（））;
		for?（vector::iterator?it?=?minVec.begin（）;?it?!=?minVec.end（）;?it++）
			DoNeighbors（*it）;

		if?（m_bFind）
			GetFinalShortestPath（）;

		if?（m_CallBack）?m_CallBack（m_pArg）;
	}
}

void?CAStar::GetFinalShortestPath（）
{
	NODE?node?=?m_close[m_close.size（）?-?1];
	m_path.clear（）;
	while?（true）
	{
		DIRECTION?direct?=?node.parent;
		NODE?parentNode?=?node;
		parentNode.nX?-=?direct.x;
		parentNode.nY?-=?direct.y;

		for?（unsigned?int?i?=?0;?i?		{
			if?（m_close[i].nX?==?parentNode.nX?&&?m_close[i].nY?==?parentNode.nY）
			{
				node?=?m_close[i];
				if?（node.nX?==?m_startNode.nX?&&?node.nY?==?m_startNode.nY）
					return;
				m_path.push_back（node）;
				break;
			}
		}
	}
}

void?CAStar::CalcValue（NODE?&node）
{
	node.g?=?GetDistance（node?m_startNode）;
	node.h?=?GetDistance（node?m_endNode）;
	node.f?=?node.g?+?node.h;
}

int?CAStar::GetDistance（NODE?&node1?NODE?&node2）
{
	int?xSub?=?abs（node1.nX?-?node2.nX）;
	int?ySub?=?abs（node1.nY?-?node2.nY）;

	return??abs（xSub?-?ySub）?*?m_moveCostHorizontal?+
		min（xSub?ySub）?*?m_moveCostDiagonal;
}

void?CAStar::DoNeighbors（NODE?&node）
{

	for?（int?i?=?0;?i?