C语言bfs算法自动走贪吃蛇,智能寻路贪吃蛇系列之 初级BFS寻路算法

BFS（广度优先搜索）算法是一种常用的图搜索算法，可以用于解决很多问题，包括寻找迷宫路径、自动走迷宫等问题。在贪吃蛇游戏中，BFS算法可以用来寻找蛇头到达食物的最短路径。

下面是一个使用C语言实现的初级BFS寻路算法：

首先，我们需要定义一个节点结构体，用来表示每个节点的位置信息和访问状态：

struct Node {
    int x, y; // 节点的横纵坐标
    int step; // 到达该节点的步数
    bool visited; // 节点是否已访问
};

然后，我们需要实现一个队列结构体，用来存储待访问的节点：

#define MAXSIZE 1000

struct Queue {
    int front, rear;
    Node data[MAXSIZE];
};

void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue q) {
    return q.front == q.rear;
}

bool isFull(Queue q) {
    return q.rear == MAXSIZE;
}

bool enqueue(Queue *q, Node node) {
    if (isFull(*q)) {
        return false;
    }
    q->data[q->rear++] = node;
    return true;
}

bool dequeue(Queue *q, Node *node) {
    if (isEmpty(*q)) {
        return false;
    }
    *node = q->data[q->front++];
    return true;
}

接下来，我们可以根据当前蛇头和食物的位置，使用BFS算法寻找最短路径：

int bfs(int map[][MAXSIZE], int n, int m, int sx, int sy, int tx, int ty) {
    int dx[] = {-1, 0, 1, 0}; // 上、右、下、左四个方向
    int dy[] = {0, 1, 0, -1};

    Queue q;
    initQueue(&q);

    Node start = {sx, sy, 0, true};
    enqueue(&q, start);

    while (!isEmpty(q)) {
        Node cur;
        dequeue(&q, &cur);

        if (cur.x == tx && cur.y == ty) { // 找到了终点
            return cur.step;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !cur.visited && map[nx][ny] != 1) { // 如果该点合法且未访问过且不是障碍物
                Node next = {nx, ny, cur.step + 1, true};
                enqueue(&q, next);
            }
        }
    }

    return -1; // 没有找到路径
}

在游戏中，我们可以使用该算法来寻找蛇头到达食物的最短路径，然后让蛇头朝着路径的第一个方向移动，就能实现自动寻路了。