A星寻路算法在QQ华夏中的应用

发表于2015-04-29
评论2 995浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

一、背景:

QQ华夏地图的特点:

因为QQ华夏地图是基于华夏的时间收费版本,为了让玩家能在游戏里更多的消耗时间,以前的地图都设计得很迂回,大量使用了高地等复杂地形。

http://km.oa.com/files/post_photo/393/157393/e0ee9e3ed288f6cab61fdc1b80658d1f.jpg

 

华夏远程寻路先前的版本使用的是导航点寻路,在地图上配置一些导航点,组成导航网络,这个方式有以下一些问题:

1.       对每一个地图都需要配置导航网络,维护困难

2.       配置复杂,导航点的配置对寻路行为的影响难以预测

3.       寻路表现行为怪异(需要先奔上最近的导航点,然后依据导航网络寻路)

 

二、游戏对寻路的要求:

1.       不要求最优路径,大体上符合最优路径即可

2.       客户端能流畅工作

 

三、寻路算法的选择:

1.    在一个地图里,从一个点到另一个点,最简单的算法,无疑是深度优先搜索,或者广度优先搜索,这类搜索的弊端是,没有利用目标点信息,属于蛮力搜索,效率不高;

2.       在广度优先搜索的基础之上,利用到目标点的位置信息,加入启发函数,就形成了A*算法;

A*寻路算法的时间复杂度大概是O(N*log(N))QQ华夏里比较大的地图尺寸有 600*400,对于客户端来说完全是能够承受的。

 

四、A*算法介绍

A*算法,作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分,就在于它的一个估值函数的设计上

 

启发函数的定义:

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

其中f(n)是每个可能试探点的估值,它有两部分组成:

一部分,为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。

另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值。

 

五、A*算法在华夏中的实现方式:

地图上的每个tile做为一个寻路结点,每个结点有路径评估值F,以及一个指向父结点的指针。使用hash_map,建立2个结点列表 (Open list – 待检查列表, Closed list – 已检查列表),key  坐标x,y组合而成,value为x,y对应的结点对象。当终点加入到Closed list时,就说明寻路成功,从终点依据结点的父节点指针可以回溯到起点,得到整个路径。算法流程如下图所示:

 

http://avocado.oa.com/fconv/files/201304/ce41fb055cd1227cf31e64cb5e43cdcd.files/image002.jpg

 

在以上流程中,最费时的就是寻找F值最小结点,是整个算法中的核心,为了快速的搜索到F值最小的结点,游戏里维护一个map, F值为Key,按从小到大排序,key对应的Value是一个保存了结点索引的list,通过这种结构,可以快速的定位到当前F值最小的结点。如下图所示:

http://avocado.oa.com/fconv/files/201304/ce41fb055cd1227cf31e64cb5e43cdcd.files/image003.png

 

六、寻路实例分析:

地图:QQ华夏琅琊盆地(大小:300 * 460)

1.       从左上到中间高地,使用工作机,平均耗时 430ms,大致路径如下图,

http://avocado.oa.com/fconv/files/201304/ce41fb055cd1227cf31e64cb5e43cdcd.files/image004.jpg

 

2.       从右下到左上,使用工作机,平均耗时 480ms,大致路径如下图,

http://avocado.oa.com/fconv/files/201304/ce41fb055cd1227cf31e64cb5e43cdcd.files/image005.jpg

 

上面2个图已经是超远距离寻路了,对一个玩家来说,使用并不是非常频繁,几百毫秒的时间也是可以接受的;中远距离寻路,一般时间都在几十毫秒以内,完全满足游戏的需求。

 

问答:

Q : 寻路过程中有动态阻挡该如何处理?

A : 远程寻路后,会把路程分段。在角色移动过程中,每一段会使用近距离寻路算法重新运算,找到合适的路径。

本文作者:pheonixwang(王文田)

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台