A*算法是用于寻找两点之间的最短路径,同时它也是一种静态路网中求解最短路最有效的直搜索方法,公式f(n)=h(n)+g(n)给出了邻居节点到目标节点所需要的总消耗成本,h(n)是当前节点到该邻居节点的所消耗的成本，g(n)是该邻居节点到目标节点的估计消耗成本,比较常用的估计方法是欧几里得方法和曼哈顿方法。
A*算法首先要准备两个列表，一个开启列表，一个关闭列表，开启列表存储还未走的节点(但不是一开始就把所有节点加入开启列表),关闭列表存储走过的节点,将起始节点加入到开启列表,在开启列表不为空时,取出开启列表中最小消耗成本的节点,判断是否是目标节点,是就直接结束A*,取得它的周围邻居节点(通常是8个),判断邻居节点是否在关闭列表中,在关闭列表中,不做处理，不在关闭列表中,再判断是否在开启列表中，若已在开启列表中,计算它的f(n),是否比以前的f(n)小,小就更新它的f(n)并将它的父节点设为当前节点。大的话就不做处理,若不在开启列表中,计算它的f(n)，更新f(n)将父节点设为当前节点。处理完它的周围邻居节点后，一轮循环结束,再移除开启列表中的当前节点，放在关闭列表中,因为已经走过这个节点。然后在开启列表不为空时继续上述循环，直到找到目标节点,或者找遍所有节点都找不到目标节点。C++代码如下(相关函数并未实现,视实际情况而定):
1 typedef struct node
2 {
3 float currentCost;//h(n)
4 float toTalCost;//f(n)
5 node * parent;//父节点
6 }Node;
7 Vector<Node> OpenList;//开启列表
8 Vector<Node> CloseList;//关闭列表
9
10 Node AStar(Node start,Node Goal){
11 OpenList.Add(start);
12 while(OpenList.Length!=0)
13 {
14 Node* minNode= OpenLIst.Min();//Min()选出最小消耗成本节点
15 if(minNode == Goal)
16 {
17 return minNode;
18 }
19 Vector<Node> Neighbors;//邻居列表
20 GetNeighBors(Neighbors,minNode）;/*得到最小消耗成本节点的周围邻居节点*/
21 for(int i=0;i<NeighBors.Count;i++)
22 {
23 if(Neighbors[i].obstacle)//如果邻居节点被标志障碍物,跳过。
24 {
25 continue;/*也可以在GetNeighBors函数里进行处理,障碍物节点不加入邻居列表*/
26 }
27 if(CloseList.Contain(Neighbors[i]))//节点已经走过不作处理
28 continue;
29 float currentCost=CacluateDistance(minNode,Neighbors[i])+minNode.currentCost;
30 float totalCost = currentCost+CacluateDistance(Neighbors[i],Goal);
31 if(OpenList.Cotain(Neighbors[i]))//如果开启列表包含该邻居节点
32 {
33
34 if(totalCost<Neighbors[i].totalCost)
35 {
36 Neighbors[i].totalCost=totalCost;
37 Neighbors[i].currentCost =currentCost;
38 Neighbors[i].parent=minNode;
39 }
40 }
41 else
42 {
43 Neighbors[i].totalCost=totalCost;
44 Neighbors[i].currentCost =currentCost;
45 Neighbors[i].parent=minNode;
46 }
47 }
48 OpenList.Remove(minNode);
49 CloseList.Add(minNode);
50 }
51 return NULL;//找不到目标节点，返回空
52 }
若成功返回一个节点,那么可以不断往回迭代父节点得到一条逆向的最短路径。A*的思想是为每个节点都估价消耗成本(沿当前所走的路径到目标节点的消耗成本),选择最小消耗成本的节点优先计算,就使节点搜索沿目标节点那边搜索，也被称之为启发式搜索。而开启列表得到最小的消耗成本节点或添加节点，应该用二叉堆(最小堆)插入,这样取最小节点时间复杂度为O(1),添加节点时间复杂度为O(log(n)),比另一种遍历取节点O(n)，加节点O(1)好一些。