A星算法与坦克大战（附源码)

yangwenjia

                                                                                                      A星算法与坦克大战
                              各位中秋快乐  ！  感谢中秋节放假能让我有时间写这么一篇文章
         最近在给自己的坦克大战升级AI  .让坦克具有AI那就要牵扯到自动寻路。寻路里面又分最优路径(距离最短）和最快路径（计算量最少 但可能会绕路）这两种本文都会讲到。第一种主流的就是A*算法了第二种网上叫Best First Search 最佳优先搜索。
          下面就开始讲讲A*理论上的一些东西。这些百度一下很多。但是看了很多都是模糊的理论没有代码，要么就是代码错误BUG一堆没法玩。没办法只能自己动手了。先上一张动图  程序最终样子
                                                     

展示

       在这个图中我们定义了一个[7x8]的矩形空间   起点 Start A点黄色坐标(1,3)    目标点Des B点坐标（5，4）
                                                   
                                                    A*里面最核心的公式  F=G+H；  
       G是什么？ G就是每走一步代价。啥意思呢，就是你给你每走一步定义一个值。以上图  A点四周上下左右随便移动一格就是一步代价A本身G=0。这个值定多少随你。一般方便计算都取10，也就是移动一格G就+10。
                                                  

2

对于八方向的也同理 （本文讲四方向）斜角方向取G值√2倍（正方形的对角线长是边长的√2倍）方便计算一般取14。
       H是什么？,H叫估价函数。也就是起点到A点大概多远估计一下。A*搜索算法是一种启发式算法。之所以叫启发是因为它有一种策略指引它去寻找目标点。而不是像其他算法无目的的全遍历找到目标。这个估算函数怎么表示  有很多种曼哈顿法 欧氏法等。一般都是曼哈顿法。名字高大上 其实就是两个坐标点的 (x相减的绝对值+y相减的绝对值)  两点间的横向距离加上纵向距离   参照这个方法 A到B的H值就是|1-5|+|3-4|=5.一般实际计算时再乘10 和G值配合好计算。看下代码

1. //计算G值，G=从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径
   
2. //参数1 要去的节点
   
3. //参数2  目前在的节点
   
4. int Astar::CalcG(NODE *cur,NODE *pcur)
   
5. {
   
6.         //当前点移动到该点的代价 定义为10
   
7.         if (cur->x== pcur->x || cur->y== pcur->y)
   
8.                 return 10;
   
9.         return 20;
   
10. }

复制代码

1. //估值H  
   
2. //普通曼哈顿法   取(当前点x-目标x 的绝对值) +  (当前点y-目标点y的绝对值)  两者相加乘10
   
3. int Astar::CalcH(NODE *cur)
   
4. {   //控制台画方格是占两个字节 所以这边除以2
   
5.         return ((abs(cur->x - Des.x)/2) + abs(cur->y - Des.y)) * 10;  
   
6. }

复制代码

    好了 现在两者相加我们的F值就有了。我们可以迈出我们第一步了。现在我们来看下一个节点坐标需要哪些属性
                        1.X轴
                        2.Y轴
                        3.F值
                        4.G值
                        5.H值
                        6.父坐标x  
                        7.父坐标y
                        8.方向  .这主要用来给坦克引导方向的
上面提到了父坐标。父坐标是用来溯源的 当我们找到目标点时，需要通过父坐标一步步的找到起点的.  A点起点四周的蓝色点就是它的子节点 也叫扩散点。他们的父坐标就是A点
  我们把上面用到的数据可以定义成一个结构体

1. typedef struct _Node
   
2. {
   
3.         int x;//节点坐标
   
4.         int y;
   
5.         int px; //父坐标
   
6.         int py;
   
7.         int dir;//方向
   
8.         int f;  //F值
   
9.         int g;//G值
   
10.         int h;//H值
    
11. }NODE,*PNODE;

复制代码

同时我们准备两个空间 一个叫open表  一个叫close表 。可以把他们看作是可以存放结构体的数组。
   close表就是当前点，就是以这个点作为基点向四周扩散的点。也叫父节点。比如我们的起点，他的父节点就是自身。它四周的点的父坐标就是它。被加入这个表的节点就不会再被用来扩散了。所以叫关闭表 关在里面了
   open表就是以当前点向外扩散的四个方向的点。这些个点需要被处理一下再加入这个列表。
    怎么处理？  我们需要判断这个扩散点是不是障碍物 是不是边界  是不是在Close表中。是不是终点  是不是已经在open表中了                    
                      如果是边界 /障碍物/以及Close表我们就忽略这个点。
                      如果这个点不在open表中那么就需要加入到open表中。如果在open表中那么要重新计算  它的G值(后面再讲)
                                                     
                                起点A四周的点我们进行计算：  上G=10  H=(|1-5|+|2-4|)*10=60 F=70
                                                                               下G=10  H=(|1-5|+|4-4|)*10=40 F=50
                                                                                左G=10  H=(|0-5|+|3-4|)*10=60 F=70
                                                                                 右G=10  H=(|2-5|+|3-4|)*10=40 F=50
                               由于这几个点都满足加入open表的条件，所以都被加入了open表  。现在对这个open表按F值的大小进行排序。选出最小F点 作为下个当前点. 这里出现了两个F值一样。按就近原则选择最后加入的 右边这个点。把它加入到Close表中，同时在Open表中删除它。我们用绿色标记下这个点。再以这个点作为当前点向四周扩散搜索。下图中红箭头代表指向它的父节点。
                                                                              

4

以这个点拓展搜索发现左右一个是起点已经在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表。继续重复上面的搜索
                                                                     

5

     


（2，4）这个点搜索到左边这个点时，发现已经在open表中了 这时我们要重新计算G值。如果这个点到左边的G值+自身的G值，比左边这个点原来的G值要小那么说明从这里走更近 需要更新他的G值并且把左边这个点的父坐标指向（2，4）这个点。如果大于原G值那就不改变 用代码表示下

1. if (CalcG(cur, pcur) + pcur->g < old->g)//当前点移动到搜索点的G+上当前点的G值  是不是比原搜索点G值小   如果大就不动
   
2.              {//更新父坐标
   
3.                  old->px = pcur->x;//就把当前这个点作为他的父坐标
   
4.                  old->py = pcur->y;
   
5.                  //更新G值为目前新值                                               
   
6.                  old->g = CalcG(cur, pcur) + pcur->g;                                       
   
7.                  old->f = old->g + old->h;//更新F值
   
8.                  //更新方向值
   
9.                  old->dir = cur->dir;
   
10.                }
    

复制代码

                                                        

6

如果搜索中发现了目标点，那么。把目标点加入close,并指示目标点的父坐标为这个点并退出循环  。
我门从尾部开始遍历这个close表。一级级的查找父坐标 直到找到起始点 就形成了路径。并且是最端路径。很多时候最短路径并不是唯一的，看各自的算法实现了。
我们通过这个网站http://www.webhek.com/post/pathfinding.html演示我们是否正确  结果基本一致
                                                        

7

那好现在路径有了 在结构体中还有个方向数据dir 。当我们上下左右移动时 分别赋值0，1，2，3。当父坐标更新时这个值也需要更新

1. //根据当前点 遍历周边4点  //不考虑斜向
   
2.                         CUR->y -= 1;  
   
3.                         CUR->dir = 0;//上
   
4.                         if (FindPoint(map, CUR, &Cur)) //从当前节点Cur 搜索CUR
   
5.                         {
   
6. 
   
7.                                 break;//是终点直接退出循环
   
8.                         }

复制代码

好了 最终找到目标点时路径上每走一步的方向也有了。把它传给我们的坦克类去实现移动就行了.
里面还有个算法是Best First Search,也叫局部最优法。对于公式F=G+H。他的G就不起作用了。可以没有。完全按照H值去引导它。所以每走一步，排序四周H最小值。再选择这个点继续。它的G值就不再增加。所以每走一步都是局部判断最小值。这个算法特点是 计算的点少。效率高，但不是最短路径，可能会绕路。

1. //G值计算
   
2.                                         if (A)
   
3.                                                 cur->g = CalcG(cur, pcur) + pcur->g;  //G值会一直增加 是A*算法
   
4.                                         else
   
5.                                             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不能运行请根据自己环境自行编译

游客，如果您要查看本帖隐藏内容请回复

yangwenjia

帖子还在编辑。不小心点了发送- -！

yangwenjia

好吧可以了

quark

谢谢大神分享，学习中。。。

零度非安全

感谢分享！

98765mm

厉害了,得学习学习

小燕朕

厉害

CalvinMcCain

楼主高明，赞一个

lukeigun

谢谢分享,加油！

hgsxwd

。。

zhangguangtao

好好学习一下

xujiahua

感谢分享

980151318

tql

15002406463

感谢分享

啊哈哈哈哈啊哈

厉害啊

wz889

学习学习！

kkk888

求求求！

Rebeccanana

感谢楼主分享qwq

qiuky_2019

很有帮助，谢谢！

月河之水

你好，我要下载的源码