距离估算方法
参考文章

A*算法使用在游戏中，自动寻路。
将游戏地图抽象成一个很大的矩阵，起始点和终止点的位置坐标已知，中间可能有很多的阻碍，求最短路径。
在这种场景下，如果将矩阵的每一块在抽象为图论中的每一个节点，这样子节点与节点之间的距离（也就是权重）就是1。

对于传统的最短路径算法，在这里，Dijkstra已经和广度优先搜索没什么区别了，因为距离为1，而Dijkstra是求有权重（权重不能为负，如果为负请用Bellman-Ford算法）。所以下面将Dijkstra使用广度优先搜索代替。

同时这和图论中的最短路径还有区别，图论中最短路径，没有办法计算目前点或者是起点与终点的估算距离。而在游戏中自动寻路的场景中，可以估算，原因在与这里的坐标已知。

寻路中使用广度优先搜索

如图：

广度优先搜索

图示偷别人，哈哈，蓝色区域是搜索过的区域，这里应该是一个类似圆形，而不是方形。

但是如果有障碍：

有障碍的广度优先搜索

左半边没有画出，也是一个完整的圆形。

在寻路中使用广度优先搜索，能够找到最短的举例，但是计算量大。

寻路中使用贪心算法

距离估算方法

因为目标点和终点已知，那么我们就可以估算当前点或是起点和终点的距离，然后在与当前点相接的点中，始终选取距离终点最短的点（不考虑回头走）。
如图：

贪心算法

这种方法使得计算量大大的减少了。
但是如果有障碍

有障碍的贪心算法

那么就被拒了，计算量仍然小，但是找到的路径不是最短的。

A*算法

如果结合广度优先算法和贪心算法的思想。使得计算量少于广度优先搜索，但是大于贪心算法。同时总能够保证找到一条最短路径。
例如：

拐个弯？

如果在这里能够拐个弯，就可以找到最短路径。
使得路径能够如下图所示

理想的路径，过于理想的搜索范围

A*算法的思想是这样的：

1. 每个节点记录三个数据，G：离开点的步数、H：和终点的距离估算、F=G+H
   同时还应该有一个P，记录其父节点，一遍能够找到路径

2. 两个集合，接壤集合，和已走结合
   同时还有一个集合是没有走的，但是这个集合并不会显式的写出来。

3. 从起点开始计算与起点接壤的节点的GHF值，然后放入接壤集合
   这里计算完了，需要将起始节点放入已走节点集合，否则会重复计算两次。
   同时需要处理p的值

4. 从接壤集合中取出F值最小的节点，计算与该节点接壤的节点GHF值，放入接壤结合，然后将该节点放入已走节点
   这里，如果一个节点已经计算过了，或者在已走节点中，那就不要算了。
   如果一个节点已经计算过，那么表明该节点以前的F值比再次计算出来的F值要小。

5. 重复步骤4，直到到达终点

其实这里还是借鉴了Dijkstra的思想，每次处理距离最短的节点。

A*算法避免的广度优先搜索（或是Dijkstra）算法的大计算量，同时，避免了贪心算法走入死胡同。

如图：

A*

在上面的路径中，可能在到达B点的时候，计算完该店，然后接壤集合中F值最小的已经不是和B点接壤的点了。而是A点上面的点，然后从该点在慢慢到A点。
同时，在走到障碍外的某点时，可能障碍内的某个点是F最小的点，因此又会计算与该店接壤的点。

下面是伪代码，其中canMove容器以二叉堆的形式存放，加快寻找F值最小的节点。
就这样了。

//伪代码

#include <vector>
using namespace std;
struct  Node
{
    int x;  //该节点在nodeMap中的坐标
    int y;

    int px;
    int py;

    int g;  //从起点到该点的步数
    int h;  //从该点带终点的估算距离
    int f;  //g+h
};

class Axing
{
public:
    Axing();//用来初始化矩阵，障碍等。
    ~Axing();
private:
    vector<vector<int>> nodeMap;        //可以移动到的点为1，障碍点为0也就是不能移动上去的。
    int countH(int curx,int cury,int endx,int endy);    //该算法可能是直接勾股定理，或者是曼哈顿算法等
    Node getMinFNode(vector<Node> &);    //这个函数是从接壤容器中取出F最小的点。返回坐标
    void addNode(vector<Node> &);       //将Node添加到容器中
    //获取一个节点可以移动到的节点，并调用handleNode()处理
    void getCanMoveNode(vector<Node> &canMove,vector<vector<bool>> &memo,Node &cur);
    //该函数处理一个节点，计算该节点的接壤节点存入canMove。
    void handleNode(vector<Node> &canMove,int x,int y,Node &cur);  
    
    //为了少穿点参数。就加了两个变量
    //不知道编程中能不能这样做。
    int endx;
    int endy;
public:
    vector<vector<int>> findPath(vector<Node> &canMove,vector<vector<bool>> &memo,int startX,int startY,int endX,int endY);
};

void Axing::getCanMoveNode(vector<Node> &canMove,vector<vector<bool>> &memo,Node &cur,Node &end)
{
    //从二叉堆canMove中取
}
void Axing::addNode(vector<Node> &canMove)
{
    //canMove以二叉堆的方式存放，.f值为key
}



void Axing::handleNode(vector<Node> &canMove,int x,int y,Node &cur)
{
    int pg=cur.g+1;
    int h=countH(x,y,_endx,_endy);
    int f=h+pg;
    Node node(x,y,px,py,h,f);
    canMove.push(std::move(node));
}


vector<vector<int>> Axing::findPath(int startX,int startY,int endX,int endY)
{
    vector<Node> canMove;           //该容器存放接壤的点，表示可移动上去
    vector<Node> hasPass;           //存放已经走过的Node，以便重建路径
    vector<vector<bool>> memo;      //该容器表示某个点是否已经走过了。

    Node startNode(startX,startY,startX,startY,0,0,0);
    
    addNode(canMove,std::move(startNode));
    while(! canMove.empty())
    {
        Node curNode = getMinFNode(canMove);
        
        int x=cur.x;
        int y=cur.y;
        //依次处理四个节点
        if(memo[x-1][y] == false )
        {

            handleNode(canMove,x-1,y,cur);
            memo[x-1][y] =true;
            if(x-1 == endX && y == endY)
            {
                break;
            }
        }
        if(memo[x+1][y] == false)
        {
            handleNode(canMove,x+1,y,cur);
            memo[x+1][y] =true;
            if(x+1 == endX && y == endY)
            {
                break;
            }
        }
        if(memo[x][y-1] == false)
        {
            handleNode(canMove,x,y-1,cur);
            memo[x][y-1] =true;
            if(x == endX && y-1 == endY)
            {
                break;
            }
        }
        if(memo[x][y+1] == false)
        {
            memo[x][y+1] =true;
            handleNode(canMove,x,y+1,cur);
            if(x == endX && y+1 == endY)
            {
                break;
            }
        }

        hasPass.push_back(std::move(curNode));
    }
    //下面就从从最后一个节点,到开始节点重建该路径
    
}