一种基于分层结构的最优路径算法

摘要：

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

关键词：最短路径搜索、分层道路图、Dijkstra算法、改进A*算法

所属期刊栏目：32

分类号：TP301.6;P208(计算技术、计算机技术)

资助基金：国家自然科学基金项目41201381;山东省自然科学杰出青年基金项目JQ201113;山东省"泰山学者"建设工程专项经费项目

在线出版日期：2013-08-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：77-82