A* 寻路算法,也有叫AStar算法的
它的英文名字叫A*Search，是一种用于寻找有效路径的算法
算法其实不是很难，假设有一个7 X 7大小的方格子，绿色的方格子作为起点而红色方格子作为终点，剩下的黑色格子则是一堵墙
从起点开始走，规定只能上下左右移动，每一次只能移动一格，且不能穿过墙壁
算法的目的就是寻找一条从起点到终点的最短路径
首先，它需要用到一个公式F=G+H和两个集合open,close
其中，F是对格子代价的评估，G表示从起点到当前格子的成本，H表示当前格子到终点的距离
需要注意的是G并不是当前格子到起点的距离，而是起点走到当前格子所走格子数，也就是前一个格子的G+1
而open集合存放的是可以到达但是未到达的格子（或者说未检测）
close集合存放已经走过的格子（或者说已检测的格子）
第一轮
1.检测起点
假设一个格子是一个Node
则把 Node(1,3) 加入到open集合中
2.取代价最小的格子作为当前格子
最开始open只有起点一个格子，所以起点成为当前格子
并且此时close集合中还没有其他格子
open:Node(1,3)
close:
然后将Node(1,3)从open集合中移除，并放入close集合中，表示当前格子已检测
3.寻找当前格子可到达的格子
因为规定了只能上下左右移动，所以可到达的格子可能有四个
判断格子是否是墙壁以及是否在open集合中
如果都不是，则将其加入到open集合中，同时将他们的父节点设置为当前格子（回溯路线用）
同时计算他们的F,G,H值
比如起点周围可达格子Node(0,3),Node(1,2),Node(1,4),Node(2,3)
第二轮
1.检测open集合中代价最小的格子
找出open集合中F值最小的格子，即Node(2,3)作为当前格子
然后将Node(2,3)从open集合中移除，放入close集合中，表示当前格子已检测
2.寻找当前格子可到达的格子
因为Node(2,3)左右格子都不符合条件，所以可达的格子只有两个
Node(2,2),Node(2,4)
将它们的父节点设置为当前格子Node(2,3)，计算F,G,H值，并加入open集合中
第三轮
1.检测open集合中代价最小的格子
找出open集合中F值最小的格子，即图中蓝色的格子中最小值
因为当前open集合中格子F值都一样，所以具体会选哪个由代码决定
为了简化我就选择Node(2,2)作为当前格子，当然也可以指定F值相同时选H值小的
然后将Node(2,2)从open集合中移除，放入close集合，表示已检测
2.寻找当前格子可到达的格子
因为Node(2,2)只有上方可达，所以只选取了Node(2,1)
将它们的父节点设置为当前格子，计算F,G,H值，加入open集合
第四轮
1.检测open集合中代价最小的格子
......
2.寻找当前格子可到达格子
......
第N轮
......
如果open集合中存在终点，则结束并返回终点
然后通过终点的父节点一步一步找到路线即可
步骤看起来好像还蛮多的，但是都是重复的
实际上代码实现很简单：
private Node findWay(Node endNode)
{
openVector.add(myNode);
while(openVector.size()>0)
{
Node currentNode=findMinNode(openVector);
openVector.remove(currentNode);
closeVector.add(currentNode);
Vector<Node> neighborsVector=findNeighbors(currentNode);
if(neighborsVector==null) continue;
for(Node node:neighborsVector)
{
if(!openVector.contains(node))
{
node.setParentNode(currentNode);
openVector.add(node);
}
}
if(openVector.contains(endNode))
{
return endNode;
}
}
return null;
}
上述代码使用的是java来实现的，但并不影响阅读
另外附上我学习算法的时的实践成果
运行需要Java环境