A*搜索算法详解（C++实现路径规划与寻路）

A* 算法的核心数据结构

要实现 A*，我们需要以下关键组件：

1. 地图表示：通常用二维数组，0 表示可通行，1 表示障碍物
2. 节点结构：记录坐标、g 值、h 值、父节点等
3. 开放列表（Open List）：待探索的节点，用优先队列（最小堆）实现
4. 关闭列表（Closed List）：已探索的节点，可用布尔数组或集合记录

C++ 实现 A* 算法

下面是一个完整的 C++ 示例代码，包含详细注释：

#include <iostream>#include <vector>#include <queue>#include <cmath>#include <algorithm>// 定义节点结构体struct Node {    int x, y;          // 坐标    double g, h;       // g: 起点到当前点的实际代价；h: 当前点到终点的预估代价    Node* parent;      // 父节点，用于回溯路径    Node(int x, int y) : x(x), y(y), g(0), h(0), parent(nullptr) {}    // 重载小于号，用于优先队列（f = g + h 越小越优先）    bool operator<(const Node& other) const {        return (g + h) > (other.g + other.h); // 注意：priority_queue 是最大堆，所以反向比较    }};// 计算曼哈顿距离作为启发函数double heuristic(int x1, int y1, int x2, int y2) {    return std::abs(x1 - x2) + std::abs(y1 - y2);}// A* 主函数std::vector<std::pair<int, int>> aStar(    const std::vector<std::vector<int>>& grid,    std::pair<int, int> start,    std::pair<int, int> goal) {    int rows = grid.size();    int cols = grid[0].size();    // 边界检查    if (grid[start.first][start.second] == 1 || grid[goal.first][goal.second] == 1)        return {};    // 初始化开放列表（优先队列）和关闭列表    std::priority_queue<Node> openList;    std::vector<std::vector<bool>> closed(rows, std::vector<bool>(cols, false));    // 创建起始节点    Node* startNode = new Node(start.first, start.second);    startNode->h = heuristic(start.first, start.second, goal.first, goal.second);    openList.push(*startNode);    // 方向数组：上下左右    int dx[4] = {-1, 1, 0, 0};    int dy[4] = {0, 0, -1, 1};    while (!openList.empty()) {        Node current = openList.top();        openList.pop();        // 如果到达终点        if (current.x == goal.first && current.y == goal.second) {            // 回溯路径            std::vector<std::pair<int, int>> path;            Node* p = ¤t;            while (p != nullptr) {                path.push_back({p->x, p->y});                p = p->parent;            }            std::reverse(path.begin(), path.end());            return path;        }        // 标记为已访问        closed[current.x][current.y] = true;        // 探索四个方向        for (int i = 0; i < 4; ++i) {            int nx = current.x + dx[i];            int ny = current.y + dy[i];            // 检查边界和障碍            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols ||                grid[nx][ny] == 1 || closed[nx][ny])                continue;            // 创建新节点            Node* neighbor = new Node(nx, ny);            neighbor->g = current.g + 1; // 假设每步代价为1            neighbor->h = heuristic(nx, ny, goal.first, goal.second);            neighbor->parent = new Node(current.x, current.y);            neighbor->parent->parent = current.parent; // 简化处理（实际应深拷贝）            openList.push(*neighbor);        }    }    return {}; // 未找到路径}// 测试函数int main() {    std::vector<std::vector<int>> grid = {        {0, 0, 0, 0, 1},        {1, 1, 0, 1, 0},        {0, 0, 0, 0, 0},        {0, 1, 1, 1, 0},        {0, 0, 0, 0, 0}    };    auto path = aStar(grid, {0, 0}, {4, 4});    if (!path.empty()) {        std::cout << "找到路径：\n";        for (auto& p : path) {            std::cout << "(" << p.first << ", " << p.second << ") ";        }        std::cout << "\n";    } else {        std::cout << "未找到可行路径！\n";    }    return 0;}

这段代码展示了如何使用 C++寻路算法 实现基本的 A* 功能。注意：上述代码为了教学简化了内存管理（实际项目中建议使用智能指针或对象池避免内存泄漏）。

优化与扩展建议

• 使用 std::unordered_set 或二维布尔数组加速关闭列表查询
• 支持对角线移动（需调整方向数组和启发函数）
• 使用欧几里得距离代替曼哈顿距离以适应不同场景
• 引入动态权重（Weighted A*）提升搜索速度

总结

通过本教程，你已经掌握了 A*搜索算法 的核心思想，并用 C++语言 实现了一个基础版本。无论你是开发游戏 AI、机器人导航系统，还是学习C++路径规划技术，A* 都是你不可或缺的工具。继续练习并尝试优化它，你将能构建更智能的路径规划系统！

记住，真正的C++寻路算法高手不仅会写代码，还会根据实际需求调整启发函数和数据结构。动手试试吧！