C++ A* 寻路导致死循环

Question

我对这种东西真的很陌生，用过this tutorial编写我的代码。

基本上，调用我的函数会导致我的代码崩溃，明显的问题是我导致了无限循环，但我看不到它。

看看:

std::vector<Vector2> TileMap::pathFind(Vector2 pathStart, Vector2 pathEnd){
    struct Node{
        Vector2 pos;
        int f;
        inline Node operator=(Node a){
            pos = a.pos;
            f = a.f;
        }
    };
    std::vector<Node> openList;
    std::vector<Vector2> closedList;
    closedList.push_back(pathStart);

    Vector2 currentNode = pathStart;
    do{
        if(currentNode.x - 1 >= 0){ //NORTH
            Node node;
            node.pos = Vector2(currentNode.x-1, currentNode.y);
            node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y));
            openList.push_back(node);
        }
        if(currentNode.x + 1 <= MAP_WIDTH){ //SOUTH
            Node node;
            node.pos = Vector2(currentNode.x+1, currentNode.y);
            node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y));
            openList.push_back(node);
        }
        if(currentNode.y - 1 >= 0){ //WEST
            Node node;
            node.pos = Vector2(currentNode.x, currentNode.y-1);
            node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y));
            openList.push_back(node);
        }
        if(currentNode.y + 1 <= MAP_HEIGHT){ //EAST
            Node node;
            node.pos = Vector2(currentNode.x, currentNode.y+1);
            node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y));
            openList.push_back(node);
        }//step 2 now

        if(!(openList.empty())){
            Node minimum = openList[0];
            int num = 0;
            for(auto i : openList){
                num++;
                if(minimum.f > i.f){
                    minimum = i;
                }
            }
            currentNode = minimum.pos;
            closedList.push_back(minimum.pos);
            openList.erase(
            std::remove_if(openList.begin(), openList.end(), [&](Node & node) {
                return node.pos == minimum.pos;
            }), openList.end());
        }

        if(currentNode == pathEnd){
            openList.clear();
        }
    }while(!(openList.empty()));
    return closedList;
}

我使用一个简单的 Vector2 结构，我在此处的头文件中编写:

#ifndef VECTOR2_H_INCLUDED
#define VECTOR2_H_INCLUDED

struct Vector2{
    int x;
    int y;
    Vector2(int x, int y){
        this->x = x;
        this->y = y;
    }
    Vector2(){
        this->x = 0;
        this->y = 0;
    }

    inline Vector2 operator=(Vector2 a){
        x=a.x;
        y=a.y;
    }

    bool operator==(Vector2 a){
        return (x==a.x && y==a.y);
    }
};

#endif // VECTOR2_H_INCLUDED

添加一些关于代码质量的评论也很好。

Answer 1

问题是你没有正确计算 node.f。引用提供的教程，

F = G + H

其中 G 是从 A 到当前方格的成本，H 是从当前方格到 B 的估计成本。但是，回顾引用这部分的代码:

node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y));

似乎G总是1，而其余代码是为了计算H。在这种情况下，G应该是从A到currentNode的步数加1，因为它移动了一步.

所以，最重要的是，仅仅保存F是不够的。必须保存 G 才能在其他方格中计算出 F。

编辑:我们不使用 (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 的原因是因为如果不绕路我们可能无法到达当前方格。例如

+---+
|   |
| | |
|S|E|
+-+-+

假设现在我们从点 S 开始在点 E。使用 (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 ，距离仅为 1。但是，它需要 5去 E 的步骤。