Ближайший путь между точками на сетке

Question

У меня размер сетки 2000х2000.У меня есть несколько точек, сохраненных в сетке, и я хочу соединить некоторые из них, но соединение должно быть ближайшим путем от одного к другому.У меня есть:

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

, где ExistingPoints - словарь точек, размещенных на сетке, а gridMatrix содержит те же точки из словаря, но его row и columnx и y от точки разделены на 10, так что они могут быть представлены на сетке.

Так как же найти ближайший путь от одной точки к другой?

РЕДАКТИРОВАТЬ

Путь может идти только по сетке, то есть он может идти только по линиям, он не может быть прямой линией, поэтому, когда мне нужно идти вверх / вниз / влево / вправо, он должен быть на 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 в одном цикле и затем идти по «лестнице»." шаблон.