A*算法是一种优秀的启发式搜索算法, 它整合了Greedy Best-First-Search算法、Dijkstra算法和一些距离计算公式的算法思想, 并利用了估值函数或评估函数作为启发方法, 从而可以高效动态地求得一条可能最优的最短路径, 因而A*算法一直被游戏开发行业和GIS系统开发等领域所广泛采用^[1]. 但目前的A*算法研究大多数都是基于任意图而不是基于网格图的游戏设计的, 本文将从多角度对A*算法在智能寻路中的搜索效率进行改进.

1 传统A*算法的简介与分析

A*算法是一种寻找最短路径的有效方法, 它常用于现代游戏的非玩家游戏(NPC)设计以及地理信息系统(GIS)开发等中. A*算法像很多求解最短路径的算法一样, 都可以找到地图上两点间的最短路径. 在简单图上, 它跟Greedy Best-First-Search (贪心最佳路径搜索算法)的效率基本上是相同的, 同样可以利用启发式进行最短路径的搜索. 启发式(Heuristic Function)搜索是指在整个将要搜索的地图中, 先对每一个将要访问的节点进行一个代价评估, 然后选择最好的节点, 再不断迭代更新搜索, 直至寻找到目标节点.

启发式搜索A*算法公式表示为:

${{F}}\left( {{n}} \right) = {{G}}\left( {{n}} \right) + {{H}}\left( {{n}} \right)$

(1)

G(n)表示从初始节点S到目标节点T, 在其搜索路径的过程中, 到达期间某一节点n所花费的代价. H(n)表示从当前节点n到目标节点T的最优路径中将要花费的估计代价, 即最短路(Shortest-Path). 简而言之, G(n)是实际代价, H(n)是估计代价, F(n)则表示节点n的估价函数. 在保证存在最短路径的条件下, A*算法的效率高低在于H(n)的选取, 假设R(n)表示n到目标节点的距离的实际数值, 如果H(n)>R(n), 则将要访问的节点数目越少, 搜索的范围越窄, 效率越高, 但不能保证得到最优路径. 如果H(n)≤R(n), 则将要访问的节点数目越多, 搜索的范围越广, 效率越低, 但肯定能得到最优路径^[2].

在A*算法的实现上, 使用OPEN列表和CLOSED列表来存放节点. 将起始点放入OPEN列表中, 对OPEN列表中的节点按照启发函数值进行升序排序, CLOSED列表则用来存放计算后得出的OPEN列表的适合要求的节点. 取出OPEN列表中第一个节点, 如果是目标节点就直接输出最短路径. 否则就计算下一个节点的估价函数值, 将最优的下一个节点放进OPEN列表中, 同时将当前节点从OPEN列表移到CLOSE列表中, 直至找到最短路径^[3].

A*算法效率高的主要原因是增加了估价函数, 通过估价函数F(n), 合适地选取下一个代价最小的节点, 以此类推, 直到找到最终节点, 相比传统的无启发函数的其他最短路径算法, 其在效率上得到了明显的提升. 但是A*算法的启发式函数是一种由经验确定的函数, 估计函数往往决定了A*的路径规划, 节点的选择也充满了不确定性, 很难保证每次选择的节点都是最优解的, 具有一定几率上在最优节点的选择出现错误, 从而导致节点的意外删除或者多余的节点选择, 导致最后计算的路径为非最优路径. 另外在计算过程中还可能出现“死循环”的现象, 形成“回环”等的无用搜索, 而无法获取到最优路径. 因此, 如何优化启发式函数成为A*算法效率高低的主要因素.

A*算法在实际运用时还可能会出现一个问题, 当实际的地图并不是一整块的二维网格, 它是被很多障碍物给划分成众多个形状不规则的地图块甚至是地图点, 并且每一个块和点的密集程度都不可能一样. 直接运用A*算法对整张地图寻找最短路径会导致搜索效率低下.

2 A*算法的优化方案

根据传统的A*算法可能出现的一系列问题, 将从以下三个方面去考虑优化和改良新的A*算法.

2.1 对可能出现“死循环”的优化

可以利用“分治”的思想去解决在现实地图中可能出现的“死循环”(Dead Loop)问题. 对现实中的地图进行具体地划分成若干个块, 然后再在这些块中进行最短路径搜索, 用来解决“死循环”的问题. 例如在游戏常见的二维地图上, 地图被河流或者道路划分成若干个不等的小块, 每一个小块都可以作为一个独立的小地图, 小地图又由复杂的网络节点所构成, 如果形成的结构还比较稠密, 则再划分成一块块的独立的小地图, 这样就可以把这些独立的小地图看成是一块稀疏图^[4]. 可以先在稀疏图中进行最短路径的搜索, 然后继续在上一层的稠密图中搜索最短路径. 这种搜索策略可以用来克服“死循环”的问题, 而且对地图进行“分治”搜索到的路径也是最优最短的.

2.2 加入方向因子的优化

启发式函数(Heuristic Function)直接或者间接地决定着传统的A*算法的搜索效率, 因此对于启发函数的优化处理是主要研究方向之一. 在传统方法的基础中引入方向这个因素, 用来提供更多的启发信息^[5]. 在寻路过程中把与目标方向相反的节点给剪枝掉, 减少多余的计算量. 传统的A*算法的启发式函数H(n)是以距离信息为计算机引导方向的. 常用的有曼哈顿距离(Manhattan Distance), 欧几里德距(Euclidean Distance), 对角线距离(Diagonal Distance), 切比雪夫距离(Chebyshev Distance)等, 而传统的A*算法以欧几里德距离作为启发函数^[6]. 地点A到地点B的欧几里德距离(Euclidean Distance)为:

