C++如何实现一个A*寻路算法？C++游戏AI与路径规划【算法实战】

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 行，但调通路径、处理斜向、适配不同地图格式才是实际耗时点。

# node # ai # c++ # cos # 排列 # red # Float # while # 封装 # 结构体 # int # 循环 # 指针 # 数据结构 # 堆 # Struct # operator # 对象 # 算法 # 曼哈顿 # 是从 # 自定义 # 最优 # 点到 # 的是 # 欧几里得 # 升序 # 最有希望 # 才是

返回目录在线咨询

上一篇：企业应采取哪些措施防止网站服务器遭受恶意入侵？
下一篇：SQL server 2008不允许保存更改的完美解决办法(图解)

您的项目需求