山东科技大学学报（自然科学版）
山東科技大學學報（自然科學版）
산동과기대학학보（자연과학판）
JOURNAL OF SHANDONG UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURAL SCIENCE)
2013年
3期
77-82
,共6页
韩李涛%牟乃夏%戴洪磊%王振勇
韓李濤%牟迺夏%戴洪磊%王振勇
한리도%모내하%대홍뢰%왕진용
最短路径搜索%分层道路图%Dijkstra算法%改进A*算法
最短路徑搜索%分層道路圖%Dijkstra算法%改進A*算法
최단로경수색%분층도로도%Dijkstra산법%개진A*산법
由于大范围复杂虚拟城市环境中开放空间导航网络节点数量较多,导致了利用传统的A*算法或Dijkstra 算法进行路径搜索的效率较低.针对该问题,基于原始道路图构建了层次道路图,重点研究了适用于层次道路图的改进A*算法:依据最短路径搜索起始点所在位置的不同,可以直接或间接在层次道路图的抽象层进行最短路径搜索,再把最短路径上的复合节点展开为原始子节点,从而获得最终的最短路径.结果表明:该方法可以快速完成虚拟角色在虚拟城市环境中的全局路径规划,路径搜索效率明显高于传统的A*算法和Dijkstra算法.
由于大範圍複雜虛擬城市環境中開放空間導航網絡節點數量較多,導緻瞭利用傳統的A*算法或Dijkstra 算法進行路徑搜索的效率較低.針對該問題,基于原始道路圖構建瞭層次道路圖,重點研究瞭適用于層次道路圖的改進A*算法:依據最短路徑搜索起始點所在位置的不同,可以直接或間接在層次道路圖的抽象層進行最短路徑搜索,再把最短路徑上的複閤節點展開為原始子節點,從而穫得最終的最短路徑.結果錶明:該方法可以快速完成虛擬角色在虛擬城市環境中的全跼路徑規劃,路徑搜索效率明顯高于傳統的A*算法和Dijkstra算法.
유우대범위복잡허의성시배경중개방공간도항망락절점수량교다,도치료이용전통적A*산법혹Dijkstra 산법진행로경수색적효솔교저.침대해문제,기우원시도로도구건료층차도로도,중점연구료괄용우층차도로도적개진A*산법:의거최단로경수색기시점소재위치적불동,가이직접혹간접재층차도로도적추상층진행최단로경수색,재파최단로경상적복합절점전개위원시자절점,종이획득최종적최단로경.결과표명:해방법가이쾌속완성허의각색재허의성시배경중적전국로경규화,로경수색효솔명현고우전통적A*산법화Dijkstra산법.
