自动寻路A＊算法的应用及优化设计

第１４卷第２期　２０１４年６月　上海应用技术学院学报（自然科学版）　ＪＯｔ　ＪＲＮＡＬ　ＯＦ　ＳＨＡＮＧＨＡＩ　ＩＮＳＴＩＴＵＴＥ　ＯＦ　ＴＥＣＨＮＯＬＯＧＹ（ＮＡＴＵＲＡＬ　ＳＣＩＥＮＣＥ）　Ｖ０Ｉ．１４　ＮＯ．２　Ｊｕｎ．２Ｏ１４　文章编号：１６７１－７３３３（２Ｏ１４）０２—０１５９—０４　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７１—７３３３．２０１４．０２．Ｏ１５　自动寻路Ａ＊算法的应用及优化设计　蒯　锐，　洪金敏　（上海应用技术学院计算机科学与信息工程学院，上海２０１４１８）　摘　要：自动寻路Ａ　算法是富互联网应用（ＲＩＡ）游戏制作过程中的核心算法，解决了地图中两点　之间寻路的问题，应用于很多游戏中．对Ａ　寻路算法的实现方法进行了研究和探讨，并对该算法　进行了优化设计，体现了该算法的功能，最后对其应用前景进行了展望．　关键词：寻路算法优化；游戏；应用　中图分类号：ＴＰ　３９３　文献标志码：Ａ　Ａｐｐｌ　ｉｃａｔｉｏｎ　ａｎｄ　Ｏｐｔｉｍｉｚｅｄ　Ｄｅｓｉｇｎ　ｏｆ　ｔｈｅ　Ａｕｔｏｍａｔｉｃ　Ｐａｔｈｆｉｎｄｉｎｇ　Ａ　Ａｌｇｏｒｉｔｈｍ　ＫＵＡＩ　Ｒｕｉ，Ｈ０ＮＧ　Ｊ　—ｍ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，　Ｓｈａｎｇｈａｉ　２０１４１８，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：ｐａｔｈｆｉｎｄｉｎｇ　Ａ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｔｈｅ　ｃｏｒｅ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ＲＩＡ　ｇａｍｅ　ｐｒｏｄｕｃｔｉｏｎ，ｗｈｉｃｈ　ｈａｓ　ｓｏｌｖｅｄ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｅ　ｐａｔｈｆｉｎｄｉｎｇ　ｂｅｔｗｅｅｎ　ｔｗｏ　ｐｏｉｎｔｓ　ｉｎ　ｔｈｅ　ｍａｐ，ａｎｄ　ｔｈｕｓ，ｈａｓ　ｂｅｅｎ　ｗｉｄｅｌｙ　ａｐｐｌｉｅｄ　ｉｎ　ａ　ｌｏｔ　ｏｆ　ｇａｍｅｓ．Ｔｈｅ　ｏｐｔｉｍｉｚｅｄ　ｐａｔｈｆｉｎｄｉｎｇ　Ａ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｗｅｒｅ　ｓｔｕｄｉｅｄ．Ｔｈｅ　ｏｐｔｉｍａｌ　ｄｅｓｉｇｎ　ｏｆ　ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｏｆ　ｐａｔｈｆｉｎｄｉｎｇ　Ａ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｄｉｓｃｕｓｓｅｄ，ｗｈｉｃｈ　ｅｍｂｏｄｉｅｄ　ｔｈｅ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｐａｔｈｆｉｎｄｉｎｇ　Ａ　ａｌｇｏｒｉｔｈｍ　ｖｉｖｉｄｌｙ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｐｒｏｓｐｅｃｔ　ｏｎ　ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｔｈｉｓ　ｔｅｃｈｎｏｌｏｇｙ　ｗａｓ　ｍａｄｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｐａｔｈｆｉｎｄｉｎｇ　ａｌｇｏｒｉｔｈｍ；ｇａｍｅ；ａｐｐｌｉｃａｔｉｏｎ　随着互联网的飞速发展，如今人们已经可以通　过网页玩游戏而无需像过去那样下载客户端并且花　费时间安装．越来越多的网页游戏开始选择了以　Ｆｌａｓｈ平台技术为前端核心．而Ａ　寻路算法则是游　戏制作过程中的核心算法，特别是在２．５Ｄ的虚拟　社区中，玩家对于人物的控制往往是由Ａ　寻路算　法来完成的．目前国外这方面的应用比较多，特别是　富互联网应用（ＲＩＡ）开发的一个新热点．　１基本原理及实现　１．１　Ａ　寻路算法　Ａ　寻路算法解决的一个最基本的问题是寻路．　这里的寻路指的是，在基于区块的地图中寻找起始　节点和终点节点间，绕开不可通过的障碍所产生的　最佳路径．“最佳”一词的确切含义需要根据实际情　虚拟社区，国内由于带宽、硬件条件所限，Ｆｌａｓｈ平　台技术结合Ａ　寻路算法的应用主要还是集中在小　游戏方面，随着硬件条件的提升，这项技术也将成为　况来定义，可以是最短时间或最短路径，也可以是最　小代价　］．比较形象的例子是穿越森林，从一头到另　收稿日期：２０１３－１０—１０　作者简介：蒯锐（１９６１－），女，副教授，主要研究方向为计算机应用．Ｅ—ｍａｉｌ：ｋｒ＠ｓｉｔ．ｅｄｕ．ｃｎ　１６Ｏ　上海应用技术学院学报（自然科学版）　第１４卷　一头，如果从森林旁边的公路绕，则代价小，路径长；　如果走森林则代价高，路径短．本设计采用考虑代价　问题的方式．　１．２算法流程描述　主循环：　（１）寻找开启列表中代价（ｆ值）最小的节点，　取出这个节点设置为当前节点．　（２）如果当前节点是终点则完成寻路，转到步　骤⑤．　（３）检查当前节点的各个相邻节点，一共８个．　①如果检查的相邻节点是不可通过的则跳过继　续处理下一个邻节点，否则继续．　②拐角判断，检查与该邻节点同一列（或行），与　当前节点同一行（或列）的节点是否为不可通过，如　果为不可通过，则跳过继续处理下一个邻节点，否则　继续．　③计算该邻节点的代价厂值（厂一ｇ＋　．ｇ：从起　始节点到当前某个节点的代价值．ｈ：从当前某个节　点到目标节点的代价值）．　④最佳路径判断：经在开启列表或关闭列表中，　判断它现在计算出的厂值是否小于原先计算出的厂　值，如果是，则将其ｇ值、ｈ值、＿厂值更新为当前计算　出的相应值，将其父节点设置为当前节点，跳过步骤　⑤．如果不是，则跳过这个邻节点处理下一个邻节　点．如果该邻节点不在开启列表或关闭列表中，继续　下一步．　⑤将计算出的ｇ、ｈ、ｆ值赋给该节点，并且将其　添加进开启列表中．　（４）将当前节点放入关闭列表中．　１．３启发函数　启发函数是Ａ　寻路算法中的一个重要的子函　数，该函数的功能是判断当前节点与目标节点之间　的预测路径值，并且不考虑障碍物．有３种主流的启　发函数，他们的作用和功能都相同，但是在Ａ　寻路　算法中所产生的效果有着很大的不同．　（１）曼哈顿启发函数．如图１（ａ），曼哈顿启发函　数是最简单的启发函数，它只是计算当前测试节点　与终点之间的列数差和行数差的和，即不考虑走对　角线．例如：ａ（１，１）ｂ（２，３），直线的代价为１，则最后　得到的结果是３．　（２）三角启发函数．如图１（ｂ），三角启发函数　是计算当前测试节点与终点之间的直线距离，即使　用两点之间距离公式．　（３）对角启发函数．如图１（ｃ），对角启发函数是　比较精确的一种启发函数，它会先根据当前测试节　点和终点的行数差和列数差的最小值，选择走一个　矩形的对角线，然后再走一条直线．　四日圈　（ａ）　（ｂ）　（ｃ）　图１　３种不同启发函数的效果　Ｆｉｇ．１　Ｔｈｅ　ｅｆｆｅｃｔｓ　ｏｆ　ｔｈｒｅｅ　ｄｉｆｆｅｒｅｎｔ　ｈｅｕｒｉｓｔｉｃ　ｆｕｎｃｔｉｏｎ　１．４拐角问题　在算法描述中有提到这样一个判断：拐角判断．　这里确切的含义是指物体绕过一个障碍物的边缘时　是否能抄近路，即是否允许物体切过障碍物．本设计　选择不抄近路的策略，如图２所示．　图２拐角问题　Ｆｉｇ．２　Ｔｈｅ　ｃｏｒｎｅｒ　ｐｒｏｂｌｅｍ　此时Ａ　寻路算法进行的步骤是，检查当前节　点的周围邻节点的情况，根据不同的情况做出不同　的选择和处理．其中黑色点代表当前节点，灰色区域　代表正在检查的节点．如果不加处理，则灰色的节点　会被添加进开启列表中，并且他的父节点会指向黑　色节点，路径也就变成了超近路的情况．　处理方法：检查与该邻节点同一列（或行），与当　前节点同一行（或列）的节点是否为不可通过，如图　３所示．这样在遇到拐角的情况时，当前节点不会把　图中灰色节点的父节点指向自己，从而避免了拐角　走斜线的问题．　图３拐角问题的解决方法　Ｆｉｇ．３　Ｔｈｅ　ｃｏｒｎｅｒ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｔｈｅ　ｐｒｏｂｌｅｍ　１．５代价问题　由Ａ　寻路算法所得出的最佳路径不仅仅指最　短路径，更加确切的含义是指代价最小的路径．每个　区块可以为其设置相应的代价系数，在计算区块代　价时，乘上这些系数，就会产生人物绕过森林选择陆　地行走的效果．有两种策略：①如果人物进入了森林　第２期　蒯　锐，等：自动寻路Ａ　算法的应用及优化设计　（人物已经在森林中了，此时开始寻路），则他会在森　林中寻找最佳路径而不去考虑外面的公路，但如果　人物是从森林外开始寻路，则他会绕过森林走公路．　这种策略表现起来比较自然，但需要添加一些逻辑　判断；②如果人物进入了森林，当外界有公路时，他　会优先考虑走出森林沿着公路走．这种策略实现起　来比较简单，但是表现不是很自然．本设计选用第二　种策略．　２　应用设计　本设计通过面向对象的思想实现Ａ　类库，寻　路程序划分为３个模块：地图显示模块、数据加载存　储模块、人物控制模块，分别对应３个主要的类：　ＧａｒｆｌｅＶｉｅｗ，ＧａｍｅＤａｔａ，ＧａｍｅＣｏｎｔｒｏｌｌｅｒ．文档类　（ｆｌａｓｈ中对于当前编译类的一种说法）的构造函数　在运行时，实例化３个类的对象，并且通过每个类所　提供的方法，实现外部数据读取以及地图和人物的　加载、人物的鼠标、寻路控制．　Ａ　寻路算法应用于人物控制，主要负责人物在　地图中的显示，并且为地图场景添加鼠标侦听以及　人物控制逻辑，实现鼠标点击以后人物的方向选择、　路径选择以及移动．人物控制设计的核心，体现了　Ａ　寻路算法的主要功能ｌ２］．人物控制模块，对应类　是ＧａｍｅＣｏｎｔｒｏｌｌｅｒ．　２．１　人物八方向移动　人物的移动一共有８个方向即：上、下、左、右、　左上、右上、左下、右下，每个方向上分为运动和静止　２个状态．因此，人物移动方向的控制就是对这１６　个动画状态的控制，本设计采用了比较粗略的代码　控制贴图的方法来实现人物移动、静止、朝向的简单　效果，较好的方法是采用与美工好的动画素材相结　合．人物控制是本设计中最综合的表现，它牵扯到了　以下环节：①人物方向的控制；②人物寻路流程的控　制；③坐标系转换；④地图的深度排序．　２．２控制流程　当鼠标点击地图时，除＿ｒ要判断人物的移动，还　要将起点、终点的坐标值放入到Ａ　寻路算法的数　据结构中，然后进行Ａ　寻路算法运算．首先判断是　否有路径产生，如果没有路径产生（封闭的情况），那　么什么也不做，如果有路径产生，则将结果取出用于　人物行走路径的控制，并且要时刻控制人物运动的　方向，因为此时的路径完全有可能是“Ｓ”形的．　图４所示为算法流程图．人物控制模块中的函　数ｓｔａｒｔＳｅａｒｃｈ根据传人的地图数据：终点和起点的　Ｘ和ｙ值计算出合适的路径．寻路时间在１～２　ｍｓ．　鼠标点击地图　获取鼠标点击的位置　多超祟　图｛至＝＼莲雪／＝＝＞　一　●Ｎ　将鼠标点击位置转换为　等角坐标系中的坐标　通过在地图加载时，已经生成的　Ｇｒｉｄ类实例，设置寻路的起点即　人物现在的位置设置寻路的终点　即鼠标点击位置　使用Ａｓｔａｒ类中的方法，将Ｇｒｉｄ　类的实例传入后进行寻路　Ｙ　开启计时器，执行人物　运动环节ｉ＝０　寻路结果数　＼　度／　ｌ　寻路结果　●Ｙ　以ｉ为索引下标，取出寻路结果　数组的一个元素，作为当前移动　的目标节点将人物当前的位置　作为起始节点　根据起点和目标点　判断人物方向　人物移动一段距离，并且　对地图进行深度排序　ｆ＋＋　图４人物行走控制流程图　Ｆｉｇ．４　Ｆｌｏｗ　ｃｈａｒｔ　ｏｆ　ｃｈａｒａｃｔｅｒｓ　ｗａｌｋｉｎｇ　ｃｏｎｔｒｏｌ　３优化及应用前景　３．１　Ａ　寻路算法的优化　Ａ　寻路算法的优化及效率主要体现在开启列　表的处理上，Ａ　在计算每一个当前节点时，都要对　开启列表进行排序，并且将周围相关节点放入开启　列表中．这样进行的结果就是，开启列表的长度随着　寻路的过程不断的在增加，排序所消耗的时间也呈递　增趋势．一张１００×１００的节点地图，在最坏情况下要　进行长度为１０　０００的数组排序，这样势必会造成寻　路在时间上所带给使用者的延迟感，并且随着地图的　增大，节点的精细，时间消耗也会不断增加．　ｌ６２　上海应用技术学院学报（自然科学版）　第１４卷　从不同的角度对这一问题有几种优化的方法：　（１）排序算法．在数据结构中数组的排序算法　有很多种，如冒泡、直接选择、直接插入．而Ａｃｔｉｏｎ—　Ｓｃｒｉｐｔ３．０是面向对象的语言，数组类型Ａｒｒａｙ类有　自己的排序方法：ｓｏｒｔ（Ａｒｒａｙ．ＮＵＭＥＲＩＣ），其中的　参数在排序时必须添加［３］．实践证明，这个排序方法　的效率是最快的，即数组排序使用类库中提供的排　序算法，并且添加参数．　（２）启发函数的选择．如前所述，启发函数基本　有３种类型，这３种类型在寻路过程中所制造出的　开启列表的长度也不一样．对角启发函数，相比较于　前二者来说，虽然在计算每个节点的代价时，会耗费　比较多的资源，但是他所产生的开启列表的长度会　小很多，当地图的节点增加时，这种启发函数的优势　就会体现出来，在时间上的消耗也会减少许多．　（３）多层面的Ａ　算法．可以将地图划分成几个　层面　］．一张地图可以划分成１０×１０的网格也可以　划分成１００×１００的网格，１０×１０的网格在寻路时　速度快，但是精细度不高，１００×１００的网格精细度　很高，但是寻路的开销大．寻路时可以先在１Ｏ×１０　的网格中寻出一条路径，然后将这个路径中的点通　过方法映射到１００×１００的网格中，在１００×１００的　网格中依次以在１０×１０网格中寻出的节点为起点　和终点，循环执行寻路算法，这样开启列表的长度就　会被减小，最坏的情况是２Ｏ×２Ｏ的长度，从而节约　了时间．　３．２性能分析及应用前景　为了比较性能，在２６×２Ｏ一５２０个节点的游戏　地图上，首先利用栅格法按８方向对地图进行划分，　采用相同的障碍物环境以及相同的初始节点和目标　节点，对各种启发函数的耗时进行分析，在路径求解　过程中分别以７．８１３　ｍｓ和３．９０６　ｍｓ为每步执行计　算的时间间隔，则各启发函数的路径计算耗时如表　１所示（误差范围小于１０　ｍｓ）：　表１各种启发函数的路径计算耗时　Ｔａｂ．１　Ａｌｌ　ｋｉｎｄｓ　ｏｆ　ｈｅｕｒｉｓｔｉｃ　ｆｕｎｃｔｉｏｎ　ｐａｔｈ　ｃｏｍｐｕｔａｔｉｏｎ　ｔｉｍｅ　ｃｏｎｓｕｍｐｔｉｏｎ　ｍＳ　虽然寻路的结果都可以保证找到最短路径，但　各启发函数性能明显不同，启发函数对Ａ　算法的　影响很大，以曼哈顿、三角和对角为启发函数，Ａ　算　法寻路时计算耗时并不相同，可见所选的启发函数　对Ａ　算法很重要，一个好的启发函数有利于尽快　找到最优解．　３种启发函数的比较：曼哈顿启发函数是３个　函数中计算方式最简单的一个，但是他忽略了走对　角线的情况，因此，由曼哈顿启发函数所产生的开启　列表的长度会非常大，因为它把很多无关的节点也　放人了开启列表中．三角启发函数相对于曼哈顿启　发函数，有了一定的改进，但是它忽略了一个重要的　问题，即合理路径．由三角启发函数计算出的值并不　是路径的真实预测值．因此，使用三角启发函数一样　会产生比较多的无关节点放入开启列表中．对角启　发函数是３个启发函数中最精确的，虽然它在计算　单个节点的代价时，是３个函数中最复杂的，开销最　大的，但是由它所产生的开启列表的长度是最少　的［　．　随着硬件条件的不断完善和网络带宽的提升，　使用Ｆｌａｓｈ平台技术创建虚拟社区会成为一个新的　ＲＩＡ应用焦点．Ａ　寻路算法正是虚拟社区中玩家　控制人物移动的核心，Ａ　寻路算法的效率也直接影　响了玩家的体验效果．如今Ａｄｏｂｅ已经推出了　Ｆｌａｓｈ３Ｄ技术以及增强了移动开发平台，相信在不　久的将来就会看到基于Ｆｌａｓｈ３Ｄ的虚拟社区，并且　可以实现手机玩家与ＰＣ玩家之间的游戏交互．　４　结　语　Ａ　寻路算法是游戏制作过程中非常重要的算　法，在制作游戏时往往要用到Ａ　寻路算法来实现　一些重要功能．本文主要研究了实现Ａ　寻路算法　及其优化方法，通过实例生动地体现了Ａ　寻路算　法的功能：当用户点击地图上的任何区域时，人物会　进行运动，并且会有正确的路径以及朝向，寻路时间　在１～２　ｍｓ，完成了优化设计．　参考文献：　［１］李子强，宋余庆，陈健美，等．基于Ｓｉｌｖｅｒｌｉｇｈｔ网页游　戏的寻径优化算法［Ｊ］．计算机工程与应用，２０１３，４９　（５）：５９－６３．　［２］Ｍａｋａｒ　Ｊ．ＡｃｔｉｏｎＳｃｒｉｐｔ大型网页游戏开发［Ｍ］．北京：　人民邮电出版社，２０１１：１２５—１３５．　［３］Ｇｒｉｆｆｉｔｈ　Ｃ．实战Ｆｌａｓｈ游戏开发［Ｍ］．北京：人民邮电　出版社，２Ｏ１２：５．　［４］周小镜．基于改进Ａ　算法的游戏地图寻径的研究　［Ｄ］．重庆：西南大学，２０１１．　［５］Ｋｅｉｔｈ　Ｐ．Ｆｌａｓｈ　ＡｃｔｉｏｎＳｃｒｉｐｔ　３．０动画高级教程ＥＭ］．北　京：人民邮电出版社，２０１０：１３４—１７０．　（编辑俞红卫）