网格上点之间的最近路径

Question

我的网格尺寸为 2000x2000。我在网格上存储了一些点，我想连接其中的一些点，但连接需要是从一个点到另一个点的最近路径。我有 :

private static readonly Dictionary<double,Point> ExistingPoints = new Dictionary<double, Point>(); private static Point[,] gridMatrix = new Point[200, 200];

其中 ExistingPoints 是放置在网格上的点的字典，gridMatrix 包含字典中的相同点，但他的 row 和 column 是来自的 x 和 y点除以 10，以便可以在网格上表示。

那么我怎样才能找到从一个点到另一个点的最近路径呢？

编辑

Path can only go on grid,也就是说它只能走直线，不能是直线，所以当我需要上/下/左/右时，它需要成90度

Answer 1

好的，就像我们在评论中所说的那样，我会这样做：

List<Point> path = new List<Point>();
Point startingPoint = new Point(1000, 1000);
Point targetPoint = new Point(500, 500);
Point currentPos = startingPoint;

//Level in Y
while (currentPos.Y != targetPoint.Y)
{
     path.Add(new Point(currentPos.X, currentPos.Y);
     currentPos.Y += (currentPos.Y > targetPoint.Y ? -1 : 1);
}
//Level in X
while(currentPos.X != targetPoint.X)
{
     path.Add(new Point(currentPos.X, currentPos.Y);
     currentPos.X += (currentPos.X > targetPoint.X ? -1 : 1);
}

//Draw the lines in steps
for (int i = 0; i < path.Count()-1; i++)
{
     DrawLineBetween(path[i], path[i + 1]);
}
DrawLineBetween(path.Last(), targetPoint);

我没有测试代码，但它可以编译并且理论上应该可以工作。该方法 DrawLineBetween 当然仍然需要实施，但我想您已经准备好了。

当然，您可以将 X 和 Y 调平组合在一个循环中，然后进入 "stair" 模式。

网格上点之间的最近路径

Closest path between points on grid

c#

algorithm

wpf

grid-layout