一种基于A星算法的游戏路径优化应用

孙玉霞，樊质军

(湖北师范大学 计算机科学与技术学院 ，湖北 黄石 435002)

一种基于A星算法的游戏路径优化应用

孙玉霞，樊质军

(湖北师范大学 计算机科学与技术学院 ，湖北 黄石 435002)

A*算法作为游戏中解决寻路问题的主要搜索算法，本文讨论了A*算法的基本原理，交代了其在游戏寻路过程中的作用及缺陷，并在A*算法基础上添加了一个对障碍预处理的方案，用一个destination集合，使角色能顺利地绕开障碍，减少搜索不必要的障碍所用的额外内存空间和运行时间，从而更加智能地到达目标结点。实验仿真证明了该算法的有效性和可行性。

A*算法；启发式函数；路径优化；预处理功能

寻路作为游戏中的基本问题之一，即角色按照程序指定的合适的路径从地图的A点抵达B点，根据角色对周围环境了解程度的不同，可分为两种类型：全局路径规划方法和完全未知或部分未知的局部路径规划方法[1]。而在此基础上，发展了许多以启发式算法为核心的智能算法，包括A*算法、D*算法、遗传算法、模拟退火算法和蚁群算法[2～5]。

启发式的A*搜索算法作为路径优化和路径搜索的经典方法，在战略性游戏中都是以此为基础来进行寻路的，虽然相对于那些老式的搜索算法，比如深度优先搜索算法，广度优先搜索算法，Dijkstra搜索算法[6～8]，在时间复杂度和空间复杂度要好的很多，但是A*搜索算法本身也存在不足，尤其是在搜索过程中出现前方障碍的问题，虽然启发式A*搜索算法可以在搜索的过程中有“方向”地往终点寻路过去，但是当遇到障碍时，也会在障碍周围进行搜索，即做了许多无用功的结点搜索，因为障碍阻挡了前方A*搜索的道路，国内外的学者也对此进行了大量的研究，例如：王善坤等[9]根据改进的人工势场法让绕过障碍的曲线更加平滑，但是依然需要在障碍周围进行搜索；蔡方方等[10]根据双层A*算法进行二次搜索来绕过障碍，虽然可以避开了障碍，但是增加了额外A*算法搜索时间；高庆吉等[11]引入了“人工搜索标记”，起到预先判断或者逃离障碍物的作用，但是依然需要对障碍周围进行无用功结点的搜索预处理。综上所述，虽然目前学者们做出了许多研究，但是依然存在搜索过程中无用功结点的出现，本文在A*算法的基础上，并在A*算法搜索的过程中，添加了一个对障碍预处理的方案，并且额外添加一个destination集合，使角色能顺利地绕开障碍，减少搜索所用的额外内存空间，从而更加智能地到达目标结点。所做的仿真实验结果中也证明了改进后算法的合理性和可行性。

1 基于A*算法的搜索规划

1.1 A*搜索算法

启发式A*搜索算法，顾名思义，就是有启发地寻找目标结点，并且在基于最小的成本下，尽可能地找到通向目标点的最合适并且最短的路径。

为了达到启发的目的，与一般的搜索算法不同，可以看图1和图2对比，在A*算法中，十分奇妙的设计了一个估价函数，这是最主要的部分：

f(n)=g(n)+h(n)

其中f(n)是从当前结点展开(一般在网格中是八个方向)搜索出来的结点的估价值，g(n)表示从当前结点到预处理搜索点的估价值，h(n)则表示预处理的结点中与目标点的估价值。

A*算法的寻路步骤如下(其中open集合列表表示预处理但未访问的结点，close集合列表则表示已经访问过的结点)：

1)从起点start开始, 把它作为一个结点首先放入open集合列表中。

2)同时预处理start起点的周围结点，一般在网格中是8个方位，并且把这8个方位的父节点设置为该start结点。

3) 当周围结点搜索完毕后，将start结点从open集合列表中删除，同时放入close集合列表中。

