双层A_算法在游戏寻路方面的研究.pdfVIP

Microcomputer Applications Vol. 26, No.1, 2010 研究与设计 微型电脑应用 2010 年第 26 卷第 1 期 文章编号：1007-757X(2010)1-0026-03 双层 A*算法在游戏寻路方面的研究 蔡方方，杨士颖，张小凤，刘东平 摘 要：A* 算法是目前实时游戏中使用最广泛的寻路算法。但 A*作为最基本的算法思想，并不能直接应用于实际项目中。 该文提出了一种结合地图四叉树预处理的双层 A*寻路算法，在提高效率的同时保证局部有哪些信誉好的足球投注网站精度，另外采用对移动单位赋 予优先级的方法来解决移动阻塞问题。实验证明能改善多单位的移动和避让问题,能同时提高有哪些信誉好的足球投注网站效率和增强游戏实时效果。 关键字：A* 算法；路径有哪些信誉好的足球投注网站；游戏开发 中图分类号：TP311.1 文献标志码：A 0 引言 A*算法作为一种灵活的，高性价比的寻路算法，一直 被游戏行业所广泛采用。但要在具体项目中成功运用 A* ， 则必须解决好诸如优化效率，碰撞策略，阻塞避让等一系列 问题。而现有的同类文章和书籍则大多只是从理论角度来对 A*进行研究。而本文则先从简要介绍 A*和 A*所面临的几 类实际问题起，提出一整套具有应用价值的双层 A*寻路策 略。 图 1 同一物体在不同分辨率的地图中所占据的面积 看似不正确的移动行为。如图 2 ，A 、B 物体要同时向 1 关于 A* 下移动，由于可移动障碍物 1~5 摆放并不整齐，导致 A 可 以直接下行，B 却只能绕远路，但是在观众看来 3、4 号障 1.1 A*算法基本思想 碍物之间的空隙较 1，2 之间更宽。而解决该问题最直接的 A*算法其核心公式为 办法就是提高地图分辨率，不仅再次造成精度与效率的矛 （） f (n) g (n) + h(n) 1 盾，而且当起始点和目的地距离较远时，计算代价会相当昂 其中 g(n)为初始点到节点 n 的移动代价，h(n)为n 点到目标 贵。 点的估计移动代价，而f (n)可以看作是 n 点的综合评估分。 而整个寻路过程，就是从起始节点开始，反复的在待选节点 集合（又称开启列表，开集合）中，选拔f 值最小的节点， 然后将该节点所有邻接节点加入开集合并且同时把该节点 从开集合移动到闭集合。直到开集合包含目标点或为空集 时，算法结束。具体算法参见文献[1][2]。 1.2 A*面临的问题 首先是地图分辨率与有哪些信誉好的足球投注网站效率的矛盾。目前大多数游戏 图2 由于有哪些信誉好的足球投注网站精度而带来的误差 都采用正方形来划分地图，其中的方格相当于 A*算法中的 最后是所谓的路口和隧道问题，当2 个以上移动单位同 节点，如图 1 所示，很明显场景划分得越精细，有哪些信誉好的足球投注网站效果就 时抵达一个狭窄路口或隧道时，如果缺乏相应的处理方法， 越好。但随之而来的必然是成倍增长的有哪些信誉好的足球投注网站耗时。因此在实 则很容易出现阻塞现象。如图 3，A 、C 要移动到最下方， 际应用当中，一般会选取与可移动物体的尺寸相近似的长度 同时B 、D 要移动到最上方，则 A 、B 会在隧道 1 处卡死不 作为方格的边长，如半个或一个物体宽度。