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是不够的。为了在其他方块中计算出F，必须保存G。

编辑:我们不使用(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。