错误的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）。这可以解释为什么某些路径会被探索，而其他路径则不会，以及为什么会被卡住。