我應該使用哪種算法來查找未加權網格中從A到B的最短路徑？

Question

該場景是基於回合的情況，玩家必須從源位置A移向位置B，但只能移動最大數量的單位。

例如，B距離A有24個單位（使用BFS計算），並且我得到了12分。我怎樣才能找到B的最佳路徑，只有12個運動單位？

注：

• 無法移動斜
• 有大的障礙物

編輯：這是類似於線索/妙探尋兇遊戲，但只有文字等等玩家將選擇一個方向朝'移動'。

這裏是我的嘗試：

示例格：（◘是障礙，○不是）

○○○○○○○○○○ 
○○○○○○○○◘◘ 
○○○◘◘◘○○◘◘ 
○○○◘◘◘○○B◘ 
○A○◘◘◘○○◘◘ 

算法：

if paces == 0, return 
try moving col closer to dest.col: 
    if col == dest.col, move row closer to dest.row 
    else if adjacent is blocked, move row away from start 

這紙上作品還行，除了當我跑進一個角落時：

○A→◘◘○○◘◘◘ 
○○↓◘◘○○B◘◘ 
○○↓◘◘○○◘◘◘ 
○○↓◘◘○○↑◘◘ 
○○↓→→→→→◘◘ 

解決方案：

public ArrayList<Location> shortestPath(final Location start, final Location dest) { 
    HashSet<Location> visits = new HashSet<>(); 
    HashMap<Location, Location> links = new HashMap<>(); 

    PriorityQueue<Location> queue = new PriorityQueue<>(Board.GRID_COLS * Board.GRID_ROWS, 
      new Comparator<Location>() { 

       @Override 
       public int compare(Location a, Location b) { 
        return Integer.compare(getHeuristic(a, dest), getHeuristic(b, dest)); 
       } 
      }); 

    queue.add(start); 

    while (!queue.isEmpty()) { 
     Location current = queue.remove(); 
     if (current.equals(dest)) { 
      ArrayList<Location> path = reconstruct(current, new LinkedList<Location>(), links); 
      path.add(dest); 
      return path; 
     } 

     visits.add(current); 
     for (Location neighbour : getNeighbours(current)) { 
      if (!visits.contains(neighbour)) { 
       queue.add(neighbour); 
       visits.add(neighbour); 
       links.put(neighbour, current); 
      } 
     } 

    } 
    return null; // failed 
} 

// Manhattan distance 
private int getHeuristic(Location src, Location dest) { 
    return Math.abs(dest.row - src.row) + Math.abs(dest.col - src.col); 
} 

private ArrayList<Location> reconstruct(Location current, LinkedList<Location> list, HashMap<Location, Location> links) { 
    if (links.containsKey(current)) { 
     list.addFirst(links.get(current)); 
     return reconstruct(links.get(current), list, links); 
    } else { 
     return new ArrayList<>(list); 
    } 
} 

private ArrayList<Location> getNeighbours(Location current) { 
    ArrayList<Location> neighbours = new ArrayList<>(); 

    if (current.row < GRID_ROWS - 1) { 
     Location n = LOCATIONS[current.row + 1][current.col]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.row > 0) { 
     Location n = LOCATIONS[current.row - 1][current.col]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.col < GRID_COLS - 1) { 
     Location n = LOCATIONS[current.row][current.col + 1]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.col > 0) { 
     Location n = LOCATIONS[current.row][current.col - 1]; 
     if (isAccessible(n, current)) neighbours.add(n); 

    } 
    return neighbours; 
} 

Answer 1

聽起來像是A*一個完美的工作。

在您的圖表，這將基本上只是是相同的（算法）的廣度優先搜索，但使用優先級隊列（由f(x)訂購）而不是隊列。

Answer 2

一些有用的評論，遊戲板的左上角應該是座標（0,0）。如果您只想知道一條路徑，您可以選擇任何返回的路徑。最佳步驟是路徑的長度 - 1，因爲路徑包含起點。希望它能幫助你。

