A星寻路算法c++语言实现

A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。c++语言实现

// ConsoleApplication3.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“
#include “iostream“
#include 
#include  
#include 
#define STEP  10
#define ANGLE 14
#define ROW   10
#define COL   10
using namespace std;

struct Point
{  

	Point（int xint y）
	  {
		  X=x;
		  Y=y;
		  F=0;
		  G=0;
		  H=0;
		  parent=NULL;
	  }
	  Point（）
	  {

	  }
	  void CalcF（）
	  {
		  F=G+H;
	  }

	bool operator<（Point p2）  
	{  
		if （F			return true;  
		return false;  
	}  

	  Point *parent;
	  int F;
	  int G;
	  int H;
	  int X;
	  int Y;	 
};

class CFindPath
{
public:
	CFindPath（）;
	CFindPath（int map[][COL]）;
	~CFindPath（）;
	Point *GetPath（Point startPoint endbool isAagle）;//获取路径链表;
	list GetSurroundPoint（Point &bool）;//获取周围可到达的点;
	bool IsCanReach（int xint y）;//判断是否是墙壁;
	void ChangePoint（Point startPoint point）;//改变已在开启列表的点;
	void AddPoint（Point startPoint endPoint point）;//添加不在开启列表的点;
	int CalculateG（PointPoint ）;//计算G
	int CalculateH（Point endPoint point）;//计算H
	bool IsCanReach（Point startint xint ybool isAngle）;//判断是否可到达;
	Point *FindOpenListPoint（Point p）;
	Point *FindColseListPoint（Point p）;
	Point *FPoint（Point p）;
private:
	list openList;//开启列表;
	list colseList;//关闭列表;
	list temList;
	int points[ROW][COL];
};

CFindPath::CFindPath（）
{

}
CFindPath::CFindPath（int map[][COL]）
{	
	for（int i=0;i		for（int j=0;j			points[i][j]=map[i][j];	
}
CFindPath::~CFindPath（）
{
	delete points;
}



Point* CFindPath::GetPath（Point startPoint endbool isAngle）//核心算法A*路径查找isAngle表示是否可以越过拐角;
{   
	openList.push_back（start）;
	while （!openList.empty（））
	{  
		openList.sort（）;//根据F值由小到大排序;
		Point temp=openList.front（）;//取出F值最小的;
	    colseList.push_back（temp）;//加入到关闭列表;
		openList.pop_front（）;//开启列表中删除F值最小的;
		list surroundPoints=GetSurroundPoint（tempisAngle）;//取出周围可到达的点;      
		while （!surroundPoints.empty（））//对每个可到达的周围的点进行判断;
		{
			 Point point=surroundPoints.front（）;		
			if（FindOpenListPoint（point））//若开启列表中存在这个点;	
			 ChangePoint（temppoint）;//判断是否是最优路径如果是改变父结点若不是则什么也不做;		
			else		
		     AddPoint（tempendpoint）;//若不在开启列表则加入;		
		surroundPoints.pop_front（）;
		}
	   if（FindOpenListPoint（end））
			return FindOpenListPoint（end）;
	}
  return FindOpenListPoint（end）;
}



	void CFindPath::ChangePoint（Point startPoint point）//改变点的父结点重新计算F值;
	{
		
		int G=CalculateG（startpoint）;
		if（G		{   point.parent=new Point（start）;
			point.G=G;
			point.CalcF（）;
		}
	}

	void CFindPath::AddPoint（Point startPoint endPoint point）//添加点到开启列表;
	{   
		point.parent=new Point（start）;
		point.G=CalculateG（startpoint）;
		point.H=CalculateH（endpoint）;
		point.CalcF（）;
		openList.push_back（point）;
	}

int  CFindPath::CalculateG（Point startPoint point）//计算G值
	{   
		
		int parentG=0;
		int G=（abs（point.X-start.X）+abs（point.Y-start.Y））!=2?STEP:

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-01-28 15:12  A星寻路算法c++\
     目录           0  2016-01-27 14:49  A星寻路算法c++\ConsoleApplication3\
     文件     9699328  2016-01-28 15:12  A星寻路算法c++\ConsoleApplication3.sdf
     文件         924  2016-01-27 14:49  A星寻路算法c++\ConsoleApplication3.sln
     文件       31232  2016-01-28 15:12  A星寻路算法c++\ConsoleApplication3.v11.suo
     文件        6679  2016-01-28 15:11  A星寻路算法c++\ConsoleApplication3\ConsoleApplication3.cpp
     文件        4546  2016-01-27 14:49  A星寻路算法c++\ConsoleApplication3\ConsoleApplication3.vcxproj
     文件        1323  2016-01-27 14:49  A星寻路算法c++\ConsoleApplication3\ConsoleApplication3.vcxproj.filters
     目录           0  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\
     文件        1782  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\cl.command.1.tlog
     文件       14836  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\CL.read.1.tlog
     文件        1372  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\CL.write.1.tlog
     文件          89  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.lastbuildstate
     文件        2518  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.log
     文件      415320  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.obj
     文件     1245184  2016-01-27 14:49  A星寻路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.pch
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link-cvtres.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link-cvtres.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link-rc.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link-rc.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344-cvtres.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344-cvtres.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344-rc.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344-rc.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10344.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10748-cvtres.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10748-cvtres.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10748-rc.read.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10748-rc.write.1.tlog
     文件           2  2016-01-28 15:01  A星寻路算法c++\ConsoleApplication3\Debug\link.10748.read.1.tlog
............此处省略132个文件信息