//?AStar.cpp:?implementation?of?the?CAStar?class.
//
//////////////////////////////////////////////////////////////////////

#include?“stdafx.h“
#include?“AStar.h“
#include?
#include?
//////////////////////////////////////////////////////////////////////
//?Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAStar::CAStar（）
{

}

CAStar::~CAStar（）
{
	int?sizetmp?=?mOpenSet.size（）;
	if?（sizetmp?!=?0）
	{
		mOpenSet.clear（）;
	}
	sizetmp?=?mCloseSet.size（）;
	if?（sizetmp?!=?0）
	{
		mCloseSet.clear（）;
	}
	if?（mMap?!=?NULL）
	{
		delete?[]?mMap;
		mMap?=?NULL;
	}
}
void?CAStar::GetBegPt（Point2d?BegPt）
{
	mBegPt?=?BegPt;
	mBegPt.F?=?0;
	mBegPt.G?=?0;
	mBegPt.IsValue?=?1;
	mBegPt.Parent?=?NULL;
}
void?CAStar::GetEndPt（Point2d?EndPt）
{
	mEndPt?=?EndPt;
	mEndPt.F?=?0;
	mEndPt.G?=?0;
	mEndPt.IsValue?=?1;
	mEndPt.Parent?=?NULL;
}

double?CAStar::Getdis（Point2d?A??Point2d?B）
{
	return?sqrt（pow（（double）（A.x-B.x）2）+pow（（double）（A.y-B.y）2））*10;
}

void?CAStar::QuickSortToOpenset（int?leftint?right）
{
	int?low?=?lefthigh?=?right;
	Point2d?PtTemp??middle;
	middle?=?mOpenSet[left];
//	middle?=?mOpenSet[（left+right）/2];//求中間值
//	middle?=?mOpenSet[（rand（）%（right-left））+left];?//生成大于等于left小于等于right的隨機數
	do
	{
		while?（?（mOpenSet[low].F?>?middle.F）?&&?（low?			low++;
		while?（?（mOpenSet[high].F??left）?）//從右掃描小于中值的數
			high--;
		//找到了一對值交換
		if（low?<=?high）
		{
			PtTemp?=?mOpenSet[high];
			mOpenSet[high]=mOpenSet[low];
			mOpenSet[low]=PtTemp;
			low++;
			high--;
		}
	}while（low?<=?high）;//如果兩邊掃描的下標交錯，就停止（完成一次）

	//當左邊部分有值（left	if（left?	{
		QuickSortToOpenset（lefthigh）;
	}

	//當右邊部分有值（right?>?low），遞歸右半邊
	if（right?>?low）
	{
		QuickSortToOpenset（lowright）;
	}
}

void?CAStar::SortToOpenset（）
{
	Point2d?Pttemp;
	int?sizetmp?=?mOpenSet.size（）;
	for?（int?i?=?sizetmp-1?;?i?>?0?;?i--）
	{
		for?（int?j?=?i?;?j?>?0?;?j--）
		{
			if?（mOpenSet[i].F?>?mOpenSet[j].F）
			{
				Pttemp?=?mOpenSet[i];
				mOpenSet[i]?=?mOpenSet[j];
				mOpenSet[j]?=?Pttemp;
			}
		}
	}
}

void?CAStar::OpensetSort（）
{
	int?size?=?mOpenSet.size（）;
//?	for?（int?i?=?0?;?i?//?	{
//?		cout<//?	}
	if?（size?!=?0）
	{
		QuickSortToOpenset（0??size-1）;
	}
//	cout<<“open:“<//?	for?（int?i?=?0?;?i?//?	{
//?		cout<//?	}
}

//PA為A的前一個點，B為目標節點，獲取A的父節點移動到A的當前開銷
int?CAStar::GetNowG（Point2d?PA?Point2d?A）
{
	int?res?;
//?	if?（PA.x?!=?A.x?&&?PA.y?==?A.y）
//?	{
//?		res?=?abs（PA.x?-?A.x）;
//?	}
//?	else?if?（PA.x?==?A.x?&&?PA.y?!=?A.y）
//?	{
//?		res?=?abs（PA.y?-?A.y）;
//?	}
//?	else
//?	{
		res?=?Getdis（PAA）;
//	}
	return?res;
}

//獲取A到達終點的預計開銷
int?CAStar:

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

????.CA....??????7232??2010-05-07?16:01??Astra\AStar.cpp

????.CA....??????1496??2010-05-03?09:19??Astra\AStar.h

????.CA....???????602??2010-05-07?15:45??Astra\CDijkstra.cpp

????.CA....??????4688??2010-05-02?20:01??Astra\CDijkstra.dsp

????.CA....???????543??2010-04-30?21:14??Astra\CDijkstra.dsw

????.CA....?????82944??2013-06-30?14:17??Astra\CDijkstra.ncb

????.CA....?????48640??2013-06-30?14:17??Astra\CDijkstra.opt

????.CA....??????1752??2013-06-30?14:16??Astra\CDijkstra.plg

????.CA....?????50970??2013-06-30?14:16??Astra\Debug\AStar.obj

????.CA....????183895??2010-05-02?16:31??Astra\Debug\AStar.obj.enc

????.CA....?????34955??2010-05-02?14:26??Astra\Debug\AStra.obj

????.CA....????315445??2013-06-30?14:16??Astra\Debug\CDijkstra.exe

????.CA....????441464??2013-06-30?14:16??Astra\Debug\CDijkstra.ilk

????.CA....?????16153??2013-06-30?14:16??Astra\Debug\CDijkstra.obj

????.CA....????400336??2013-06-30?14:16??Astra\Debug\CDijkstra.pch

????.CA....???1393664??2013-06-30?14:16??Astra\Debug\CDijkstra.pdb

????.CA....??????1824??2013-06-30?14:16??Astra\Debug\StdAfx.obj

????.CA....????173056??2013-06-30?14:16??Astra\Debug\vc60.idb

????.CA....????159744??2013-06-30?14:16??Astra\Debug\vc60.pdb

????.CA....??????1226??2010-04-30?21:14??Astra\ReadMe.txt

????.CA....???????296??2010-04-30?21:14??Astra\StdAfx.cpp

????.CA....???????769??2010-04-30?21:14??Astra\StdAfx.h

????.C.D...?????????0??2013-06-30?14:16??Astra\Debug

????.C.D...?????????0??2013-06-30?14:17??Astra

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

??????????????3321694????????????????????24