Java中的A星實現

Question

我想在Java中實現A *，但是我碰到了一堵磚牆，基本上不知道如何從這一點開始。

我目前正在關注來自Wikipedia的僞代碼。

我的節點構造，像這樣：

static class Node { 
    int col; 
    int row; 
    int g; 
    int h; 
    int f; 
    public Node(int col, int row, int g, int h) { 
     this.col = col; 
     this.row = row; 
     this.g = g; 
     this.h = h; 
     this.f = g+h; 
    } 
} 

它重要注意到，在創建節點時f計算。

我當前的A *代碼，這是uncomplete：

public void makeAstar(MapParser parsedMap) { 
     // create the open list of nodes, initially containing only our starting node 
     ArrayList<Node> openList = new ArrayList<Node>(); 
     // create the closed list of nodes, initially empty 
     Map closedMap = new Map(rowSize, columnSize, "Closed map"); 
     // Fill closedMap with 0's 
     closedMap.buildMapWithValue(0); 
     // Create neighbourlist 
     ArrayList<Node> neighbourList = new ArrayList<Node>(); 

     // Some vars 
     int rowTemp = 0; 
     int colTemp = 0; 
     int currentCost = 0; 
     int tempCost = 0; 

     //TODO hardcore cost! rowTemp+colTemp 

     // Initialize with the first node 
     openList.add(new Node(0,0,9,this.getMapValue(0, 0))); 

     while(!openList.isEmpty()) { 
      // Consider the best node, by sorting list according to F 
      Node.sortByF(openList); 
      Node currentNode = openList.get(0); 
      openList.remove(0); 

      // Stop if reached goal (hardcoded for now) 
      if(currentNode.getCol() == 4 && currentNode.getRow() == 4) { 
       System.out.println("Reached goal"); 
       break; 
      } 

      // Move current node to the closed list 
      closedMap.setMapValue(currentNode.getRow(), currentNode.getCol(), 1); 

      // Get neighbours 
      rowTemp = currentNode.getRow()-1; 
      colTemp = currentNode.getCol(); 
      if(!currentNode.isTopRow()) { // Add value^
       neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp))); 
      } 

      rowTemp = currentNode.getRow(); 
      colTemp = currentNode.getCol()-1; 
      if(!currentNode.isRightColumn()) { // Add value < 
       neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp))); 
      } 

      rowTemp = currentNode.getRow(); 
      colTemp = currentNode.getCol()+1; 
      if(currentNode.isLeftColumn()) { // Add value > 
       neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp))); 
      } 

      rowTemp = currentNode.getRow()+1; 
      colTemp = currentNode.getCol(); 
      if(currentNode.isBottomColumn()) { // Add value v 
       neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp))); 
      } 

      // As long as the neighbour list is not empty 
      while(!neighbourList.isEmpty()) { 
       Node temp = neighbourList.get(0); 
       neighbourList.remove(0); 

       if(!isNotInClosedMap(temp.getRow(), temp.getCol())) { 
        continue; 
       } 

       //Stuck here !   

      } 
     }   
    } 

最後一行的評論基本上是在那裏我已經結束，這相當於在僞附近for each neighbor in neighbor_nodes(current)東西。此外，我明白，G是從開始節點的總成本，但我如何計算這個值？

由於有些人可能會注意到在初始創建鄰居row+col時增加了一個硬編碼的G值，這就開始位置是0,0而言。

Answer 1

我認爲你正在尋找的計算公式爲：

tentative_g_score := g_score[current] + dist_between(current,neighbor) 

言下之意是，你需要在每個節點存儲沿着迄今發現它的最佳路徑分數。您爲當前節點創建了一個新的分數，並且如果通過當前節點的路徑優於鄰居節點的最佳分數，則其目標是更新每個鄰居的最佳分數。

我不確定硬編碼G值相對於算法的重要性。如果您已經知道獲取每個節點的最佳案例成本，我認爲您不需要A *。

我強烈建議重構重新命名您的字段以匹配您正在使用的僞代碼中的標識符。這會讓你更容易看到你的代碼是如何工作的，並且與僞代碼無關。它也可以幫助將僞代碼交織爲註釋。