一种混合算法在游戏寻径中的应用

王善坤，张治海

（大连理工大学 城市学院，辽宁 大连116600）

一种混合算法在游戏寻径中的应用

王善坤，张治海

（大连理工大学 城市学院，辽宁 大连116600）

路径规划是游戏人工智能领域的核心问题，如何建立一种高效的路径规划方法仍是研究的热点之一。针对游戏中NPC的路径规划问题，将A*算法与改进的人工势场法相结合，提出了一种混合算法。A*算法用于全局路径规划，生成节点路径。改进的人工势场法用于局部路径规划，使NPC能够有效避让环境中的动态障碍物。实验仿真结果验证了该算法的有效性和可行性。

A*算法；人工势场法；路径规划；人工智能

NPC（非玩家角色）通常指的是在游戏中不受玩家控制，而是由计算机控制的角色。如何保证NPC在游戏虚拟场景中无障碍的自由运动一直是游戏寻径问题的研究热点。NPC的寻径问题可以被描述为：为NPC寻找一条从起始点到目标点的安全、无碰撞的最优路径［1］。在以往的研究中，通常将路径规划方法分为两类:全局路径规划和局部路径规划［2］。A*算法是一种最具代表性的全局路径规划方法，但其只适用于静态环境，并不适用于动态环境。人工势场法是一种最常用的局部路径规划方法，该方法结构简单、计算量小，并具备良好的避障能力，但其存在局部极小值等问题。文中提出了一种适用于NPC寻径问题的混合算法，该算法将全局路径规划和局部路径规划相结合：将A*算法用于全局路径规划，生成节点路径。随后对路径进行优化处理，减少了路径中节点的数量，使路径更加平滑、真实；将改进的人工势场法用于局部路径规划，使NPC能够有效避让环境中的动态障碍物。实验仿真结果验证了该算法的有效性和可行性。

1　基于A*算法的全局路径规划

1.1A*算法

A*算法是一种典型的启发式搜索算法，常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上［3］。其启发函数如式（1）所示：

式（1）中，f（n）为起始点经n节点到目标点的启发函数；g（n）为起始点到n节点的实际代价；h（n）为从节点n到目标点最佳路径的估计值［4］。如果估计值等于节点n到目标点的实际距离，那么A*法可以非常高速的找到最佳路径（搜索过程中几乎不会走弯路）；如果估计值比节点n到目标点的实际距离小，那么A*算法保证能找到一条最佳路径；如果估计值比从节点n到目标点的实际距离大，则A*不能保证找到一条最佳 路径，但它运行得更快。

A*算法在执行时需要维护两张表：OPEN表和CLOSED表，OPEN表保存所有已生成而未访问的节点，CLOSED表中记录已访问过的节点［5］。算法执行流程如下：

Step1：设起始点为S，目标点为G，初始化OPEN表和CLOSED表，将起始点S放入OPEN表；

Step2：若OPEN表为空，搜索结束，未找到路径；否则从OPEN表中取出f值最小节点n；

Step3：若n为目标点G，搜索结束。从目标点G回溯到起始点S，获得两点间的最佳路径；

Step4：若n不是目标点，则检查n的全部连通的相邻子节点。对于每一个子节点m，计算g（m）的值。若m在OPEN表中，且其值比表中的小，则将n作为m的父节点，并重新计算g（m）和f（m）；若m不在OPEN表中，则将n作为m的父节点，计算g（m）、h（m）和f（m），并将其加入到OPEN表中；

Step5：从OPEN表中删除节点n，并将节点n放入CLOSED表；

Step6：重复Step2～Step5，直到搜索到目标点G，或是搜索失败，路径不存在。

1.2路径优化

A*算法所规划的路径是由一系列路径节点构成的，图1所示为从A到C的节点路径。A*算法所规划的路径中存在着大量的多余节点，例如，图1中A、B间是可视的，两点间存在直线路径，A、B间的其余节点都是不必要的。优化A*路径就是仅保留路径中的必要节点，删除路径中的非必要节点，优化前和优化后的路径，分别如图1和图2所示。从图中可以看到，优化后的路径更短、更平滑，并且突破了网格地图中A*路径的8方向限制，实现了360度的全方位路径。

