基于最优路径存储的游戏寻径算法①.PDFVIP

计 算 机 系 统 应 用 2013 年 第 22 卷 第 2 期 基于最优路径存储的游戏寻径算法① 1,2 2 2 2 宋广涛 , 马 跃 , 廉东本 , 孙 咏 1( 中国科学院 研究生院, 北京 100049) 2( 中国科学院 沈阳计算技术研究所, 沈阳 110168) 摘 要: 研究了应用于游戏中的多个路径搜寻算法, 以及游戏路径搜寻的一些特点, 提出了基于最优路径存储的 寻径算法. 主要是通过最优路径矩阵存储部分的最优路径, 减少大量路径的重复计算, 提高游戏中的路径计算效 率. 针对游戏场景角色的移动引起路径点通行状态的变化导致当前的最优路径失效, 提出了路径更新算法, 更新 最优路径矩阵当中的最优路径. 另外, 针对地图路径点规模增大的情况, 提出了地图路径点分块处理的策略, 然 后对每一子块分别使用最优路径矩阵进行路径存储. 关键词: 最优路径; 路径更新; 游戏寻径; 分块处理 Game Path Finding Algorithm Based on the Optimal Path Storage 1,2 2 2 2 SONG Guang-Tao , MA Yue , LIAN Dong-Ben , SUN Yong 1(Graduate School, Chinese Academy of Sciences, Beijing 100049, China) 2(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China) Abstract: Researching some path finding algorithms used in the game, as well as some of the features of game path finding, and giving the routing algorithm based on the optimal path storage. Storing part of the optimal path through the optimal matrix to reduce the large number of repeated path computation, and improve the efficiency of path computation in the game. For the role movement in game scenes changing the state of path points to pass lead to the optimal path of the optimal path matrix invalid. Path update algorithm is given to update the optimal path of the optimal path matrix. As map path points become larger and larger, map paths are divided; then paths are stored for each sub-block using the optimal path matrix. Key words: optimal path; path update; game path finding; block processin 为减少人员伤亡, 财产损失, 提高在特殊火灾和 (3) 能够应对游戏场景当中路径点通行状态的变化, 灾害事故处置行动中的成功率, 近年来基于游戏模式 (4)大量的行走路径之间有重叠部分. 的模拟演练系统得到了快速的发展, 游戏寻径对于模 拟演练系统又是不可或缺的一部分.