17370845950

A*算法用优先队列按f(n)=g(n)+h(n)扩展最有希望节点，g为起点到当前实际代价，h为到目标预估代价（如曼哈顿距离），需维护开放列表（最小堆）、关闭列表和地图数据，保证最优性需h可容许。

核心思路：用优先队列驱动的启发式搜索

不是暴力遍历所有格子，而是每次从“最有希望到达终点”的节点开始扩展。关键靠两个值：f(n) = g(n) + h(n)。其中 g(n) 是从起点到当前节点的实际代价（比如走过的格子数或距离和），h(n) 是从当前节点到目标的预估代价（常用曼哈顿距离或欧几里得距离）。优先队列按 f(n) 升序排列，保证最先出队的是当前综合代价最小的节点。

数据结构准备：节点与开放/关闭集合

定义一个结构体封装节点信息：

// 示例：2D网格中每个格子的表示
struct Node {
  int x, y;
  float g, f;
  Node* parent = nullptr;
  Node(int x, int y) : x(x), y(y), g(0), f(0) {}
};

需要三个容器：

• 开放列表（open set）：用 std::priority_queue 或 std::set 存储待探索节点，按 f 排序
• 关闭列表（closed set）：用 std::unordered_set（配合自定义哈希）或 std::set 记录已完全处理的坐标，避免重复访问
• 地图数据：二维 vector 或数组，标记是否可通行（如 grid[y][x] == 0 表示空地）

主循环：扩展、计算、更新

算法主体是 while 循环，直到开放列表为空或找到终点：

• 取出 f 最小的节点 current
• 若 current 是终点，调用回溯函数（从 parent 指针一路返回起点）生成路径
• 否则将其加入关闭列表，检查上下左右（或八方向）邻居
• 对每个合法邻居 next（在地图内、未被阻挡、不在关闭列表中）：
  • 计算新 g 值（current.g + cost(current → next)，通常为 1 或 sqrt(2)）
  • 若 next 不在开放列表中，或新 g 更小，则更新其 g、f 和 parent，并插入或重新排序开放列表

实用优化与注意事项

真实游戏里不能只写个“能跑通”的版本：

• 启发函数要可容许（admissible）：h(n) 不能高估真实代价，否则不保证最优；曼哈顿距离适合四向移动，欧氏距离适合八向，对角线移动可用切比雪夫距离
• 避免浮点误差影响排序：用整数运算或加小偏移量；priority_queue 需自定义比较器，注意 operator 是大顶堆，要反着写
• 内存友好：不每次都 new Node，可用对象池或二维数组预分配节点；用坐标哈希代替指针比较更稳定
• 提前终止与失败处理：开放列表空了还没到终点，说明不可达，返回空路径

基本上就这些。写出来不到 200 行，但调通路径、处理斜向、适配不同地图格式才是实际耗时点。