图1　未优化的路径

图2　优化后的路径

2　基于改进人工势场法的局部路径规划

人工势场法是一种常用的局部路径规划方法［6］，它的基本思想是将NPC抽象成一个质点，将其在游戏虚拟环境中的运动，抽象成在人造的虚拟力场中的运动，目标点对其产生吸引力，障碍物对其产生排斥力，最后通过求合力来控制NPC的运动。应用人工势场法规划出来的路径一般是比较平滑并且安全，但是这种方法存在局部极小值等问题。

2.1斥力势函数

在虚拟力场中，障碍物对NPC产生斥力。算法中所用的斥力势函数如式（2）所示：

在式（2）中，η为斥力系数；ρ（x，x0）为NPC与障碍物之间的最短距离；ρ（x，xg）为NPC与目标点之间的相对距离；ρ0为常数，在ρ0的范围内NPC受到障碍物的斥力，在此范围外则不受斥力作用。斥力为斥力势函数的负梯度，可以分解为两个分力之和，即：

在式（3）中，Frep为障碍物对NPC的排斥力，Frep1和Frep2是它的两个分力。Frep1的方向是从障碍物指向NPC，Frep2的方向是从NPC指向目标点。

2.2引力势函数

在虚拟力场中，目标点对NPC产生吸引力。算法中所用的引力势函数如式（6）所示：

在式（6）中，k为引力系数；ρ（x，xg）为NPC与目标点之间的相对距离。引力为引力势函数的负梯度，其方向从NPC指向目标点，即：

NPC所受的合力如式（8）所示:

2.3斥力系数

传统的人工势场法认为所有障碍物对NPC的排斥作用都是相同的，因此NPC对所有障碍物都应采用相同的避让策略。但在游戏场景中，不同位置、不同类型的障碍物对NPC的排斥作用是不一样的，越是靠近NPC的行进方向、对NPC的威胁越大的障碍物，其对NPC的排斥作用就越明显，因而NPC总是会选择优先避让位于其行进方向上的最具威胁的障碍物。将以上策略应用于传统的人工势场法，引入斥力系数Cfr，Cfr的计算公式如式（9）所示：

在式（9）中，θ为NPC行进方向与斥力之间的夹角；β为威胁因子，其值大于、等于1。引入斥力系数后，斥力计算公式如式（10）所示：

3　混合算法

传统的路径规划方法并不适用于复杂、多变环境中的NPC路径规划问题，文中将全局路径规划和局部路径规划相结合，提出了一种适用于NPC路径规划的混合算法。首先根据已知全局环境信息，将A*算法用于全局路径规划，生成从起始点到目标点的全局路径，并对路径进行优化处理，剔除路径中的冗余节点，使路径变得更平滑。然后根据从NPC运动过程中所获取的局部环境信息，将人工势场法用于局部路径规划，对路径进行优化、调整，使NPC安全、无碰撞的到达目标点。混合算法不仅利用全局环境信息建立了全局最优路径，还具有良好的避障能力，有效解决了复杂、多变环境中的NPC路径规划问题。算法执行流程如下：

Step1：根据已知环境信息，将A*算法用于全局路径规划，生成从起始点到目标点的路径节点序列；

Step2：优化A*路径；

Step3：将路径中起始点的相邻节点作为子目标点；

Step4：获取NPC的位置及其视距内的局部环境信息，计算引力Fatt，斥力Frep及其合力F；依据作用于NPC上的合力F和NPC的速度，计算NPC的新位置；

Step5：当NPC的运动出现停滞或震荡时，利用A*算法重新规划从NPC当前位置到子目标点之间的路径；优化新路径，并用其替代原路径；

Step6：重复Step4～Step5，直到NPC到达子目标点；

Step7：取路径中当前子目标点的下一个相邻节点作为子目标点；

Step8：转到Step4，直到NPC到达目标点；若N步后仍未到达目标点，则转到Step1重新规划。

