改进A*算法在游戏地图路径搜索中的应用研究

钟 瑛 陈凌峰 朱顺痣

（厦门理工学院计算机与信息工程学院 福建 361024）

0 前言

全球电子游戏产业始于20世纪70年代，在这四十多年的快速发展中，从电视游戏、电脑游戏再到网络游戏，电子游戏产业在全球市场中占据了不可忽视的份量。2000年中国网络游戏市场规模仅为0.3亿元人民币，到2006年市场规模已经达到65.4亿元人民币，2011年中国网络游戏市场规模达413.8亿元，环比增长17.5%。同时网络游戏也带动了如通信业、IT产业、媒体以及出版业等发展[1]。

对游戏方面的学术研究和科技发展一直是游戏产业快速发展原因之一。路径搜索问题作为其中一项重要的研究课题也一直被学者们研究讨论。路径搜索问题本质上是指在给定的网络图中寻找出一条从起始点到目标点之间最短路径[2]。对于路径搜索问题，已经有很多搜索决策了，大体上可以分为盲目搜索算法和启发式搜索算法。A*算法作为启发式搜索算法之一，被广大游戏开发人员应用于游戏地图中的路径搜索。

1 A*算法

A*算法是启发式搜索算法的一种，也被称为最好的优先搜索算法，在许多游戏路径搜索中都会使用A*算法，是由著名的人工智能学者Nilsson等专家提出的。A*算法采用的表达式是：F(n)=H(n)+G(n)，F(n)表示节点n的估价函数，G(n)表示从起始节点S0到节点n的行走代价，H(n)是从节点n到目标节点Sg的最优路径的估价值[3]，这个依赖于启发式信息。A*算法对启发函数进行了一些条件约束，例如：对于所有的节点，均有h（n）≤h*（n）,h*（n）是节点n到目标节点Sg的实际距离，这样能够保证寻找到的路径是最优路径。

A*算法的具体步骤如下：

将起始节点S0放入OPEN表中。

如果OPEN表为空，则搜索失败，退出算法。

选择OPEN表中F值最小的节点为当前节点n，然后移到CLOSE表。

判断当前节点n是不是目标节点Sg，如果是，则搜索成功，退出算法；否则继续第（5）步。

扩展当前节点n的所有子节点，若没有可扩展的子节点，则算法继续；否则，设子节点m，对每一个子节点计算其F值、G值、H值，并作如下判断：

子节点m既不在OPEN表中也不在CLOSE表中，则将它放入OPEN表中，并将一个指向父节点的指针指向节点n。这样当找到目标节点的时候可以根据这个指针，回溯到起始节点，得到搜索到的路径。

子节点m已经在OPEN中，判断新F值是否小于已有的F值。若是，则更新子节点m的数据，并将指针指向节点n，否则不处理。

子节点m已经在CLOSE表中，则不作处理，继续算法。

跳转到第(3)步，直至找到目标节点或者搜索失败。

2 A*算法的不足和改进

2.1 A*算法的不足

虽然A*算法相对于其他算法都具有较高的效率，但其本身也存在着不足，可以归纳为两点：

对OPEN表的遍历。在A*算法选择进行扩展的节点时，都要在OPEN表中选取F值最小的节点来进行扩展。此时，需要对OPEN表进行遍历，这一步骤是A*算法中最耗时的部分。在寻找F值最小的节点的时候，需要对OPEN表进行排序或者比较，然而，游戏环境中的节点有时都会成千上万，导致OPEN表中存储的节点势必也会很多，遍历OPEN表则将产生很大的计算量。而在游戏中，路径搜索要反复进行，OPEN表也会反复被遍历，如此累计起来的大量耗时计算，会让玩家有种极其不好的游戏体验感。

如果搜索的路径相对较长，靠近目标节点由于G值的不断累计将导致F值会相对较大，而该节点的F值会和远离目标节点的部分节点的F值相同，A*算法计算过程中会把这些节点也计算进去，最后将导致产生大量的无用节点。因此，通过减少无用节点量也会提高A*算法的效率。

