Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (21): 25-29.DOI: 10.3778/j.issn.1002-8331.2004-0423

Previous Articles     Next Articles

Research on Path Planning Algorithm with Obligatory Node Constraint

WANG Lei, SUN Lifan   

  1. 1.School of International Education, Henan University of Science and Technology, Luoyang, Henan 471023, China
    2.School of Information Engineering, Henan University of Science and Technology, Luoyang, Henan 471023, China
  • Online:2020-11-01 Published:2020-11-03



  1. 1.河南科技大学 国际教育学院,河南 洛阳 471023
    2.河南科技大学 信息工程学院,河南 洛阳 471023


As for the problems of searching too many nodes and running inefficiently on traditional A-Star algorithm, this paper proposes a path planning algorithm with obligatory node constraint. Considering the layout of obstacles, this algorithm limites searching directions of A* by finding out an obligatory node of shortest path. And then it connects both shortest path segments to form the shortest path. An experiment is performed between traditional A-Star algorithm and improved algorithm in maps of 100×100 grids. It shows that the operation efficiency of A-Star algorithm has been significantly improved.

Key words: A-Star algorithm, obstacle block, landing point, simulate path, obligatory node, path planning



关键词: A*算法, 障碍物块, 登陆点, 模拟路径, 必经点, 路径规划