基于Silverlight网页游戏的寻径优化算法

李子强，宋余庆，陈健美，冯 江

江苏大学 计算机科学与通信工程学院，江苏 镇江 212013

基于Silverlight网页游戏的寻径优化算法

李子强，宋余庆，陈健美，冯 江

江苏大学 计算机科学与通信工程学院，江苏 镇江 212013

游戏，在国外被称为“第九艺术”，是一种世界范围内的通用语言。随着微软开发的Silverlight技术快速崛起，使得中国Silverlight网页游戏迅速发展，越来越多的研究开始侧重于如何寻求游戏角色更优的路径搜索上来[1]。作为一种灵活的、高性价比的寻路算法，A*（A-Star，A*）搜索算法一直被游戏行业广泛采用[2]。然而在Silverlight游戏这个对寻路实时性和路径真实性要求较高的应用领域，A*仍有几点不足之处[3]。诸如：标准的A*算法搜索比较费时，尤其是当寻路规模过大时，其时间消耗令玩家无法忍受；其次，直接利用算法得到的路径往往曲曲折折，过于机械化。除此之外，游戏地图中的特殊地形、目标结点可达不可达的判断、地图中障碍物位置的动态改变以及当某一狭窄路径交通堵塞时如何改变寻路策略等都是需要考虑的问题[4]。本文通过分析现有算法应用于Silverlight网页游戏中存在的不足，结合Silverlight游戏使用网格地图的特点，在现有研究的基础上，将光线跨越算法和动态关键点寻路技术应用于传统的A*路径搜索中，提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有使用二叉堆存储开启列表并引入“父结点”指针的A*算法的基础上，利用光线跨越算法减小传统路径搜索算法的规模，同时引入“动态关键点”的概念并结合光线跨越算法优化算法返回的路径。实验证明，该算法能够极大地缩短寻径时间，提高寻路单位的响应速度，且寻得的路径更短、更平滑，有效提高了游戏角色的智能性，增强了Silverlight网页游戏的实时效果，用户体验更加良好顺畅。

1 启发式A＊算法

1.1 A＊算法简介

A*搜寻算法，俗称A星算法，是一种在图形平面上有多个结点的路径，求出最低通过成本的启发式动态规划搜索算法[5]。常用于游戏中的NPC（非玩家控制角色）和线上游戏中BOT（机器人）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS（Breadth First Search，BFS）算法一样，可以进行启发式的搜索[4]。

在此算法中，设g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。则A*算法的公式可表示为[6]：f(n)=g(n)+h(n)。该公式遵循以下特性：

（1）如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径。此时，该求解转化为单源最短路径问题，即用Dijkstra算法可求解。

（2）如果h(n)≤“n到目标的实际距离”，则一定可以求出最优解，而且h(n)越小，需要计算的结点越多，算法效率越低。

1.2 A＊算法流程

本文使用引入了“父结点”指针的A*算法，该指针能够有效地避免标准A*算法中存在的“回路问题”[7]。具体算法流程描述如下：

步骤1从起点S开始，把它作为待处理的结点存入一个“开启列表”，开启列表就是一个等待检查结点的列表。

步骤2寻找起点S周围可以到达的结点，将它们放入“开启列表”，并设置它们的“父结点”为S。

步骤3从“开启列表”中删除起点S，并将其加入“关闭列表”。“关闭列表”中存放的都是不需要再次检查的结点。

步骤4从“开启列表”中选择F值最低的结点C，把它从“开启列表”中删除，并放到“关闭列表”中。

步骤5检查它所有相邻并且可以到达的结点。如果这些结点还不在“开启列表”里的话，将它们加入“开启列表”，计算这些结点的G、H和F，并设置它们的“父结点”为C。

步骤6如果某个相邻结点D已经在“开启列表”里了，检查如果用新的路径（就是经过C的路径）到达它的话，G值是否会更低一些。如果新的G值更低，那就把它的“父结点”改为目前选中的结点C，然后重新计算它的F值和G值（H值不需要重新计算，因为对于每个方块，H值是不变的）。如果新的G值比较高，就说明经过C再到达D不是一个明智的选择，因为它需要更远的路，这时什么也不做。

