分级查询(Hierarchical Path-Finding )

Hierarchical Path-Finding

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

一、A* Path-Finding

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/40780145