计算机游戏中地图路径发现算法的优化与实现

邱 磊

(武汉船舶职业技术学院计算机教研室,湖北武汉430050)

计算机游戏中地图路径发现算法的优化与实现

邱 磊

(武汉船舶职业技术学院计算机教研室,湖北武汉430050)

在概述地图路径发现问题的基础上,给出了一个平滑A*算法所得路径的方法.为了达到平滑路径的目的,先采用了最直接的路线,忽略了转弯,然后用一个预平滑过程来处理路径,在A*算法找到路径后再进行处理.讨论了如何改进A*算法的启发函数.给出一个引导型A*算法,主要的改变是将结点空间从二维扩展到三维,使搜索过程能曲线转弯,避免了碰撞障碍物,实现了“合法”转弯.

游戏地图；路径发现；A*算法；启发函数

路径发现算法是策略型计算机游戏中的关键技术,是游戏人工智能领域的基础和重要组成部分.路径发现系统使用启发式搜索算法对游戏地图进行搜索,现阶段国内外的相关研究集中在算法的优化和搜索空间的简化上.A*算法作为一种启发式搜索算法［1］被广泛地应用,很多文献探讨对A*算法的优化问题［2-4］.因此,对地图路径发现方法进行优化与改进,在提高计算机游戏的性能方面有较大应用价值,本文拟结合几种现实化的技术优化地图路径发现算法,并对其进行实现与分析.

1 关于路径发现问题

首先以一个虚构的亚斯兰大陆地图(图1)来介绍路径发现问题,假设要找到从月影村到万念崖的最短路径,每前进一步都有很多不同的路径到不同的地点,可以通过评估函数来评估各条路径的好坏,评估函数的作用就是预测评估各可能路径的好坏,并返回一个数值.每走一步都选择评估函数返回值最小的路径,直到到达目的地,这种搜索算法称之为最佳优先搜索.以当前所在地点到目的地的直线距离作为评估函数的返回值,则最佳优先搜索的搜索过程如图2所示.

图1 亚斯兰大陆地图

图2 最佳优先搜索的树状展开图

在搜索时,每一步先找到与当前所在地点连接的所有邻近地点,然后使用评估函数,选择评估函数返回数值最小的地点作为下一步的起点.比如当走到丁香谷后,应选择凄惶岭作为下一步的地点.这样一步一步,直到发现评估函数返回值为0,表明已经到了目的地.但该算法实际上有严重的缺陷：首先,它所找到的路径不是最短的,丁香谷的下一步应该选黑森林入口,而不是凄惶岭.因为这个算法只顾眼前利益,无法保证长远(全局)最优,因此习惯地称之为“贪婪算法”.其次,贪婪算法有可能很慢,它有可能在一开始就沿着错误的路径走下去,直到醒悟回来再往回折.比如,要从忘忧城走到水晶城堡,用贪婪算法的话第一步会走到恶魔城,但实际上恶魔城是一条死路.

上述问题的症结就在于没有考虑已经走过的路的距离,如果把估价函数改进一下：f(n)=g(n)+ h(n)［5-6］,其中g(n)为从起始点到地点n的实际最短距离；h(n)为从地点n到目的地的预测最短距离,称之为启发函数.使用f(n)这种估价函数的最佳优先搜索算法就叫做A*算法.可以从数学上证明：如果从地点n到目的地的实际最短距离总是大于或等于h(n)的话,则A*算法是全局最优的,也就是说A*算法总能找到最短的路径［7］,而且还可以证明A*算法是效率最高的.使用A*算法搜索过程的树状展开图如图3所示.

图3 A*算法搜索过程的树状展开图

2 路径发现算法的优化

路径发现要求搜索的路径尽量平滑和自然,本节探讨几种现实化的技术,以使游戏中各类物体能实现更真实、形象的运动.

2.1 简单平滑算法

标准A*算法求得路径后,利用函数Walkable (point A,pointB),按照一给定的粒度(通常采用格子宽度的1/5)沿着从点A到点B的连线采样.同时,基于围绕游戏物体中心的菱形图案的四个点,利用游戏物体的宽度,在每个点处检查游戏物体是否重叠了任何相邻的堵塞方格；如果遇到的是未堵塞的方格,该函数返回真,否则返回假.

算法执行时,在最后一个关键点能从当前位置被看到之前,所有的关键点都会被逐步忽略,由于加入了基于角色宽度的碰撞检测,因此结果很精确.

2.2 曲线转弯技术

我们要为游戏物体添加现实的曲线转弯,以使它们每次需要转弯时,改变方向显得不那么生硬.为此,首先要知道什么是游戏物体的转弯半径：物体沿着某圈圈运动,该圆圈的半径就是该物体的转弯半径.当在初始点朝着某个方向需要到达目标点时,可找到的最短路径有两种可能：一种是尽可能向左转,走个圆圈至方向正好对准了目标点,然后继续前进；一种是选择右转,然后进行相同处理.利用某些几何关系,两种最短路径的长度可证明很容易被计算出来,然后选择较短的一个.

2.3 引导型A*算法

引导型A*算法不用＜X,Y＞表示二维结点网格上结点的位置,而是采用三维的结点空间,用＜X,Y,方向＞表示结点的位置,新增的方向是指南针的八个方向之一.算法执行过程中,当在结点p去检查其子结点q时,不仅要检查q是否是一个堵塞的方格,还要检查从p到q的曲线路径是否是可行的；若可行并且沿着该路径行进不会撞到任何被堵塞的方格,则认为该子结点是有效的.因此,对于给定的游戏物体尺寸和转弯半径,按上述检查后求得的有效路径才是“合法”的.