步骤7重复步骤4～步骤6，直到目标格G已经在“开启列表”，这时候路径被找到，从目标格开始，沿着每一格的父结点移动直到回到起始格，这就是路径。如若开启列表已经空了，说明路径不存在。

1.3 优化开启列表的方法

A*算法中最缓慢的部分就是在开启列表中寻找F值最低的结点（或者方格），其速度取决于地图的大小。而在游戏地图中可能有成百甚至上千的结点需要在某一时刻使用A*搜索，这样反复搜索这么大的开启列表会严重拖慢整个A*搜索的过程。然而这些时间在极大程度上受列表存储方式的影响。在诸多开启列表的存储方式中，最简单的存储方法就是顺序存储每个结点，然后在每次需要提取最低耗费元素的时候遍历整个列表。这虽能提供快速的插入速度，但由于每次都需要遍历整个列表才能确定哪个F值是最低的，使得移除速度可能是最慢的。

对于这一问题的一般处理方法是通过保持开启列表有序来提高搜索效率。这虽会花费一点预处理的时间，因为每次插入新的元素都需要为之选择一个合适的位置。但是由于它的F值是最低的，所以只需移除第一个元素就可以，其大大加快了移除元素速度。其中可以保持开启列表有序的方法有很多，比如选择排序、冒泡排序和快速排序。以上最简单的方法是，当需要添加新元素时，从列表头起，用将要插入元素的F值与每个元素的F值比较，一旦找到相等或者更高的F值，就把新元素插入到列表中该元素的前面。另外，可以通过使用列表中所有元素的平均值来确定是从表头还是从表尾开始处理。比平均F值低的元素从表头开始处理，反之则从表尾开始处理，这样可以节省一半的处理时间。以上方法虽然简单，但是在时间上却不如快速排序的时间消耗小。在快速排序中，首先从比较新元素和列表中间元素的F值开始，如果新元素的F值低，就和1/4处元素进行比较；如果还是更低，就比较它和1/8处的元素，以此类推，不断地折半开启列表进行比较，直到找到合适的位置为止。

在有序列表中，每个元素都按照由低到高或由高到低的顺序保存在恰当的位置。这很有用，但是还不够。事实上，不用关心数字A是否比B在更低的位置上，只要保证F值最低的元素存放在列表顶端便于访问即可，至于列表的其他部分即使混乱也没关系。列表的其他部分只有在需要另一个F值最低的元素的时候，才有必要保持有序。这正是二叉堆所具备的功能。二叉堆是一种特殊的堆，二叉堆是完全二叉树或者近似完全的二叉树。二叉堆满足堆的特性，即父结点的键值总是大于或者等于任何子结点的键值。在二叉堆上可以进行插入结点，删除结点，取出值最小的结点等基本操作。二叉堆和快速排序很类似，通常被那些苛求A*搜索速度时使用。实际经验表明，二叉堆能提高平均寻路速度2～3倍，尤其对拥有大量结点的地图的（如100×100结点或更多）提高更明显[8]。鉴于二叉堆在提高A*算法搜索效率上的优势，本文将采用二叉堆来优化开启列表。

2 光线跨越算法

实现直线光栅化的方法之一是解直线的微分方程式，即

其有限积分近似解：

式中x1，y1和x2，y2是所求直线的端点坐标，yt是直线上某一步的初值。此公式表示所求直线上 y值的逐次递归关系。当此公式用于直线光栅化时，称为数字微分分析器（Digital Differential Analyzer，DDA）。简单的DDA选择Δx或Δy中的较大者为一个光栅单位。

在二维光栅显示器上，画线算法在每一行（或列）上选择最能代表直线的像素显示，如图1中的方框所示。而光线跨越算法必须选取光线穿过的每一个像素，新增选取的像素如图1中的圆圈所示。注意在一些列中选取了多个像素。对DDA算法稍加修改即可用于光线跨越算法[9]。

图1 光线跨越算法

在图1中，方框表示由标准的DDA算法提取的像素，圆圈表示光线跨越算法新增的像素。该图显示了光线跨越水平（或垂直）平面进入体元的二维示意图。注意，光线在三维均匀网络中前进时，它在两相邻竖直平面间跨越的距离为常数，在图2标记为Δx。同样，它在两相邻水平平面间跨越的距离也为常数。在图2标记为Δy。在三维中还存在第三个常数Δz。当光线在场景中进行时，它通过三个面之一进入体元。

