游戏中的路径搜索算法

游戏中的路径搜索算法 { 求得路径 PATH; 地游戏能否顺利运行的重要保证 , 。返回路径 PATH; 搜索算法简介1 } 首先提提状态空间搜索状态空间搜索就是将问求解过 。, 每一个 的子节点 for (X x)程现为从初始状态到目标状态寻找这个路径的过程由于求 。{ 解问题的过程中分枝有很多使得求解的路径很多这就构成了 , , 不在 队列和 队列中 if( x Start Searched )一个图这个图就是状态空间问题的求解实际上就是在这个图 , 。{ 中找到一条路径可以从开始到结果这个寻找的过程就是状态 。求 的估价值 x ;空间搜索游戏中的各个场景就是许多不同的状态空间角色移 。, 将 插入 队列中 x Start ;} 动的起点和终点就可看作这个角色的初始状态和目标状态比 。在 队列中 else if( x Start )如游戏中场景通常分为多个大小相同的方块角色的步长以这 , , { 些方块为单位如果角色的步长是一个方块则它所在的方块周 。, 的估价值小于 队列的估价值 if( x Start )围有八个方块按照顺时针编为 至 号如图 所示角色想 ( 0 7 , 1 ) , 更新 队列中的估价值 Start ;移动时只能走这八个方块中的一个这些方块被赋予障碍或非 。} 障碍属性障碍属性的方块角色不能通过, 。 else { 的估价值小于 队列的估价值 if( x Searched ){ 更新 队列中的估价值 Searched ; 从 队列中移出节点并插入 Searched , Start } } 图 1 将 节点插入 队列中 X Searched ;按照估价值将 队列中的节点排序 Start ; 传统搜索算法1.1 } 盲目搜索算法是最有代表性的传统搜索算法广度优先搜 。} 索和深度优先搜索这两种就属于盲目搜索广度优先是从 。} 初始状态一层一层向下找直到找到目标为止深度优先是按照 , 。以上算法程序全部用 语言编写C++。 一定的顺序前查找完一个分支再查找另一个分支以至找到目 , , 两种算法的比较 2 标为止他们都是在一个给定的状态空间中穷举这种算法在游 。。 下面就用一个例子对两种算法作一下比较戏中的表现就是按照特定的顺序如顺时针把角色周围的八个 。, 方块按照从 到 的顺序都搜索一次找出下一步的位置后再 0 7 , , 以图 代表游戏场景的地形如果场景中某处是不 2 。采取同样的方法搜索下八个方块。 的高山河流等地形时则此处的方块具有障碍属性在图 、, , 灰色方块表示黑色的方块表示此处可以通行白色的方 。, 经过改进后的新搜索算法目的地标有 的方块表示起点标 有 的 方 块 表 示 角 色, S , R 1.2 经过改进后的搜索算法在排列待扩展方块的顺序上提出了 的路径。 新方法即根据特定的信息选择最有希望的方块加以扩展它对, 。 根据评估出的估价状态空间中的每一个搜索的位置进行评估 , 值得到最好的位置再从这个位置进行搜索直到目标以免盲目 , , 地扩展这种算法应用到游戏中后表现为选定一个方向如顺 。: , 时针方向循环搜索八个方块如果得到了非障碍属性的方块 , X, 就把它作为下一步的位置方块 的前一个循环方块 即被视, X Y 为最有希望的方块从方块 开始搜索时就把方块 作为循 。X , Y 环的起点而不是把方块 周围的方块 作为起点所以搜索 , X 0 。 过程中设置两个队列队列和 队列队列存 : Start Searched 。Start 放所有准备搜索的方块的信息队列中 存 放 已 搜 索 过 , Searched 的方块的信息循环中的每一步只考虑 队列中最有希望的。Start 方块算法的伪程序如下 。: S Path_Search( ){ 图 2 初始化 队列和 队列 Start Searched 使用传统搜索算法寻路2.1 如果使用传统搜索算法所示的情况这是则可能出现图 , 3 。 因为到达 这一点后由于算法始终从它周围的 号点开始R1 , 0 R R 搜索如果目的地没有处在被搜索点的周围无 就会出现错误, , , R R1 法到达目的地。 R R R R R R R R1 R R S R 图 4 R 从上面这个例子可以看出传统算法一般只适用于求 , R 较简单的问题在状态空间不大的情况下它是比较合适的算。 R 可是当状态空间十分大它不但效率不 且不预测的情况下, , S 而且容易出错而新算法修改了传统算法在搜索上的一些。 图 之处能引导算法优先搜索接近目的地的位置这样可以省 3 , , 使用新搜索算法寻路量无畏的搜索路径减少了出错的可能性提高了游戏的运 , , 2.2 如果使用新搜索算法就会得出正确的路径如图 所示 , , 4 。 率。 以上是以顺时针方向找到的路径也可以按逆时针方 从起点 至 点之间的路径两种算法的结果是相同的关键。S R1 , 。 就在从 点开始搜索后由于它与终点之间已经没有障碍属找路径道理是一样的这里就不再阐述了R1 , , , 。 结论性的方块新算法可以使角色直接向终点前进 , 。3 游戏中的角色也越 现在游戏中的场景越来越复杂, , 多有了优秀的寻路算法玩家能很容易的使用鼠标控制角 , 。 移动同时游戏中的敌人也变的越来越聪明了这样一来 。, 。 的可玩性有了很大提高可以吸引更多的玩家加入到游戏当, 参考文献 李远静 莫诚生 游戏编程北京清华大学出版社[1] , Windows , , , 2004 程序北京北京大学出版社[2] Charles Petzold, Windows , , , 1998 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 页上接第 ( 108 ) 站点 执行 和 时历史缓冲区的 图中标出了站点 仅需记录原始文档长度原始文档的内容不必保存每 1: 1 O1 O8 , , 冲区有一个文档偏移变量指出其在原始文档中的位置在状态。。 算法改进计算插入操3.3 操作到缓冲区的时候按顺序查找各个缓冲区 ,上文在介绍 算法时为了简化问题是在文档状态初FOPT , , 位置 如果插入的位置出现在原始文档部分则要创建新的, , 现在考虑一下文档初始状态不为始为空的前提条件下分析的区改进前面的算法使之支持原始文档不为空的情况并不难 ,, 空的情况当文档初始状态不为空时并不是文档的所有部分都 当执行的操作逐渐增多时必须有一种机制来减 另外, 。, , 映射到操作缓冲区这时我们可以把操作缓冲区页存的消耗可以考虑整合 等在中提出得算法限于篇下转第 , ( 102 ), Sun [2], 分成多个部分如图 所示 , : 不再详述5 。 结束语4 本文提出了一种基于隐藏恢复原理的一致性维护算法 算法综合了文档标注算法和基于操作转换的算法的优点 , 来的算法相比在时间复杂度和空间复杂度上做了相应的优 , 由于目前我们的研究刚刚起步下一步 很多地方还不完善, , 将实现一个基于该算法的协同文本编辑器以进行更深入 , 究。图 文档状态不为空时历史缓冲区的组织5 参考文献 [1] Ellis, C. A. and Gibbs, S. J. ,Concurrency control in groupware systems. In Proc. ACM, 1989, 399- 407 [2] Sun C., Achieving Convergence, Causality Preservation, and Intention Preservation in R eal- Time Cooperative Editing Systems, ACM, 1998 [3] Yang J M, Gu N and Wu X Y, A Document Mark Based Method Supporting Group Undo, From Internet [4] Vidot, N ., Cart, M., Ferri′e, J. & Suleiman, M., Copies convergence in a distributed real- time collaborative environment, ACM, 2000 吴筱媛顾宁基于文档标注的并发控制方法计算机研究与发展[5] ,, ,,2002, Vol.39,N o.12