为了实现引导型A*算法,必须解决在考虑起始方向、后续方向定位以及转弯半径,甚至结束方向的情况下,如何计算从p到q的最短路径.我们需要在地图的当前位置和方位至下一个关键点之间计算出最短的“合法”路径,并且在到达关键点时面向一个既定的方向：一种情况是沿着相同的方向(顺时针或逆时针)绕过两个圆弧；一种情况是沿着不同的转向绕过两个圆弧,求解过程中运用了三角几何知识［］.

2.4 启发函数的改进

改进的A*算法需要一个改进的启发值［9］,标准A*算法的启发函数只是从当前位置到目标点的直线距离,使用该启发函数在每个位置都需要对八个基本方向进行等价的处理,这会导致搜索时间相当长.然而,为了利用当前点指向目标点的角度以及转弯半径,把启发函数变成从当前位置到目标点的最短曲线距离加上指向目的地的角度,为了避免每次按上述计算,我们预先建立一个启发代价表.该表内容为：从当前位置到任何角度、10个方格距离范围以内的目标点的启发值；对于超出10个方格距离的目标点按10个方格来计算,并加上与实际距离的差量.由于该表依赖于游戏物体的转弯半径,如果转弯半径改变,我们需要重新计算这个表.

2.5 简单平滑算法的改进

在A*算法找到路径后,首先用一个预平滑过程来处理路径,然后再用本文的简单平滑算法,与引导型-48(搜索3个方格距离内的所有方格称为引导型-48搜索,共48*8=384个子结点)搜索的区别在于：只允许沿着之前A*算法找出来的路径上的结点移动,并且假定每个结点的前方第1个、2个或第3个方格的相邻方格都是原来路径的关键点,同时修改启发函数的代价使之朝着最初路径确定的方向搜索.

3 实现与分析

图4 路径发现优化技术示意图

图4 (a)使用标准A*算法路径发现后返回的结果,产生了不尽人意的“Z字形”效果；图4(b)采用后处理技术平滑后的路径；图4(c)为沿着转弯半径进行平滑转弯的效果；图4(d)为引导性A*算法实现的“合法”转弯,使得搜索过程能曲线转弯,避免了碰撞障碍物.转弯半径成为了搜索的一部分,这就保证在整条路径里只包含“合法”的转弯.

如图5所示,标准A*算法找到的最短的路径是从a到c,但由于c处周围障碍物间的“空隙”使得转弯半径的大小不足以使游戏物体在c处右转弯,于是此种情况下,标准A*算法将返回一个无效的路径.若采用本文的引导型A*算法,游戏物体在发现上述障碍物情况后,会寻找一条穿过位置b的替代路径.但同时我们会发现,即使在b处,一个90°的左转弯同样由于障碍物间的“空隙”太小而不可行.于是,引导型A*算法最终选择了先做一个右转圈,然后再继续前进.

图5 路经发现算法的优化实现

4 结束语

算法实现的结果说明,地图路径发现算法的优化有效地平滑了标准A*算法计算出的路径,避开了由于转弯半径太小游戏物体无法转弯的情况,保证了最优路径的求解.引导型A*算法的时间主要花费在检查堵塞单元的内部循环上,通过代码优化,可使性能提高一倍,另外,针对启发函数的改进及48结点平滑的修改均能加快发现潜在的路径,所有这些优化为玩家带来了审美上更加愉悦的体验.总之,地图路径发现算法作为游戏引擎中的一个核心组成部分,仍是人工智能领域的一个热点问题,通常需混合多种技术才能得到一个比较好的解决方案,本文对此做了有益的探索.

［1］李艳,陈彩,李铁松,等.游戏地图中的分层动态路径搜索算法［J］.计算机工程,2012(1)：288-289.

［2］林笃斌,李欣.基于DEM格网的改进型A*路径搜索算法［J］.计算机工程与设计,2011(10)：3414-3418.

［3］李楠,赵擎,徐肖豪.基于A*算法的机场滑行路径优化研究［J］.计算机仿真,2012(7)：88-92.

［4］王殿君.基于改进A*算法的室内移动机器人路径规划［J］.清华大学学报：自然科学版,2012(8)：1085-1089.

［5］Anand A.Path planning in agents with incomplete information in dynamic environments［D］.Melbourne：Royal Melbourne Institute of Technology,2011.

［6］邱磊.基于A*算法的游戏地图寻路实现及性能比较［J］.陕西科技大学学报：自然科学版,2011(6)：89-93.

［7］叶展.游戏的设计与开发：梦开始的地方［M］.北京：人民交通出版社,2003：265-267.

［8］Pinter M.Toward More Realistic Pathfinding［DB/OL］.(2001-03-14).http：//www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php.

［9］邱磊.2D游戏地图的寻路实现［J］.湖南工业大学学报,2012 (1)：66-69.

(编辑:姚佳良)

Optimization and implementation of pathfinding algorithms for game maps

QIU Lei
(Staff Room of Computer,Wuhan Institute of Shipbuilding Technology,Wuhan 430050,China)

Based on the summary of the pathfinding questions,a method of smoothing the path which A*algorithm computed was given.In order to achieve this effect,we firstly took the most direct route,regardless of the angle,and then used a new pre-smoothing path before the standard A*algorithm found and completed its path.We introduced how to modify heuristic of A*algorithm,and gave a directional A*algorithm.The main change to the algorithm was the addition of a third dimension to two-dimension node,which enabled searching process include curved turns,and avoid collisions.

game map；pathfinding；A*algorithm；heuristic

1672―6197(2013)01―0038―04

TP312；TP391

A

2012- 11- 11

邱磊,男,tsuly@163.com