图2 沿光线两相邻体元间的x和y距离增量

在二维情况下，如果dx＜dy，则光线从垂直于x轴的平面进入下一体元；该体元可沿x轴定位，dx=dx+Δx。类似地，如果dy＜dx，则光线从垂直于y轴的平面进入下一体元；该体元可沿 y轴定位，dy=dy+Δy。在图3中设体元由一个角点的索引(i,j,k)定位，则下一体元的索引为i=i+ix,j=j+jy,k=k+kz，其中ix、jy、kz取+1还是－1取决于光线的方向。

本文所用的二维光线跨越算法描述如下：

初始化ix,jy,Δx,Δy,dx,dy

图3 沿着光线总的x和y距离

3 基于Silverlight网页游戏的寻径优化算法

在利用二叉堆优化开启列表并引入“父结点”指针优化A*算法的基础上，本文将之与光线跨越算法相结合并引入“动态关键点”的概念，提出了一种基于Silverlight网页游戏的寻径优化算法。该寻径优化算法的具体步骤如下：

步骤1判断目标结点G是否可达。若不可达，则直接返回路径不存在，算法结束。

步骤2若目标结点为可达结点，则从起始点S到目标点G之间利用光线跨越算法计算光线经过的结点。若经过的所有结点都为可达结点，则路径为点S和点G之间的线段，算法结束。

步骤3记录S到G的第一个不可达结点的前一结点和最后一个不可达结点的后一结点，分别记为S′和G′。把当前结点S′作为起始点，并添加进开始列表Open中。将S′周围所有可达或可通过结点，添加进Open表，并添加S′作为父结点。从开启列表Open中删除结点S′，并将S′添加进关闭列表Close中。

步骤4从二叉堆优化的Open表中选择F最低结点（第一个），然后对选中的结点做如下处理：首先，将它从Open表删除，然后添加进关闭列表Close中。然后，检查所有相邻结点，跳过那些在Close表中的或不可达的结点，添加进Open表。对还不在Open表中的（即新添加进去的），把选中结点作为新结点的父结点。如果某结点已经在Open表里，检查现在这条路径是否更好。即使用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不做；如果新的G值更低，那就把（选中结点）相邻结点的父结点改为目前选中的结点，重新计算F和G值。F值由以下启发函数得到，F=G+H。G按当前点相对于父结点的位置得到：若在父结点直角方向，则在父结点G值上加10，对角线方向加14；H采用曼哈顿启发方式，即当前结点到目标结点之间水平和垂直结点数量之和（忽略对角线）。

步骤5重复步骤4，直到结束点G′被添加进Open表中，转步骤6；或Open表为空，返回路径不存在，算法结束。

步骤6从目标点开始，沿着每一结点的父结点移动回起始结点，记录这条路径并删除路径中方向相同的冗余结点。比如：有路径结点路径[0，1]、[0，2]、[0，3]和[1，2]，由于结点[0，1]、[0，2]与[0，1]、[0，2]、[0，3]方向相同，故删除结点[0，2]。路径结点可表现为[0，1]，[0，3]，[1，2]。记录这些动态关键点。

步骤7把S和G添加进步骤6所获得的关键点列表的开始和结尾，从S点开始，利用光线跨越算法，进一步过滤动态关键点列表。方法是以S点为当前结点，若某动态关键点与S间全为光线可达结点，则删除此关键点与S点间的其他关键点；若不可达，则把该关键点作为当前结点。依次向下过滤，在达到G时结束过滤，则返回路径为以上剩余关键点的折连线，算法结束。

算法的流程图如图4所示。

图4 寻径优化算法的流程图

4 实验结果

为了准确分析改进算法的寻路性能，本文将其与使用二叉堆存储开启列表并引入“父结点”指针的标准A*算法进行比较。实验的硬件环境：CPU Intel®CoreTM2 Duo E7500@2.93 GHz，内存为2 GB。软件环境：操作系统为Microsoft Windows XP Professional。开发平台为.NET，语言为C#。测试地图由地图编辑器生成，为了更直观地体现本文改进方案的360°全方位寻径效果，地图编辑器保留了结点的网格边框。

