基于A*算法的电子游戏路径优化处理

李子涵，孙建红，王永利

（1.南京理工大学电子工程与光电技术学院，江苏南京 210094；2.南京理工大学计算机科学与工程学院，江苏 南京 210094）

当今，游戏人工智能可为游戏产品获取更高的用户粘性[1]。A*寻路算法作为一种启发式算法[2-3]，在电子游戏编程中获得了广泛使用，其与盲目式算法相比，有运算速度较快、搜寻精度较高[4]等优点；以此为基础，后人还发展出D*算法等动态路径规划算法[5-6]。为解决传统A*算法中寻路质点无体积[7]的问题，膨胀处理障碍物，为路径留出缓冲，再使用射线法简化冗余节点。为克服贝塞尔曲线平滑法不适用的问题，现提出一种拟曲线平滑方法，在关键节点间插值后，使用多段线段模拟曲线，克服了贝塞尔曲线平滑法产生的刺状畸变，使平滑后的路径具有良好的视觉效果。

1 A*算法与栅格地形划分法简介

A*算法是一种在智能寻路中常用的启发式算法，其原理是使用开启列表和关闭列表，通过求取式（1）启发函数的函数值，找出开启列表中当前启发值最小的路径点，获取其相邻节点，以此引导路径搜索，最终得到一条关于当前启发值最优的路径[8]，式（1）如下所示：

栅格法是模拟地形环境的一种常用方法，它使用相互连接的单位栅格覆盖复杂地形，设置可通过坡度角和可通过高度，将栅格划分为可通过区域与不可通过区域，简化不规则地形。

在寻路栅格中使用A*算法，所得原始路径是由目标节点到初始节点的一系列父节点回溯构成，因此原始路径是充满冗余和锯齿的，如果在可视化实现中直接使用原始路径，视觉效果将会非常差，并且锯齿拐角处的速度突变并不符合物体运动的实际情况。

2 障碍物膨胀处理

在场景中设置寻路起点与终点，使用A*寻路算法完成寻路，可以得到原始路径，如图1 所示。

图1 原始路径

可以看出，原始路径中的确存在大量冗余转折点和锯齿状路径，且由于启发函数的贪心性质[9]，导致大量局部路径段紧贴障碍物延伸，又因寻路物体的模型存在可产生物理碰撞的体积，在仿真动画中，将会出现寻路物体的部分模型镶嵌进障碍物模型中，可能引起难以预测的系统漏洞[10]，因此应当引入障碍物膨胀算法，获得安全路径。

在寻路算法寻找最优路径的计算过程中，并不对当前真实地形进行考察，只依赖于已经预先生成的寻路网络[11]，故在进行障碍物膨胀算法时，只需考虑路径点的可通过性与不可通过性即可。根据用户需要，调节膨胀半径R，遍历路径节点以R为半径做球体碰撞检测，若检测到碰撞物为非地面的碰撞事件，则将该节点设置为不可通过节点，即将障碍物向外膨胀一个安全距离R，之后生成寻路网络，可以看到障碍物周围被设置为不可通过的缓冲区域，如图2（a）所示，此时运行寻路算法得到安全路径，如图2（b）所示。

图2 膨胀处理结果

3 射线法简化冗余节点

在得到安全路径后，可将路径中的冗余节点进行简化。从初始节点开始遍历路径中的所有节点：

1）假设当前节点编号为i0，那么其后两个路径节点编号分别为i0+1 与i0+2，如图3（a）所示。

2）以节点i0为起点，为方向发射射线，进行碰撞检测，若该射线在节点i0与节点i0+2 之间未检测到碰撞事件，则i0+1 节点为冗余节点，移除之,如图3（b）所示。此时存储路径节点的列表元素从第i0+2 号元素开始，全体向前移动一位补位，先前的i0+2 节点变为当前的i0+1 节点，同理先前的i0+3 节点变为当前的i0+2 节点。

