C语言A*搜索算法详解（从零开始实现A*寻路算法）

什么是A*算法？

A*算法是一种启发式搜索算法，它结合了Dijkstra算法的“最短路径优先”思想和贪心算法的“目标导向”策略。其核心公式为：

f(n) = g(n) + h(n)

• g(n)：从起点到当前节点 n 的实际代价（已走过的距离）
• h(n)：从当前节点 n 到终点的预估代价（启发函数，常用曼哈顿距离或欧几里得距离）
• f(n)：节点 n 的总评估代价，值越小越优先探索

实现步骤概览

1. 定义地图结构（二维数组表示障碍物与空地）
2. 创建节点结构体，包含坐标、g/h/f 值、父节点指针等
3. 使用开放列表（Open List）和关闭列表（Closed List）
4. 循环查找 f 值最小的节点，扩展其邻居
5. 直到找到终点或开放列表为空

C语言代码实现

下面是一个完整的、可运行的 C 语言 A* 算法实现。我们使用曼哈顿距离作为启发函数，并假设地图为 10x10 的网格。

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define MAP_WIDTH 10#define MAP_HEIGHT 10#define OBSTACLE 1#define EMPTY 0// 节点结构体typedef struct Node {    int x, y;    int g, h, f;    struct Node* parent;} Node;// 地图数据（0=空地，1=障碍物）int map[MAP_HEIGHT][MAP_WIDTH] = {    {0,0,0,0,0,0,0,0,0,0},    {0,1,1,1,1,0,0,0,0,0},    {0,0,0,0,1,0,0,0,0,0},    {0,0,0,0,1,0,0,0,0,0},    {0,0,0,0,1,0,0,0,0,0},    {0,0,0,0,0,0,0,0,0,0},    {0,0,0,0,0,0,0,0,0,0},    {0,0,0,0,0,0,0,0,0,0},    {0,0,0,0,0,0,0,0,0,0},    {0,0,0,0,0,0,0,0,0,0}};// 曼哈顿距离作为启发函数int heuristic(int x1, int y1, int x2, int y2) {    return abs(x1 - x2) + abs(y1 - y2);}// 创建新节点Node* createNode(int x, int y, int g, int h, Node* parent) {    Node* node = (Node*)malloc(sizeof(Node));    node->x = x;    node->y = y;    node->g = g;    node->h = h;    node->f = g + h;    node->parent = parent;    return node;}// 在列表中查找节点（简化版，实际可用哈希表优化）bool inList(Node** list, int size, int x, int y) {    for (int i = 0; i < size; i++) {        if (list[i] && list[i]->x == x && list[i]->y == y)            return true;    }    return false;}// 主A*搜索函数Node* aStar(int startX, int startY, int endX, int endY) {    Node* openList[100];  // 开放列表（最大100个节点）    Node* closedList[100]; // 关闭列表    int openCount = 0, closedCount = 0;        // 起始节点    Node* start = createNode(startX, startY, 0,                heuristic(startX, startY, endX, endY), NULL);    openList[openCount++] = start;        while (openCount > 0) {        // 找出f值最小的节点        int minIndex = 0;        for (int i = 1; i < openCount; i++) {            if (openList[i]->f < openList[minIndex]->f)                minIndex = i;        }                Node* current = openList[minIndex];                // 移动到关闭列表        closedList[closedCount++] = current;        // 从开放列表移除        for (int i = minIndex; i < openCount - 1; i++)            openList[i] = openList[i + 1];        openCount--;                // 到达终点        if (current->x == endX && current->y == endY) {            return current; // 返回路径终点        }                // 检查四个方向的邻居（上下左右）        int dx[4] = {0, 0, -1, 1};        int dy[4] = {-1, 1, 0, 0};                for (int i = 0; i < 4; i++) {            int nx = current->x + dx[i];            int ny = current->y + dy[i];                        // 边界检查和障碍物检查            if (nx < 0 || nx >= MAP_WIDTH || ny < 0 || ny >= MAP_HEIGHT ||                map[ny][nx] == OBSTACLE || inList(closedList, closedCount, nx, ny))                continue;                        int tentativeG = current->g + 1; // 假设每步代价为1            bool isNew = !inList(openList, openCount, nx, ny);                        if (isNew || tentativeG < getGFromOpen(openList, openCount, nx, ny)) {                Node* neighbor = createNode(nx, ny, tentativeG,                               heuristic(nx, ny, endX, endY), current);                if (isNew) {                    openList[openCount++] = neighbor;                } else {                    // 更新已有节点（简化处理，实际需替换）                    free(neighbor);                }            }        }    }        return NULL; // 未找到路径}// 辅助函数：获取开放列表中某坐标的g值（简化版）int getGFromOpen(Node** list, int size, int x, int y) {    for (int i = 0; i < size; i++) {        if (list[i]->x == x && list[i]->y == y)            return list[i]->g;    }    return 9999;}// 打印路径void printPath(Node* end) {    if (!end) {        printf("未找到路径！\n");        return;    }        // 回溯路径    Node* path[100];    int pathLen = 0;    Node* cur = end;    while (cur) {        path[pathLen++] = cur;        cur = cur->parent;    }        printf("找到路径（从起点到终点）：\n");    for (int i = pathLen - 1; i >= 0; i--) {        printf("(%d, %d) ", path[i]->x, path[i]->y);    }    printf("\n");}int main() {    Node* result = aStar(0, 0, 9, 9);    printPath(result);    return 0;}

注意：上述代码为教学简化版，实际项目中建议使用优先队列（如二叉堆）优化开放列表的查找效率，并完善内存管理。

常见问题与优化

初学者常遇到的问题包括：

• 路径不最优：确保启发函数 h(n) 不高估真实代价（即满足“可采纳性”）
• 性能差：使用最小堆（优先队列）代替线性搜索开放列表
• 内存泄漏：记得释放动态分配的 Node 内存

总结

通过本教程，你已经掌握了如何用C语言实现A*路径搜索算法。A*算法因其高效性和可靠性，广泛应用于各类需要智能寻路的场景。希望你能在此基础上继续优化，比如支持对角线移动、不同地形代价、动态障碍物等高级功能。

关键词回顾：C语言A*算法、A*路径搜索、C语言实现A星算法、A*寻路算法教程