CGF路径导航规划及优化转向问题研究

李国平

（石家庄机械化步兵学院，河北 石家庄 050083）

在战术级的虚拟作战仿真中，仿真成员除部分仿真实体模型外，还存在一些具有自主智能属性的虚拟仿真成员，称为计算机生成兵力（Computer Generation Force,CGF），其通过构建作战实体的物理、行为、环境等仿真模型，最大限度地真实再现作战单元的各种战场行为。

目前，随着遗传算法、学习机制、神经网络等多种人工智能方法的发展和应用，CGF实体已经具有了较高的智能属性，但在一些具体的应用中，还需要有针对性地对CGF智能体行为进行改进，如CGF在作战仿真中的路径选择，不仅要满足战术需求，而且要最优化，能够逼真地再现运动状态。本文针对其中的CGF路径导航原理及导航点位置转向问题进行研究。

1 CGF路径导航

1.1 CGF路径导航原理

CGF在虚拟战场的行进路径是通过连接CGF初始位置、目标位置，以及预先设定的导航点来确定的。初始位置是 CGF实体在执行某次作战任务时的当前位置，通过战场地形环境信息来获取；目标位置根据作战任务来确定；导航点则是根据CGF的运动属性、作战要求、地理环境、仿真需求等多个影响因素综合确定。在构建虚拟战场环境时，应预先建立导航点链表。

确定CGF初始位置、目标位置后，下一步需要确定初始位置与目标位置之间的导航点。影响导航点确定的关键因素为战术需求，因此导航点确定的第一步为确定关键导航点，即在导航点链表中搜索CGF运动过程中因作战需要必须经过的地域范围内的导航点；第二步为确定初始位置与离初始位置最近的关键导航点之间、关键导航点与目标位置导航点之间的一般导航点。一般导航点的数目可由仿真系统的需求精度来确定。

在确定完导航点后，CGF从初始位置到目标位置之间运动路径可能存在多条，需要在仿真运行开始前选取一条最优化的路径，实际应用中可通过A*路径搜索算法来实现，本文不具体描述。

1.2 CGF路径导航规划

CGF在虚拟战场中的运动路径规划一般分为三种类型：静态规划、动态规划和综合规划。静态规划是根据战术行动任务的作战方向，预先在仿真系统运行前通过确定初始位置、目标位置、关键导航点、一般导航点，并利用路径优化搜索算法确定出一条最优路径，在仿真系统运行期间，CGF实体只能按照预定路线运动。动态规划是指在仿真系统运行期间，CGF实体的运动路径是通过偶然事件触发临时确定的，规划方法同静态规划。综合规划是静态规划与动态规划两者的结合运用，首先通过静态规划确定好一条预先路径，当CGF实体在仿真运行过程中因发生突发事件而需要改变方向时，再改变原有运动路径。

比较以上三种规划，静态规划由于是预先规划路径，在仿真系统运行期间大大降低了系统负荷，有效地提高了系统运行效率，但由于不能临时改变 CGF的运行路径，因此不能够实时反应战场偶然变化所引起的CGF实体作战行为，仅适用于CGF实体具有固定运动路径的系统仿真，如机动仿真。动态规划的路径确定由于是在仿真系统运行期间进行，在很大程度上占用了系统运行资源，对系统运行的实时性有较大影响，仅适用于偶然性、短周期的战术行动仿真。综合规划兼顾了静态规划和动态规划的优点，不仅最大程度考虑了作战的偶然性因素，而且显著地提高了系统的实时性、高效性、逼真度，在战术级作战仿真系统构建中应用非常广泛。

2 CGF导航点优化转向算法

2.1 CGF导航点转向

通常情况下，CGF运动到下一导航点位置时会发生运动方向的改变，即导航点转向。导航点转向原理为：按照预先设定CGF行进方案或偶然事件出发，构建以导航点为圆心、CGF实体在导航点转过的最大弧度圆弧半径末端构建虚拟导航点A'、B'，如图1（a）所示，然后从CGF运动方向发生变化开始，通过对图1（a）运动折线进行采样、拟合，最终形成图1（b）所示的运动曲线路径。