3）重复上述射线碰撞检测，直到当前io节点与io+2 节点间检测到碰撞事件，则io+1 节点不为冗余节点，如图3（c）所示；此时使用赋值语句i=i+1，将射线检测的起始节点由io移至io+1。

4）重复上述射线碰撞检测，直到io+1 值大于等于节点列表元素数，跳出循环，简化完成，如图3（d）所示。

图3 射线法简化冗余节点

为了保证测试结果的客观性，如图4 建立以下3 个场景，通过调整场景中障碍物的多寡来控制场景的复杂程度（图4（a）障碍物稀疏，环境简单；图4（b）障碍物较多，环境较为复杂；图4（c）障碍物众多且相互交错，环境复杂），以测试该方法在不同复杂程度环境中的运行效果。

图4 3种不同复杂程度的场景

运行寻路程序，统计3 个场景中路径转折点的个数，如表1 所示。

表1 场景中路径转折点数量

从表1 可以看出，射线简化算法显著简化了路径中的冗余转折点。

4 拟曲线路径平滑方法

选取图4 中最复杂的测试场景图4（c）。如图5（a）所示，在简化路径冗余转折点后，可以看出原路径中锯齿状抖动已经全部消失，但路径折转处仍是尖锐的。三次样条曲线[12]与贝塞尔曲线[13]是生成曲线的常见算法。三次样条曲线的绘制过程需要多次求导数[14]，计算量较大，且该文涉及的仿真中路径点均为离散点，故该文不适用此法。贝塞尔曲线基于伯恩斯坦多项式在闭区间上的一致收敛性，可以通过少量的点，去控制生成复杂的曲线[15]。

考虑直接使用贝塞尔曲线进行路径平滑，但运行程序后发现系统溢出报错。究其原因，由于场景中路径点过多，求取高阶贝塞尔曲线是一个占用大量资源的计算过程，以至于产品难以正常运行，为了克服此问题，现将原路径进行分段贝塞尔曲线平滑，但贝塞尔曲线的生成是一个连续的过程，路径中任何一个节点的变化都会对整条路径产生影响[16]，分段进行贝塞尔曲线平滑后，每两段曲线间的连接处无法保证平滑。通过分段生成三阶贝塞尔曲线，得到图5（b），对比图5（a）可以看出，路径中部分尖锐拐弯处变得平滑，但某些路径段却出现刺状畸变，平滑效果不理想。

图5 使用贝塞尔曲线平滑

由于贝塞尔曲线平滑方法与产品要求不相符，故弃之不用，现另提出一种拟曲线平滑方法。由于在平滑前使用射线法简化冗余节点时，删去了大量节点，而拟曲线平滑处理的本质是用多段线段去模拟曲线，所以在平滑处理前仍需进行路径点插值处理。将存储路径点的向量列表nodes 的可用长度扩展为列表中当前节点数量的4 倍，再使用Vector3.Lerp 方法在每两个相邻路径点的1/4、1/2 与3/4 处插入新的路径点。插值完毕后，从初始节点后一个节点开始遍历路径中的所有节点。

1）假设当前节点编号为ib，其前后两个路径节点编号分别为ia、ic，使用式（2），取节点ia与节点ic的中点，记为点iac。

2）设置平滑强度strength(0 ≤strength≤1)，使用式（3），得到节点（当strength=0 时，节点即为节点ib，当strength=1 时，节点即为节点iac）。

再将路径点向量列表中的节点ib替换为节点，完成节点ib的平滑。

3）使用赋值语句ib=ib+1，将当前节点后移一位，循环上述平滑过程，直到ic大于等于节点列表元素数，跳出循环，平滑完成。

设置平滑强度strength=0.8，执行此算法后得到如图6 所示路径，可以看出此时路径拐弯处的视觉效果已经接近曲线。

图6 使用拟曲线平滑

5 改进分段拟曲线路径平滑方法