4)先检查预处理的这些点，是否是“可用结点”(不是障碍或者不在close集合列表中)，当确认是可用结点，则计算那些预处理结点的f，g，h的值，同时在计算的过程中比较大小，将最小的结点排在open集合列表中，方便下一步使用。

5)如果某个预处理结点已经在open集合列表中了, 检查如果用新的路径时此时的估价函数是否更低，如果是，则更新，更新的同时也需要适当调整下大小排序，否则不更新。

6)判断该相邻方格是否为终点，不是的话重复第4,5步，是的话就结束程序，并且根据之前每个结点存在的父节点，回溯标记，找到终点，并且输出路径，结束程序。

图1 一般搜索算法的预处理搜索范围

1.2 传统启发式A*搜索算法的不足

在A*中算法中，最重要的就是启发式函数的选取，不同的启发式函数会造成不同搜索范围，搜索范围越小，搜索路径越精确，造成的误差就会越少。但是当前方存在障碍时，会出现许多无意义的搜索，引起绕道或者原路返回，则花费大量不必要的时间和空间，如图3 .

图3 A*算法遇障碍时搜索范围

2 针对A*算法不足的改进方案及思路

基本思路：在小人寻路的过程中，自动绕开前方的障碍物，避免走进复杂或者特殊地形，从而避免搜索更多无意义的结点，达到搜索范围更小，确定目标更精确的效果。具体思路如下：

1)利用局部障碍检测方法对最近障碍物进行预处理

在搜索过程中将可能遇到的障碍进行预处理功能，从而使小人在寻路过程中，自动避开障碍物，避免无意义的搜索。在障碍物的预处理上，为避免浪费大量时间，采用目标点局部障碍检测方法，即当朝向目标点的前方出现障碍的时候(如图4，图5)，取最近的障碍并且检测，在程序中，可以将小人和目标点连成。

图4 小人寻路时所遇障碍

一条直线，从小人这个点往目标点作一个射线，一旦该射线有障碍，那么就检测到了障碍，并且将该障碍物做预处理，如果该射线没有遇到障碍，就说明前方通畅无阻，就可以笔直地往目标点走去了。

2) 以两个边界结点坐标确定障碍位置并进行存储

为了用尽可能小的内存来存储障碍的坐标结点，只需要存下两个边界点的坐标(当然，也可以存下大于两个的边界点坐标)，其中边界点的特点就是，除了一个方向，其他方向都没有相应的障碍。

3) 添加destination列表，表示目标结点集合

确定了障碍的边界点以后(边界点可以有多个点，为了方便起见，设两个障碍边界点为A点和B点，并且O点为小人所在点，C点是最终的终点)，然后需要计算OA+AC和OB+BC的绕行距离，但是无论是曼哈顿距离，还是对角线距离，或者是欧几里得距离，都比绕行距离要小，并且距离差会随着目标障碍物的增大而增大。此时增加一个destination目标节点列表，表示目标节点集合，此列表操作的顺序是先进先出，利用此方法会优先找到绕开障碍的一个出口点，出口点就是当前的目标点。假设此时B点是出口点即目标点，那么将B点先压入destination列表中，由于到B点的路畅通无阻，所以小人将迅速找到B点，并且完美地绕开了障碍物，此时B点出栈，目标点变为了原终点C点，再继续搜索找到C点，将C点出栈，此时destination列表中没有任何集合，小人寻路完成，至此程序结束。

图6 传统A*算法搜索范围

3 实验仿真分析

实验仿真的硬件环境：Inter(R) Core(TM) i5-4200 CPU @ 1.60GHz 2.30GHz,内存为4GB;操作系统为Microsoft Windows 8.1;仿真系统开发平台为:Dev-cpp5.4.0;