2.2 A*算法的改进

针对上述所说的不足，本文提出了相应的改进方法，针对OPEN表的遍历，使用最小二叉堆进行优化OPEN表结构；针对计算过程产生的过多无用节点，采用以向量夹角余弦作为新启发式信息加入计算的方法来改善。

（1）最小二叉堆优化OPEN表遍历

最小二叉堆是二叉堆的一种数据结构，其定义是：二叉堆是一颗有序的完全二叉树。所谓有序性，就是父子节点值之间有大小的约定。如果每个节点的值都小于它的子节点的值，则称为最小化堆[4] ，也就是最小二叉堆。使用最小二叉堆存储OPEN表中的节点，以节点的F值作为父子节点值的约定，每个节点的F值都比它的子节点的F值都要小，依次类推，其根节点便是OPEN表中F值最小的节点。所以当搜索过程中需要寻找最小F值时，直接读取根节点就可以。

（2）以向量夹角余弦作为新启发式信息

在3.1的(2)所提到的不足点，在A*算法中是一种常见现象。因为随着路径搜索的不断深入，节点的G值不断累积，虽然H值会随着靠近目标节点而减小，但F值总体是递增的。而对于那些远离目标的节点，是H值较大，G值较小，但组成的F值可能和那些靠近目标节点的F值相同，从而导致算法对两种节点都会计算，增加了计算量。为此，本文对该现象提出了以向量夹角余弦作为新启发式信息来解决这个问题。

如图1，A为起始节点，B为目标节点，C和D分别是A*算法搜索过程中考察过的节点，则向量和向量之间的夹角为α，向量和向量之间的夹角为β。假设采用欧几里得距离作为启发函数的A*算法，C和D的各自F值刚好相同，而C点在最优路径上。那么在计算过程中，C点和D点都会被考察，但由于C点更接近于目标节点B且在最优路径上，C点应更优先计算，而D点虽然会被考察但会变为无用节点。

根据向量夹角余弦公式和A、B、C各自的坐标，可以求出：

图1 不同位置的向量夹角余弦

为此，根据余弦函数，本文对每一个需要计算启发函数的节点n作如下处理：

节点n的启发函数：

其中，ho（n）是节点n根据欧几里得距离计算出的估价值，hcos（n）是节点n根据节点n和起始节点组成向量和向量

之间的夹角ω的余弦值的估价值。W是一定权值。

所以，对于C、D两点有：

通过上述处理后，必定存在Fcos（C）＜Fcos（D），因此，在计算过程中，C点比D点优先考查。当C点的后续节点m存在Fcos（m）≤Fcos（D），D点将在计算结束前都不会被考查，则程序将减少对无用节点的考查，加速了程序的运行。如果将这样的处理扩大到整个程序的计算过程中，必然会减少考查无用节点数，程序的计算效率便能得到进一步的提高。

为了保证A*算法的单调性约束h（xi）-h（xj）≤c（xi，xj），选择适当的W来保证限制，具体测试数据及结果见后续。由此可知，节点n离目标节点和起始节点的连线越远，则hcos（n）越大，估价函数值也会比原本没有加入hcos（n）时的估价值还大。并且hcos（n）是非直线式变化的。通过加入向量夹角的余弦值作为启发式信息之一，可以限制A*算法的搜索范围，减少搜索过程中无效节点的数量。

3 仿真实验模拟

本文使用MFC程序实现了标准的A*算法和改进的A*算法。将标准的A*算法、Dijkstra算法、加入向量夹角余弦的改进A*算法进行了比较，同时还对不同W权值的改进A*算法进行了比较。在此，所有的计算都是使用了最小二叉堆的OPEN表进行计算。图1 是在仿真实验中标准A*算法的路线图。

图1 仿真实验程序中标准A*算法

3.1 改进A*算法的对比试验

