什么是 A* 算法?它是如何运作的?它有哪些具体的应用?
A*算法及它在 Unity 中 2D 的 Demo 实现#
A*(读作 A-Star)算法,是一种启发式的搜索算法,常用于游戏的寻路系统。它可以认为是贪心算法+广度优先搜索(BFS) 算法的结合版。它的每一步决策是基于代价评估的。
A*算法通过下面这个函数来计算每个节点的综合评估值。
- 是节点 n 的综合评估值。
- 是节点 n 距离起点的代价步数(可能会被更新)。
- 是节点 n 距离终点的预计代价,也被称为启发函数。
A*算法#
A*算法一般是基于方格(或像素点)的,它将待搜索的区域均简化成一个个的小方格,最终得到的路径是一些小方格的组合。当然也可以是其他形状,也可以基于特殊地形进一步改良升级(NavMesh 寻路)。
这里我以简化为方格为例。
假如有如下区域,白色是可通过的,黑色是障碍物,不可通过,黄色是起点,蓝色是终点:

算法描述:
首先,用到的数据结构最好是优先队列,但由于 C# 没有提供优先队列,用链表也是 ok 的,只是稍微慢点。需要一个 Open 表和一个 Close 表。
- 将初始节点(起点)放入到 Open 列表中
- 当 Open 列表不为空时:
- 在 Open 列表中找到 F 值最小的节点,作为当前方格节点
- 从 Open 列表中移除当前方格节点
- 将当前方格节点添加到 Close 节点
- 找到当前方格节点的所有合法的邻近的节点(上、下、左、右,不越界、不是障碍物)
- 遍历所有邻近节点:
- 如果当前邻近节点不在 Open 列表里
- 如果当前邻近节点不在 Close 列表里,则标记当前邻近节点的前驱节点是当前节点,当前邻近节点的 G 是当前节点 G+1,把当前邻近节点添加到 Open 列表里
- 否则,什么也不做
- 否则,说明当前邻近已经在 Open 列表中,如果当前节点的 G 比当前邻近节点的前驱节点的 G 更小,则更新当前邻近节点的前驱节点为当前节点,当前邻近节点的 G 赋值为当前节点的 G+1。
- 如果当前邻近节点不在 Open 列表里
- 如果终点在 OpenList 中,则直接返回终点方格节点
- 返回空
看不懂的话,我先放一张动图来演示:

方格的左下角的值是 G 值,右下角的值是 H 值,左上角的值是 F 值(F = G + H)。对于任意方格,H 值都是固定的,所以不用记录在节点中。但是 G 值是可能会被更新的,所以 G 值应该需要作为节点的属性,然后 F 值也不用记录了,因为可以直接根据 G+H 得到。每个方格还要记录它的前驱节点。
方格被标记为绿色,代表被标记为当前节点的邻近节点。
方格被标记为红色,代表邻近节点被添加到 Open 列表中,且它的前驱被标记为当前节点。
方格被标记为浅棕色,代表方格节点是当前 F 值最小的节点,且已从 Open 列表中移出,加入了 Close 列表。
方格被标记为紫色,代表该节点是路径节点。路径节点(从目标点开始)通过找到它的前驱,找到下一个路径节点,直到找到出发点(因为出发点没有前驱)。
在这个例子中,并没有发生更新 G 值的情况。
我再举个发生更新 G 值的例子:

如果当前节点(5 1 4) 的邻近节点(6 3 3 靠左) 的前驱节点(6 2 4) 的 G 的值比当前节点的 G 的值大,则将邻近节点的前驱修改为当前节点,将它的 G 值也更新。
如果不更新 G 值,A*寻路可能得到的路径并不是最优的,而是“绕路”的。
A*算法在 Unity 中的实现#
GiHub 源码地址:
等待补充
留言