A星算法与坦克大战（附源码)
本帖最后由 yangwenjia 于 2018-9-25 07:54 编辑A星算法与坦克大战
各位中秋快乐！感谢中秋节放假能让我有时间写这么一篇文章
最近在给自己的坦克大战升级AI.让坦克具有AI那就要牵扯到自动寻路。寻路里面又分最优路径(距离最短）和最快路径（计算量最少 但可能会绕路）这两种本文都会讲到。第一种主流的就是A*算法了第二种网上叫Best First Search 最佳优先搜索。
下面就开始讲讲A*理论上的一些东西。这些百度一下很多。但是看了很多都是模糊的理论没有代码，要么就是代码错误BUG一堆没法玩。没办法只能自己动手了。先上一张动图程序最终样子
在这个图中我们定义了一个的矩形空间 起点 Start A点黄色坐标(1,3) 目标点Des B点坐标（5，4）
A*里面最核心的公式F=G+H；
G是什么？ G就是每走一步代价。啥意思呢，就是你给你每走一步定义一个值。以上图A点四周上下左右随便移动一格就是一步代价A本身G=0。这个值定多少随你。一般方便计算都取10，也就是移动一格G就+10。
对于八方向的也同理 （本文讲四方向）斜角方向取G值√2倍（正方形的对角线长是边长的√2倍）方便计算一般取14。
H是什么？,H叫估价函数。也就是起点到A点大概多远估计一下。A*搜索算法是一种启发式算法。之所以叫启发是因为它有一种策略指引它去寻找目标点。而不是像其他算法无目的的全遍历找到目标。这个估算函数怎么表示有很多种曼哈顿法 欧氏法等。一般都是曼哈顿法。名字高大上 其实就是两个坐标点的 (x相减的绝对值+y相减的绝对值)两点间的横向距离加上纵向距离 参照这个方法 A到B的H值就是|1-5|+|3-4|=5.一般实际计算时再乘10 和G值配合好计算。看下代码
//计算G值，G=从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径
//参数1 要去的节点
//参数2目前在的节点
int Astar::CalcG(NODE *cur,NODE *pcur)
{
//当前点移动到该点的代价 定义为10
if (cur->x== pcur->x || cur->y== pcur->y)
return 10;
return 20;
}
//估值H
//普通曼哈顿法 取(当前点x-目标x 的绝对值) +(当前点y-目标点y的绝对值)两者相加乘10
int Astar::CalcH(NODE *cur)
{ //控制台画方格是占两个字节 所以这边除以2
return ((abs(cur->x - Des.x)/2) + abs(cur->y - Des.y)) * 10;
}
好了 现在两者相加我们的F值就有了。我们可以迈出我们第一步了。现在我们来看下一个节点坐标需要哪些属性
1.X轴
2.Y轴
3.F值
4.G值
5.H值
6.父坐标x
7.父坐标y
8.方向.这主要用来给坦克引导方向的
上面提到了父坐标。父坐标是用来溯源的 当我们找到目标点时，需要通过父坐标一步步的找到起点的.A点起点四周的蓝色点就是它的子节点 也叫扩散点。他们的父坐标就是A点
我们把上面用到的数据可以定义成一个结构体
typedef struct _Node
{
int x;//节点坐标
int y;
int px; //父坐标
int py;
int dir;//方向
int f;//F值
int g;//G值
int h;//H值
}NODE,*PNODE;
同时我们准备两个空间 一个叫open表一个叫close表 。可以把他们看作是可以存放结构体的数组。
close表就是当前点，就是以这个点作为基点向四周扩散的点。也叫父节点。比如我们的起点，他的父节点就是自身。它四周的点的父坐标就是它。被加入这个表的节点就不会再被用来扩散了。所以叫关闭表 关在里面了{:10_264:}
open表就是以当前点向外扩散的四个方向的点。这些个点需要被处理一下再加入这个列表。
怎么处理？我们需要判断这个扩散点是不是障碍物 是不是边界是不是在Close表中。是不是终点是不是已经在open表中了
如果是边界 /障碍物/以及Close表我们就忽略这个点。
如果这个点不在open表中那么就需要加入到open表中。如果在open表中那么要重新计算它的G值(后面再讲)
起点A四周的点我们进行计算：上G=10H=(|1-5|+|2-4|)*10=60 F=70
下G=10H=(|1-5|+|4-4|)*10=40 F=50
左G=10H=(|0-5|+|3-4|)*10=60 F=70
右G=10H=(|2-5|+|3-4|)*10=40 F=50
由于这几个点都满足加入open表的条件，所以都被加入了open表。现在对这个open表按F值的大小进行排序。选出最小F点 作为下个当前点. 这里出现了两个F值一样。按就近原则选择最后加入的 右边这个点。把它加入到Close表中，同时在Open表中删除它。我们用绿色标记下这个点。再以这个点作为当前点向四周扩散搜索。下图中红箭头代表指向它的父节点。
以这个点拓展搜索发现左右一个是起点已经在Close列表中了。一边时障碍物。所以只剩上下两个点能加入open表 再计算这两个点的F值 .以当前点走到上边的点代价是10再加上当前点本身的G值就是这个点的G值
上 G=10+10=20 H=50 F=70
下 G=10+10=20 H=30 F=50
再次对open表排序 取F最小值。又有两个一样的，再以就近原则 把下面这个点作为当前点标记为绿色 移除open表，加入close表。继续重复上面的搜索
（2，4）这个点搜索到左边这个点时，发现已经在open表中了 这时我们要重新计算G值。如果这个点到左边的G值+自身的G值，比左边这个点原来的G值要小那么说明从这里走更近 需要更新他的G值并且把左边这个点的父坐标指向（2，4）这个点。如果大于原G值那就不改变 用代码表示下
if (CalcG(cur, pcur) + pcur->g < old->g)//当前点移动到搜索点的G+上当前点的G值是不是比原搜索点G值小 如果大就不动
{//更新父坐标
old->px = pcur->x;//就把当前这个点作为他的父坐标
old->py = pcur->y;
//更新G值为目前新值
old->g = CalcG(cur, pcur) + pcur->g;
old->f = old->g + old->h;//更新F值
//更新方向值
old->dir = cur->dir;
}
如果搜索中发现了目标点，那么。把目标点加入close,并指示目标点的父坐标为这个点并退出循环。
我门从尾部开始遍历这个close表。一级级的查找父坐标 直到找到起始点 就形成了路径。并且是最端路径。很多时候最短路径并不是唯一的，看各自的算法实现了。
我们通过这个网站http://www.webhek.com/post/pathfinding.html演示我们是否正确结果基本一致
那好现在路径有了 在结构体中还有个方向数据dir 。当我们上下左右移动时 分别赋值0，1，2，3。当父坐标更新时这个值也需要更新
//根据当前点 遍历周边4点//不考虑斜向
CUR->y -= 1;
CUR->dir = 0;//上
if (FindPoint(map, CUR, &Cur)) //从当前节点Cur 搜索CUR
{
break;//是终点直接退出循环
}
好了 最终找到目标点时路径上每走一步的方向也有了。把它传给我们的坦克类去实现移动就行了.
里面还有个算法是Best First Search,也叫局部最优法。对于公式F=G+H。他的G就不起作用了。可以没有。完全按照H值去引导它。所以每走一步，排序四周H最小值。再选择这个点继续。它的G值就不再增加。所以每走一步都是局部判断最小值。这个算法特点是 计算的点少。效率高，但不是最短路径，可能会绕路。
//G值计算
if (A)
cur->g = CalcG(cur, pcur) + pcur->g;//G值会一直增加 是A*算法
else
cur->g = CalcG(cur,pcur);//此G值不会增加 局部计算相当于A算法 非A*
总结：
1. 初始化参数
起始点start
终点Des
h值
g值
f值
方向
开启列表open
关闭列表close
2. 程序主体
将起始点start加入开启列表open
重复一下工作
○ 寻找开启列表open中F值最小的节点，设为当前点current
○ 开启列表open中移出当前点current
○ 关闭列表open中加入当前点current
○ 对当前点的每一个相邻点判断
§ 如果它不可通过或者已经在关闭列表中，略过。否则：
§ 如果它不在开启列表中，加入开启列表中
§ 如果在开启列表中，G值判定，若此路径G值比之前路径小，则此相邻点的父节点为当前点，同时更新G与F值。反之，则保持原来的节点关系与G、F值。
○ 当目标点Des在开启列表中，则结束程序，此时有路径生成，此时由Des节点开始逐级追溯上一级父节点，直到追溯到开始节点start，此时各节点即为路径。
当开启列表为空，则结束程序，此时没有路径
源码中的open 和close 表 是通过vector容器实现了。不了解的同学可以看作动态数组可以根据加入数据扩大
开发环境VS2017.如果exe不能运行请根据自己环境自行编译
**** Hidden Message ***** 帖子还在编辑。不小心点了发送- -！ 好吧可以了{:9_227:} 谢谢大神分享，学习中。。。 感谢分享！ 厉害了,得学习学习 厉害 楼主高明，赞一个 谢谢分享,加油！ 。。 好好学习一下 感谢分享 tql 感谢分享 厉害啊 学习学习！
求求求！ 感谢楼主分享qwq 很有帮助，谢谢！ {:5_103:}你好，我要下载的源码
页:
[1]
2