基于区域搜索的A＊算法在游戏寻径中的应用研究-论文.pdf

《基于区域搜索的A＊算法在游戏寻径中的应用研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第22卷第13期电子设计工程2014年7月Vo1．22No．13ElectronicDesignEngineeringJu1．2014基于区域搜索的A：l：算法在游戏寻径中的应用研究张程，肖大薇，张盈谦(大连理工大学城市学院，辽宁大连116600)摘要：寻径是人工智能中的重要组成部分，是游戏开发领域的研究热点。A算法是目前使用最广泛的寻径算法，但其存在搜索耗时、路径曲折等问题。本文提出了一种基于区域搜索的A算法，在提高搜索效能的同时保证了搜索精度，并有效解决了路径曲折问题。实验仿真结果验证了该算

2、法在游戏地图寻径中的有效性和可行性。关键词：A算法；路径搜索；人工智能；游戏开发中图分类号：TP3O1．6文献标识码：A文章编号：1674—6236(2Ol4)l3—00l5—03TheapplicationofA球algorithmbasedontheregionsearchinthegamepath—findingZHANGCheng，XIAODa-wei，ZHANGYing-qian(CityInstitute，DalianUniversityofTechnology,Dalian1166

3、00,China)Abstract：Pathfindingistheimportantpartintheartificialintelligencefieldandhasattractedincreasingattentioninthefieldofgamedevelopment．Aalgorithmisthemostwidespreadtypeofgamepath-findingatpresentbuttheproblemsstillexistsuchastheCUl-Vepathandthe

4、time-consuming．ThispaperproposesanAalgorithmbasedontheregionsearchthatcanraisethesearcheficiency，ensureitsaccuracyandefectivelysolvethecurvepathproblem．Thefeasiblenessandeffectivenessoftheproposedalgorithminthegamepath-findingaredemonstratedbysimulat

5、ionsresults．Keywords：Aalgorithm；path-finding；artificialintelligence；gamedevelopment人工智能(AI)技术已经在计算机科学和产业中发挥了重有多个节点的路径，求出最低通过成本的算法。常用于游戏要的作用，而寻径算法通常会是这些AI模块的核心部分哪。寻中的NPC(非玩家控制单位)的移动计算，或在线游戏的BOT径问题是人工智能的基本问题，具有普适性，并且在很多领域(机器人)的移动计算上。该算法像Dijkstra算法～样，可以

6、找得到应用。A算法是目前游戏中使用最广泛的寻径算法，能到一条最短路径；也像BFS一样，进行启发式的搜索。其启发够很好地解决基本的寻径问题121。但A算法也有很多局限性，函数可以用如下公式表示：存在诸如：随着搜索空间的增大，算法的性能会骤然下降，而9fn)=g(n)+h(n)(1)且对CPU和内存资源的需求也会急剧上升，并不适合大地图其中，【n)是从起始点经由节点n到目标点的启发函数；搜索；算法创建的路径往往是曲折的Z字型路径，过于机械n)是从起始点到n节点的实际代价；^(n)是从节点n到目标化，

7、缺乏真实感；算法仅适用于静态环境，在动态环境中(障碍点的估计代价。能否找到最优路径的关键在于^(n)的选取：物位置发生改变)效果较差等需要考虑的问题。本文针对传统如果(n)<=n到目标点的实际距离，搜索的点数多，搜索范A算法的不足，提出了一种基于区域搜索的A算法，其思路围大，效率低，但能得到最优路径；如果^(n)>n到目标点的实如下：对游戏地图进行预处理，将其划分为若干可自由通行的际距离，搜索的点数少，搜索范围小，效率高，但不能保证得相连区域。以区域作为寻径节点，采用A算法生成从起始点到最优路径

8、。到目标点的最优区域路径。依据区域路径，获取起始点到目标1．2A算法流程点的最终可行路径。实验仿真结果证明，该算法能够大大缩短A算法在执行过程中需要维护两张表，Open表和寻径时间，特别适合大地图寻径，且获得的路径更平滑，有效Closed表[51。其中，Open表保存所有已生成而未考察的节点，提高了系统的自治性，增强了游戏的可玩性。Closed表中记录已访问过的节点同。算法流程如下：1)设起始点为S，目标点为G，初始化Open表和Closed1A木算法表，将起始点S放入Open表。1．1A算法简