参考：http://blog.csdn.net/qq_34446253/article/details/51427423
http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
http://blog.csdn.net/qq_35653247/article/details/52335088
http://www.skywind.me/maker/astar.htm
https://www.cnblogs.com/flash3d/archive/2013/02/04/2891915.html
http://blog.csdn.net/silangquan/article/details/40516625?utm_source=tuicool&utm_medium=referral
http://blog.csdn.net/z824074989y/article/details/78486539
http://blog.csdn.net/qq_34446253/article/details/51427423
A*搜索算法是一种启发性的算法，根据现在到达位置的步数以及之后的“估计步数”，即f=g+h，f是整个起点到终点的代价，g是从起点到我们目前位置的步数，而h是从目前位置到达终点的估计值。
一般具体实现分为以下几步：
一个open表，一个close表；首先open表存储起点，然后开始，把起点放入close表中，检测该点周围点的f值（g+h，g已知，h为本点到终点的横纵索引差估计而来），然后按照f值，把这些点放入open表中，并且根据f值进行堆排序，其中最小f值点 放入close中，继续循环，直到找到终点位置。
A*算法大致意思如上所示，但是为了更好地理解，以及与别人交流，还是需要了解A*算法一些概念以及知识。
一、A*算法背景
A*算法是一种静态路网中求解最短路径最有效的直接搜索方法（是最有效的直接搜索算法）
二、A*算法的一些概念
学习A*之前，先学习一下其他概念，有助于理解A*。
启发式搜索：就是每一次搜索时，对每一个位置进行评估，获得最好的位置，再从这个位置进行搜索直达目标（之所以叫做启发，是因为会在搜索到的位置中选取一个好的位置作为下一次搜索的起点）。在启发式搜索中，对位置的评估估价是十分重要的。
估价函数：从当前节点移动到目标节点的预估费用。
A*算法与BFS：BFS算法是A*算法的一个特例。对于每一个BFS算法，从当前节点扩展出来的每一个节点，都要放进队列中进行进一步扩展，也就是说BFSDE估价函数永远等于0.
选取最小估价：数据结构中？对于每次都要选取最小估价的节点，应该用到最小优先级队列（也叫最小二叉堆）。在C++的STL里右现成的数据结构priority_queue，可以直接使用，当然不要忘记重载自定义节点的比较操作符。
三、A*算法的理论
公式：f（n）=g（n）+h（n）
其中，f是从初始状态经由状态n到目标状态的代价估计，
g（n）是在状态空间中从出事状态到状态n的实际代价，
h（n）是从状态n到目标状态的最佳路径的估计代价。
（这里，代价的意思是花费的代价，对于路径搜索问题，路程就是代价，我们关心走过的路程）
这个公式关键的地方时在与估价函数的选取，即h（n）的选取
四、A*算法的具体一些操作
A*是启发式搜索加动态规划，具体的实现主要依靠两个队列open队列和close队列，从一点开始探索几个相邻的格子，然后评价G值即起点到该点的值，按从小到大排列在open队列中，再从中取出最小f值的点，把这个点提取出来放到close中，再次把这个点周围的点进行分析，能排入的就排入到open表中，值得注意的是，这些点中有的不能抵达，有的是open中以及存在的，对于已经存在的点，需要判断G值，是增加了还是减少了，如果增加了，这个点就不改变，如果减少了，说明这条路径的实际代价更少，那么将这点的父节点改为刚刚加入close中的那个点，重复以上过程，一直到目标点出现。
上面这个过程是抽象的思考，实际的实现中要进行一些操作才行。
比如：定义一个类，取个名AstarPoint吧，有私有变量，存有点的坐标，以及该坐标下，对应的F、G、H等代价值，还有父节点Fid的值（一般装父节点在队列中的序号）。大概这几个值就差不多够用了。
然后再定义一个类，用来寻找路径，输入地图，当前坐标，目的坐标，就可以计算了；
这里面比较关键的地方有一下几点：
每一个节点都要计算当前的G与H
1、代价G的计算：
根据当前的坐标相对于父节点的位置的代价，父节点的代价G，两个代价值相加即可。
2、估价H的计算：
这个最关键，H使用不同的启发式算法有几种，比如曼哈顿距离，两点在南北方向的距离加上东西方向的距离；
使用对角线距离，
使用欧几里得距离
使用平方后的欧几里得距离（平方容易导致昂贵的开方消耗）