摘要
自动计算生成虚拟人的最优路径是虚拟人路径规划研究中的关键问题之一,针对这一问题对A*算法进行了分析、实现和改进.通过对估价函数进行加权处理,缩短了搜索路径,减少了搜索时间;并且引入"人工搜索标志"避免了重复搜索无效区域,能有效快速地逃离障碍物陷阱,使算法在未知环境中有效准确地找到可行性路径,进而对可行性路径进行优化得到最短路径,解决了虚拟人避障与导航问题.
Automatically calculating and generating optimal walking path is one of the key issues in virtual human path planning. This paper analyzed the A ^＊ algorithm and realized it. We modified the traditional A^＊ algorithm, by weighing the process of evaluation function, which makes the number of searching step reduced from 200 to 80, and searching time reduced from 4. 359 s to 2. 823 s in the feasible path planning. We introduce the artificial searching marker to avoid searching the invalid region repeatedly, which can help effectively and quickly escape the barrier trap, making the algorithm more effective and accurate in finding the feasible path in unknown environments, and through optimizing the feasible path to get the shortest path, we solve the issue of virtual human＇s obstacle avoidance and navigation.
出处
《厦门理工学院学报》
2011年第4期45-49,共5页
Journal of Xiamen University of Technology
关键词
A*算法
评价函数
路径优化
搜索标志
A^ ＊ Mgorithm
evaluation function
path optimization
search marker
