Прослеживая путь через лабиринт в Java

Question

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

110111 
110101 
010100 
110100 
011100 
000000 

Чтобы указать, где находится начало и конец являются:

S10111 
11010E 
010100 
110100 
011100 
000000 

код я должен решить, как и проследить путь лабиринта, приводится ниже:

public List<Location> solution() { 
    int[][] solvedMaze = new int[height][width]; 
    Location current; 

    PriorityQueue<Location> queue = new PriorityQueue<>(new Comparator<Location>() { 
     @Override 
     public int compare(Location a, Location b) { 
      double distanceA = distance(start, a)/1.5 + distance(a, end); 
      double distanceB = distance(start, b)/1.5 + distance(b, end); 
      return Double.compare(distanceA, distanceB); 
     } 

     private double distance(Location first, Location second) { 
      return Math.abs(first.i() - second.i()) + Math.abs(first.j() - second.j()); 
     } 
    }); 

    queue.add(start); 

    while ((current = queue.poll()) != null) { 
     if (solvedMaze[current.i()][current.j()] != 0) { 
      continue; 
     } 

     int mod = 1; 

     for (Location next : new Location[]{ 
      current.south(), current.west(), current.north(), current.east() 
     }) { 
      if (isInMaze(next) && isClear(next)) { 
       if (solvedMaze[next.i()][next.j()] == 0) { 
        queue.add(next); 
       } else { 
        mod = Math.min(solvedMaze[next.i()][next.j()], mod); 
       } 
      } 
     } 

     solvedMaze[current.i()][current.j()] = mod; 

     if (isFinal(current)) { 
      break; 
     } 
    } 

    for (int i = 0; i < height; i++) { 
     for (int j = 0; j < width; j++) { 
      System.out.print(solvedMaze[i][j]); 
     } 
     System.out.println(); 
    } 

    if (solvedMaze[end.i()][end.j()] != 0) { 
     List<Location> route = new ArrayList<>(); 
     Location temp = end; 

     while (!temp.equals(start)) { 
      route.add(temp); 

      Location best = null; 
      int bestNumber = solvedMaze[temp.i()][temp.j()]; 

      for (Location next : new Location[]{ 
       temp.north(), temp.south(), temp.west(), temp.east() 
      }) { 
       if (isInMaze(next) && solvedMaze[next.i()][next.j()] != 0) { 
        if (solvedMaze[next.i()][next.j()] < bestNumber) { 
         bestNumber = solvedMaze[next.i()][next.j()]; 
         best = next; 
        } 
       } 
      } 

      assert best != null; 
      temp = best; 
     } 

     route.add(start); 
     Collections.reverse(route); 

     return route; 
    } else { 
     return null; 
    } 
} 

где Location - это класс, который содержит координаты x и y, и start и end - это местоположения. По какой-то причине мой вывод всегда null, и я не уверен, почему. После некоторой простой отладки print я обнаружил, что условие solvedMaze[next.i()][next.j()] < bestNumber в логике восстановления никогда не вводится. В чем проблема с этим методом? Есть ли лучший (более эффективный) способ его решения?

Answer 1

Выбранная вами логика, похоже, полагается на 1 на solvedMaze, которая была заменена на «кратчайшее расстояние от начала», поэтому она проходит назад от End to Start на пути к лучшему (aka downcending).

E.g. solvedMaze должно быть:

1 2 0 12 13 14 
2 3 0 11 0 15 
0 4 0 10 0 0 
6 5 0 9 0 0 
0 6 7 8 0 0 
0 0 0 0 0 0