C++ A* Pathfinding causes infinite loop

Question

I'm really new to this kind of thing and used this tutorial to write my code.

Basically, calling my function causes my code to crash, the obvious problem would be that I'm causing an infinite loop, but I can't see it.

Take a look:

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

I use a simple Vector2 struct I wrote in a header file here:

#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

Adding some comments on code quality would be nice too.

Answer 1

The problem is that you didn't calculate node.f correctly. Referring to the tutorial provided,

F = G + H

where G is the cost from A to the current square and H is the estimated cost from the current square to B. However, looking back to the code referring this part:

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

It seems that the G is always 1, while the rest of the code is for working out H. In this case , G should be the steps it takes from A to currentNode plus 1, since it has take one step to move.

So, the most important part is that, only saving F is not enough. G has to be saved in order to work out F in other squares.

Edit: The reason why we do not use (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 is because we might not reach the current square without a detour. e.g.

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

Supposed that now we are at point E starting form point S. Using (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 , the distance is only 1. However, it takes 5 steps to go to E.