前言

在游戏开发、机器人导航、地图导航等领域，寻路算法扮演着至关重要的角色。提到寻路，大家最熟悉的可能是 DFS（深度优先搜索）和 BFS（广度优先搜索）。但是，它们都有一个致命的缺点：盲目搜索。它们会把周围的节点全部遍历一遍，效率极低。
为了高效地找到最优路径，A*（A-Star）算法应运而生。它结合了 BFS 的完备性和贪心算法的启发性，是当前最流行的寻路算法之一。

今天，我们就用 C 语言，手把手带你实现一个 A* 算法，并用一个 5x5 的迷宫进行测试。

一、 A* 算法核心思想

A* 算法之所以聪明，是因为它引入了一个评估函数：

F(n)=G(n)+H(n)

• G(n)：表示从起点到当前节点 nn 的实际代价（比如移动了多少步）。

• H(n)：表示从当前节点 nn 到终点的预估代价（启发式函数，比如曼哈顿距离）。

• F(n)：表示经过节点 nn 的总代价预估。

算法流程：

1. 把起点加入开启列表（Open List）。

2. 只要开启列表不为空，就从中找出 FF 值最小的节点，作为当前节点。

3. 把当前节点从开启列表移到关闭列表（Closed List）。

4. 如果当前节点就是终点，顺着父节点回溯，找到路径，算法结束。

5. 否则，检查当前节点周围所有可走的邻居节点：

   • 如果邻居在关闭列表中，或者不可走（比如撞墙），跳过。

   • 如果邻居不在开启列表中，计算它的 F,G,HF,G,H，把它的父节点设为当前节点，并加入开启列表。

   • 如果邻居已经在开启列表中，比较新的 GG 值是否更小。如果是，更新它的 G,FG,F 值和父节点。

6. 循环结束仍没找到终点，说明无路可走。

二、 地图与数据结构定义

我们用二维数组 grid 表示地图。0 代表平地，1 代表障碍物。

#define ROWS 5
#define COLS 5

// 定义地图，1 为障碍，0 为可通行
int grid[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

为了方便管理节点状态，我们定义一个 Node 结构体：

typedef struct {
    int r, c;             // 当前节点的行列坐标
    int g, h;             // G值和H值
    int parent_r, parent_c; // 父节点坐标，用于回溯路径
    bool in_open;         // 是否在开启列表中
} Node;

三、 核心代码实现

3.1 启发式函数 (计算 H 值)

这里我们使用曼哈顿距离（Manhattan Distance），即两点在水平和垂直方向上的距离之和。

// 计算曼哈顿距离
int heuristic(int r1, int c1, int r2, int c2) {
    return abs(r1 - r2) + abs(c1 - c2);
}

3.2 A* 算法主函数

void astar(int sr, int sc, int er, int ec) {
    Node nodes[ROWS][COLS];
    bool closed[ROWS][COLS] = {false}; // 关闭列表标记

    // 1. 初始化节点信息
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            nodes[i][j].r = i;
            nodes[i][j].c = j;
            nodes[i][j].g = INT_MAX; // 初始 G 值设为无穷大
            nodes[i][j].h = heuristic(i, j, er, ec);
            nodes[i][j].parent_r = -1;
            nodes[i][j].parent_c = -1;
            nodes[i][j].in_open = false;
        }
    }

    // 起点初始化
    nodes[sr][sc].g = 0;
    nodes[sr][sc].in_open = true;

    // 上下左右四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (1) {
        // 2. 在开启列表中寻找 F 值最小的节点
        int minF = INT_MAX;
        int cr = -1, cc = -1;

        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (nodes[i][j].in_open && !closed[i][j]) {
                    int f = nodes[i][j].g + nodes[i][j].h;
                    if (f < minF) {
                        minF = f;
                        cr = i;
                        cc = j;
                    }
                }
            }
        }

        // 如果找不到可扩展的节点，说明无路可走
        if (cr == -1) {
            printf("无路径\n");
            return;
        }

        // 3. 判断是否到达终点
        if (cr == er && cc == ec) {
            // 回溯路径
            int path_r[100], path_c[100];
            int len = 0;
            int r = er, c = ec;

            while (r != -1) {
                path_r[len] = r;
                path_c[len] = c;
                len++;

                int pr = nodes[r][c].parent_r;
                int pc = nodes[r][c].parent_c;
                r = pr;
                c = pc;
            }

            // 因为是从终点回溯到起点，所以要倒序输出
            printf("A* 路径：");
            for (int i = len - 1; i >= 0; i--) {
                printf("(%d,%d) ", path_r[i], path_c[i]);
            }
            printf("\n路径长度：%d\n", len);
            return;
        }

        // 4. 将当前节点移入关闭列表
        closed[cr][cc] = true;
        nodes[cr][cc].in_open = false;

        // 5. 遍历四个相邻节点
        for (int d = 0; d < 4; d++) {
            int nr = cr + dirs[d][0];
            int nc = cc + dirs[d][1];

            // 边界判断
            if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
            // 障碍物或已在关闭列表中
            if (grid[nr][nc] == 1 || closed[nr][nc]) continue;

            // 计算从起点到邻居的新 G 值 (每次移动代价为1)
            int ng = nodes[cr][cc].g + 1;

            // 如果发现更优路径，则更新
            if (ng < nodes[nr][nc].g) {
                nodes[nr][nc].g = ng;
                nodes[nr][nc].parent_r = cr;
                nodes[nr][nc].parent_c = cc;
                nodes[nr][nc].in_open = true;
            }
        }
    }
}

3.3 主函数入口

int main(void) {
    // 从 (0,0) 寻路到 (4,4)
    astar(0, 0, 4, 4);
    return 0;
}

四、 运行结果

编译并运行上述代码，控制台将输出如下结果：

A* 路径：(0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (2,4) (3,4) (4,4) 
路径长度：9

路径解析：

• 起点在左上角 (0,0)，终点在右下角 (4,4)。

• 由于中间有大量障碍物 1，A* 算法巧妙地绕过了障碍，走出了一条最短路径。

• 总步数为 9 步（包含起点和终点）。

五、 代码优化与思考

上述代码非常适合初学者理解 A* 算法的原理，但在实际工程（如游戏引擎）应用中，还需要做以下优化：

1. 开启列表的优化：我们在寻找最小 FF 值时，使用的是双重 for 循环遍历整个地图（时间复杂度 O(N2)O(N2)）。在实际开发中，通常使用优先队列（Priority Queue）或者二叉堆（Binary Heap）来维护开启列表，这样每次取最小值的时间复杂度降为 O(1)O(1) 或 O(log⁡N)O(logN)。

2. 启发式函数的选择：除了曼哈顿距离，如果允许斜向移动，可以使用对角线距离或欧几里得距离。

3. 地图数据的优化：如果地图非常大（如 10000x10000），二维数组可能会占用过多内存，可以考虑使用稀疏矩阵或图结构来存储。

结语

A* 算法是寻路领域的一把利剑。理解了 F=G+HF=G+H 这个核心公式，你就掌握了 A* 的灵魂。希望这篇 C 语言实战代码能帮你打通寻路算法的任督二脉。