c++ - A* 路径代码中的错误搜索

Question

我编写了一些 C++ 代码来查找 A* 路径，但它的行为很奇怪。这里有相当多的代码，所以我将把它分成 block 并尝试解释我在做什么。我不会解释 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 类。我知道，我知道，将这些变量设为私有(private)并使用 setter/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(这在我的代码中只有一次)。然后是父 X 和 Y 值。 List 是一个 bool 值:fale = 开放列表，true = 封闭列表。

我还有一个 Object 类。此处唯一重要的变量是 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 只是为了确保我们不会永远循环(如果我可以修复这段代码，它就不会发生。截至目前，这是非常必要的)。从这一点开始的所有内容，直到我另有标记，都在 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;
                }
            }

这是 i j 循环的最后一部分:

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值最低的Node，将其更改为当前节点，并将其加入到closed list中。防止无限循环的保护也到此结束:

// 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<int>::max() 的值开始或一些非常大的数字，或者使用优先级队列而不是 std::vector存储节点(如 std::priority_queue 或 boost::d_ary_heap_indirect )。

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