Java 中的 A* 搜尋演算法

不同的搜尋演算法針對不同的任務而客製化。今天我們要討論的是 A* 搜索，這是最有效的尋路演算法之一。這個非常適合電腦遊戲和建立搜尋圖，例如城市之間的道路等。例如，您可能已經注意到，在戰略或戰術視訊遊戲中，按下按鈕後，您的玩家或團隊如何立即開始，毫不拖延地穿過場地到達您指定的點。之所以沒有延遲，是因為遊戲使用了有效的演算法來準確計算玩家需要如何到達某個地方。或者敵人明確地找到了玩家並開始從遠處朝正確的方向行走。通常，A*演算法用於此類操作。

什麼是A*演算法

尋路演算法 A* 是最佳優先搜尋演算法的範例。A*演算法的目的是找到從一點到另一點的路徑。它是搜尋圖演算法的經典之一。讓我們透過一個例子來了解它是如何運作的。想像一個具有自上而下視圖的 2D 遊戲。讓我們將遊戲區域劃分為正方形貪婪，例如像棋盤一樣的 8*8 單元格。我們的細胞可以是兩種類型之一：可通過的或不可通過的（障礙）。每一段時間，玩家或接近玩家的敵人都會移動一個單元格。在遊戲中，可通過的單元可以具有不同的性質，例如平坦的道路、草地或沙子，這決定了沿著它們移動的難度，但為了簡單起見，我們假設所有可通過的單元都以相同的方式通過。下圖中，藍色的單元格是障礙物。 讓我們將一個單元格（或節點）指定為起始單元格（角色位於其中），將另一個單元格指定為目標或目標單元格（帶有標誌的單元格），並描述A* 演算法在這種情況下的工作原理。角色位於儲存格 (1,1) 中，目標位於儲存格 (7,7) 中。每個單元格都有水平、垂直和對角線的鄰居。是否計算對角線節點取決於遊戲。例如，在許多自上而下的視圖遊戲（例如炸彈人或吃豆人）中，角色只能水平或垂直移動。在這種情況下，除了接觸邊緣之外，每個節點只有 4 個鄰居。如果我們談論的是角色可以沿對角線移動的遊戲，則每個節點最多可以有 8 個鄰居。在演算法的第一步，角色所在的儲存格有兩個鄰居。更準確地說，是三個，但其中一個是障礙。 很明顯，對角線更長。如果我們將單元格的邊有條件地設定為等於 1，則該單元格的對角線長度等於 2 的平方根。這就是畢達哥拉斯定理所說的。若要從儲存格 A 到儲存格 B，必須先選取相鄰儲存格之一，然後選取下一個，依此類推。另外，在此過程中，了解是否有可能從初始單元格到達目標單元格。A* 演算法在每一步都會根據函數 F 的值選擇一個相鄰小區。此函數測量候選小區包含在我們的最短路徑中的程度。這就是成本函數，它是移動函數 G 和啟發函數的和。

• G 成本 — 是距離起始節點的距離。

• H 成本（啟發式）是與結束（目標）節點的距離。這個功能可以不同，由開發人員決定哪個比較好。也許 H 的選擇是 A* 中最重要的，這就是使演算法的任何特定實現或多或少有效的一點。理論上你可以使用任何你想要的功能。

  在我們的例子中，我們知道目標單元格的位置，並且可以計算目標單元格和當前單元格之間的幾何歐幾里德距離。距離越短，我們離目標越近。

• F 成本 = G + H。因此，演算法計算所有鄰居節點的 F 成本，並選擇 F 成本最低的一個首先查看。當我們選擇一個時，我們將其標記為關閉並計算該節點鄰居的值。

正如我們上面提到的，如果角色可以在我們的網格上沿著 8 個方向移動，那麼對角線的步長將比水平或垂直的步長，也就是說，它會更昂貴。讓我們水平、垂直和對角移動。讓我們將沿著一個單元格垂直和水平「通過」的價格指定為相等，例如 10，對角線指定為 14，以避免出現小數。這就是我們的 G 函數的計算方式。

