A*算法使用在游戏中，自动寻路。
将游戏地图抽象成一个很大的矩阵，起始点和终止点的位置坐标已知，中间可能有很多的阻碍，求最短路径。
在这种场景下，如果将矩阵的每一块在抽象为图论中的每一个节点，这样子节点与节点之间的距离（也就是权重）就是1。
对于传统的最短路径算法，在这里，Dijkstra已经和广度优先搜索没什么区别了，因为距离为1，而Dijkstra是求有权重（权重不能为负，如果为负请用Bellman-Ford算法）。所以下面将Dijkstra使用广度优先搜索代替。
同时这和图论中的最短路径还有区别，图论中最短路径，没有办法计算目前点或者是起点与终点的估算距离。而在游戏中自动寻路的场景中，可以估算，原因在与这里的坐标已知。
寻路中使用广度优先搜索
如图：
图示偷别人，哈哈，蓝色区域是搜索过的区域，这里应该是一个类似圆形，而不是方形。
但是如果有障碍：
左半边没有画出，也是一个完整的圆形。
在寻路中使用广度优先搜索，能够找到最短的举例，但是计算量大。
寻路中使用贪心算法
因为目标点和终点已知，那么我们就可以估算当前点或是起点和终点的距离，然后在与当前点相接的点中，始终选取距离终点最短的点（不考虑回头走）。
如图：
这种方法使得计算量大大的减少了。
但是如果有障碍
那么就被拒了，计算量仍然小，但是找到的路径不是最短的。
A*算法
如果结合广度优先算法和贪心算法的思想。使得计算量少于广度优先搜索，但是大于贪心算法。同时总能够保证找到一条最短路径。
例如：
如果在这里能够拐个弯，就可以找到最短路径。
使得路径能够如下图所示
A*算法的思想是这样的：
每个节点记录三个数据，G：离开点的步数、H：和终点的距离估算、F=G+H
同时还应该有一个P，记录其父节点，一遍能够找到路径两个集合，接壤集合，和已走结合
同时还有一个集合是没有走的，但是这个集合并不会显式的写出来。从起点开始计算与起点接壤的节点的GHF值，然后放入接壤集合
这里计算完了，需要将起始节点放入已走节点集合，否则会重复计算两次。
同时需要处理p的值从接壤集合中取出F值最小的节点，计算与该节点接壤的节点GHF值，放入接壤结合，然后将该节点放入已走节点
这里，如果一个节点已经计算过了，或者在已走节点中，那就不要算了。
如果一个节点已经计算过，那么表明该节点以前的F值比再次计算出来的F值要小。重复步骤4，直到到达终点
其实这里还是借鉴了Dijkstra的思想，每次处理距离最短的节点。
A*算法避免的广度优先搜索（或是Dijkstra）算法的大计算量，同时，避免了贪心算法走入死胡同。
如图：
在上面的路径中，可能在到达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));
}
//下面就从从最后一个节点,到开始节点重建该路径
}
