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

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;
g_score[n.first] = INT_MAX;
g_score[start] = 0;
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;

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++