A* algorithm doesn’t find the shortest path when I put a big wall

  a-star, c++

My implementation of the A* algorithm doesn’t guarantee the shortest path when there is a big wall covering the board. Does it have something to do with the calculations of the costs?

I provided a picture for you to understand what I’m saying. As you can see in the picture, it doesn’t find the shortest path

Heuristic func:

double calc_heuristic(T src, T end, std::map<T, std::pair<sf::Vector2f, bool>> &tileCoords_){
    sf::Vector2f srcLoc(tileCoords_[src].first);
    sf::Vector2f endLoc(tileCoords_[end].first);
    return std::abs(srcLoc.x - endLoc.x) + std::abs(srcLoc.y - endLoc.y);
}

Algorithm:

int count = 0;
std::set<std::pair<std::pair<double, uint32_t>, T>> open_set;
open_set.insert(std::make_pair(std::make_pair(0, count), start));
std::map<T, T> came_from;
std::map<T, uint32_t> g_score;
std::map<T, double> f_score;
for (auto n : adjList)
    g_score[n.first] = INT_MAX;
g_score[start] = 0;
for (auto n : adjList)
    f_score[n.first] = INT_MAX;
f_score[start] = calc_heuristic(start, end, tileCoords_);
std::vector<T> open_set_v {start};
std::vector<T> path_;

while (!open_set.empty()){
    auto current_pair = *(open_set.begin());
    T current = current_pair.second;

    open_set.erase(open_set.begin());
    auto it1 = std::find(open_set_v.begin(), open_set_v.end(), current);
    open_set_v.erase(it1);

    if (current == end)
        break;

    for (auto neighbor : adjList[current]){
        uint32_t temp_g_score = g_score[current] + 1;
        if (temp_g_score < g_score[neighbor.first]){
            came_from[neighbor.first] = current;
            g_score[neighbor.first] = temp_g_score;
            f_score[neighbor.first] = temp_g_score + calc_heuristic(neighbor.first, end, tileCoords_);
            if (std::find(open_set_v.begin(), open_set_v.end(), neighbor.first) == open_set_v.end()){
                count++;
                open_set.insert(std::make_pair(std::make_pair(f_score[neighbor.first], count), neighbor.first));
                open_set_v.push_back(neighbor.first);
            }
        }
    }
}

Source: Windows Questions C++

LEAVE A COMMENT