啟發式函數我們如何計算H？

這是一個啟發式函數。這個名字本身就意味著它是由經驗決定的，並且可以有所不同。這裡我們將其等於點 (x1, y1) 和 (x2, y2) 之間的所謂歐幾里德距離： 圖中，對於第一步，有兩個選項，它們的成本是相同的，但在下一步中，角色在其中一個選項中陷入了死胡同。因此，我們要走另一條路。在下一次迭代中，我們已經有 4 個選項。 其中兩個不合適，因為它們向後引導，其他選項同樣好，但演算法決定最好沿對角線到達單元格 (3,2)。此外，在每個步驟中，重複計算函數 F，直到角色到達目標儲存格。當然，如果這樣的一段存在的話。 gif 圖片上的綠色路徑表示角色到旗幟的最佳路徑。

A*演算法一步一步

要在 Java 中實作該演算法，需要執行以下步驟 1. 首先，您需要建立兩個列表，分別為開放節點和封閉節點。2. 初始化兩個列表。在封閉鍊錶中，起始節點指向開放鍊錶。3. 當開啟清單中有元素時： 3a。求具有最小 F 3b 的節點 min。從開啟清單 3c 中刪除 min。決定鄰居最小值（如果考慮對角線，則最多 8 個）3d。檢查每個鄰居：a)如果鄰居是目標小區，則停止搜尋b)如果不是，則為其計算G、H。G = min.G + 鄰居與 min 之間的距離 F = G + H c) 如果與鄰居位置相同的節點在開放列表中且其 F 小於鄰居的 F，則跳過該鄰居 d) 如果與鄰居位置相同的節點在關閉清單中，且其f小於鄰居的f，跳過該鄰居。否則，將該節點新增至開啟清單 內循環 3e 結束。將 min 新增至閉合清單 外循環結束 因此，在每次迭代中，我們將執行下一步：

• 從我們的開放清單中選擇估計總分最低的儲存格。
• 從開啟清單中刪除該儲存格。
• 將我們可以到達的所有儲存格新增到開啟清單中。
• 當我們這樣做時，我們也會處理從該節點到每個新節點的新分數，看看它是否比我們迄今為止所擁有的有所改進，如果是，我們會更新我們對該單元的了解。

A* 偽代碼

下面是 A* 尋路的簡短偽代碼：

Input: a grid with locked and empty cells, with start and goal cell.
Output: least cost path from start to goal cell.

       Initialisation
openList = {startCell} //list of traversed cells
closedList = {}  //list of already traversed cells
g.startCell = 0 //cost from source cell to a cell
h.startCell = h(startCell, goal) //heuristic
f.startCell = g.startCell + h.StartCell

   while openList is not empty
           do

       //let the currentCell equal the cell with the least f value
       currentCell = Cell on top of openList, with least f


                if currentCell == end return
       remove currentCell from openList
       add currentCell to closedList
       foreach n in child.currentCell
                    if n in closedList
       continue
       cost = g.currentCell + distance(currentCell,n)
       if (n in openList and cost < g.n)
           remove n from closedList
           g.n = cost
           h.n = h(n, goal)
           f.n = g.n + h.n

從偽代碼到 Java 中的 A* 實現

A*尋路在Java實作中應該有一些方法來服務演算法：

• Cell，保存必要參數的結構
• 開放列表和封閉列表
• 啟發式函數的計算方法
• 追蹤從來源到目的地的路徑的方法
• 檢查給定單元格是否被阻止、是否已到達、是否有效等的方法

package Asterist;

import java.util.PriorityQueue;
import java.util.Stack;

public class AAsterisk {

//Java Program to implement A* Search Algorithm

   //Here we're creating a shortcut for (int, int) pair
   public static class Pair {
       int first;
       int second;
       public Pair(int first, int second){
           this.first = first;
           this.second = second;
       }

