具有稀疏障碍的近似迷宫算法

AN APPROXIMATELY MAZE-ALGORITHM FOR A SHORTEST PATH WITH SPARSE OBSTACLES

本文中给出了一个在具有稀疏障碍的迷宫中寻找给定两个单元之间的最短路径的走迷宫算法,算法以“不改变方向”为预测条件,沿直线方向扩展。经大量的随机实验对比,结果证明本文中的算法大量地缩减了搜索范围,是一个高效的算法。

This article presents a maze-running algorithm, which is used to find a shortest path between two given points in a grid with sparse polygon obstacles. The algorithm executes the search using a ' don't change direction' heuristic along the line towards the target point. According to the result of many contrastive on-the-fly experiments, the algorithm substantially reduce the size of the searching region. It is an efficient algorithm.