C语言实现A星算法实例

对于一个A星算法实例，我们需要先定义节点结构体和地图数组。节点结构体包括节点坐标、父节点指针、G值和H值，地图数组包括每个点的障碍物状态和G值。

定义节点结构体如下：

typedef struct node {
    int x; // x坐标
    int y; // y坐标
    int G; // 从起点到该节点的代价
    int H; // 从该节点到终点的估计代价
    struct node *parent; // 父节点指针
} Node;

定义地图数组如下：

int map[ROW][COL] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 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, 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表示可通过，1表示障碍物。

接下来定义A星算法函数，包括估价函数、查找最小F值节点函数、计算G值函数、计算H值函数、判断节点是否在开启列表或关闭列表中函数、更新节点函数、添加节点到开启列表函数、查找路径函数。

估价函数：

int estimate(Node *node, Node *end) {
    return abs(node->x - end->x) + abs(node->y - end->y);
}

查找最小F值节点函数：

Node* find_min_f_node(List *list) {
    Node *min_f_node = list->head;
    Node *p = list->head->next;
    while (p != NULL) {
        if (p->G + p->H < min_f_node->G + min_f_node->H) {
            min_f_node = p;
        }
        p = p->next;
    }
    return min_f_node;
}

计算G值函数：

int calculate_g(Node *node, Node *start) {
    int g = 0;
    Node *p = node;
    while (p != start) {
        g += abs(p->x - p->parent->x) + abs(p->y - p->parent->y);
        p = p->parent;
    }
    return g;
}

计算H值函数：

int calculate_h(Node *node, Node *end) {
    return abs(node->x - end->x) + abs(node->y - end->y);
}

判断节点是否在开启列表或关闭列表中函数：

int is_in_list(Node *node, List *list) {
    Node *p = list->head;
    while (p != NULL) {
        if (p->x == node->x && p->y == node->y) {
            return 1;
        }
        p = p->next;
    }
    return 0;
}

更新节点函数：

void update_node(Node *node, Node *parent, int g) {
    node->parent = parent;
    node->G = g;
}

添加节点到开启列表函数：

void add_to_open_list(Node *node, Node *end, List *open_list) {
    Node *p = open_list->head;
    while (p->next != NULL && p->next->G + p->next->H < node->G + node->H) {
        p = p->next;
    }
    node->parent = p;
    node->G = p->G + abs(node->x - p->x) + abs(node->y - p->y);
    node->H = estimate(node, end);
    node->next = p->next;
    p->next = node;
}

查找路径函数：

void find_path(Node *start, Node *end) {
    List *open_list = create_list();
    List *close_list = create_list();
    add_to_list(start, open_list);
    while (!is_empty(open_list)) {
        Node *current_node = find_min_f_node(open_list);
        if (current_node->x == end->x && current_node->y == end->y) {
            break;
        }
        remove_from_list(current_node, open_list);
        add_to_list(current_node, close_list);
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int x = current_node->x + i;
                int y = current_node->y + j;
                if (x >= 0 && x < ROW && y >= 0 && y < COL && map[x][y] == 0) {
                    Node *node = create_node(x, y);
                    if (!is_in_list(node, close_list)) {
                        int g = calculate_g(node, start);
                        if (!is_in_list(node, open_list)) {
                            update_node(node, current_node, g);
                            add_to_open_list(node, end, open_list);
                        } else if (g < node->G) {
                            update_node(node, current_node, g);
                        }
                    }
                }
            }
        }
    }
    if (current_node->x != end->x || current_node->y != end->y) {
        printf("No path found!\n");
    } else {
        while (current_node != start) {
            printf("(%d, %d) -> ", current_node->x, current_node->y);
            current_node = current_node->parent;
        }
        printf("(%d, %d)\n", start->x, start->y);
    }
}

完整代码如下：