上述中，我们提出将向量夹角余弦加入估价函数中进行搜索。在对向量夹角余弦附上权值W并进行一定的处理后，作为启发式信息来缩小A*算法的搜索范围，提高其效率。当考察的节点离起始节点和目标节点之间的直线越远，其估价值就会因为新启发式信息而变大，其增加量是曲线增长的。经过多次试验测试后，确定权值W在一定范围内，可大大减少A*算法的搜索节点数和总访问节点次数。

表1 不同权值W的采用向量夹角余弦作为启发式信息的改进A*算法

由上面的数据可以看出，标准A*算法的搜索节点数和总访问节点次数都较大。而无论权值W多少，改进A*算法的搜索节点数和搜索总访问节点次数都少于标准A*算法，说明这个启发式信息是符合A*算法的搜索。并且权值W为15比W为5的A*算法更具有效率。本文采用的启发函数是欧几里得距离，而这样的估价值是远远小于实际最优路径值，那么加入新启发式信息，也能够保证A*算法的单调性约束。通过数据分析，采用新启发式信息的改进A*算法比标准A*算法提高了1-15%不等，且取决于权值W。

3.2 Dijkstra算法、改进A*算法对比试验

传统的路径搜索问题的算法有很多种，而常用于游戏地图的搜索算法是A*算法和Dijkstra算法。因此，仿真实验中也把Dijkstra算法作为其中一种路径搜索算法进行比较，从中可以对比三种算法在游戏地图中的路径搜索效率。以下是50组数据中的6组数据。

表2 多种路径搜索算法的实验数据

1 94 120 384 413 88 187 2 58 126 124 129 51 112 3 104 257 393 435 96 228 4 43 79 161 178 32 56 5 66 143 285 308 57 120 6 101 244 376 410 93 213

从上述数据中可以看出，虽然在问题有解的情况下，Dijkstra算法能够找到解且是最优的，但它搜索节点数和总访问节点次数都是非常多，如果应用于实际游戏地图中其效率将是很低的。而A*算法明显比Dijkstra算法更具有效率，两种数据都少于Dijkstra算法的数据。改进A*算法依旧能够比标准A*算法更加有效率。通过数据分析，改进A*算法比标准A*算法提高了5-15%不等。

4 总结

A*算法中作为启发式搜索算法的一种，深受程序开发人员的推崇，在许多游戏地图路径搜索中都有所应用。但A*算法本身并不完美，也存在这不足。首先，A*算法最耗时的部分就是在OPEN表中寻找F值最小的节点。本文采用最小二叉堆的方法来构造OPEN表，利用最小二叉堆的根节点最小值的特点，不但省去了对OPEN表的遍历所消耗的时间，也极大的优化了A*算法对OPEN表的增、删操作，路径搜索的效率提高了5%。其次，通过引入了以向量夹角余弦作为新的启发式信息，来收缩A*算法的搜索范围和减少搜索无用的节点。最 后得出的A*算法比标准A*算法的游戏路径搜索效率提高了近15%。

[1]张玥.基于产业链结构的中国网络游戏产业发展研究[J].中原工学院学报, 2012年10月第23卷(第5期):64-67.

[2]周先曙.最短路径问题及其解法研究[J].电脑知识与技术,2010年2月, 第6卷(第6期):1403-1405,1412.

[3]邱磊.基于A*算法的游戏地图寻路实现及性能比较[J].陕西科技大学学报, Dec.2011(No.6):89-93.

[4]翁惠玉, 俞勇.数据结构：题解与拓展[M].1.高等教育出版社, 2011-07,151-155.

[5]Patrick Lester.A* Pathfinding for Beginners [EB/OL].July 18, 2005[2012-2-20].http://www.policyalmanac.org/games/aStarTutorial.htm.

[6]陈和平，张前哨．A算法在游戏地图寻径中的应用与实现[J]．计算机应用与软件，2005(12)：118—120.

[7]刘敏.Dijkstra算法求解最短路径的设计与实现[J].电脑知识与技术, April 2012(No.12):2759-2761.

[8]邱磊, 张辉.2D游戏地图的寻路实现[J].湖南工业大学学报,2012年1月(第26卷第1期):66-69.