#include“stdafx.h“
#include“a_star.h“

U8?Astar::m_mtrxMapMatrix[HEIGHT][WIDTH];

U16?BitNum（U8?n）
{
	return?1<}

U8?GetBit（U16?n）
{
	assert（n?!=?0）;
	assert（n%2?==?0?||?n?==?1）;

	U8?t=0;
	while（n?!=?1）
	{
		t++;
		n>>=1;
	}
	return?t;
}

Astar::Astar（void）:m_pntTerminal（）m_pntStart（）
{
	memset（m_mtrxMapMatrix0sizeof（m_mtrxMapMatrix））;
	m_lstPathList.clear（）;
	m_vctOpenList.clear（）;
	m_lstCloseList.clear（）;
	m_wdStep?=?0;
}

Astar::~Astar（）
{
	InitOpenList（）;
	InitCloseList（）;
	m_lstPathList.clear（）;
}

MapNode*?Astar::CreateNewNode（MapNode*?pconst?U8?dir）
{
	if（nullptr?!=?p）
	{
		//不是開始點
		U8?t?=?GetBit（dir）;
		APoint?pos（p->m_pntPoint+DIR_VECTOR[t]）;
		//判斷點是否在地圖內
		if（WithinMap（pos））
		{
			//在地圖內
			U8?pv?=?m_mtrxMapMatrix[pos.GetX（）][pos.GetY（）];
			//判斷對應位置上是否有障礙物
			if（BAR?!=?pv）
			{
				//若無障礙物
				//依據規則創建新節點，防止出現重復
				MapNode*?temp?=?new?MapNode;
				temp->m_btValue?=?pv;
				temp->m_bIsVisited?=?false;
				temp->m_bIsReachable?=?true;
				temp->m_pntPoint?=?p->m_pntPoint+DIR_VECTOR[t];//計算新節點位置
				p->m_btSur?+=?dir;			//標記新節點相對于源節點的位置
				if（0?==?t%2）//非對角線方向?
				{
					temp->m_btSur?=?~（BitNum（（t+7）%8）+BitNum（（t+9）%8）+BitNum（t））;//依據規則，該點只能探測三個方向
					temp->m_pFrom?=?p;
				}
				else//對角線方向
				{
					t?=?（t+4）%8;
					temp->m_btSur?=?（BitNum（（t+7）%8）+BitNum（（t+9）%8）+BitNum（t））;//依據規則，該點有三個方向不用探索
					temp->m_pFrom?=?p;
				}
				return?temp;//返回新節點
			}
			else
			{
				//若有障礙物
				//不創建新節點
				p->m_btSur?=?dir;//標記障礙物相對于源節點的位置：注意，障礙物不可跨越
				if（0?!=?t%2）//判斷是否是對角線上的障礙物
				{
					//不是則對角線方向不可通過
					p->m_btSur?+=?BitNum（（t+7）%8）;
					p->m_btSur?+=?BitNum（（t+9）%8）;
				}
				return?nullptr;
			}
		}
		else
		{
			//不在地圖內
			//不創建新節點
			p->m_btSur?+=?dir;//標記表示已經訪問過
			return?nullptr;
		}
	}
	else
	{
		//是開始點
		//創建開始點
		MapNode*?temp?=?new?MapNode;
		temp->m_btValue?=?0;
		temp->m_bIsVisited?=?false;
		temp->m_bIsReachable?=?true;
		temp->m_pntPoint?=?m_pntStart;
		temp->m_btSur?=?0;	
		temp->m_pFrom?=?nullptr;
		return?temp;//返回新節點
	}
}

void?Astar::InitCloseList（void）
{
	if（!m_lstCloseList.empty（））
	{
		for（list::iterator?it?=?m_lstCloseList.begin（）;it?!=?m_lstCloseList.end（）;it++）
		{
			assert（*it?!=?nullptr）;

			delete?*it;
		}
		m_lstCloseList.clear（）;
	}
}

void?Astar::InitOpenList（void）
{
	if（!m_vctOpenList.empty（））
	{
		for（vector::iterator?it?=?m_vctOpenList.begin（）;it?!=?m_vctOpenList.end（）;it++）
		{
			assert（*it?!=?nullptr）;

			delete?*it;
		}
		m_vctOpenList.clear（）;
	}
}

void?Astar::SetFec（MapNode*?node）
{
	SetGac（node）;
	SetHec（node）;
	node->m_fFec?=?node->m_fGac?+?node->m_fHec;
}

void?Astar::SetGac（MapNode*?node）
{
	float?t;

	if（nullptr?!=?node->m_pFrom）
	{
		APoint?cab;
		a?=?（node->m_pntPoint）;
		b?=?（node->m_pFrom->m_pntPoint）;
		c?=?a?-?b;
		t?=?node->m_pFrom->m_fGac;
		t?+=?VectorLenth（c）;
	}
	else
	{
		assert（

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2728??2017-04-07?22:30??point.h

?????文件???????6439??2017-04-08?13:39??a_star.cpp

?????文件???????3303??2017-04-08?14:14??a_star.h

?????文件????????690??2017-04-08?13:49??main.cpp

-----------?---------??----------?-----??----

????????????????13160????????????????????4