自动生成迷宫与迷宫寻路c语言

### C语言实现迷宫生成和寻路算法

#### 迷宫生成算法

迷宫生成可以采用深度优先搜索（DFS），这是一种递归方法，能够创建复杂的迷宫结构。通过随机访问相邻未访问过的格子来构建迷宫。

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

#define WIDTH 21
#define HEIGHT 21

char maze[HEIGHT][WIDTH];

void init_maze() {
    for (int y = 0; y < HEIGHT; ++y) {
        for (int x = 0; x < WIDTH; ++x) {
            if ((x % 2 == 0) || (y % 2 == 0)) {
                maze[y][x] = '#'; // Wall
            } else {
                maze[y][x] = ' '; // Space
            }
        }
    }
}

// Directions: up, down, left, right
const int dx[] = {0, 0, -2, 2};
const int dy[] = {-2, 2, 0, 0};

void carve_passages_from(int cx, int cy) {
    shuffle(dx, sizeof(dx)/sizeof(dx[0]));
    for (int i = 0; i < 4; ++i) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx] == '#') {
            maze[(cy+ny)/2][(cx+nx)/2] = ' ';
            maze[ny][nx] = ' ';
            carve_passages_from(nx, ny);
        }
    }
}

void shuffle(int* array, size_t n) {
    srand(time(NULL));
    while (--n > 0) {
        size_t k = rand()%(n+1);
        int tmp = array[k];
        array[k] = array[n];
        array[n] = tmp;
    }
}

void generate_maze() {
    init_maze();
    carve_passages_from(1, 1);
}

这段代码定义了一个简单的奇数宽度和高度的网格作为基础框架，并利用深度优先搜索从起始位置`(1,1)`开始挖掘通道直到无法继续为止[^1]。

#### 寻路算法

对于迷宫中的路径查找，同样可应用深度优先搜索来进行探索。这里展示如何基于给定起点找到终点的方法：

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

Point start = {1, 1};     // Start point
Point end = {(WIDTH-2), (HEIGHT-2)}; // End point

int find_path(Point current) {
    if (!(current.x >= 0 && current.x < WIDTH &&
          current.y >= 0 && current.y < HEIGHT))
        return 0;

    if (maze[current.y][current.x] != ' ')
        return 0;

    if (current.x == end.x && current.y == end.y)
        return 1;

    maze[current.y][current.x] = '.'; // Mark as visited path
    
    const int directions[][2] = {{0,-1},{0,1},{-1,0},{1,0}};
    
    for (size_t d = 0; d < 4; ++d){
        Point next = {.x=current.x+directions[d][0], .y=current.y+directions[d][1]};
        
        if(find_path(next)){
            printf("(%d,%d)\n",next.x,next.y);
            return 1;
        }
    }

    maze[current.y][current.x] = ' '; // Unmark on backtrack
    return 0;
}

int main(){
    generate_maze();

    printf("Maze:\n");
    for (int y=0; y<HEIGHT; ++y){
        for (int x=0; x<WIDTH; ++x){
            putchar(maze[y][x]);
        }
        puts("");
    }

    printf("\nPath found from (%d,%d):\n",start.x,start.y);
    find_path(start);

    return 0;
}

此程序首先打印出生成好的迷宫布局，接着尝试从指定起点到终点寻找一条可行路线并输出经过的位置坐标[^3]。