using System; 
using System.Collections.Generic; 
using System.Drawing; 

namespace Game 
{ 
    class Program 
    { 
     /// <summary> 
     /// Find a matrix with all possible optimum paths from point A to point B in the game board 
     /// </summary> 
     /// <param name="board">Game board</param> 
     /// <param name="moves">Allowed moves</param> 
     /// <param name="matrix">Resulting matrix</param> 
     /// <param name="A">Point A</param> 
     /// <param name="B">Point B</param> 
     private static void FindMatrix(List<List<char>> board, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B) 
     { 
      matrix = new List<List<int>>(); 
      A = new Point(-1, -1); 
      B = new Point(-1, -1); 
      //Init values of the matrix 
      for (int row = 0; row < board.Count; row++) 
      { 
       matrix.Add(new List<int>()); 
       for (int col = 0; col < board[row].Count; col++) 
       { 
        matrix[matrix.Count - 1].Add(board[row][col] == '◘' ? -1 : 0); 
        switch (board[row][col]) 
        { 
         case 'A': 
          { 
           A.X = col; 
           A.Y = row; 
           matrix[row][col] = -1; 
           break; 
          } 
         case 'B': 
          { 
           B.X = col; 
           B.Y = row; 
           break; 
          } 
        } 
       } 
      } 
      if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board 
      { 
       var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() }; 
       int index = 0; 
       int level = 0; 
       pairs[index].Add(A); 
       while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B)) 
       { 
        pairs[Math.Abs(1 - index)].Clear(); 
        level++; 
        foreach (var pair in pairs[index]) 
         foreach (var move in moves) //Test all possible moves 
          if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < board.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < board[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the board? Not visited before? 
          { 
           pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y)); 
           matrix[pair.Y + move.Y][pair.X + move.X] = level; 
          } 
        index = Math.Abs(1 - index); 
       } 
       matrix[A.Y][A.X] = 0; 
      } 
     } 

     /// <summary> 
     /// Finds all possible optimum paths from point A to point B in the game board matix 
     /// </summary> 
     /// <param name="matrix">Game board matrix</param> 
     /// <param name="moves">Allowed moves</param> 
     /// <param name="A">Point A</param> 
     /// <param name="B">Point B</param> 
     /// <param name="result">Resulting optimum paths</param> 
     /// <param name="list">Temporary single optimum path</param> 
     private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list) 
     { 
      if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition 
      { 
       result.Add(new List<Point>(list)); 
      } 
      else 
      { 
       foreach (var move in moves) 
        if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the board? Next step? 
        { 
         list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell 
         WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list); 
         list.RemoveAt(list.Count - 1); //Clean temporary cell 
        } 
      } 
     } 

     /// <summary> 
     /// Finds all possible optimum paths from point A to point B in the game board 
     /// </summary> 
     /// <param name="board">Game board</param> 
     /// <returns>All possible optimum paths</returns> 
     public static List<List<Point>> FindPaths(List<List<char>> board) 
     { 
      var result = new List<List<Point>>(); 
      var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise) 
      List<List<int>> matrix; //Matrix temporary representation of the game to store all possible optimum paths 
      Point A; 
      Point B; 
      FindMatrix(board, moves, out matrix, out A, out B); 
      if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board 
      { 
       List<Point> list = new List<Point>(); 
       list.Add(A); 
       WalkMatrix(matrix, moves, A, B, ref result, ref list); 
      } 
      return result; 
     } 

     static void Main(string[] args) 
     { 
      List<List<char>> board = new List<List<char>> //An example of game board 
      { 
       new List<char>("○○○○○○○○○○"), 
       new List<char>("○○○○○○○○◘◘"), 
       new List<char>("○○○◘◘◘○○◘◘"), 
       new List<char>("○○○◘◘◘○○B◘"), 
       new List<char>("○A○◘◘◘○○◘◘") 
      }; 
      List<List<Point>> paths = FindPaths(board); 
     } 
    } 
}