Why my A* (A star) algorithm can’t move and it loops?

  a-star, algorithm, c++, dijkstra

My algorithm works almost well, but unfortunately, when it reaches a corner, it can’t move further. Can you give me some hints on what I am doing wrong?
If the algorithm does not encounter obstacles, it is free to move left, right, up and down. However, if on a corner, as in the map I posted below, it cannot go down and to the left, constantly going back and forth to the same spot.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>

#ifdef _WIN32
#include <Windows.h>
#else
#include <unistd.h>
#endif

using namespace std;

struct Node
{
    int pos_x;
    int pos_y;
    int cost_g;
    double cost_h;
    double cost_f;
    Node* parent;
};

int main(void)
{
    string FILENAME;
    ifstream FILE;
    cout << "File name: ";
    cin >> FILENAME;
    FILE.open(FILENAME);
    int height, width;
    cout << "Height: ";
    cin >> height;
    cout << "Width: ";
    cin >> width;
    int **tab;
    int rows = width;
    tab = new int*[width];

    while(rows--)
    {
        tab[rows] = new int[height];
    }

    for(int i = 0; i <= width-1; i++)
    {
        for(int j = 0; j <= height-1; j++)
        {
            FILE >> tab[i][j];
        }
    }

    FILE.close();
    cout << endl;

    for(int i = 0; i < width ; i++)
    {
        for(int j = 0; j < height ; j++)
        {
            cout << " " << tab[i][j];
        }

        cout << endl;
    }

    bool check = false;
    int choice_x, choice_y;

    do
    {
        cout << "Start point:";
        cout << "n   Specify position X: ";
        cin >> choice_x;
        cout << "   Specify position Y: ";
        cin >> choice_y;

        if(tab[choice_x][choice_y] == 5)
        {
            cout << "ntEnter the coordinates again.n";
        }

        else
        {
            check = true;
        }
    }
    while(!check);

    tab[choice_x][choice_y] = 3;

    Node node_start
    {
        choice_x,
        choice_y,
        0,
        0,
        0,
        NULL
    };
    check = false;

    do
    {
        cout << "End point:";
        cout << "n   Specify position X: ";
        cin >> choice_x;
        cout << "   Specify position Y: ";
        cin >> choice_y;

        if(tab[choice_x][choice_y] == 5)
        {
            cout << "ntEnter the coordinates again.n";
        }

        else
        {
            check = true;
        }
    }
    while(!check);

    tab[choice_x][choice_y] = 3;

    Node node_stop
    {
        choice_x,
        choice_y,
        0,
        0,
        0,
        NULL
    };
    vector<Node> set_closed;
    set_closed.push_back(node_start);
    vector<Node> set_open;
    Node node_closed{};
    node_closed = set_closed.back();
    bool enter, skip = false;

    while(true)
    {
        for(int x = -1; x <= 1; x++)
        {
            for(int y = -1; y <= 1; y++)
            {
                if((x == 0 && y == 0) || (x == -1 && y == -1) || (x == 1 && y == -1)
                        || (x == -1 && y == 1) || (x == 1 && y == 1))
                {
                    continue;
                }

                if(node_closed.pos_x+x < 0 || node_closed.pos_y+y < 0)
                    continue;

                if(node_closed.pos_x+x >= height || node_closed.pos_y+y >= width)
                    continue;

                if(tab[node_closed.pos_x+x][node_closed.pos_y+y] == 5)
                    continue;

                Node node_open
                {
                    node_closed.pos_x+x,
                    node_closed.pos_y+y,
                    0,
                    0,
                    NULL
                };
                enter = true;


                for(int i = 0; i < set_open.size(); i++)
                {
                    if(node_open.pos_x == set_open[i].pos_x && node_open.pos_y == set_open[i].pos_y)
                    {
                        skip = true;
                        break;
                    }
                }

                if(skip)
                continue;

                if(enter)
                {
                    int cost_g = 1;
                    double cost_h = sqrt(pow(node_open.pos_x - node_stop.pos_x, 2) + pow(node_open.pos_y - node_stop.pos_y, 2));
                    double cost_f = cost_g + cost_h;
                    node_open.cost_g = cost_g;
                    node_open.cost_h = cost_h;
                    node_open.cost_f = cost_f;
                    node_open.parent = &node_closed;
                    set_open.insert(set_open.end(), node_open);
                }
            }
        }

        Node node_parent;
        node_parent = set_open.back();

        for(int i = 0; i < set_open.size(); i++)
        {
            if(node_parent.cost_f > set_open[i].cost_f)
            {
                node_parent = set_open[i];
            }
        }

        set_closed.push_back(node_parent);

        for(int i = 0; i < set_open.size(); i++)
            if(node_parent.pos_x == set_open[i].pos_x && node_parent.pos_y == set_open[i].pos_y)
            {
                set_open.erase(set_open.begin()+i);
            }

        if(set_closed.back().pos_x == node_stop.pos_x && set_closed.back().pos_y == node_stop.pos_y)
        {
            break;
        }

        node_closed = set_closed.back();
        skip = false;
    }

    for(int i = set_closed.size()-1; i > 0; i--)
    {
        //change to nodes
        tab[set_closed[i].pos_x][set_closed[i].pos_y] = 3;
    }

    cout << endl;

    for(int i = 0; i < width; i++)
    {
        for(int j = 0; j < height ; j++)
        {
            cout << " " << tab[i][j];
        }

        cout << endl;
    }

    return 0;
}

Here is the map I am using for testing. At position 17:2, the algorithm backtracks and loops. LINK

Visualization: enter image description here

Source: Windows Questions C++

LEAVE A COMMENT