自动生成迷宫问题c语言

### C语言实现自动生成迷宫算法示例

为了创建一个随机生成的迷宫，在C语言中可以采用多种方法。一种常见的策略是利用Prim算法，该算法能有效地构建具有复杂结构且无环路的迷宫[^3]。

下面展示了一个简化版本的Prim算法用于生成迷宫的例子：

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

#define WIDTH 21    /* 宽度 */
#define HEIGHT 11   /* 高度 */

char maze[HEIGHT][WIDTH];     // 迷宫数组初始化

void init_maze() {
    int i, j;
    for (i = 0; i < HEIGHT; ++i) {        // 初始化边界墙
        for (j = 0; j < WIDTH; ++j) {
            if ((i % 2 == 0 && j % 2 == 0) || i == 0 || i == HEIGHT - 1 || j == 0 || j == WIDTH - 1)
                maze[i][j] = '#';          // 墙壁标记为#
            else
                maze[i][j] = ' ';           // 走廊为空格
        }
    }

}

typedef struct _cell Cell;

struct _cell {
    int x, y;
};

Cell queue[(WIDTH * HEIGHT)];      // 存储待处理单元格队列
int front = 0, rear = 0;

// 将新位置加入到队列并打乱顺序以增加随机性
void enqueue(int x, int y) {
    static int first_time = 1;
    if (first_time) srand(time(NULL)), first_time = 0;
    
    int pos = rand() % (rear - front + 1);
    queue[pos].x ^= queue[front].x ^= queue[pos].x ^= queue[front].x,
    queue[pos].y ^= queue[front].y ^= queue[pos].y ^= queue[front].y;
    queue[++rear] = (Cell){x, y};
}

// 移除当前正在访问的位置
void dequeue(void) {
    ++front;
}

// 判断给定坐标是否有效（即不是墙壁）
int valid_pos(int x, int y) {
    return !(maze[y][x] != ' ');
}

// 获取指定方向上的邻居节点
void get_neighbor(Cell c, char dir, Cell* nbor) {
    switch(dir){
        case 'N': (*nbor).x=c.x;(*nbor).y=c.y-2;break;
        case 'S': (*nbor).x=c.x;(*nbor).y=c.y+2;break;
        case 'W': (*nbor).x=c.x-2;(*nbor).y=c.y;break;
        case 'E': (*nbor).x=c.x+2;(*nbor).y=c.y;break;
    }
}

// 执行Prim算法的核心逻辑
void prim_algorithm() {
    Cell start = {(rand()%(WIDTH/2))*2,(rand()%(HEIGHT/2))*2};       // 设置起点
    
    while(front<=rear){
        Cell current = queue[front];
        
        // 访问四个可能的方向之一
        const char dirs[]="NESW";
        size_t num_dirs=strlen(dirs);

        for(size_t d=0;d<num_dirs;++d){
            Cell neighbor;
            get_neighbor(current,dirs[d],&neighbor);
            
            if(valid_pos(neighbor.x,neighbor.y)){
                maze[current.y+(current.y<neighbor.y?1:-1)][current.x+(current.x<neighbor.x?1:-1)]=' ';
                enqueue(neighbor.x,neighbor.y);
            }
        }
        dequeue();
    }
}

这段代码展示了如何通过Prim算法来生成一个简单的二维字符阵列表达的迷宫。此过程始于选定的一个起始点，并逐步扩展至整个网格空间直到所有可达区域都被探索完毕为止。值得注意的是，这里使用了`enqueue()`函数中的随机化操作使得每次运行都能得到不同的结果，从而实现了真正意义上的“随机”。