关于A星寻路的介绍我就不多说了，网上到处都有，具体实现也各有写法，但大致还是一样的，下面是使用C++实现的源码，不足之处还望指出以便共同学习！
//
// CAstar.h
// Astar
//
// Created by xujw on 15/4/9.
// Copyright (c) 2015年 xujw. All rights reserved.
//
/*
F:路径评分 = g+h
G:走一格格子的花销
H:当前格子到目标格子的估算花销
上下左右走一格花销为10，斜着走一格花销为14，以方便计算
即格子宽高为10 对角线为14
*/
#ifndef __Astar__CAstar__
#define __Astar__CAstar__
#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
//地图最大值
#define MAX_X 10
#define MAX_Y 10
enum class AType
{
ATYPE_UNKNOWN,
ATYPE_CLOSED,
ATYPE_OPENED,
ATYPE_BARRIER //障碍
};
class APoint
{
public:
APoint();
~APoint();
int x;
int y;
AType type; //类型:障碍、开放列表、关闭列表
int f; //f = g+h
int g;
int h;
APoint *parent;
bool operator == (const APoint& po)
{
if (x == po.x && y == po.y)
{
return true;
}
return false;
}
};
class CAstar
{
vector<APoint*> _openList; //开放列表
vector<APoint*> _closeList; //关闭列表
vector<APoint*> _neighbourList; //周边节点
APoint* _endPoint;
APoint* _curPoint;
vector< vector<APoint*> > _allPoints;
public:
CAstar();
~CAstar();
APoint* findWay(APoint* beginPoint,APoint* endPoint,vector< vector<APoint*> >& allPoints);
// APoint* findWay(int beginX,int beginY,int endX,int endY);
private:
int getF(APoint *point);
int getH(APoint *point);
vector<APoint*> getNeighboringPoint(APoint* point);
};
#endif /* defined(__Astar__CAstar__) *///
// CAstar.cpp
// Astar
//
// Created by xujw on 15/4/9.
// Copyright (c) 2015年 xujw. All rights reserved.
//
// 上下左右走一格花销为10，斜着走一格花销为14，以方便计算
// 即格子宽高为10 对角线为14
#include "CAstar.h"
//自定义排序函数
bool mySort(const APoint* p1,const APoint* p2)
{
return p1->f < p2->f;
}
APoint::APoint():x(0)
,y(0)
,h(0)
,f(0)
,g(0)
,parent(nullptr)
,type(AType::ATYPE_UNKNOWN)
{
}
APoint::~APoint()
{
}
#pragma mark------CAstar-------
CAstar::CAstar():_endPoint(nullptr)
,_curPoint(nullptr)
{
}
CAstar::~CAstar()
{
_openList.clear();
_closeList.clear();
_neighbourList.clear();
_allPoints.clear();
}
APoint* CAstar::findWay(APoint *beginPoint, APoint *endPoint,vector< vector<APoint*> >& allPoints)
{
//传递地图
_allPoints = allPoints;
_endPoint = endPoint;
if (_endPoint->type == AType::ATYPE_BARRIER)
{
cout<<"终点是障碍"<<endl;
return nullptr;
}
if (*_endPoint == *beginPoint)
{
cout<<"起始点相同"<<endl;
return nullptr;
}
_openList.push_back(beginPoint);
beginPoint->type = AType::ATYPE_OPENED;
beginPoint->f = getF(beginPoint);
//---------
do
{
//获取最小值的节点
_curPoint = _openList[0];
_openList.erase(_openList.begin());
_curPoint->type = AType::ATYPE_CLOSED;
_closeList.push_back(_curPoint);
if (*_curPoint == *_endPoint)
{
cout<<"have find way"<<endl;
return _curPoint;
}
//获取相邻的节点
vector<APoint*> neVec = getNeighboringPoint(_curPoint);
for (int i = 0; i<neVec.size(); i++)
{
auto tmpoint = neVec[i];
if (tmpoint->type == AType::ATYPE_CLOSED)
{
continue;
}
//是否在开放列表里
if (tmpoint->type != AType::ATYPE_OPENED)
{
tmpoint->parent = _curPoint;
tmpoint->g = _curPoint->g + 10;
//计算H值
tmpoint->h = getH(tmpoint);
//添加到开放列表里
_openList.push_back(tmpoint);
tmpoint->type = AType::ATYPE_OPENED;
}
else
{
//已经在开放列表里
if (tmpoint->h < _curPoint->h)
{
tmpoint->parent = _curPoint;
tmpoint->g = _curPoint->g + 10;
}
}
}
//排序 F值最小的排在前面
sort(_openList.begin(), _openList.end(), mySort);
} while (_openList.size()>0);
cout<<"---can not find way---"<<endl;
return nullptr;
}
//APoint* CAstar::findWay(int beginX, int beginY, int endX, int endY)
//{
//
//
// return nullptr;
//}
int CAstar::getF(APoint *point)
{
return (point->g + getH(point));
}
int CAstar::getH(APoint *point)
{
//曼哈顿城市街区估算法
return (abs(_endPoint->y - point->y) + abs(_endPoint->x - point->x))*10;
}
vector<APoint*> CAstar::getNeighboringPoint(APoint *point)
{
_neighbourList.clear();
// cout<<"nei size:"<<_neighbourList.size()<<endl;
if (point->x < MAX_X-1)
{
if (_allPoints[point->x+1][point->y]->type != AType::ATYPE_BARRIER)
{
_neighbourList.push_back(_allPoints[point->x+1][point->y]);
}
}
if (point->x >0)
{
if (_allPoints[point->x-1][point->y]->type != AType::ATYPE_BARRIER)
{
_neighbourList.push_back(_allPoints[point->x-1][point->y]);
}
}
if (point->y < MAX_Y-1)
{
if (_allPoints[point->x][point->y+1]->type != AType::ATYPE_BARRIER)
{
_neighbourList.push_back(_allPoints[point->x][point->y+1]);
}
}
if (point->y >0)
{
if (_allPoints[point->x][point->y-1]->type != AType::ATYPE_BARRIER)
{
_neighbourList.push_back(_allPoints[point->x][point->y-1]);
}
}
return _neighbourList;
}下面是测试代码：
//
// main.cpp
// Astar
//
// Created by xujw on 15/4/9.
// Copyright (c) 2015年 xujw. All rights reserved.
//
#include <iostream>
#include "CAstar.h"
void printMap(char map[MAX_X][MAX_Y],int width,int height)
{
for (int i = 0; i<width; i++)
{
for (int j = 0; j<height; j++)
{
printf("%c ",map[i][j]);
}
printf("
");
}
}
int main(int argc, const char * argv[]) {
cout<<"---map---"<<endl;
//初始化地图矩阵 0代表障碍
char mapdata[MAX_X][MAX_Y] =
{
{'1','0','0','1','0','1','1','1','1','1'},
{'1','1','1','1','0','1','1','1','1','1'},
{'0','0','0','1','0','1','1','1','1','1'},
{'1','0','0','1','0','1','1','1','1','0'},
{'1','1','1','1','0','1','1','1','1','1'},
{'1','1','0','0','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1'},
{'1','0','0','1','1','1','1','1','1','1'},
{'1','1','0','0','1','1','1','1','1','1'},
{'1','0','1','1','1','1','1','1','1','1'},
};
printMap(mapdata, MAX_X, MAX_Y);
//创建地图
vector< vector<APoint*> > map;
for (int i = 0; i<MAX_X; i++)
{
vector<APoint*> tmp;
for (int j = 0; j<MAX_Y; j++)
{
APoint *point = new APoint();
point->x = i;
point->y = j;
if (mapdata[i][j]=='0')
{
point->type = AType::ATYPE_BARRIER;
}
tmp.push_back(point);
}
map.push_back(tmp);
}
//开始寻路
auto star = new CAstar();
auto point = star->findWay(map[0][0], map[9][9], map);
if (!point)
{
return 0;
}
cout<<"---下面是路径点(倒序)---"<<endl;
while (point)
{
mapdata[point->x][point->y] = '*';
cout<<point->x<<","<<point->y<<endl;
point = point->parent;
}
cout<<"---打印路径---"<<endl;
printMap(mapdata, MAX_X, MAX_Y);
//-------------释放内存----------
delete star;
for (int i = 0; i<MAX_X; i++)
{
for (int j = 10; j<MAX_Y; j++)
{
delete map[i][j];
map[i][j] = nullptr;
}
}
return 0;
}运行截图：
源码下载(使用Xcode可以直接运行):https://github.com/sky068/AStarSearch