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;
}

我很确定这里没有问题；很简单的东西。

接下来是我的 Node 类。我知道，我知道，将这些变量设为私有并使用吸气剂；我这样做只是为了测试目的。

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（在我的代码中只出现一次）。然后是父级 X 和 Y 值。列表是一个布尔值：fale = 打开列表，true = 关闭列表。

我还有一个对象类。这里唯一重要的变量是 X、Y 和 Passable，它们都通过 getter 访问。
现在这是我的实际寻路代码的开始。它返回与方向相对应的数字字符串，如下所示：
432
501
678
所以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 只是为了确保我们不会永远循环（如果我可以修复此代码，则不会。到目前为止，这是非常必要的）。从这一点开始，直到我另外标记为止，所有内容都在 ij 循环内。

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 分数最低的节点，将其更改为当前节点，并将其添加到关闭列表中。对无限循环的保护也在这里完成：

// 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); 开始，因为原则上该值，将（总是）低于或等于开放集中的任何其他节点。只需从 std::numeric_limits::max() 的值或一些非常大的数字开始，或者使用优先级队列而不是 std::vector存储节点（如 std::priority_queue 或 boost::d_ary_heap_indirect）。

我很确定这就是问题所在。并且由于您的启发式通常可以等于获得的实际路径距离，因此开放集中的后续节点很可能具有与当前节点相同的成本（g + h）。这可以解释为什么某些路径被探索而另一些则没有，以及为什么它会被卡住。