基于A星算法的游戏路径优化的仿真分析

樊质军+杨朋英+孙玉霞

摘要：路径搜索是许多游戏的核心组成部分，路径搜索的算法有很多，不同的搜索算法有不同的搜索效率。A*算法是游戏中解决寻路问题的主要搜索算法，该文通过对A*算法的分析与研究，找出不足并进行优化和改进。在A*算法基础上添加了一个对障碍预处理的方案，使角色能顺利地绕开障碍，减少搜索不必要的障碍所用的额外的空间和时间。并进行了寻路仿真实验，对比分析了传统算法和改进算法的性能。实验结果表明改进A*算法的可行性与有效性。

关键词：A*算法；启发式函数；寻路；预处理

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）01-0195-02

寻路作为游戏中的基本问题之一，即角色按照程序指定的合适的路径从地图的A点抵达B点，根据角色对周围环境了解程度的不同，分为全局路径规划方法和完全未知或部分未知的局部路径规划方法两种。目前网络游戏、手机增值等业务迅猛发展，寻路技术已成为游戏的一个核心组成部分。物体按照某种指定方式移动，就要求程序必须能够找到一条从起点到目标点的最佳路径，这条路径应该是绕过障碍物并且到达目的地最短的路径，而A*算法就是完成这个任务的最好的算法。

1 A*算法的不足与改进

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

在《一种基于A星算法的游戏路径优化应用》的文章中，讲述了传统A*算法的不足，即在面对障碍时进行了许多无用功结点的搜索，并对此不足作出了相应的改进，添加了一个对障碍预处理的方案，并且额外添加一个destination集合，使角色能顺利地绕开障碍，减少搜索所用的额外内存空间，从而更加智能地到达目标结点，并且对此改进方法作了仿真分析。

2 仿真实验

2.1 实验环境及设备

实验仿真的硬件设备：Inter（R） Core（TM） i5-4200 CPU @ 1.60GHz 2.30GHz，内存为4GB；操作系统为Microsoft Windows 8.1；仿真系统开发平台环境为：Dev-cpp5.4.0；

2.2 实验基本流程及技术难点

2.2.1 实验基本流程

图1为实验整体流程图。

2.2.2 技术难点

（1） 目标结点选取

在传统的A*算法中，目标点只有一个，为了让角色优先到达障碍边界出口点，根据堆栈的思想，将此作为一个destination目标集合，将边界出口点作为最先到达的临时目标点。

（2） 障碍的内存存储

为了用尽可能少的内存存储障碍，运用了一个边界出口点方法，即存储障碍边界点的障碍，这里的方法可以有很多，本文的方法是将障碍再加一层屏障。

（3） 多個边界出口点的选取

一个障碍可能会有多个边界出口点，为了选取最近以及最可靠的出口点，根据角色到出口点加上出口点到终点的距离来进一步判断出口点的选取。

（4） 预处理障碍

在角色寻路的过程中，从角色到目标点或者临时目标点的连线中，如果检测到存在障碍，那么立刻停止检测，就该障碍作进一步处理。

2.2.3 结果数据分析

（1） 内存结点的分析

添加了改进方案的A*算法在搜索的过程中，搜索无用功的结点明显减少，例如表1中哈曼顿的结点从51减少到了16，搜索范围变小，例如多障碍的结点由643减少到了143，并且根据图2可知，结点减少率大约在80%左右，综上所述，改进以后的算法能更精确且快速地绕开障碍并寻找路径，直至抵达终点。

（2） 消耗时间的分析

在实际游戏中，游戏在生成地图的时候已经预处理了障碍，又因为A*算法是基于静态网格下的，即障碍都是静态的，针对5种不同的地形实验进行A*算法改进前和改进后消耗时间的精确测试，如表2和表3，可以清楚地看出每组实验测试了5组数据，并且从中去掉一个最高值和最低值，取剩下三组数据求平均值[1]，使最终的平均值数据更加精确，而5种不同的实验（实验一到实验五）中改进前和改进后结点的个数分别对应为：73，29，730，121，858和14，22，110，52，173，结合这些数据绘制出随着结点个数变化时间消耗分析预测图，如图3，可以明显地看出，虽然在结点很少的情况下，改进后的A*算法所需时间高于传统的A*算法，但是随着结点个数增加，并且根据线性预测分析法[2]可以明显看出，改进的A*算法要优于传统的A*算法，综上所述，在基于改进A*算法上预处理所需内存明显减少的情况下，游戏所运行的的时间也有一定的优化，从而验证了改进A*算法的真实性和可行性。

3 结束语

本文在A*算法的基础上，添加了对就近障碍预处理找出边界出口的方案，结合一个destination集合，对传统A*算法进行了改进，并进行仿真实验，由图2的减少率图和图3的耗时预测分析图可以明显地看出，该改进方法在预处理搜索的内存大大减少，并且基于此在时间上也有一定的优化，综上所述，根据仿真实验结果，验证了改进的A*算法的可行性和真实性。

参考文献：

[1] 周世健. 截尾均值与平尾均值[J]. 地球科学与环境学报， 1996（4）：84-90.

[2] Aitchison J， Dunsmore I R. Statistical prediction analysis[M]. Cambridge University Press， 1975.endprint