随着3D游戏的日趋流行,在复杂的3D游戏环境中如何能使非玩家控制角色准确实现自动寻路功能成为了3D游戏开
发技术中一大研究热点。其中A算法得到了大量的运用，A算法较之传统的路径规划算法;实时性更高、灵活性更强,寻路
结果更加接近人工选择的路径结果.A*寻路算法并不是找到最优路径，只是找到相对近的路径，因为找最优要把所有可行
路径都找出来进行对比，消耗性能太大，寻路效果只要相对近路径就行了。
寻路算法有深度优先搜索算法和广度优先搜索算法，不断根据自定义方向按照规定的方向不断的扫描，当扫描到终点后才能返回路径，但是有个更高效的寻路算法A*
A*算法主要是根据G、H、F三个重要的东西查找最好的路径
G:从起点到达当前已经走到的路径的距离长度
H：当前位置距离终点有多远（一般采用欧几里得求解两点距离，求当前位置的点到终点的距离就是H值）
F = G + H
图解如下：
准备两个表
openList和closeList
openList：待定选择的点，可能的路径的点
closeList：确定路径的点
伪算法：
1.开始起始位置，存放在openList中
while( openList != NULL) {
1.从openList获取最小F点坐标
2.将该点从openList删除
3.将该点加入到closeList中
4.查找该点周围满足条件的点
满足条件： 1. 没有超过地图边界
2. 不是墙壁
3. 不是已经走过的路径
for(遍历满足条件的点) {
if（判断这些点是否在openList中） {
1.计算G、H、F
2.添加到openList中
}
}
if（判断终点是否在closeList中）
返回终点
}
最终根据终点去查找前面一个点，前面一个点去查找它前面一个点，直到到达起点
代码调试 起点坐标(6,8) 终点坐标(13,10)
接着返回最小的F值，由于是起点所以就是起点坐标 (6,8)
接着根据当前起点的坐标查找周围的格子，前提是满足条件的格子
这些周围的格子满足条件：
此时起点的周围点四个点都可以通过
通过函数搜索返回四个点的坐标如下
接着for遍历周围的点，判断这些点是否在开区间内，如果不在，就计算该点的G,H,F值
G值就是起始点到当前点的路径，一格表示10
H值就是当前点到终点的欧几里得两点距离公式计算根号(x2-x1)的平方 – (y2-y1)的平方得到两点距离就是H值，接着F = G + H得到90
接着将该点存入到openList中去
其他3个点也这样计算，最终openList表里面存储了起点的周围四个点，并且这些点都计算了G,H,F值
计算完后，选择最小的F的点作为需要走的路径的点
所以第一次选择坐标7，8的点，后面的走法跟这个一样
比如第一次从起始点开始选择，起始点上下左右四个方向，计算好G，H，F值后存入openList中，最终openlist存放了点(5,8)(7,8)(6,7)(6,9),第二次从openList待定点去查找F最小的是哪一个点，接着将该点作为起始点,查找该点四个方向同时计算该点的上下左右四个方向的点的GFH值，然后计算好后继续存入到openList中，等待第三次循环查找F最小的是哪一个点。然后将F最小的点存入closeList中，每次循环结束后，需要判断终点的坐标是否在closeList中，如果不在就继续找，直到最终终点存入到closelist中就结束，return closelist
本次程序采用链表，当起始点查找到了最小的F的点后，该点的指针域存储起始点
寻路步骤
1.从起点开始，把它作为待处理的方格存入一个预测可达的节点列表,简称openList，即把起点放入"预测可达节点列表”，可达节点列表openList就是一个等待检查方格的列表。
2.寻找openList中F值最小的点min (一开始只有起点)周围可以到达的方格（可到达的意思是其不是障碍物，也不存在关闭列表中的方格,即不是已走过的方格)。计算min周围可到达的方格的F值。将还没在openList 中点放入其中，并设置它们的"父方格"为点min,表示他们的上一步是经过min到达的。如果min下一步某个可到达的方格已经在openList列表那么并且经min点它的F值更优,则修改F值并把其"父方格"设为点min,
3.把2中的点min从"开启列表"中删除并存入"关闭列表"closeList 中, closeList中存放的都是不需要再次检查的方格。如果2中点min 不是终点并且开启列表的数量大于零，那么继续从第2步开始。如果是终点执行第4步，如果openList列表数量为零，那么就是找不到有效路径。
4.如果第3步中min是终点，则结束查找，直接追溯父节点到起点的路径即为所选路径。
main.cpp
#include <iostream>
#include <graphics.h>
#include "Astar.h"
using namespace std;
int width = lines * 80;
int height = cols * 40;
int maze[18][20] = //迷宫对应的二维数组，使用一级指针表示
{ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 2, 2, 2, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 },
{ 0, 2, 2, 2, 2, 2, 0, 0, 0, 2, 2, 2, 2, 2, 0, 2, 0, 2, 2, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 2, 0 },
{ 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
int cols = 20; //二维数组对应的列数
int lines = 18; //二维数组对应的行数
IMAGE img[4];
//初始化资源
void init() {
loadimage(&img[0], "res//wall2.jpg", 80, 40);
loadimage(&img[1], "res//start.png", 80, 40);
loadimage(&img[2], "res//end.png", 80, 40);
loadimage(&img[3], "res//空地.png", 80, 40);
}
int Count = 0; //设置起点和终点标志 0表示设置起点位置 1表示设置终点位置
//画地图
void draw() {
auto msg = GetMouseMsg(); //获得鼠标点击消息
char s[12];
char s1[12];
//判断是否鼠标左键单机 并且 该位置是否是有效的点击位置
if (Count != 2) {
if (msg.uMsg == WM_LBUTTONDOWN)
{
int row = msg.y / 40;
int col = msg.x / 80;
//设置终点位置
if (Count == 1) {
maze[col][row] = 3;
Count++;
/*sprintf(s, "[%d,%d]", msg.x, msg.y);
sprintf(s1, "[%d,%d]", row, col);
outtextxy(0, 0, s);
outtextxy(100, 0, s1);*/
}
//设置起点位置
if (Count == 0) {
maze[col][row] = 1;
Count++;
/*sprintf(s, "[%d,%d]", msg.x, msg.y);
sprintf(s1, "[%d,%d]", row, col);
outtextxy(0, 0, s);
outtextxy(100, 0, s1);*/
}
}
}
for (int i = 0; i < lines; i++) {
for (int j = 0; j < cols; j++) {
if (maze[i][j] == 1) { //起点
putimage(i * 80, j * 40, &img[1]);
}
else if (maze[i][j] == 3) {
putimage(i * 80, j * 40, &img[2]); //终点
}
if (maze[i][j] == 2) {
putimage(i * 80, j * 40, &img[0]);
}
if (maze[i][j] == 0) {
putimage(i * 80, j * 40, &img[3]);
}
}
}
}
//设置起点和终点位置
vector<Point> FindPath() {
vector<Point> Path;
Point strat; //起始点
for (int i = 0; i < lines; i++) {
for (int j = 0; j < cols; j++) {
if (maze[i][j] == 1) { //起点
strat.x = i;
strat.y = j;
Path.push_back(strat);
}
if (maze[i][j] == 3) {
strat.x = i;
strat.y = j;
Path.push_back(strat);
}
}
}
return Path;
}
//清除
void clear(vector<Point> path) {
vector<Point>::iterator it;
for (it = path.begin(); it != path.end();) {
maze[(*it).x][(*it).y] = 0;
it = path.erase(it);
}
}
//清除地图路径
void clear_draw(vector<Point>& set, list<Point*>& path) {
Count = 0;
path.clear();
clear(set); //清除地图
set.clear();
}
int main() {
init();
//初始化窗口大小
initgraph(width, height);
//开始绘制
BeginBatchDraw();
//InitAstarMaze(cols, lines); //初始化地图行和列
while (1) {
//清屏
cleardevice();
vector<Point> set; //临时存储起始点 和终点 以及路径
if (Count == 2)
set = FindPath(); //获取起点和终点位置
Point p;
if (Count == 2) {
auto path = GetPath(&set.front(), &set.back()); //获取从起点到终点的路径
path.pop_back(); //删除末尾元素
if (!path.empty()) {
//绘制路径
for (list<Point*>::iterator it = path.begin(); it != path.end(); it++) {
maze[(*it)->x][(*it)->y] = 1;
//保存路径到set
p.x = (*it)->x;
p.y = (*it)->y;
set.push_back(p);
}
draw(); //绘制地图
FlushBatchDraw(); //绘图输出
system("pause");
clear_draw(set, path); //清除地图路径
}
}
draw(); //绘制地图
FlushBatchDraw(); //绘图输出
}
return 0;
}
Astra.cpp
#pragma once
#include <math.h>
#include "Astar.h"
#include <iostream>
static std::list<Point*> openList; //开放列表
static std::list<Point*> closeList; //关闭列表
static Point* findPath(Point& startPoint, Point& endPoint, bool isIgnoreCorner);
static std::vector<Point*> getSurroundPoints(const Point* point);
static bool isCanreach(const Point* point, const Point* target); //判断某点是否可以用于下一步判断
static Point* isInList(const std::list<Point*>& list, const Point* point); //判断开启/关闭列表中是否包含某点
static Point* getLeastFpoint(); //从开启列表中返回F值最小的节点
//计算FGH值
static int calcG(Point* temp_start, Point* point);
static int calcH(Point* point, Point* end);
static int calcF(Point* point);
/*分配节点*/
Point* AllocPoint(int x, int y) {
Point* temp = new Point;
memset(temp, 0, sizeof(Point));//初始值清零
temp->x = x;
temp->y = y;
return temp;
}
/*初始化A*搜索的地图*/
void InitAstarMaze( int _lines, int _colums)
{
//maze = _maze;
lines = _lines;
cols = _colums;
}
/*清理地图，并释放资源*/
void ClearAstarMaze() {
//maze = NULL;
//lines = 0;
//cols = 0;
std::list<Point*>::iterator itor;
//清除openList 中的元素
for (itor = openList.begin(); itor != openList.end();) {
//delete* itor;
itor = openList.erase(itor);
}
//清理closeList 中的元素
for (itor = closeList.begin(); itor != closeList.end();) {
//delete* itor;
itor = closeList.erase(itor);
}
}
/*计算节点的G值*/
static int calcG(Point* temp_start, Point* point)
{
int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? kCost1 : kCost2;
int parentG = (point->parent == NULL ? NULL : point->parent->G); //如果是初始节点，则其父节点是空
return parentG + extraG;
}
static int calcH(Point* point, Point* end)
{
//用简单的欧几里得距离计算H，可以用多中方式实现
return (int)sqrt((double)(end->x - point->x) * (double)(end->x - point->x) + (double)(end->y - point->y) * (double)(end->y - point->y)) * kCost1;
}
/*计算节点的F值*/
static int calcF(Point* point)
{
return point->G + point->H;
}
/*从开放列表中查找最小F值的节点*/
static Point* getLeastFpoint()
{
if (!openList.empty())
{
auto resPoint = openList.front();
std::list<Point*>::const_iterator itor;
for (itor = openList.begin(); itor != openList.end(); itor++) {
if ((*itor)->F < resPoint->F)
resPoint = *itor;
}
return resPoint;
}
return NULL;
}
/*搜索从起点到终点的最佳路径*/
Point* findPath(Point* startPoint, Point* endPoint)
{
openList.push_back(AllocPoint(startPoint->x, startPoint->y)); //置入起点,拷贝开辟一个节点，内外隔离
while (!openList.empty())
{
auto curPoint = getLeastFpoint(); //找到F值最小的点
//std::cout<<"--找到最小的点: G="<<curPoint->G<<" F="<<curPoint->F<<" "<<curPoint->H<<std::endl;
//system("pause");
openList.remove(curPoint); //从开启列表中删除
closeList.push_back(curPoint); //放到关闭列表
//1. 找到当前周围四个格中可以通过的格子
auto surroundPoints = getSurroundPoints(curPoint);
//std::cout<<"Point 数目："<<surroundPoints.size()<<std::endl;
std::vector<Point*>::const_iterator iter;
for (iter = surroundPoints.begin(); iter != surroundPoints.end();)
{
Point* target = *iter;
//std::cout<<"周围的点： x="<<target->x<<" y="<<target->y<<std::endl;
//2,对某一个格子，如果它不在开放列表中，加入到开启列表，设置当前格为其父节点，计算F G H
Point* exist = isInList(openList, target);
if (!exist)
{
target->parent = curPoint;
target->G = calcG(curPoint, target);
target->H = calcH(target, endPoint);
target->F = calcF(target);
openList.push_back(target);
iter++;
}
//3，对某一个格子，它在开放列表中，计算G值, 如果比原来的大, 就什么都不做, 否则设置它的父节点为当前点,并更新G和F
else
{
/*int tempG = calcG(curPoint, target);
if (tempG < target->G)
{
exist->parent = curPoint;
exist->G = tempG;
exist->F = calcF(target);
}*/
//delete* iter;
iter = surroundPoints.erase(iter);
}//end else
}
//end for
surroundPoints.clear();
Point* resPoint = isInList(closeList, endPoint);
if (resPoint) {
return resPoint; //返回列表里的节点指针，不要用原来传入的endpoint指针，因为发生了深拷贝
}
}
return NULL;
}
std::list<Point*> GetPath(Point* startPoint, Point* endPoint)
{
Point* result = findPath(startPoint, endPoint);
std::list<Point*> path;
//返回路径，如果没找到路径，返回空链表
while (result)
{
path.push_front(result);
result = result->parent;
}
ClearAstarMaze(); //清除 openList closeList
return path;
}
static Point* isInList(const std::list<Point*>& list, const Point* point)
{
//判断某个节点是否在列表中，这里不能比较指针，因为每次加入列表是新开辟的节点，只能比较坐标
std::list<Point*>::const_iterator itor;
for (itor = list.begin(); itor != list.end(); itor++) {
if ((*itor)->x == point->x && (*itor)->y == point->y) {
return *itor;
}
}
return NULL;
}
bool isCanreach(const Point* point, const Point* target)
{
if (target->x<0 || target->x>(lines - 1)
|| target->y<0 || target->y>(cols - 1)
// || (maze[target->x * cols + target->y] == 1)
// || maze[target->x * cols + target->y] == 2
|| maze[target->x][target->y] == 2
|| (target->x == point->x && target->y == point->y)
|| isInList(closeList, target)) //如果点与当前节点重合、超出地图、是障碍物、或者在关闭列表中，返回false
return false;
else
{
if (abs(point->x - target->x) + abs(point->y - target->y) == 1) { //非斜角可以
//std::cout<<"--点可达: x="<<point->x<<" y="<<point->y<<std::endl;
return true;
}
else
{
return false;
}
}
}
/*获取当前点周边可走通的节点*/
std::vector<Point*> getSurroundPoints(const Point* point)
{
std::vector<Point*> surroundPoints;
for (int x = point->x - 1; x <= point->x + 1; x++) {
for (int y = point->y - 1; y <= point->y + 1; y++) {
Point* temp = AllocPoint(x, y);
if (isCanreach(point, temp)) {
surroundPoints.push_back(temp);
}
}
}
return surroundPoints;
}
//程序 = 数据结构 + 算法
Astar.h
#pragma once
#include <vector>
#include <list>
extern int maze[][20]; //迷宫对应的二维数组，使用一级指针表示
extern int cols; //二维数组对应的列数
extern int lines; //二维数组对应的行数
const int kCost1 = 10; //直移一格消耗
const int kCost2 = 14; //斜移一格消耗
typedef struct _Point
{
int x, y; //点坐标，这里为了方便按照C++的数组来计算，x代表横排，y代表竖列
int F, G, H; //F=G+H
struct _Point* parent; //parent的坐标
}Point;
// void InitAstar(int *_maze, int _lines, int _colums);
Point* AllocPoint(int x, int y);
void InitAstarMaze(int _lines, int _colums);
std::list<Point*> GetPath(Point* startPoint, Point* endPoint);
void ClearAstarMaze();
运行结果：
