Кратчайший путь Java

Как сказал Марк, это задача о кратчайшем пути, которую можно решить легко и эффективно.

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

Псевдокод для BFS:

findShortestPath(source,target):
  queue<- new queue
  visited <- {}
  Map<point,point> parents <- empty map
  queue.push(source)
  while (queue.empty() == false): 
     current <- queue.takeFirst()
     if (current.equals(target)):
         extract the path from source to destination using the map parents(*)
         return
     visited.add(current)
     for each p such that p and current are neighbors: //insert neighbors to queue
          if p is not in visited: 
                if (p is not an obstacle):
                   queue.push(p)
                   parents.put(p,current) //current is the parent of p

(*) Извлечь путь из карты очень просто: просто следуйте current <- parent.get(current), пока не получите null, таким образом вы извлечете точный путь, который будете использовать.

Обратите внимание, что даже более быстрым решением [в большинстве случаев] будет A* с эвристика манхэттенского расстояния, но реализовать ее намного сложнее.

задача о кратчайшем пути много изучалась, и по этой проблеме существует много литературы. Вероятно, лучше всего просто использовать существующий алгоритм, а не пытаться изобретать его самостоятельно.

Например, простым и эффективным алгоритмом является алгоритм Дейкстры. Из Википедии:

1. Пусть узел, с которого мы начинаем, называется начальным узлом. Пусть расстояние узла Y будет расстоянием от начального узла до Y. Алгоритм Дейкстры назначит некоторые начальные значения расстояния и попытается улучшить их шаг за шагом. Назначьте каждому узлу предварительное значение расстояния: установите его равным нулю для нашего начального узла и бесконечностью для всех остальных узлов.
2. Отметьте все узлы как непосещенные. Установите начальный узел как текущий. Создайте набор непосещенных узлов, называемый непосещенным набором, состоящий из всех узлов, кроме начального узла.
3. Для текущего узла рассмотрите всех его непосещенных соседей и вычислите их ориентировочные расстояния. Например, если текущий узел A помечен ориентировочным расстоянием 6, а ребро, соединяющее его с соседом B, имеет длину 2, то расстояние до B (через A) будет 6+2=8. Если это расстояние меньше ранее записанного ориентировочного расстояния B, то перезапишите это расстояние. Несмотря на то, что соседний узел был просмотрен, он не помечен как посещенный в это время и остается в наборе непосещенных.
4. Когда мы закончим рассмотрение всех соседей текущего узла, отметим текущий узел как посещенный и удалим его из набора непосещенных. Посещенный узел больше никогда не будет проверяться; его расстояние, записанное сейчас, является окончательным и минимальным.
5. Если узел назначения помечен как посещенный (при планировании маршрута между двумя конкретными узлами) или если наименьшее предварительное расстояние между узлами в непосещенном наборе равно бесконечности (при планировании полного обхода), то остановитесь. Алгоритм завершен.
6. Установите непосещенный узел, отмеченный наименьшим предварительным расстоянием, в качестве следующего «текущего узла» и вернитесь к шагу 3.

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