A*（A星）寻路算法是一种广泛应用于路径搜索问题中的启发式算法。它结合了最佳优先搜索和Dijkstra算法的优点，旨在提高搜索效率的同时确保找到从起点到终点的最短路径。
假设有如下白色网格，蓝色点A与B分别代表起始点与终点位置，黑色块代表障碍物，算法要求取的即是由A到B的最短路径：
一般来讲，网格间的距离为1，因为网格是正方形的，所以对角线的距离即为(sqrt{2})，约等于1.4，为了避免小数值，我们把距离乘上10，所以网格在横向与纵向的距离为10，对角线距离为14。
我们暂时先移除障碍物，以便更清晰的看到算法是如何运作的。
无障碍物例子
我们需要着重讲的两个值是黄色框与红色框内的两个数值，如下图：
如上图黄色框内的值为14，红色框内的值为28，我们把黄色框内的值称之为G-Cost G成本，简单讲即是当前节点到起始节点A点的移动距离 成本，红色框内的值称为H-Cost H成本，它是当前节点到终止节点的距离 这里即是B点，因为当前节点距离B节点为2个斜对角距离，所以值为28。数值42即是F-Cost，它是G-Cost与H-Cost相加的和。
$$
FCost = GCost + HCost
$$
当FCost的值在所有当前邻近节点比对中是最小的，那么这个最小的FCost值所对应的节点即是路径获取的下一个节点 这里FCose=42是最小值，我们会在该节点的邻近节点再次获取各个邻近节点的GCost，HCost及FCost，并标记当前节点状态为"已关闭"状态 图中红色节点。如图：
当一个节点被标记为“已关闭”（closed）状态时，这意味着该节点已经被处理过，即算法已经评估了从起点到达这个节点的所有可能路径，并且找到了到达该节点的最低代价路径。这些节点被存储在一个称为“关闭列表”（close list）或“已关闭集合”中的数据结构里。
与"已关闭"状态相反的是开放节点，是开放列表中的节点，即当前待探索的节点集合。这些节点尚未被处理，但已被算法标记为潜在的路径节点。开放列表是一个优先队列（Priority Queue），用于存储待探索的节点。这些节点是当前算法认为“可能属于最优路径”的候选节点。开放列表中的节点会根据总代价 f(n) = g(n) + h(n) 排序，每次选择 f(n) 最小的节点进行扩展。
要求取新探索节点的邻近节点的GCost，通过如下公式求取：
$$
GCost_{new}=GCost_{parent}+移动距离
$$
以A点左侧网格节点为例，在探索该点网格时GCost为10：
继续探索下一个节点即 FCost=42的节点的邻近网格时，相同位置 上图红框内的节点的网格之前GCost等于10，理论上根据 Gn=Gp+移动距离的公式，此时的GCost应为24，但是因为24大于10，所以不会对GCost进行覆盖，只有新探索后的GCost小于之前探索后的值才会覆盖之前的结果，所以这里保持之前网格节点的结果不变。
记住，HCost的结果与(HCost_{parent})无关，它的结果就是直接求取当前网格节点到终点的距离成本。
继续循环往复搜索下一个FCost成本最小的节点 已搜索的所有节点最小，直到与目标节点重合，整个算法也到此收敛：
障碍物例子一
这是在没有任何障碍物的情况下，算法的基本运行逻辑。但是A星算法的目的就是为了在有障碍物的情况下所提出的算法。所以我们需要考虑有障碍物的情况：
如上图，此时FCost最小值为42，这时还没法发现问题，继续搜索下一个节点：
可以发现目前已探索的节点的最小FCost为48，并且有3个节点出现了48，针对这个情况，如果有多个不同的节点都有相同的FCost值，那么优先选择具有最小HCost的那个节点，即离终止节点最近的节点。所以我们选择HCost为24的节点：
此时所有已搜索过的节点最小FCost还是有两个48，并且它们的HCost都为38，该情况下我们可以随机选择一个节点进行搜索，我们先选取右边FCost为48的节点：
目前最小FCost剩下一个为48的节点，可以继续选取该节点进行探索：
我们注意到如图所示位置的网格节点从 FCost=62变为了 FCost=54，这是因为探索新节点后根据 Gn=Gp+移动距离，GCost从28变为了20，得到的FCost更小，所以覆盖了之前FCost的值：
继续探索：
剩下4个FCost为62的节点，我们选取HCost为48的两个节点：
根据这个规则探索到所有能探索的所有节点：
最后，通过路径回溯，选取最短路径：
还记得么？我们所有探索的节点，都通过各自的父级点引出，路径回溯的原理，即是通过目标节点反向找到其父节点直到最开始的父节点(即起始节点)，从而构成了路径链条，该路径链条即是最短路径。
障碍物例子二
我们看另一个例子，这个例子只显示FCost，起始点与目标点依旧为A与B，黑色物体为障碍物，新增了小箭头，目的是想表明当前的节点对应的父节点位置。
继续探索右上角的FCost为58的节点，可以看到下图红色方框内的两个节点还是指向A节点，这是因为通过它引出来的节点内部的GCost大于A节点引出的GCost，导致对应位置的FCost没法覆盖原来的值，也就没法指向新的父节点。这也表明红色方框框选内的两个节点不是新探索出来的父节点的最短路径：
继续探索：
通过这种方式就能看到路径回溯的完整的父子节点链条。
代码实现：
以下是实现上述示例的伪代码：
function A_Star(start, goal, grid):
// 初始化开放列表（优先队列）和关闭列表（集合）
open_list = PriorityQueue() // 优先队列，按 f(n) = g(n) + h(n) 排序
closed_list = Set()
// 创建起点节点，并计算其 g(n) 和 h(n)
start_node = Node(position=start, g=0, h=heuristic(start, goal), parent=None)
open_list.add(start_node)
while open_list is not empty:
// 从开放列表中取出 f(n) 最小的节点
current_node = open_list.pop()
// 如果当前节点是目标节点，回溯路径
if current_node.position == goal:
return reconstruct_path(current_node)
// 将当前节点加入关闭列表，避免重复处理
closed_list.add(current_node.position)
// 遍历当前节点的所有邻近节点
for neighbor in get_neighbors(current_node, grid):
// 如果邻近节点是障碍物或已在关闭列表中，跳过
if neighbor is obstacle or neighbor.position in closed_list:
continue
// 计算从起点到邻近节点的临时 g(n)
tentative_g = current_node.g + cost_to_move(current_node, neighbor)
// 如果邻近节点不在开放列表中，或新路径更优，则更新
if neighbor not in open_list or tentative_g < neighbor.g:
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor, goal)
neighbor.f = neighbor.g + neighbor.h
neighbor.parent = current_node // 记录父节点
// 如果邻近节点不在开放列表中，将其加入
if neighbor not in open_list:
open_list.add(neighbor)
// 如果开放列表为空且未找到目标节点，返回失败
return None // 没有路径
