计算机与数字工程2023，Vol.51Issue(12)：2846-2851,6.DOI:10.3969/j.issn.1672-9722.2023.12.015
结合Bresenham与JPS的静态栅格地图的路径搜索算法
Path Search Algorithm for Combining Bresenham with JPS's Static Raster Map
摘要
Abstract
Path planning has always been the focus of research on artificial intelligence and games.The most widely used heu-ristic algorithm is the A*algorithm.Its disadvantage is that there are too many dynamic expansion nodes,which will take up a lot of computer memory and affect the pathfinding rate.The improved JPS jump point algorithm is proposed to reduce memory consump-tion.This algorithm has problems such as a large number of jump points and calculation redundancy.This algorithm has problems such as a large number of jumping points and calculation redundancy.This paper combines the Bresenham algorithm with the JPS jumping point algorithm.Before using the JPS jumping point algorithm,firstly the Bresenham algorithm is used to find the straight path between the starting point and the end point,and the previous node of the obstacle node in the straight path is recorded.Second-ly,the JPS jumping point algorithm is used to find the path of the two points,and finally the paths are spliced to reduce the number of jumping points and the number of nodes for offline search.The simulation results show that the algorithm can effectively reduce the number of jump points and reduce the number of nodes for offline search.关键词
Bresenham算法/JPS算法/A*算法/路径规划Key words
Bresenham algorithm/JPS algorithm/A*algorithm/path planning分类
信息技术与安全科学引用本文复制引用
张遥,马丽丽..结合Bresenham与JPS的静态栅格地图的路径搜索算法[J].计算机与数字工程,2023,51(12):2846-2851,6.基金项目
陕西省教育厅科研计划项目(编号:21JP049)资助. （编号:21JP049）
