a*算法在c++中2d网格路径搜索的最简可行版本：用priority_queue实现开放列表，曼哈顿距离作启发式函数，正确更新g值与f=g+h排序，支持0/1地图、起点终点输入，核心约40行可直接运行。
用A*算法在C++中实现2D网格路径搜索最简可行版本
直接能跑通的A*实现，核心就几十行，不需要第三方库。关键不是写得多，而是把heuristic、cost和open_set更新逻辑写对——错一个地方，路径就绕远或根本找不到。
假设地图是vector<vector>></vector>，0表示可通行，1表示障碍；起点(sx, sy)，终点(ex, ey)。用priority_queue做开放列表，自定义比较器按f = g + h排序：
struct Node {
int x, y, g;
Node(int x, int y, int g) : x(x), y(y), g(g) {}
};
struct Compare {
bool operator()(const Node& a, const Node& b) {
return a.g + abs(a.x-b.x) + abs(a.y-b.y) > b.g + abs(b.x-b.x) + abs(b.y-b.y);
}
};
注意：priority_queue默认是大顶堆，所以比较符里用>才能让最小f在队首。别写成，否则路径会乱。
如何正确计算曼哈顿启发式并避免越界访问
2D网格里用曼哈顿距离（abs(x-ex) + abs(y-ey)）足够快且满足A*可采纳性。但必须在每次取邻居前检查坐标是否在[0, width)和[0, height)范围内，否则map[y][x]会越界读写——尤其当起点紧贴边界时，x-1或y+1立刻崩。
- 四个方向邻居：用
dx[4] = {0, 0, 1, -1}和dy[4] = {1, -1, 0, 0}比写四次if更不容易漏 - 检查顺序必须是：先判坐标合法 → 再判
map[new_y][new_x] == 0→ 最后查是否已访问过 - 不要在
heuristic里用欧氏距离——浮点运算慢，且在网格中不满足可采纳性（可能高估）
为什么用unordered_set存closed_set比vector快得多
每扩展一个节点，都要查它是否已处理过（即是否在closed set里）。如果用vector<pair>></pair>线性遍历，100×100地图最坏情况要查上万次；换成unordered_set<string></string>或unordered_set<long></long>（比如y * width + x），平均O(1)。
推荐用整数编码：key = y * map_width + x，避免字符串构造开销。别用set——红黑树O(log n)不必要，且unordered_set在小数据量下也足够稳定。
容易忽略的一点：unordered_set默认bucket数可能太小，首次插入前调用reserve(expected_max_size)能减少rehash次数。
路径回溯时怎么避免内存泄漏和空指针
A*找到终点后，需要从终点沿parent指针往回走。别用裸指针存父节点——容易忘delete，也不方便拷贝。直接用vector<vector>>></vector>存每个格子的父坐标，初始化为{-1,-1}：
vector<vector>>> parent(height, vector<pair>>(width, {-1,-1}));
// 找到终点后：
vector<pair>> path;
for (int x = ex, y = ey; x != -1 && y != -1; ) {
path.push_back({x, y});
int px = parent[y][x].first;
int py = parent[y][x].second;
x = px; y = py;
}
reverse(path.begin(), path.end());
</pair></pair></vector>
注意循环条件用x != -1 && y != -1，而不是parent[y][x] != {-1,-1}——后者比较pair效率低，且可能因未初始化导致误判。起点的parent[sy][sx]保持{-1,-1}，作为终止信号。
真正麻烦的是动态障碍或实时重规划——这时候得换Jump Point Search或D* Lite，但纯静态网格，A*加这几个细节就够了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
