A星算法简单直观

Astar C++源代码 Astar.h A*类头文件 Astar.cpp A*类源代码文件

// 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 < right） ）//从左扫描大于中值的数
			low++;
		while （ （mOpenSet[high].F < middle.F） && （high > left） ）//从右扫描小于中值的数
			high--;
		//找到了一对值交换
		if（low <= high）
		{
			PtTemp = mOpenSet[high];
			mOpenSet[high]=mOpenSet[low];
			mOpenSet[low]=PtTemp;
			low++;
			high--;
		}
	}while（low <= high）;//如果两边扫描的下标交错，就停止（完成一次）

	//当左边部分有值（left	if（left < high）
	{
		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 < size ; i++）
// 	{
// 		cout<// 	}
	if （size != 0）
	{
		QuickSortToOpenset（0  size-1）;
	}
//	cout<<“open:“<// 	for （int i = 0 ; i < size ; 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