基础 | 图与路径查找----A*算法
本系列为笔者初学c/c++和游戏AI开发的学习过程，算法为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),若有错误请在评论区留下批评意见。
语言：c/c++ (11及以上)
平台：macOS mojave
编辑器/编译器：vs Code / g++
图与路径查找
三、A*算法
Patrick Lester在2005年的一篇论文中详细讲解了A*算法的原理，这篇论文应该算是该算法最好的讲解了，所以笔者在这里也就不再赘述，直接结合工程实现来讲解。
读者也可以直接到到文章出处看原文：
https://www.cnblogs.com/alex-tech/archive/2012/03/09/2387908.html 论文翻译
http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf 论文地址
3.1 搜索区域
在游戏中，我们通常会用方格或者多边形来分隔地图，这些格子表示一个个不同的区域，可以放置资源，或者让角色通过。
全部的方格便构成了一个搜索区域，寻路算法在这个简化的区域内去寻找路径。路径被描述为从A到B经过的方块的集合。
这些方格在数学模型中也被称为节点。
如下图，假设我们想要从绿色的方块移动到红色的方块，中间隔了一堵蓝色的墙：
3.2 开始搜索
简单来讲，A*算法也是启发式算法的一种，通过不断向外扩展搜索未接触过的节点，来抵达目标。
步骤一：
做如下开始搜索：
从点A开始，并且把它作为待处理点存入一个“开启列表”。OpenList存储待搜索的方格。
寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格，并把它们放入开启列表。
从开启列表中删除点A，把它加入到一个“关闭列表”，ClosedList列表中保存所有不需要再次检查的方格。
步骤二：
依据“路径评分F”从“开启列表”中取出一个方格。我们选取的是F值最小的那个方格。
所谓的F是如下公式：
F = G + H
其中：
G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
H = 从网格上那个方格移动到终点B的预估移动耗费。
当前方格的 G = 上一个方格的G + 上一个方格到当前方格的移动耗费，通常我们令水平或垂直移动的耗费为10，对角线的耗费为14。
当前方格的 H = 当前方格到目标方格的曼哈顿距离，从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向，忽略一切障碍物。
经过这个步骤，你应该得到如下图所示的结果：
从图上我们可以看到，F值最小的是绿色方格右边那个方格，F = 40，G = 10， H = 30
步骤三：
对选中的方格，我们做以下操作：
把它从开启列表中删除，然后添加到关闭列表中。
检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无法通过的地形)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。
如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。如果不是，那就什么都不做。如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格。最后，重新计算F和G的值。
接着，检查开启列表，选择其中F值最低的那个格子。如果有F值相同的点，随便选哪个都可以。
最后，重复以上几个小步骤，直到找到目标方格即可。
3.3 A*算法总结
整个A*算法可以归纳成以下的逻辑步骤：
把起始格添加到开启列表。
重复如下的工作：
寻找开启列表中F值最低的格子。我们称它为当前格。
把它切换到关闭列表。
对其相邻的8格中的每一个？
如果它不可通过或者已经在关闭列表中，略过它。反之如下。
如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
停止，当你
把目标格添加进了关闭列表(注解)，这时候路径被找到，或者
没有找到目标格，开启列表已经空了。这时候，路径不存在。
3. 保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
3.3 A*算法实现
因为我们是在另一个类中调用A*算法来计算路径，所以我们额外需要：
setMaze（）：每次计算的时候都要重置地图
GetPath（）：返回计算出来的路径列表，并将其坐标转换为世界坐标。
getSearchPath（）：返回所有搜索过的方格，包括被丢弃不用的那些方格，其实就是 closeList。
因为对于计算机来说，二维数组是最方便的计算方式，所以我们会将世界地图上的方格坐标转换为二维数组中相对应的坐标。
智能指针Point和世界地图上的方格一一对应，保存着一个父节点和子节点。
A*算法的主体实现起来十分的简单，这也是这个算法如此流行的原因，简单而又强大，不需要太复杂的修改就能适应多种场合。
其他细节可以到仓库中下载代码查看，直接阅读代码是最好的学习方式，更能加深理解。
如果读者已经正确安装好了SFML和其他工具，只需要make就可以直接运行了。
3.3 A*算法演示
视频中，黄色是起始节点，红色是目标节点，黑色为墙壁，绿色为全部查找节点，蓝色为查找路径：