4.1 寻径效果测试

在地图编辑器编辑生成的网格地图上进行寻路实验，寻路结果如图5所示。图5中，左上角S点为寻径起点，目标点为右下角G点。在图5中占据大部分地图结点区域的白色底纹区域为角色可通行结点区域，分布于图5左下和右上的多边形结点区域以及处于图5中心区域的“T”型结点区域为山丘、沟壑或人为设定的障碍物等逻辑占据的不可通行结点区域，相对处于下方的路径SG为标准A*算法寻得的路径，点M、N为本文改进算法获得的动态关键点，其和起点S及终点G间的光线路径SMNG为本文改进的A*算法寻得的路径。

图5 算法寻径效果比较

从图5可以看出，在寻径起点和终点相同的前提下，由标准A*算法返回的路径SG较为曲折，从根本上来讲，这是由于现有A*算法从逻辑上限定了寻路方向为4方向（不包括对角）或者8方向（包括对角方向）的局限造成的。本文改进的A*寻路算法返回的路径SMNG较为平滑，其返回的路径没有标准A*寻径的4方向或8方向局限，为360°全方向路径，而且路径SMNG较路径SG更短，因此本文改进方案的寻径效果要明显优于现有的使用二叉堆存储开启列表并引入“父结点”指针的标准A*算法。

由于光线跨越算法和动态关键点的使用，本文提出的改进的A*算法寻得的路径没有传统A*算法寻径4个方向或8个方向的局限性，为360°全方位路径。算法寻得的路径短，且避免了A*算法存在的回路问题，寻路单位也不会到达不可达区域，所寻路径更优更贴近现实。在Silverlight网页游戏中表现为游戏角色智能的提高，游戏玩家游戏体验的提升。

4.2 寻径时间测试

表1记录了图5中寻径的时间，为了减小误差，分别记录了使用二叉堆存储开启列表并引入“父结点”指针的标准A*算法和本文改进算法在图5上10次寻径的时间消耗。

表1 算法寻径消耗时间比较 ms

从表1可计算得知，在同等的硬件条件和软件环境下，标准A*算法寻径图5路径SG的平均时间为1.4 ms，本文改进算法寻径图5路径SMNG的平均时间为0.4 ms。

图5的寻径规模为64×41结点，在本文测试环境下为寻径屏幕左上角到右下角（飞利浦190CW9显示器19 in，分辨率为1 440×900），由于单次的寻径起点和终点一般不会超出整个客户端屏幕鼠标可点击区域，因此该测试用例可基本代表Silverlight网页游戏寻路的需求。从表1的寻路时间分析可以看出，在同等的硬件条件和软件环境下，改进算法的寻径时间消耗远远小于标准A*算法的时间消耗。在Silverlight游戏通常每秒6帧（每帧166.7 ms）的情况下，寻径时间消耗远远小于帧切换的时间消耗，因此不会出现帧补偿导致的画面跳跃现象（游戏中表现为画面的卡滞），能够很好满足游戏实时性需求。

从上面的实验结果中可以看出，改进后的算法返回的路径没有现有A*算法8方向的局限性，其返回的路径为360°全方向路径，较之标准的A*算法返回的8方向路径短且平滑，可使得Silverlight游戏角色寻径更加自然，能有效提高游戏角色的智能性。同时，改进后的算法在寻路时间消耗上要远远小于现有的使用二叉堆存储开启列表并引入“父结点”指针的标准的A*算法，游戏角色寻路时间要远远小于游戏画面的帧切换时间。实验证明该方法切实可行。

5 结束语

本文在分析Silverlight网页游戏中寻路算法现有研究的基础上，结合Silverlight网页游戏地图的特点，将光线跨越算法引入传统路启发式径搜索算法并引入“动态关键点”对现有的寻路算法进行了改进，提出了一种基于Silverlight网页游戏的寻径优化算法。重点解决了现有算法应用于Silverlight网页游戏寻路时时间消耗大和寻得的路径不够平滑优化这两个问题。实验结果表明，该路径搜索算法减少了寻路的时间消耗，寻得的路径更短更平滑。该算法能够满足Silverlight网页游戏的寻路实时性和路径真实性需求，提高游戏角色的智能性和游戏的可玩性。且随着游戏寻路规模的增大，改进后的算法对效率的提升更显著。