       @Override
       public boolean equals(Object obj) {
           return obj instanceof Pair && this.first == ((Pair)obj).first && this.second == ((Pair)obj).second;
       }
   }

   // Creating a shortcut for tuple<int, int, int> type
   public static class Details {
       double value;
       int i;
       int j;

       public Details(double value, int i, int j) {
           this.value = value;
           this.i = i;
           this.j = j;
       }
   }

   // a Cell (node) structure
   public static class Cell {
       public Pair parent;
       // f = g + h, where h is heuristic
       public double f, g, h;
       Cell()
       {
           parent = new Pair(-1, -1);
           f = -1;
           g = -1;
           h = -1;
       }

       public Cell(Pair parent, double f, double g, double h) {
           this.parent = parent;
           this.f = f;
           this.g = g;
           this.h = h;
       }
   }

   // method to check if our cell (row, col) is valid
   boolean isValid(int[][] grid, int rows, int cols,
                   Pair point)
   {
       if (rows > 0 && cols > 0)
           return (point.first >= 0) && (point.first < rows)
                   && (point.second >= 0)
                   && (point.second < cols);

       return false;
   }

   //is the cell blocked?

   boolean isUnBlocked(int[][] grid, int rows, int cols,
                       Pair point)
   {
       return isValid(grid, rows, cols, point)
               && grid[point.first][point.second] == 1;
   }

   //Method to check if destination cell has been already reached
   boolean isDestination(Pair position, Pair dest)
   {
       return position == dest || position.equals(dest);
   }

   // Method to calculate heuristic function
   double calculateHValue(Pair src, Pair dest)
   {
       return Math.sqrt(Math.pow((src.first - dest.first), 2.0) + Math.pow((src.second - dest.second), 2.0));
   }

   // Method for tracking the path from source to destination

   void tracePath(
           Cell[][] cellDetails,
           int cols,
           int rows,
           Pair dest)
   {   //A* Search algorithm path
       System.out.println("The Path:  ");

       Stack<Pair> path = new Stack<>();

       int row = dest.first;
       int col = dest.second;

       Pair nextNode = cellDetails[row][col].parent;
       do {
           path.push(new Pair(row, col));
           nextNode = cellDetails[row][col].parent;
           row = nextNode.first;
           col = nextNode.second;
       } while (cellDetails[row][col].parent != nextNode); // until src


       while (!path.empty()) {
           Pair p = path.peek();
           path.pop();
           System.out.println("-> (" + p.first + "," + p.second + ") ");
       }
   }

// A main method, A* Search algorithm to find the shortest path

