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

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

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

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

  • 是节点n的综合评估值。
  • 是节点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