摘要
以三维虚拟场景中角色的自动寻径为研究背景,提出了一种基于A~*算法的跃层寻径方法,采用改进的启发函数评估各个扩展节点的代价值以确定问题的最优解。通过引入碰撞检测机制,对改进的A~*算法得到的路径进行修正以避免碰撞行为的发生,并对修正后路径的关键点进行插值,借助Bézier曲线构建平滑的导航路径。通过实验验证,在目标点可达的情况下,寻径结果能够良好地适配跃层的情形。
Taking the automatic role pathfinding in three-dimensional virtual scene as the research background, the author proposes a method of multi-layer pathfinding based on A-star algorithm, and uses advanced heuristic functions to evaluate the cost values of various expansion nodes to confirm the optimal solution to the problems. By introducing collision detection mechanism, the navigation path generated by the improved A~* algorithm is modified to avoid collision; and by interpolating the fixed path, the smooth navigation path is constructed using Bézier Curve. The experimental results show that the path finding results can well adapt to the multi-layer case when the target point is reachable.
引文
[1]王防修,周康.基于回溯法的Dijkstra算法改进及仿真[J].计算机仿真,2013,30(11):352-355.Wang Fangxiu,Zhou Kang.Improvement and Simulation of Dijkstra Algorithm Based on Backtracking Algorithm[J].Computer Simulation,2013,30(11):352-355.
[2]郑辉.一种基于谱分析的三维寻径启发式函数[D].杭州:浙江大学,2016.Zheng Hui.A Spectral Based Heuristic Function for 3Dpath finding[D].Hangzhou:Zhejiang University,2016.
[3]张帅,李学仁,张鹏,等.基于改进A*算法的无人机航迹规划[J].飞行力学,2016,34(3):39-43.Zhang Shuai,Li Xueren,Zhang Peng,et al.UAV path planning based on improved A*algorithm[J].Flight Dynamics,2016,34(3):39-43.
[4]孙炜,吕云峰,唐宏伟,等.基于一种改进A*算法的移动机器人路径规划[J].湖南大学学报(自然科学版),2017,44(4):94-101.Sun Wei,LüYunfeng,Tang Hongwei,et al.Mobile Robot Path Planning Based on an Improved A*Algorithm[J].Journal of Hunan University(Natural Science),2017,44(4):94-101.
[5]王道平,徐展,杨岑.基于两阶段启发式算法的物流配送选址-路径问题研究[J].运筹与管理,2017,26(4):70-75,83.Wang Daoping,Xu Zhan,Yang Cen.Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm[J].Operations Research and Management Science,2017,26(4):70-75,83.
[6]孟珠李,焦俊,李郑涛,等.基于A*与B样条算法的农用机器人路径规划系统[J].安徽大学学报(自然科学版),2018,42(1):45-53.Meng Zhuli,Jiao Jun,Li Zhengtao,et al.Agricultural robot path planning system based on A*and B spline algorithm[J].Journal of Anhui University(Natural Science Edition),2018,42(1):45-53.
[7]Yang L,Song D,Xiao J,et al.Generation of dynamically feasible and collision free trajectory by applying six-order Bezier curve and local optimal reshaping[C]//Intelligent Robots and Systems(IROS),2015 IEEE/RSJ International Conference on.IEEE.Hamburg,Germany:IEEE,2015:643-648.
[8]汤圣君,张叶廷,许伟平,等.三维GIS中的参数化建模方法[J].武汉大学学报(信息科学版),2014,39(9):1086-1090,1097.Tang Shengjun,Zhang Yeting,Xu Weipin,et al.Parametric Modeling Method in Three-Dimensional GIS[J].Geomatics and Information Science of Wuhan University,2014,39(9):1086-1090,1097.
[9]詹总谦,林元培,艾海滨.基于3ds Max二次开发的建筑物快速三维重建[J].测绘通报,2016(11):22-25,42.Zhan Zongqian,Lin Yuanpei,Ai Haibin.Rapid 3DReconstruction Based on Secondary Development of 3ds Max[J].Bulletin of Surveying and Mapping,2016(11):22-25,42.