[1]Xu Z G，Van Doren M.A museum visitors guide with the A～* pathfinding algorithm[C]//Proceedingsof2011 IEEE International Conference on Computer Science and Automation Engineering.Shanghai：[s.n.]，2011.

[2]BaiWenfeng，Han Lina.An improvedA～* algorithm in path planning[C]//Proceedings of 2010 International Conference on Computer，Mechatronics，Control and Electronic Engineering.Changchun：[s.n.]，2010.

[3]高晔，邢毅.Vega平台下三维并行A～*算法的设计与实现[J].计算机工程与应用，2012，48（7）：231-233.

[4]周小镜.基于改进A*算法的游戏地图寻径的研究[D].重庆：西南大学，2011.

[5]Russell S，Norvig P.Artificial intelligence：a modern approach[M]. [S.l.]：Prentice Hall，2002.

[6]龚道雄，刘翔.迷宫搜索算法的比较研究[J].计算机应用研究，2011（28）：4433-4436.

[7]许珂乐.网络游戏中的寻路算法初探[EB/OL].（2011-09-28）. [2012-04-26].http：//www.cnki.net/kcms/detail/15.1211.f.20110928. 2034.038.html.

[8]詹海波.人工智能寻路算法在电子游戏中的研究和应用[D].武汉：华中科技大学，2006.

[9]Rogers D F.计算机图形学的算法基础[M].石教英，彭群生，译.北京：机械工业出版社，2002.

LI Ziqiang,SONG Yuqing,CHEN Jianmei,FENG Jiang

School of Computer Science and Telecommunication Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China

Aimed to the problems of A*algorithm search in Silverlight web games,such as the path optimization problem and the time-consuming problem,this paper associates the light across algorithm with the A*algorithm search that uses the light across algorithm and the parent node pointer,and proposes an advanced algorithm search in Silverlight web games.The algorithm is based on the existing research results and uses the light across algorithm to reduce the A*algorithm search scale.Meanwhile,it introduces the dynamic critical point technique that combined with the light across algorithm to optimize the path.The experiment in the grid map that used in Silverlight web games proves that this algorithm can effectively find out an optimal practical path,according to the prevailing conditions set by the system.It can raise the search efficiency and reduce the complexity of the planning issue and improve the playability.

A*algorithm;light across algorithm;dynamic critical points;heuristic searching;path search;Silverlight web games

为了解决A*路径搜索算法在Silverlight网页游戏中的搜索费时和路径曲折等问题，在结合光线跨越算法和引入父结点指针的二叉堆存储开启列表的A*算法的基础上，提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有研究的基础上使用光线跨越算法减小A*算法搜索规模，同时将动态关键点技术与光线跨越算法结合来优化算法返回的路径。将该算法在游戏所使用的网格地图中进行实验，实验结果表明，该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径，同时缩短寻路的时间消耗和所寻的路径长度，提高游戏的可玩性。

A*算法；光线跨越算法；动态关键点；启发式搜索；地图寻径；Silverlight网页游戏

A

TP301.6

10.3778/j.issn.1002-8331.1206-0370

LI Ziqiang,SONG Yuqing,CHEN Jianmei,et al.Advanced algorithm search in Silverlight web game.Computer Engineering and Applications,2013,49（5）：59-63.

教育部博士点基金（No.20113227110010）；江苏省高校自然基金（No.10KJB520004）；江苏省软件与集成电路专项基金（No.2009[100]）；江苏省普通高校研究生科研创新计划（No.CXZZ11_0575）。

李子强（1987—），男，硕士研究生，主要研究方向：网络游戏设计与开发、医学图像处理；宋余庆（1959—），男，教授，博士生导师，主要研究方向：网络游戏设计与开发、医学图像处理；陈健美（1962—），女，教授，主要研究方向：数据挖掘、医学图像；冯江（1987—），男，硕士研究生，主要研究方向：网络游戏设计与开发、医学图像。E-mail：nano_li@126.com

2012-06-25

2012-10-12

1002-8331（2013）05-0059-05

CNKI出版日期：2012-10-31 http://www.cnki.net/kcms/detail/11.2127.TP.20121031.0947.014.html