錯誤的A *路徑代碼搜索

Question

我有一些C++代碼是爲了查找A *路徑而寫的，但它的行爲很奇怪。這裏有相當多的代碼，所以我將它分成幾塊，並試圖解釋我在做什麼。我不會解釋A *路徑如何工作。我假設你是否試圖幫助你已經知道算法。

首先，這是我的計算節點的H值函數：

int 
calculateH(int cX, int cY, int eX, int eY, int horiCost = 10, int diagCost = 14) { 
int h; 
int xDist = abs(eX - cX); 
int yDist = abs(eY - cY); 

if (xDist > yDist) 
    h = (diagCost * yDist) + (horiCost * (xDist - yDist)); 
else 
    h = (diagCost * xDist) + (horiCost * (yDist - xDist)); 

return h; 
} 

我敢肯定這裏沒有問題;很簡單的東西。

接下來我的節點類。我知道，我知道，將這些變量隱藏起來並使用getter;我只是這樣做了測試目的。

class Node { 
public: 
Node(int x_, int y_, int g_, int h_, int pX_, int pY_, bool list_) { 
    x = x_; 
    y = y_; 
    g = g_; 
    h = h_; 
    pX = pX_; 
    pY = pY_; 
    list = list_; 
}; 
int x, y, g, h, pX, pY; 
bool list; 
}; 

每個節點都有一個X和Y變量。我只存儲G和H，而不是F，並在需要時計算F（在我的代碼中只有一次）。然後是Parent X和Y值。 List是一個布爾值：fale =打開列表，true =關閉列表。

我也有一個對象類。這裏唯一重要的變量是X，Y和Passable，它們都是通過getter訪問的。
這裏是我的實際尋路代碼的開始。它返回對應方向上的一串數字，如下圖所示：
所以1種手段向右移動，8種手段去向下和向右，0表示不去任何地方。

string 
findPath(int startX, int startY, int finishX, int finishY) { 
// Check if we're already there. 
if (startX == finishX && startY == finishY) 
    return "0"; 
// Check if the space is occupied. 
for (int k = 0; k < objects.size(); k ++) 
    if ((objects[k] -> getX() == finishX) && 
     (objects[k] -> getY() == finishY) && 
     (!objects[k] -> canPass())) 
     return "0"; 
// The string that contains our path. 
string path = ""; 
// The identifier of the current node. 
int currentNode = 0; 
// The list of nodes. 
vector<Node> nodes; 
// Add the starting node to the closed list. 
nodes.push_back(Node(startX, startY, 0, 
    calculateH(startX, startY, finishX, finishY), 
    startX, startY, true)); 

現在我們循環直到找到目的地。請注意，sizeLimit只是爲了確保我們不會永久循環（如果我可以修復此代碼，則爲WONT，因爲現在是非常必要的）。從這一點開始，直到我標記爲止，都在i j循環內。

int sizeLimit = 0; 
while ((nodes[currentNode].x != finishX) | (nodes[currentNode].y != finishY)) { 

    // Check the surrounding spaces. 
    for (int i = -1; i <= 1; i ++) { 
     for (int j = -1; j <= 1; j ++) { 
      bool isEmpty = true; 
      // Check if there's a wall there. 
      for (int k = 0; k < objects.size(); k ++) { 
       if ((objects[k] -> getX() == (nodes[currentNode].x + i)) && 
        (objects[k] -> getY() == (nodes[currentNode].y + j)) && 
        (!objects[k] -> canPass())) { 
        isEmpty = false; 
       } 
      } 

下一個部分：

// Check if it's on the closed list. 
      for (int k = 0; k < nodes.size(); k ++) { 
       if ((nodes[k].x == (nodes[currentNode].x + i)) && 
        (nodes[k].y == (nodes[currentNode].y + j)) && 
        (nodes[k].list)) { 
        isEmpty = false; 
       } 
      } 

在繼續：

// Check if it's on the open list. 
      for (int k = 0; k < nodes.size(); k ++) { 
       if ((nodes[k].x == (nodes[currentNode].x + i)) && 
        (nodes[k].y == (nodes[currentNode].y + j)) && 
        (!nodes[k].list)) { 
        // Check if the G score is lower from here. 
        if (nodes[currentNode].g + 10 + (abs(i * j) * 4) <= nodes[k].g) { 
         nodes[k].g = nodes[currentNode].g + 10 + (abs(i * j) * 4); 
         nodes[k].pX = nodes[currentNode].x; 
         nodes[k].pY = nodes[currentNode].y; 
        } 
        isEmpty = false; 
       } 
      } 

這是IJ循環的最後一部分：

if (isEmpty) { 
       nodes.push_back(Node(nodes[currentNode].x + i, 
        nodes[currentNode].y + j, 
        nodes[currentNode].g + 10 + (abs(i * j) * 4), 
        calculateH(nodes[currentNode].x + i, nodes[currentNode].y + j, finishX, finishY), 
        nodes[currentNode].x, 
        nodes[currentNode].y, 
        false)); 
      } 
    } 
} 

現在我們找到節點最低的F分數，將其更改爲當前的分數de，並將其添加到封閉列表中。對無限截枝的保護也完成了在這裏：

// Set the current node to the one with the lowest F score. 
    int lowestF = (nodes[currentNode].g + nodes[currentNode].h); 
    int lowestFIndex = currentNode; 
    for (int k = 0; k < nodes.size(); k ++) { 
     if (((nodes[k].g + nodes[k].h) <= lowestF) && 
      (!nodes[k].list)) { 
      lowestF = (nodes[k].g + nodes[k].h); 
      lowestFIndex = k; 
     } 
    } 
    currentNode = lowestFIndex; 
    // Change it to the closed list. 
    nodes[currentNode].list = true; 

    sizeLimit ++; 
    if (sizeLimit > 1000) 
     return ""; 
} 

我遇到的問題是，它不會找到一定路徑。如果路徑在任何點上升或離開，它似乎永遠不會工作。向下，向左和向右都工作正常。無論如何大部分時間。我完全不知道是什麼原因造成這個問題。有一次，我甚至嘗試手動以下我的代碼，看看問題出在哪裏。毫不奇怪，沒有工作。還有一件事：如果你在計算我的大括號（首先哇，你比我想象的更有奉獻精神），你會注意到我在最後錯過了一個大括號。更不用說我的迴歸聲明瞭。最後有一些代碼來實際製作我遺漏的路徑。我知道那部分不是問題，我現在已經註釋掉了，它仍然不能以相同的方式工作。我添加了一些代碼來告訴我它不工作，它在尋路部分，而不是解釋。

對不起，我的代碼是如此混亂和低效。我是C++的新手，所以對我的技術的任何批評建議也是受歡迎的。

Answer 1

我認爲，當你正在尋找下一個「currentNode」時，你不應該從lowestF = (nodes[currentNode].g + nodes[currentNode].h);開始，因爲原則上這個值（總是）會低於或等於open-組。只需從std::numeric_limits<int>::max()或某個非常大的值開始，或者使用優先級隊列而不是std::vector來存儲節點（如std::priority_queue或boost::d_ary_heap_indirect）。

我很確定這是問題所在。由於你的啓發式經常可以等於實際獲得的路徑距離，所以開放集合中的後續節點很有可能具有與當前節點相同的成本（g + h）。這可以解釋爲什麼某些路徑會被探索，而其他路徑則不會，以及爲什麼會被卡住。