现在的位置: 首页 > 综合 > 正文

Hierarchical Path-Finding

2017年11月03日 ⁄ 综合 ⁄ 共 1000字 ⁄ 字号 评论关闭

Hierarchical Path-Finding

     《Near Optimal Hierarchical Path-Finding》中提出了一种层次A*算法,正好能够用于解决项目大地图寻路的问题。大致思路是:1)预处理。将地图划分为nxn大小的区块,找出每个区块与周围四个区块在边界上的互通点,在区块中使用局部A*对找出的点做连通性测试并将其保存下来;2)寻路时,使用预处理得到的数据(边界上的可通点与区块内部的互通点),先在区块层级上做一次A*,根据结果再在每个区块中使用局部A*找到区块与区块之间的路径,最终得到完整路径。

一、A* Path-Finding

     A*算法就不多讲了,可参考:

     A*算法的优化可从搜索节点储存和OpenList排序两方面入手。

二、预处理

     每个相邻区块(C1和C2)都有一条由公共边,该边两侧小格组成L1和L2,则连通点集E满足下列条件:

  • E ⊂ L1 ∪ L2
  • ∀t ∈ L1 ∪ L2 : t ∈ E ⇔ symm(t) ∈ E ,其中symm(t)为对称关系
  • E不含不可行走格子

     对在E中且同边的连续格子取其中点,如下图所示:

Image(6)

    对上面得到的位于同一区块的点集合使用local A*做连通性测试,下图用直线连接来表示两点互通:

Image(7)

三、寻路

     使用区块连通信息,进行区块级A*,得到区块之间的连接点,如果在预处理时保存了区块内互通点的路径,就不必再进行区块内的local A*了。

     实验结果表明,在未采用区块内预存路径的情况下,中长距离寻路使用层次A*后的平均效率是普通A*的5倍以上,距离越长效率对比越明显。

image

     A* 93ms

image

HPA* 15ms

     从上图中可以看出,HPA*得到的路径并不是最优的,它是在最优和效率上的折中,适合作为长距离寻路的一种优化方案。

四、优化点

  • 可扩展为多层而不仅限于一层
  • 预存区块内连通点路径
  • 区块边界可通面积较大时,产生不自然路径,如下图所示:

image

          一个改进的方法是对过长的边界再做划分:

Image(5)

posted on 2011-11-12 12:50 Heath 阅读(1159) 评论(0)  编辑 收藏 引用 所属分类: Game
Development

抱歉!评论已关闭.