如何用C++实现A*寻路算法

一、什么是A*寻路算法？

A寻路算法（A search algorithm），也叫A算法，是一种启发式搜索算法，常用于求解路径规划问题。A算法结合了Dijkstra算法和启发式搜索的优点，能够在保证找到最短路径的情况下，大大降低搜索的时间和空间消耗。

二、A*寻路算法的原理

1.最短路径

在计算机科学中，最短路径问题是指两点之间的所有路径中，经过的边或节点数最少的一条路径，也叫做最优路径或最短路线问题。在有向图中，Dijkstra算法是求解最短路径问题最常用的算法之一。

2.启发式搜索

启发式搜索（Heuristic Search）是一种通过估价函数来指导搜索过程的算法。它可以通过一些启发式方法，在尽量少的情况下，快速找到一个近似最优解。比如，在A*算法中，由于估价函数的存在，可以对路径规划问题进行有效的搜索。

3.A*算法的估价函数

A算法中的估价函数通常采用f(n) = g(n) + h(n)的形式（其中n是当前节点，g(n)表示从起始节点到n的实际代价，h(n)表示从n到目标节点的估算代价），f(n)表示当前节点的总代价，优先考虑f(n)值低的节点。因此，当A算法考虑下一步要搜索哪个节点时，会根据f(n)的值来确定下一步的搜索方向。

三、C++实现A*寻路算法

对于使用C++实现A*寻路算法，我们需要完成以下几个步骤：

1.定义数据结构

我们先需要定义一些数据结构，用于存储地图信息、节点信息，以及节点之间的连接关系。

struct MapNode {
    int x, y;
    int f, g, h;
    MapNode *parent; // 向前搜索访问的父节点指针
    MapNode(int _x, int _y):x(_x), y(_y), f(0), g(0), h(0), parent(NULL){}
};

class Astar {
public:
    Astar(int width, int height, int *map);
    ~Astar();
    int findPath(MapNode start, MapNode end, bool isIgnoreCorner);

private:
    MapNode *getNode(int x, int y) const;
    void calcG(MapNode *node);
    void calcH(MapNode *node, MapNode *end);
    void calcF(MapNode *node);
    MapNode *getLeastFNode();
    bool isCanReach(const MapNode *node, const MapNode *target, bool isIgnoreCorner) const;
    std::vector<MapNode *> getSurroundNodes(const MapNode *node, bool isIgnoreCorner) const;
    void printMap(MapNode *node);

private:
    int m_mapWidth;
    int m_mapHeight;
    int **m_map;
    std::list<MapNode *> m_openList; //开启列表
    std::list<MapNode *> m_closeList; //关闭列表
    MapNode *m_startNode;
    MapNode *m_endNode;
};

2.初始化地图

我们需要将地图信息放入到m_map数组中，其中0表示空地，1表示障碍物，-1表示起点或终点。

Astar::Astar(int width, int height, int *map) {
    m_mapWidth = width;
    m_mapHeight = height;
    m_map = new int *[m_mapHeight];
    for (int i = 0; i < m_mapHeight; i++) {
        m_map[i] = new int[m_mapWidth];
        for (int j = 0; j < m_mapWidth; j++) {
            m_map[i][j] = map[i * m_mapWidth + j];
            if (m_map[i][j] == -1) {
                m_startNode = new MapNode(j, i);
            } else if (m_map[i][j] == -2) {
                m_endNode = new MapNode(j, i);
            }
        }
    }
}

3.按照算法规则实现C++代码

我们需要按照A*算法的规则，实现C++代码，计算节点之间的代价，以及搜索路径。

int Astar::findPath(MapNode start, MapNode end, bool isIgnoreCorner) {
    m_openList.push_back(new MapNode(start.x, start.y));

    while (!m_openList.empty()) {
        auto currNode = getLeastFNode();
        m_closeList.push_back(currNode);

        if (currNode->x == end.x && currNode->y == end.y) {
            printMap(currNode);
            return 1;
        }

        auto surNodes = getSurroundNodes(currNode, isIgnoreCorner);
        for (auto &node : surNodes) {
            if (!isCanReach(currNode, node, isIgnoreCorner)) {
                continue;
            }

            if (std::find(m_openList.begin(), m_openList.end(), node) != m_openList.end()) {
                calcG(node, currNode);
            } else {
                calcG(node, currNode);
                calcH(node, &end);
                m_openList.push_back(node);
            }

            node->parent = currNode;
            calcF(node);

            if (std::find(m_openList.begin(), m_openList.end(), &end) != m_openList.end()) {
                printMap(node);
                return 1;
            }
        }
    }

    return -1;
}

四、示例说明

以下是一个简单的示例，用于展示如何使用C++实现A*寻路算法:

int main() {
    // 定义地图大小和地图数据
    int mapWidth = 5;
    int mapHeight = 5;
    int mapData[] = {0, 0, 1, -1, 0,
                     0, 0, 1, 0, 0,
                     1, 1, 1, 1, 0,
                     0, 0, 0, 0, 0,
                     -2, 0, 0, 0, 0};

    // 创建A*对象并进行路径搜索
    Astar *astar = new Astar(mapWidth, mapHeight, mapData);
    MapNode start(0, 0);
    MapNode end(4, 0);
    astar->findPath(start, end, false);

    return 0;
}

在上述示例中，我们创建了一个5x5的地图，地图数据中0表示空地，1表示障碍物，-1表示起点，-2表示终点。然后，我们创建了A*对象，设置好起点和终点，并调用findPath()方法进行路径搜索。