A*（A-star）算法 C++ 代码

A*（A-star）算法是一种启发式搜索算法，常用于解决寻路问题，特别是在游戏开发、机器人导航等场景中非常实用。它的核心思想是利用对目标节点的估计距离和实际路径长度来指导搜索过程，从而尽可能找到最短路径。

下面是C++实现A*算法的一个简单示例：

#include <iostream>
#include <vector>
#include <queue>

// 定义图中的节点结构
struct Node {
    int x, y;
    int cost; // 到起点的成本
    int heuristic; // 从当前节点到目标点的启发式估算值
    bool visited; // 是否访问过

    Node(int _x, int _y) : x(_x), y(_y), cost(0), heuristic(heuristic_cost(x, y)), visited(false) {}
};

int heuristic_cost(int x, int y) { // 用曼哈顿距离作为启发式函数
    return abs(x - target_x) + abs(y - target_y);
}

bool operator<(const Node& a, const Node& b) {
    return a.cost + a.heuristic > b.cost + b.heuristic;
}

void a_star_search(Node** grid, int width, int height, int startX, int startY, int endX, int endY) {
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> open_list;
    open_list.push({startX, startY, 0, heuristic_cost(startX, startY)});
    
    Node* start = new Node(startX, startY);
    while (!open_list.empty()) {
        Node current = open_list.top();
        open_list.pop();

        if (current.x == endX && current.y == endY) {
            print_path(current);
            break;
        }

        current.visited = true;

        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                int newX = current.x + dx;
                int newY = current.y + dy;

                if (newX >= 0 && newX < width && newY >= 0 && newY < height && !grid[newX][newY].visited) {
                    int newCost = current.cost + 1; // 每次移动花费1步

                    if (grid[newX][newY].cost > newCost) {
                        grid[newX][newY].cost = newCost;
                        grid[newX][newY].parent = &current;
                        grid[newX][newY].heuristic = heuristic_cost(newX, newY);

                        open_list.push(grid[newX][newY]);
                    }
                }
            }
        }
    }
}

// 打印路径
void print_path(Node* node) {
    std::cout << "Path found from (" << node->x << ", " << node->y << ") to (" << endX << ", " << endY << ")\n";
    Node* parent = node->parent;
    while (parent != nullptr) {
        std::cout << "(" << parent->x << ", " << parent->y << ") ";
        parent = parent->parent;
    }
    std::cout << "\n";
}

int main() {
    // 初始化网格和其他参数
    // ...

    a_star_search(grid, width, height, startX, startY, endX, endY);
    return 0;
}

在这个示例中，`a_star_search`函数接受一个二维网格表示地图，以及起点和终点坐标。它使用优先队列存储待处理的节点，并按照F值（总成本+启发式成本）进行排序。当找到目标节点时，会调用`print_path`打印路径。