在拟曲线平滑得到的路径中，总体上消除了路径拐弯处的尖锐转折，但可以看出在局部路径中出现了“急弯”，如图7（a）所示，以及在无障碍物的空旷区域处，原本为直线段的路径产生了弧形畸变，如图7（b）所示。

图7 拟曲线平滑所得局部路径

究其原因，在拟曲线平滑之前使用了射线简化，导致路径中原本间距均匀的节点被大量删除，只剩下转折处的关键节点，而关键节点分布不均匀，在环境复杂处关键节点密集，环境空旷处关键节点稀疏，拟曲线平滑使用简单插值，在关键节点密集处产生冗余插值，导致平滑后产生“急弯”，而环境空旷处由于插值点数量不够，导致无需平滑的直线路径段产生弧形畸变，为解决此问题，现对拟曲线平滑方法进行改进，提出改进分段拟曲线平滑方法。

设置段长值SegmentLength，从初始节点开始遍历路径中的所有节点。

1）假设当前节点编号为i，代入式（4），得到节点i与节点i+1 之间的距离length。

2）将length代入式（5），得到节点i与节点i+1之间需要插值点的个数num。

由于段长SegmentLength可能无法被节点距离length整除，而式（5）使用取整函数，得到的段长舍去了余数，遍历整个路径将产生积累误差，因此引入段长余数rem，使用式（6）更新rem值，同时修改num赋值语句为式（7）。

3）使用赋值语句i=i+1，将当前节点后移一位，循环上述平滑过程，直到i+1 大于等于节点列表元素数，跳出循环，插值完成。

设置段长值SegmentLength=1，平滑强度strength=0.8，将当前节点列表中的元素代入拟曲线平滑函数，得到如图8 所示路径。

图8 使用改进分段拟曲线平滑所得路径

从图8 可看出，此时路径中已无“急弯”和弧形畸变。

6 仿真测试参数及客观评价

现考虑使用曲率对平滑效果进行客观评价，取路径曲线L拐弯处弧，其切线转角为Δα，弧长为Δs，则该段弧平均曲率为，使点M′沿弧趋向于点M，若弧平均曲率的极限存在，则称其为曲线L在点M处的曲率，记为K,即由于使用拟曲线路径平滑法所得路径并非真实的曲线，而是由若干线段组成，故无法直接用曲率进行客观平滑效果考量，但因平滑后路径视觉效果非常接近曲线，故该实验可使用与该路径弯道处视觉效果重合的曲率圆在弯道中点临近的一段圆弧来近似代替原路径，使考量简化。若曲率半径,那么可以将曲率考量简化为路径拐弯处的曲率半径考量。

通过统计转折处的曲率半径与弧形畸变数量，得到表2（表中贝塞尔曲线平滑法简称“贝塞尔”，拟曲线平滑法简称“拟曲线”，改进分段拟曲线平滑法简称“改进”）。

表2 3种平滑方法下各转折处曲线的曲率半径

剔除畸变值，使用贝塞尔曲线平滑法得到的平均曲率半径为8.58 mm，畸变率为45.45%，使用拟曲线平滑法得到的平均曲率半径为6.50 mm，畸变率为13.64%，使用改进分段拟曲线平滑法得到的平均曲率半径为9.59 mm，无畸变。可以看出，改进分段拟曲线路径平滑法对比贝塞尔曲线平滑法，无路径畸变，且路径拐弯处平均曲率半径增大11.77%。

7 结论

该文以传统A*算法得到的原始路径为基础，针对原始路径冗余节点多、美观度不足的问题，提出了射线简化冗余点与拟曲线路径平滑两种路径处理方法。首先将原寻路环境中的障碍物进行安全膨胀处理，然后通过节点插值、射线法检测障碍物、冗余点删除操作，得到化简后的路径，再以此为基础，进行节点插值后，使用拟曲线平滑，得到较美观的路径，之后在拟曲线平滑的基础上做出改进，提出改进分段拟曲线平滑法，使平滑效果得到提升。仿真结果表明，该方法效果显著。