摘要： 给出了一个在具有稀疏障碍的迷宫中寻找给定两个单元之间的最短路径的走迷宫 算法，算法以“不改变方向”为预测条件，沿直线方向扩展。路径的扩展方向为8个，以水 平和竖直方向及二者相结合得出路径的扩展方向，缩减了传统的最短路径的长度和搜索范围 ，是一个高效的算法。

关键词: 最短路径, 稀疏障碍, 最小迂回, 网格图

Abstract: This article presents a maze-running algorithm, which is used to fin d a shortest path between two given points in a grid with sparse polygon obstacl es. The algorithm executes the search using a "don't change direction" heuristic along the line towards the target point. The path has eight extending direction s, which is decided by the horizontal, the vertical and the combined directions. According to the result of many contrastive on-the-fly experiments, the algorit hm reduces the length of traditional shortest path and the size of searching reg ion. It is an efficient algorithm.

中图分类号: 

• TP301.6