李子涵，孙建红，王永利

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

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

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

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

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

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