图1 CGF运动路径示意图

图1中转向半径即为CGF在导航点转过的最大弧度圆弧的半径。

2.2 CGF导航点优化转向算法及实现

在仿真系统运行过程中，CGF会沿着拟合后的曲线路径运动至导航点，此时供CGF到达下一目的地的路径有两个选择：（1）CGF实体向左转，沿逆时针方向的圆弧，直到朝向下一目标方向；（2）智能体向右转，沿顺时针方向的圆弧，直到朝向目标方向，进而沿着直线机动到目标位置，如图2所示。

图2 CGF转向示意图

通常情况下，图2中标示的两个路径距离不会相等，必有一个最短的优化路径作为CGF在导航点路径的选择。因为CGF在沿着拟合后的曲线路径运动到与目标方向一致时，很可能移动了近半个圆，或者是较小角度，这取决于初始方向与到达目的地的方向夹角。关于图2的两条路径距离计算的几何关系如图3所示。

图3 CGF转向几何关系示意图

图3所示的几何关系基于笛卡儿坐标系，点P是圆弧的圆心，也就是转向半径所在圆的圆心，点Q是CGF离开圆弧轨迹的位置（直线轨迹的起点），而d是直线部分的长度。

计算最优路径的方法，首先假设 CGF实体运动路径在其视线方向上进行了拟合平滑处理，在直线方向上删除了不必要的临时导航点。

计算两个导航点最短路劲的程序代码如下：

在以上算法中应用到了 CGF的原始点位置坐标及方向角，而在实际仿真过程中，这两个值都是随时间而变化，因此需要实时确定CGF实体的即时位置和方向角作为 CGF在导航点转向仿真周期内的原始点和方向角。下面程序说明如何实现即时位置和方向角。

2.3 消除导航点转向实体

上述最优路径算法结合了折线平滑方法，通常在设置导航点时，往往以虚拟战场中的障碍物、独立点为导航点，因此有可能出现CGF实体在曲线路径上运动时与虚拟战场中障碍物重叠的现象，如图4所示。

图4 CGF导航点转向碰撞示意图

为了解决此类问题，可以采用可变转向半径的方法来修正CGF的行进路径。在实际仿真系统应用中，CGF实体可为装甲车辆、分队等实体单位，当这些实体在导航点转向时，相对于导航点分别存在一个最近点位置B和一个最远点位置A，如图5所示。

图5 CGF可变转向半径示意图

CGF在导航点附近沿着拟合曲线路径进行转向时，可以预先调整、控制B点距离O点的距离始终大于一个固定值，并以距离导航点最近点B为圆心、AB为半径同时相对自身转向，等同于实时改变了转向半径，即可变转向半径。采用可变转向半径方法，有效地保证了CGF实体与导航点障碍物之间的距离，避免了CGF在转向过程中与障碍物碰撞现象的发生。

3 结束语

本文首先对 CGF实体在虚拟战场中的路径导航问题进行了规划，提出了三种常用方法及应用方向，重点给出了实现 CGF在一个导航点和下一个预订导航点之间更为逼真、精确的转向方法，并介绍了处理CGF实体在运动过程中可能出现的与障碍物碰撞问题的解决方法。在具体的CGF智能体运动应用中，应根据实际的战术仿真需求灵活采用不同的方法，以便提高仿真的实时性和逼真度。

[1]Printer MARCO.Toward More Realistic Pathfinding[J].Game Developer magazine,April 2001.

[2]Rbin STEVE.A* Aesthetic Optimizations[J].Game Programming Ggems.Charles Riever Media,2000.

[3]Pottinger DAVE C.Coordinated Unit Movement[J].Game Developer magazine,6(1),January.1999,6(1).

[4]王杏林,郭齐胜,等.基于多agent的聚合级CGF系统的体系结构研究[J].计算机工程与应用,2001(19):64-66.

[5]张航义.基于Agent的CGF行为建模技术研究[J].计算机仿真,2002,20(8):79-811.

[6]田尊华,赵龙,贾焰.基于实体行为的动态碰撞检测算法研究[J].系统仿真学报,2009(5).