实验仿真环境为仿真软件生成的50×50的网格地图，如图6和如图8所示。其中s代表起点，A代表所预处理搜索的结点，x代表障碍，小点则代表可通行的路径，d代表终点。首先，图6中，仿真实验很好的验证了前文1.2中A*算法在遇到障碍时的不足，即虽然有启发式地向目标点寻去，但是也要在阻碍它的障碍周围进行预处理搜索。图7中运用了改进后的方法，可以明显看出预处理搜索的范围减少了。图8中，加入了多种复杂障碍，也能很明显的看出，当障碍复杂，起始点与目标点距离远时，A*算法这一不足突出地更加明显，为了让读者分辨清楚，用红色框框着的区域代表障碍。图9中，当我们运用了改进后的A*算法时，更加可以明显地看出，搜索预处理的结点数大大减少，并且也同时更加智能地绕开了障碍，最终达到目标点。从上面的仿真实验结果可以看出，该改进后的A*算法较传统的A*算法，预处理的搜索范围明显减少，也更加智能地绕开了障碍，大大提升了性能。

图8 传统A*算法在多障碍下的搜索范围

4 结语

本文在基于A*算法的基础上，添加了对就近障碍预处理找出边界出口的方案，并且结合一个destination集合，结合这三种方法，改进了传统A*算法在游戏中的运用，即解决了前方出现障碍时(特别在障碍拥有特殊地形的情况下),出现许多无用功搜索结点，从而消耗额外内存,大大减少了对额外内存的消耗；同时，也为游戏中小人在寻找较远目标点时，减少了所消耗的额外时间(如转向问题)，仿真实验也证明了该改进算法的可行性和真实性。从而使小人在绕开障碍时变得更加智能化，同时也让游戏变得更加流畅，大大提升了游戏的品质，也给玩家在游戏中带来更好的体验。

[1]庄慧忠,社树新,吴铁军.机器人路径规划及相关算法研究[J].科技通报,2004,20(3):210～215.

[2]陈和平,张前哨.A*算法在游戏地图寻径中的应用与实现[J].计算机应用与软件,2005, 22(12):118～120.

[3]Stentz A.Optimal and efficient path planning for partially-known environments[C].Proceedings of the IEEE International Conference on Robotics and Automation. San Diego, Carlifonia, USA,1994:3310～3317.

[4]Gemeinder M,Gerke M.GA-based path planning for mobile robot systems employing an active search algorithm[J].Applied Soft Computing, 2003, A3:149～158.

[5]Dorigo M,Maniezzo V,Colorni A. Ant system:optimization by a colony of cooperating agent[J].IEEE Transactions on Systems Man and Cybernetics, 1996,26(1):29～41.

[6]田翠华,许卫平,陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报(自然科学版), 2013, 29(3):19～24.

[7]卢启衡,冯晓红.基于宽度优先搜索的路径生成算法[J].现代计算机:专业版,2006(12):87～89.

[8]蔚洁,杨怀雷,成汝震.基于Dijkstra算法的最优路径搜索方法[J]. 河北师范大学学报(自然科学版),2008,32(5):590～593.

[9]王善坤,张治海.一种混合算法在游戏寻径中的应用[J].电子设计工程，2016(19)：22～24.

[10]蔡方方,杨士颖,张小凤等.双层A_算法在游戏寻路方面的研究[J].微电脑应用,2010,6(1):26～28.

[11]高庆吉,于咏生,胡丹丹.基于改进A*算法的可行性路径搜索及优化[J].中国民航学院学报，2005,23(4):42～45.

A game path optimization application based on A* algorithm

SUN Yu-xia,FAN Zhi-jun

(College of Computer Science and Technology, Hubei Normal University,Huangshi 435002, China)

A* algorithm is the main search algorithm to solve the problem of pathfinding in the game, this paper discusses the basic principle of A* algorithm, explains its functions and defects in the process of finding the game, and based on A* algorithm adds a scheme of obstacle pretreatment, with a collection of destination, the role can avoid obstacles successfully, to reduce the extra memory space and run time used to search for unnecessary obstacles, and thus more intelligently to reach the target node. The simulation results show the effectiveness and feasibility of the algorithm.

A* algorithm; heuristic function; path optimization; preprocessing function

湖北省教育厅重点项目(D20162501)

2017—01—05

孙玉霞(1976— )，湖北黄冈人，硕士，副教授。

TP301.6

A

2096-3149(2017)02- 0072-05

10.3969/j.issn.2096-3149.2017.02.016