a星算法c语言实例

以下是一个 A* 算法的 C 语言实现示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ROW 10
#define COL 10

typedef struct {
    int x;
    int y;
} Point;

// 地图，0 表示可以通过，1 表示障碍物
int map[ROW][COL] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

// 起点和终点
Point start = {0, 0};
Point end = {9, 9};

// 计算两点间的曼哈顿距离
int manhattan_distance(Point a, Point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

// 检查点是否在地图内且可以通过
bool is_valid_point(Point p) {
    if (p.x < 0 || p.x >= ROW || p.y < 0 || p.y >= COL)
        return false;
    return map[p.x][p.y] == 0;
}

// 判断点是否在列表中
bool is_point_in_list(Point p, Point list[], int len) {
    for (int i = 0; i < len; i++) {
        if (list[i].x == p.x && list[i].y == p.y)
            return true;
    }
    return false;
}

// A* 算法
bool a_star() {
    // 开启列表和关闭列表
    Point open_list[ROW * COL];
    int open_list_len = 0;
    Point close_list[ROW * COL];
    int close_list_len = 0;

    // 当前节点和下一个节点
    Point current = start;
    Point next;

    // 将起点加入开启列表
    open_list[open_list_len++] = current;

    while (open_list_len > 0) {
        // 从开启列表中找到曼哈顿距离最小的节点
        int min_index = 0;
        for (int i = 1; i < open_list_len; i++) {
            if (manhattan_distance(open_list[i], end) < manhattan_distance(open_list[min_index], end))
                min_index = i;
        }
        current = open_list[min_index];

        // 如果当前节点是终点，则找到路径
        if (current.x == end.x && current.y == end.y)
            return true;

        // 将当前节点从开启列表中移除，并加入关闭列表
        for (int i = min_index; i < open_list_len - 1; i++)
            open_list[i] = open_list[i + 1];
        open_list_len--;
        close_list[close_list_len++] = current;

        // 扩展当前节点的邻居节点
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                next.x = current.x + i;
                next.y = current.y + j;

                // 忽略自身和对角线方向的邻居节点
                if ((i == 0 && j == 0) || (i != 0 && j != 0))
                    continue;

                // 检查邻居节点是否在地图内且可以通过
                if (!is_valid_point(next))
                    continue;

                // 检查邻居节点是否在关闭列表中
                if (is_point_in_list(next, close_list, close_list_len))
                    continue;

                // 计算邻居节点的 f 值
                next.f = current.g + 1 + manhattan_distance(next, end);

                // 检查邻居节点是否已经在开启列表中
                int index = -1;
                for (int k = 0; k < open_list_len; k++) {
                    if (open_list[k].x == next.x && open_list[k].y == next.y) {
                        index = k;
                        break;
                    }
                }

                // 如果邻居节点不在开启列表中，则将其加入开启列表
                if (index == -1) {
                    next.g = current.g + 1;
                    open_list[open_list_len++] = next;
                }
                // 否则，如果邻居节点的 f 值小于开启列表中对应节点的 f 值，则更新开启列表中对应节点的 f 值为邻居节点的 f 值，并更新其父节点为当前节点
                else if (next.f < open_list[index].f) {
                    open_list[index].f = next.f;
                    open_list[index].g = current.g + 1;
                }
            }
        }
    }

    // 没有找到路径
    return false;
}

int main() {
    if (a_star()) {
        printf("找到路径！\n");
    } else {
        printf("没有找到路径！\n");
    }
    return 0;
}

在本例中，我们使用一个二维数组来表示地图，0 表示可以通过，1 表示障碍物。起点和终点分别用坐标表示。在 `a_star()` 函数中，我们使用开启列表和关闭列表来实现 A* 算法。开启列表中存储的是待扩展的节点，关闭列表中存储的是已经扩展过的节点。每次从开启列表中找到曼哈顿距离最小的节点进行扩展，直到找到终点或者开启列表为空。在扩展节点时，我们先检查其邻居节点是否在地图内且可以通过，然后判断其是否在关闭列表中，最后计算其 f 值（g 值加上曼哈顿距离），并加入开启列表或者更新开启列表中已有节点的 f 值。