a星算法走迷宫c语言

以下是使用A*算法走迷宫的C语言代码示例：

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

#define ROW 10
#define COL 10

typedef struct {
    int x, y; // 坐标
    int f, g, h; // f = g + h
} Node;

int map[ROW][COL] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 0, 1, 1, 1, 0, 1, 0},
    {0, 1, 1, 0, 1, 1, 1, 0, 1, 0},
    {0, 1, 1, 1, 1, 0, 0, 1, 1, 0},
    {0, 1, 0, 1, 1, 0, 0, 1, 1, 0},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 1, 0, 1, 0, 1, 0, 1, 1, 0},
    {0, 1, 0, 0, 0, 1, 0, 0, 1, 0},
    {0, 0, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

bool is_valid(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) {
        return false;
    }
    if (map[x][y] == 0) {
        return false;
    }
    return true;
}

bool is_destination(int x, int y, Node dest) {
    if (x == dest.x && y == dest.y) {
        return true;
    }
    return false;
}

int get_distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void print_path(Node path[], int len) {
    for (int i = 0; i < len; i++) {
        printf("(%d, %d) ", path[i].x, path[i].y);
    }
    printf("\n");
}

void a_star(Node start, Node dest) {
    Node open_list[ROW * COL], close_list[ROW * COL];
    int open_len = 0, close_len = 0;
    open_list[open_len++] = start;

    while (open_len > 0) {
        // 从open_list中找到f值最小的节点
        int min_f = open_list[0].f, min_index = 0;
        for (int i = 1; i < open_len; i++) {
            if (open_list[i].f < min_f) {
                min_f = open_list[i].f;
                min_index = i;
            }
        }
        Node current = open_list[min_index];

        // 如果当前节点是目标节点，输出路径并返回
        if (is_destination(current.x, current.y, dest)) {
            Node path[ROW * COL];
            int path_len = 0;
            while (current.x != start.x || current.y != start.y) {
                path[path_len++] = current;
                current = close_list[current.h];
            }
            path[path_len++] = start;
            print_path(path, path_len);
            return;
        }

        // 将当前节点从open_list中删除，并加入close_list
        open_list[min_index] = open_list[--open_len];
        close_list[close_len++] = current;

        // 遍历当前节点的邻居节点
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int x = current.x + i, y = current.y + j;
                if (!is_valid(x, y)) {
                    continue;
                }
                Node neighbor = {x, y, 0, 0, 0};
                neighbor.g = current.g + 1;
                neighbor.h = get_distance(x, y, dest.x, dest.y);
                neighbor.f = neighbor.g + neighbor.h;

                // 如果邻居节点已经在close_list中，跳过
                bool in_close_list = false;
                for (int k = 0; k < close_len; k++) {
                    if (close_list[k].x == neighbor.x && close_list[k].y == neighbor.y) {
                        in_close_list = true;
                        break;
                    }
                }
                if (in_close_list) {
                    continue;
                }

                // 如果邻居节点不在open_list中，加入open_list
                bool in_open_list = false;
                for (int k = 0; k < open_len; k++) {
                    if (open_list[k].x == neighbor.x && open_list[k].y == neighbor.y) {
                        in_open_list = true;
                        if (neighbor.g < open_list[k].g) {
                            open_list[k].g = neighbor.g;
                            open_list[k].f = neighbor.f;
                            close_list[neighbor.h] = current;
                        }
                        break;
                    }
                }
                if (!in_open_list) {
                    open_list[open_len++] = neighbor;
                    close_list[neighbor.h] = current;
                }
            }
        }
    }

    printf("No path found.\n");
}

int main() {
    Node start = {1, 1, 0, 0, 0};
    Node dest = {8, 8, 0, 0, 0};
    a_star(start, dest);
    return 0;
}