我有一个程序可以创建一个类似于以下内容的2D数组：
X X X X X X X B X X
B X X X X X X X X X
B X X X X X X X X X
X X X X X X X B X X
X X X X X O B X X X
B X X X X X B X X X
X X X X X X X X X X
X X X X X X X X X X
X =可以自由漫游的空白空间
B =无法自由漫游的受阻区域
O =被移动的物体
我想帮助您弄清楚如何找到到达任何终点的最短路径。通常，我会使用Dijkstra算法，但是要考虑多个点而不是1点。该对象的重点是边缘，我想在那里找到最短的路径。
Lee的算法：http : //en.wikipedia.org/wiki/Lee_algorithm
本质上是BF搜索，下面是一个示例：http : //www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf
要有效实施，请签出：更改FloodFill-Algorithm以获得两个数据点的Voronoi领土？-当我说标记时，请用您来自+ 1的位置上的数字标记。
例如，如果您有一个网格，其中* =障碍物，则可以向上，向下，向左和向右移动，并且从S开始，必须转到D，并且0 =自由位置：
S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
您将S放入队列中，然后“扩展”它：
S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
然后扩展其所有邻居：
S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
和所有这些邻居的邻居：
S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D
依此类推，最终您将获得：
S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9
因此，从S到D的距离为9。运行时间为O（NM），其中N =行数，M =列数。我认为这是最容易在网格上实现的算法，并且在实践中也非常有效。它应该比经典的dijkstra更快，但是如果使用堆实现dijkstra可能会获胜。
对任何起点和端点执行此操作，然后选择您所用整数最小的端点。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句