A*寻路算法C++实现

发表于2016年1月28日由244128133

写了一天终于用C++的方式把 A*算法撸出来了,写完后才发现如果有拐角的地方有4种方式需要不同的处理他.

起点和到达点的位置关系和对角的方向关系的不同所以判断的条件也不同了.暂时没有找到更好的方法,如果有谁知道可以联系我.算法实现原理:http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html代码如下:

</pre>

#include "stdafx.h"
#include "iostream"
#include <list>
#include <cstdlib>
#include <string>
#define STEP 10
#define ANGLE 14
#define ROW 10
#define COL 10
using namespace std;

struct Point
{

Point(int x,int 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<p2.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 start,Point end,bool isAagle);//获取路径链表;
 list<Point> GetSurroundPoint(Point &,bool);//获取周围可到达的点;
 bool IsCanReach(int x,int y);//判断是否是墙壁;
 void ChangePoint(Point start,Point point);//改变已在开启列表的点;
 void AddPoint(Point start,Point end,Point point);//添加不在开启列表的点;
 int CalculateG(Point,Point );//计算G
 int CalculateH(Point end,Point point);//计算H
 bool IsCanReach(Point start,int x,int y,bool isAngle);//判断是否可到达;
 Point *FindOpenListPoint(Point p);
 Point *FindColseListPoint(Point p);
 Point *FPoint(Point p);
private:
 list<Point> openList;//开启列表;
 list<Point> colseList;//关闭列表;
 list<Point> temList;
 int points[ROW][COL];
};

CFindPath::CFindPath()
{

}
CFindPath::CFindPath(int map[][COL])
{
 for(int i=0;i<ROW;i++)
 for(int j=0;j<COL;j++)
 points[i][j]=map[i][j];
}
CFindPath::~CFindPath()
{
 delete points;
}

&nbsp;

Point* CFindPath::GetPath(Point start,Point end,bool 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<Point> surroundPoints=GetSurroundPoint(temp,isAngle);//取出周围可到达的点;
 while (!surroundPoints.empty())//对每个可到达的周围的点进行判断;
 {
 Point point=surroundPoints.front();
 if(FindOpenListPoint(point))//若开启列表中存在这个点;
 ChangePoint(temp,point);//判断是否是最优路径如果是改变父结点若不是则什么也不做;
 else
 AddPoint(temp,end,point);//若不在开启列表则加入;
 surroundPoints.pop_front();
 }
 if(FindOpenListPoint(end))
 return FindOpenListPoint(end);
 }
 return FindOpenListPoint(end);
}

&nbsp;

void CFindPath::ChangePoint(Point start,Point point)//改变点的父结点重新计算F值;
 {

 int G=CalculateG(start,point);
 if(G<point.G)
 { point.parent=new Point(start);
 point.G=G;
 point.CalcF();
 }
 }

void CFindPath::AddPoint(Point start,Point end,Point point)//添加点到开启列表;
 {
 point.parent=new Point(start);
 point.G=CalculateG(start,point);
 point.H=CalculateH(end,point);
 point.CalcF();
 openList.push_back(point);
 }

int CFindPath::CalculateG(Point start,Point point)//计算G值
 {

 int parentG=0;
 int G=(abs(point.X-start.X)+abs(point.Y-start.Y))!=2?STEP:ANGLE;
 if(point.parent)
 parentG=point.parent->G!=0?point.parent->G:0;
 return G+parentG;

}

int CFindPath::CalculateH(Point end,Point point)//计算H值;
 {
 int step=abs(point.X-end.X)+abs(point.Y-end.Y);
 return step*STEP;

}

Point* CFindPath::FindOpenListPoint(Point p)//查找点是否在开启列表中;
 {
 list<Point>::iterator i;
 for(i=openList.begin();i!=openList.end();i++)
 {
 if(p.X==i->X&&p.Y==i->Y)
 {
 return &*i;
 }
 }
 return NULL;
 }

list<Point> CFindPath::GetSurroundPoint(Point &p,bool isAngle)//获取周围可到达结点;
{ list<Point> temPoints;

for(int i=p.X-1;i<=(p.X+1>=ROW?p.X:p.X+1);i++)
 for(int j=p.Y-1;j<=(p.Y+1>=COL?p.Y:p.Y+1);j++)
 {
 if(IsCanReach(p,i,j,isAngle))
 {

 Point mPoint(i,j);
 temPoints.push_back(mPoint);
 }
 }
 return temPoints;
}
 Point *CFindPath::FindColseListPoint(Point p)
 {

list<Point>::iterator i;
 for(i=colseList.begin();i!=colseList.end();i++)
 {
 if(p.X==i->X&&p.Y==i->Y)
 {
 return &*i;
 }
 }
 return NULL;
 }

bool CFindPath::IsCanReach(Point start,int x,int y,bool isAngle)//判断点是否可以到达
{
 Point point;
 point.X=x;
 point.Y=y;
 if(!IsCanReach(x,y)||FindColseListPoint(point))
 {
 return false;
 }
 else
 {
 if(abs(x-start.X)+abs(y-start.Y)==1)
 return true;
 else
 {
 if(isAngle)//如果可以拐角直接返回
 return isAngle;

//以下为4种不同拐角的情况判断
 if(x<start.X&&y<start.Y) //(到点) 0 | 1 //到点和起点的位置有4种情况所以有4种不同的拐角
 { // -----|-----
 if(points[start.X][y]==0&&points[x][start.Y]==0) // 1 | 0(起点)
 return true; //
 }
 else if(x<start.X&&y>start.Y)
 {
 if(points[x][start.Y]==0&&points[start.X][y]==0)
 return true;
 }
 else if(x>start.X&&y<start.Y)
 {
 if(points[start.X][y]==0&&points[x][start.Y]==0)
 return true;
 }
 else if(x>start.X&&y>start.Y)
 {
 if(points[x][start.Y]==0&&points[start.X][y]==0)
 return true;

}
 return false;

 }
 }
}

bool CFindPath::IsCanReach(int x,int y)//判断点是否可以通过
{
 return points[x][y]==0;
}
int main(int argc, char* argv[])
{
 int map[10][10]={//地图//0 1 2 3 4 5 6 7 8 9
 /*0*/{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 /*1*/{ 1, 0, 0, 1, 1, 0, 1, 0, 0, 0},
 /*2*/{ 1, 0, 1, 1, 1, 0, 0, 0, 0, 0},
 /*3*/{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1},
 /*4*/{ 1, 1, 1, 1, 0, 0, 0, 0, 1, 1},
 /*5*/{ 1, 1, 0, 1, 0, 0, 0, 0, 0, 0},
 /*6*/{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
 /*7*/{ 1, 1, 0, 0, 1, 1, 0, 0, 0, 1},
 /*8*/{ 1, 1, 0, 0, 1, 0, 0, 1, 0, 1},
 /*9*/{ 1, 1, 1, 0, 1, 1, 1, 1, 0, 1}
 };
 CFindPath path(map);//初始化地图;
 Point start(1,1);//起点;
 Point end(9,8);//终点
 Point *point=new Point();
 point=path.GetPath(start,end,false);
 if(point==NULL)
 {
 cout<<"无法到达终点!"<<endl;
 }
 else
 {
 while (point!=NULL)
 {
 cout<<point->X<<","<<point->Y<<endl;
 point=point->parent;
 }
 }
 delete point;
 point=NULL;
 getchar();
 return 0;
}

&nbsp;
<pre>

以上代码在VS2012上测试通过.