什么是 A* 算法?它是如何运作的?它有哪些具体的应用?

A*算法及它在 Unity 中 2D 的 Demo 实现#

A*(读作 A-Star)算法,是一种启发式的搜索算法,常用于游戏的寻路系统。它可以认为是贪心算法+广度优先搜索(BFS) 算法的结合版。它的每一步决策是基于代价评估的。

A*算法通过下面这个函数来计算每个节点的综合评估值。

f(n)=g(n)+h(n) f(n) = g(n) + h(n)
  • f(n)f(n) 是节点 n 的综合评估值。
  • g(n)g(n) 是节点 n 距离起点的代价步数(可能会被更新)。
  • h(n)h(n) 是节点 n 距离终点的预计代价,也被称为启发函数。

A*算法#

A*算法一般是基于方格(或像素点)的,它将待搜索的区域均简化成一个个的小方格,最终得到的路径是一些小方格的组合。当然也可以是其他形状,也可以基于特殊地形进一步改良升级(NavMesh 寻路)。

这里我以简化为方格为例。

假如有如下区域,白色是可通过的,黑色是障碍物,不可通过,黄色是起点,蓝色是终点:

算法描述:

首先,用到的数据结构最好是优先队列,但由于 C# 没有提供优先队列,用链表也是 ok 的,只是稍微慢点。需要一个 Open 表和一个 Close 表。

  1. 将初始节点(起点)放入到 Open 列表中
  2. 当 Open 列表不为空时:
    1. 在 Open 列表中找到 F 值最小的节点,作为当前方格节点
    2. 从 Open 列表中移除当前方格节点
    3. 将当前方格节点添加到 Close 节点
    4. 找到当前方格节点的所有合法的邻近的节点(上、下、左、右,不越界、不是障碍物)
    5. 遍历所有邻近节点:
      1. 如果当前邻近节点不在 Open 列表里
        1. 如果当前邻近节点不在 Close 列表里,则标记当前邻近节点的前驱节点是当前节点,当前邻近节点的 G 是当前节点 G+1,把当前邻近节点添加到 Open 列表里
        2. 否则,什么也不做
      2. 否则,说明当前邻近已经在 Open 列表中,如果当前节点的 G 比当前邻近节点的前驱节点的 G 更小,则更新当前邻近节点的前驱节点为当前节点,当前邻近节点的 G 赋值为当前节点的 G+1。
    6. 如果终点在 OpenList 中,则直接返回终点方格节点
  3. 返回空

看不懂的话,我先放一张动图来演示:

方格的左下角的值是 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 源码地址:

https://github.com/zzxzzk115/AlgorithmInUnity/tree/main/AlgorithmDemo/Assets/Scripts/PathFinding/AStar

等待补充


留言

⬆︎TOP