2

我编写了一些 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 类。而且我知道，我知道，将这些变量设为私有并使用 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 是一个布尔值：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 分数最低的 Node，将其更改为当前节点，并将其添加到关闭列表中。防止无限循环的保护也在这里完成：

// 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++ 新手，因此也欢迎对我的技术提出任何批评意见。

4

1 回答 1

4

我认为当你在寻找下一个“currentNode”时，你不应该从lowestF = (nodes[currentNode].g + nodes[currentNode].h);这个值开始，因为原则上，这个值将（总是）低于或等于开放集中的任何其他节点。只需从 的值std::numeric_limits<int>::max()或某个非常大的数字开始，或者使用优先级队列而不是std::vector来存储节点（如std::priority_queue、 或boost::d_ary_heap_indirect）。

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

于 2011-03-18T05:22:58.237 回答