${{Euclidean\_distance}} = \sqrt {{{({\rm A}.x - {\rm B}.x)}^2} + {{({\rm A}.y - {\rm B}.y)}^2}} $

(2)

但是用欧几里德距离成为启发式函数有着很明显的漏洞, 因为实际代价G(n)可能会与启发式函数H(n)发生相斥, 而且其开平方根会使计算机的计算开销更大. 所以, 可以使用Octile距离来进行优化, Octile距离的主要思想就是假设只能进行45°转弯.

$\begin{array}{l}{{Octile\_distance}} = {\rm{max}}(|{\rm A}.x - {\rm B}.x|,|{\rm A}.y - {\rm B}.y|) \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+(\sqrt 2 - 1) \times \min (|{\rm A}.x - {\rm B}.x|,|{\rm A}.y - {\rm B}.y|)\end{array}$

(3)

上式中max表示取最大值, min表示取最小值. 另外, 在选择最优节点路径时还受到了方向(Direction)因素的影响, 如果只用距离来作为约束条件, 那么它就可能不是最优的约束条件. 考虑从一个位置移动到下一个位置的最小代价为D, 并加入方向因子(Direction Factor)θ来提高算法的效率与准确性^[7].

${{F}}(n) = G(n) + a \times {\rm{sin}}(\theta ) + D \times {{Octile\_distance(next)}}$

(4)

其中a作为权重比例系数, 它取决了方向在A*算法中的关键性, 对于不同的情况, 这个权重比例系数要按照算法经验进行调整, 权重比例系数的大小和目标的重要性以及策略的选择有关. θ则表示起始节点和目标节点构成的矢量, 当前节点与下一个最优节点形成的矢量, 两个矢量之间的夹角^[8].

2.3 对节点排序的优化

在传统A*算法中, 每次访问OPEN表必然需要找到F(n)值最小的节点, 如果对OPEN表进行整体的搜索比较, 会导致耗费大量的时间. 可以采取对OPEN表的节点进行排序, 在查找F(n)值最小的节点时就会节省大量时间. 对一些极限数据, 单一的排序效率并不高. 因此, 可以根据不同的数量级和不同的情况去采取不同的排序. 当数据量相对大时就采用快排(QuickSort), 并分段递归排序. 当分段后的数据量小于某个阀值, 就采用插入排序(InsertionSort). 如果递归过深, 就采用堆排序(HeapSort). 采取这种优化过的排序方法可以更有效地对OPEN表进行升序排列. 最后, 每次对OPEN表中加入新的节点的时候我们采用二分插入的方法, 使得OPEN表始终保持有序状态. 这样比每次都盲目地搜索整个OPEN表的速度要快至少50%的时间.

3 优化的A*算法的伪代码

伪代码如下:

//Pseudo code

while OPEN has Node do

　if temp_Node equal E then output the path with temp_Node

　else do

　　Init Queue = {

　　　The neighbour of temp_Node;

}

　　for each node in Queue do

　　　if CLOSE not contains node then

　　　　//判断节点的搜索方向

　　　　if Queue.Count > 1 and node is not in direction from S to E

　　　　then

　　　　　push node into Temp

　　　　else do

　　　　if node is in direction from temp_Node to E then

　　　　　//计算该节点的启发式函数

　　　　　calculate the value of heuristic function for node

　　　　push node into OPEN

　　　　set temp_Node as node’s parent node

　　　else do

　　　　push node into Temp

　　//将临时节点存放在CLOSE列表中

　　push temp_Node into CLOSE

　　pop temp_Node from OPEN

　　if OPEN.Count =0 and temp_Node is not E

　　Pop up the first node in Temp and push into OPEN

if temp_Node is not E

　Can not find a way from S to E //不存在最短路径

4 实验和对比分析

对于传统A*算法中的启发函数的优化处理^[9], 加入方向因子θ, 剪枝, 划分小地图, 部分细节代码优化等优化方案后的A*算法的效率对比.

实验一. 单独对节点排序的优化, 寻找最短路径时访问的节点数.

从表1的数据可以看出, 在障碍物稠密程度相同的情况下, 随着地图网格数的增大, 在运行时间和网格访问的数量上, 优化过的A*算法要比传统的A*算法都要少一部分, 在效率上, 经过排序优化的A*算法更优.

实验二. 选取有障碍的二维网格地图作比较.

从图1和图2可以看出, 在障碍物稠密程度相同的情况下, 对于相同大小的地图, 在运行时间效率和节点访问数量上进行对比, 对未进行优化的传统A*算法, 访问过的网格为483个. 但经过加入方向因子优化过的A*算法, 范围过的网格仅为191个.

实验三. 综合各种因素的A*算法的优化, 显示寻找最短路径时访问的节点数.

从表2的数据可以看出, 在障碍物稠密程度相同的情况下, 随着地图网格数的增大, 在运行时间和网格访问的数量上, 优化过的A*算法要比传统的A*算法都要少很多, 随着地图的增大, 二者在运行时间效率和网格访问数量上的差距越来越明显, 提升效率约为50%.

5 结论

在传统A*算法搜索策略的基础上, 通过加入方向因子, 以及有效的剪枝和回溯, 部分细节代码优化等优化方案, 进一步地改进A*算法的启发式搜索策略. 最后的A*算法的评估实验证明, 优化方案是有效的, 优化的A*算法比传统的A*算法, 较大地减小了算法搜索的规模, 减少了网格访问数量和运行时间.