A*算法 C++代码

A*算法是一种启发式搜索算法，常用于寻找两点之间的最短路径。它的基本思想是在每个节点上评估从起点到当前节点的成本加上到达目标点的预估成本，优先处理那些看起来更接近目标的节点。以下是简单的A*算法的C++代码实现：

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

struct Node {
    int x, y;
    int costSoFar = 0;
    int heuristic; // 从该点到终点的估计代价

    bool operator<(const Node& other) const { // 比较依据总成本
        return (costSoFar + heuristic) < (other.costSoFar + other.heuristic);
    }
};

class AStar {
public:
    std::vector<Node> findPath(int startX, int startY, int endX, int endY) {
        std::vector<Node> openList;
        std::vector<Node> closedList;

        Node startNode = {startX, startY, 0, manhattanDistance(startX, startY, endX, endY)};
        openList.push_back(startNode);

        while (!openList.empty()) {
            Node current = openList.front();
            openList.pop();

            if (current.x == endX && current.y == endY) {
                return reconstructPath(current);
            }

            closedList.push_back(current);

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

                    if (nx >= 0 && nx < width && ny >= 0 && ny < height && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        Node neighbor = {nx, ny, current.costSoFar + 1, manhattanDistance(nx, ny, endX, endY)};
                        neighbor.parent = &current;
                        openList.push(neighbor);
                    }
                }
            }
        }

        return {}; // 如果找不到路径，返回空
    }

private:
    int width, height;
    std::vector<std::vector<bool>> visited;
    int manhattanDistance(int x1, int y1, int x2, int y2) {
        return abs(x1 - x2) + abs(y1 - y2);
    }

    std::vector<Node> reconstructPath(Node node) {
        std::vector<Node> path;
        while (node.parent != nullptr) {
            path.push_back(node);
            node = *node.parent;
        }
        path.push_back(node); // 添加起点
        std::reverse(path.begin(), path.end());
        return path;
    }
};

在这个代码中，`findPath`函数接收起点和终点坐标，并利用`openList`、`closedList`和`visited`数组来管理搜索过程。`manhattanDistance`计算曼哈顿距离作为启发式函数。

注意这只是一个基础版本的A*算法，实际应用中可能需要根据具体环境调整启发式函数和其他细节。