This paper presents an algorithm, which is used to find the shortest path between two given nodes in a grid with sparse polygon obstacles. Among these obstacles some of them may be bridged. The algorithm executes the search using a “don't change direction” heuristic along the line towards the target node. The path has eight searching directions, which are decided by the opposition of sources and target nodes. According to the result of many contrastive and on-the-fly experiments, the algorithm reduces the size of searching region. The path length is also shorter than those found by using traditional algorithms. Performance analysis shows that this algorithm is efficient.
LeeD. T.FreparataF. P.. Euclidean Shortest Paths in The Presence of Rectilinear Barriers. NETWORKS.198414:393–410.
8.
ZhiZhouGuoliangChen, Gu Jun. Finding Obstacle Avoiding Shortest Path Using Connection Graph With O(t log t) Edges. Chinese Journal of Computers, 1999, 22(5):519–524.
9.
FarongZhang. “A Searching Algorithm for Approximately Shortest Path Among Obstacles”. Computer Engineering, Vol. 25, No. 3, 1999, pp. 15–16.
10.
QiaoyuSunYinrongPan etc, “An Approximately Maze-Algorithm for a Shortest Path with Sparse Obstacles”. Computer Applications And Software, Vol. 20, No. 5, 2003, pp. 37–39.
11.
QiaoyuSun etc, “A Maze-Algorithm with Eight Directions”. Computer Engineering, Vol. 30, No. 1, 2004, pp. 90–91.