   void aStarSearch(int[][] grid,
                    int rows,
                    int cols,
                    Pair src,
                    Pair dest)
   {

       if (!isValid(grid, rows, cols, src)) {
           System.out.println("Source is invalid...");
           return;
       }


       if (!isValid(grid, rows, cols, dest)) {
           System.out.println("Destination is invalid...");
           return;
       }


       if (!isUnBlocked(grid, rows, cols, src)
               || !isUnBlocked(grid, rows, cols, dest)) {
           System.out.println("Source or destination is blocked...");
           return;
       }


       if (isDestination(src, dest)) {
           System.out.println("We're already (t)here...");
           return;
       }


       boolean[][] closedList = new boolean[rows][cols];//our closed list

       Cell[][] cellDetails = new Cell[rows][cols];

       int i, j;
       // Initialising of the starting cell
       i = src.first;
       j = src.second;
       cellDetails[i][j] = new Cell();
       cellDetails[i][j].f = 0.0;
       cellDetails[i][j].g = 0.0;
       cellDetails[i][j].h = 0.0;
       cellDetails[i][j].parent = new Pair( i, j );


  // Creating an open list


       PriorityQueue<Details> openList = new PriorityQueue<>((o1, o2) -> (int) Math.round(o1.value - o2.value));

       // Put the starting cell on the open list,   set f.startCell = 0

       openList.add(new Details(0.0, i, j));

       while (!openList.isEmpty()) {
           Details p = openList.peek();
           // Add to the closed list
           i = p.i; // second element of tuple
           j = p.j; // third element of tuple

           // Remove from the open list
           openList.poll();
           closedList[i][j] = true;

              // Generating all the 8 neighbors of the cell

           for (int addX = -1; addX <= 1; addX++) {
               for (int addY = -1; addY <= 1; addY++) {
                   Pair neighbour = new Pair(i + addX, j + addY);
                   if (isValid(grid, rows, cols, neighbour)) {
                       if(cellDetails[neighbour.first] == null){ cellDetails[neighbour.first] = new Cell[cols]; }
                       if (cellDetails[neighbour.first][neighbour.second] == null) {
                           cellDetails[neighbour.first][neighbour.second] = new Cell();
                       }

                       if (isDestination(neighbour, dest)) {
                           cellDetails[neighbour.first][neighbour.second].parent = new Pair ( i, j );
                           System.out.println("The destination cell is found");
                           tracePath(cellDetails, rows, cols, dest);
                           return;
                       }

                       else if (!closedList[neighbour.first][neighbour.second]
                               && isUnBlocked(grid, rows, cols, neighbour)) {
                           double gNew, hNew, fNew;
                           gNew = cellDetails[i][j].g + 1.0;
                           hNew = calculateHValue(neighbour, dest);
                           fNew = gNew + hNew;

                           if (cellDetails[neighbour.first][neighbour.second].f == -1
                                   || cellDetails[neighbour.first][neighbour.second].f > fNew) {

                               openList.add(new Details(fNew, neighbour.first, neighbour.second));

                               // Update the details of this
                               // cell
                               cellDetails[neighbour.first][neighbour.second].g = gNew;
//heuristic function                               cellDetails[neighbour.first][neighbour.second].h = hNew;
                               cellDetails[neighbour.first][neighbour.second].f = fNew;
                               cellDetails[neighbour.first][neighbour.second].parent = new Pair( i, j );
                           }
                       }
                   }
               }
           }
       }

       System.out.println("Failed to find the Destination Cell");
   }

   // test
   public static void main(String[] args) {


   //0: The cell is blocked
  // 1: The cell is not blocked

       int[][] grid = {
               { 1, 1, 0, 0, 1, 0, 0, 0 },
               { 1, 0, 0, 1, 1, 0, 1, 0 },
               { 1, 1, 0, 1, 0, 0, 1, 0 },
               { 1, 1, 0, 1, 1, 1, 1, 1 },
               { 1, 1, 0, 0, 0, 1, 1, 1 },
               { 0, 1, 1, 1, 0, 1, 1, 0 },
               { 1, 1, 0, 1, 1, 1, 1, 0 },
               { 0, 1, 1, 1, 1, 1, 1, 1 }

       };


       // Start is the left-most upper-most corner
       Pair src = new Pair(0,0);
               //(8, 0);

       // Destination is the right-most bottom-most corner
       Pair dest = new Pair(6, 6);

       AAsterisk app = new AAsterisk();
       app.aStarSearch(grid, grid.length , grid[0].length, src, dest);

   }
}

在範例中，我們得到了與上圖相同的網格。只需用二維數組“繪製”它即可。程式輸出以下路徑： 可以看出，這是這兩點之間可以建立的幾條最短路徑之一。請注意，圖片範例中的第六步和程式輸出中的第六步是不同的，儘管這些路徑同樣有效。該程式選擇眾多最有效的選項之一。

結論

我們研究了 A* 搜尋演算法，弄清楚它是如何運作的以及為什麼它在實踐中非常好。我們只考慮了一種啟發式函數——歐幾里德距離。事實上，我們也可以應用例如曼哈頓距離，從而擺脫計算平方根的需要。A* 演算法在實踐中效果很好：在電玩遊戲中，為導航器找到最短路徑，建立地圖。