A*算法存在大面积遮挡墙时无法找到最短路径，是否与代价计算相关？

问题结论 #

该问题确实和你的代价计算、节点更新逻辑直接相关，核心问题有两处。

问题复现示意图 #

核心问题分析 #

1. Open Set节点更新逻辑存在漏洞 #

你代码中仅对首次加入open set的节点插入了有序std::set结构，当已经在open set中的节点被搜索到更优的g_score时：

• 你只更新了内存中g_score、f_score变量的值，没有修改std::set中已经存储的旧条目
• std::set的排序依赖插入时的键值，旧条目对应的是更高的f_score，会导致有序集的排序完全错乱，程序会优先处理f_score更高的非最优节点
• 大面积遮挡场景下，非最短路径的终点节点可能会比最优路径的中间节点更早被从set中取出，触发current == end直接中断搜索，返回非最短路径。

2. 启发函数与移动规则不匹配（潜在问题） #

你当前使用的曼哈顿距离作为启发函数，仅在网格仅允许上下左右四方向移动、单步移动代价固定为1的场景下满足可采纳性（启发值不会大于实际最小路径代价）。如果你的场景支持斜向移动，曼哈顿距离会高估实际路径代价，A*算法就无法保证输出最短路径。

修复方案 #

• 修正open set更新逻辑：当已存在于open set的节点找到更优g_score时，先删除std::set中该节点对应的旧条目，再插入新的f_score对应的条目，保证有序集排序正确。
• 匹配启发函数与移动规则：如果支持八方向移动，将启发函数替换为切比雪夫距离max(Δx, Δy)，或者将斜向移动的代价修改为√2，保证启发函数可采纳。
• 快速校验方法：临时修改启发函数固定返回0，此时A*会退化为Dijkstra算法，如果此时可以输出最短路径，即可进一步确认启发函数的适配问题，如果仍然输出错误路径，则完全是open set更新逻辑的问题。

相关代码 #

启发函数代码 #

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

算法主体代码 #

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

内容的提问来源于stack exchange，提问作者stunicks