一种基于分层结构的最优路径算法 (2013年)

由于大范围复杂虚拟城市环境中开放空间导航网络节点数量较多,导致了利用传统的A*算法或Dijkstra 算法进行路径搜索的效率较低。针对该问题,基于原始道路图构建了层次道路图,重点研究了适用于层次道路图的改进A*算法:依据最短路径搜索起始点所在位置的不同,可以直接或间接在层次道路图的抽象层进行最短路径搜索,再把最短路径上的复合节点展开为原始子节点,从而获得最终的最短路径。结果表明:该方法可以快速完成虚拟角色在虚拟城市环境中的全局路径规划,路径搜索效率明显高于传统的A*算法和Dijkstra算法。