4　实验仿真分析

实验仿真的硬件环境：CPU Intel®CoreTMi5-2400@3.1 GHz，内存为2GB；软件环境：操作系统为MicrosoftWindows XPProfessional；仿真系统开发平台为：MicrosoftVisualC++6.0。

实验仿真环境为仿真软件生成的30×20的网格地图，如图3所示。地图中点S为路径搜索的起始点，点G为路径搜索的目标点，黑色方格表示森林、山川、动物等人为设置的障碍物，黑色方格区域为NPC不可通行区域，白色方格区域为NPC可通行区域。首先根据全局环境信息，将A*算法用于全局路径规划，生成并优化一条从起始点S，到目标点G的节点路径。图4中的两个黑色小圆点，为优化后的路径节点。随后，将改进的人工势场法用于局部路径规划，控制NPC沿着A*算法所规划的路径移动，并能够有效的避开动态障碍物。图5中，在已规划的路径上出现了5处点状障碍物，NPC依然可以避开障碍物，继续沿着A*所规划的路径向目标点移动。图6中，前方路径上出现了“L”形障碍物，NPC移动到“L”形障碍物前出现了停滞，陷入了局部极小点。当NPC的运动出现停滞或震荡时，利用A*算法重新规划从NPC当前位置到子目标点之间的路径，优化新路径，并用其替代原路径。图6中，在“L”形障碍物附近出现的两个小黑点为新规划的路径节点，由新路径替代原有的路径，NPC沿着新规划的路径移动，最终到达目标点。从上面的实验仿真结果可以看出，该算法所规划的路径较之传统的A*算法更加平滑、真实，算法的避障性能要优于传统的人工势场法。

图3　优化后的路径

图4　A*规划的全局路径

图5　仿真过程

图6　仿真结果

5　结束语

文中将A*算法与改进的人工势场法相结合，提出了一种适用于NPC路径规划的混合算法。该算法取两者之长，去两者之短，即解决了A*算法所规划的路径不够平滑的问题，又解决了人工势场法存在的局部极小值问题。实验仿真结果表明该算法生成的路径更平滑，并且具备良好的避障能力，使得NPC的寻径更加自然，有效地提高了NPC智能性。

［1］柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动机器人动态路径规划方法［J］.电子学报，2011，39（5）:1220-1224.

［2］叶炜垚，王春香，杨明，等.基于虚拟障碍物的移动机器人路径规划方法.机器人［J］，2011，33（3）:273-275.

［3］Amit.Pathfinding-Introduction［EB/OL］.（2009-05-01）［2014-09-30］.http://theory.stanford.edu/～amitp/GameProgramming/Astar Comparision.htm l.

［4］詹海波.人工智能寻路算法在电子游戏中的研究和应用［D］.武汉:华中科技大学，2006.

［5］张程，肖大薇，张盈谦.基于区域搜索的A*算法在游戏寻径中的应用研究.电子设计工程［J］，2014，22（13）:15-17.

［6］张殿富，刘福.基于人工势场法的路径规划方法研究及展望［J］.计算机工程与科学，2013，35（6）:89-95.

The study of hybrid algorithm in im p lementing of game

WANG Shan-kun，ZHANG Zhi-hai
（City Institute，Dalian University of Technology，Dalian 116600，China）

Path planning is the core issues in theartificial intelligence field ofgames，and how to establish an effectivemethod of path planning is still focused on.For path planning of NPC in the environmentof games，combiningwith the A*algorithm and the improved artificialpotential fieldmethod，A hybrid algorithm is proposed.A staralgorithm has utilization in the global path planner and created the node path.The improved artificial potential field method is applied to local path planner and it can achieve the aim at avoiding the dynamic obstacles in the environment.The experimental simulation result verifys the feasibility and effectivenessof the algorithm.

A star algorithm；artificial potential field method；path planning；artificial intelligence

TN02

A

1674-6236（2016）19-0022-03

2015-10-17稿件编号：201510107

王善坤 （1960—），男，辽宁大连人，副教授。研究方向：人工智能、数据挖掘。