数据结构结课设计——使用随机深度优先搜索完成随机迷宫的生成

 博主在本学期的c语言数据结构课程选择了随机迷宫生成作为结课设计，并运用随机深度优先，下面是我的代码设计思路与代码，

  设计思路上迷宫的随机生成问题可以分成两个大步骤来进行：

第一步 迷宫的随机初始化：

通过二维数组来对迷宫进行表示，将迷宫全部设置为1，再通过随机函数将迷宫内部随机生成，再将迷宫内部的左上角和右下角初始化为0来保证起点与出口是通路。这样就完成了迷宫的一个初始化，当然这样随机生成的迷宫的内部是完全不能保证迷宫内部的连通性的，无法作为迷宫来正常游玩，所以我们还需要第二步来保证迷宫内部的连通性。

第二步：确保迷宫的连通性：

对于迷宫内部连通性的处理方法是使用随机深度优先搜索，利用栈的数据结构来进行迷宫行走和搜索，理论是在保证外墙无法修改破坏的情况下，随机方向进行迷宫行走，并将行走轨迹入栈，如果四边均为墙壁或者已走过路径，则随机将墙壁打通并标记为已走过路径，以此类推可能生成一个可正常游玩的随机迷宫。

代码实现：

首先创建结构体并创建四个偏移量用来在后面实现节点对四个方向的随机操作：

typedef struct

{

    int size;//迷宫大小

    int maze[100][100];

}maze;



typedef struct

{

    int x;//x坐标

    int y;//y坐标

    

}Node;

// 四个方向的偏移量，分别对应上、下、左、右

int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

/*{-1, 0} 表示向上移动（y坐标减1）

{1, 0} 表示向下移动（y坐标加1）

{0, -1} 表示向左移动（x坐标减1）

{0, 1} 表示向右移动（x坐标加1）*/

 深度优先搜索函数，对迷宫上下左右四个方向的可行走通路进行随机的探索，如果遇到死胡同墙壁就进行随机破墙来确保迷宫内部的连通性，防止出现无法走出迷宫的情况：

void DFS(maze &m, int startX, int startY)

{

    stack<Node> s;//声明了一个模板栈s

    Node start = {startX, startY};

    s.push(start);//将起点入栈

    m.maze[startX][startY] = 2;  // 标记为已访问



    while (!s.empty()) {//s.empty()检查栈是否为空

        Node cur = s.top();//获取栈顶元素赋值给cur

        s.pop();//从栈 s 中移除栈顶元素



        if (cur.x == m.size - 2 && cur.y == m.size - 2) {

            // 到达终点，已经找到通路，直接返回

            return ;

        }



        // 随机打乱方向顺序，实现一定随机性

        random_shuffle(dir, dir + 4);//随机洗牌函数，用于将数组中的元素随机重新排序



        for (int i = 0; i < 4; ++i) {

            int newX = cur.x + dir[i][0];

            int newY = cur.y + dir[i][1];

            if (newX >= 1 && newX < m.size - 1 && newY >= 1 && newY < m.size - 1 && (m.maze[newX][newY] == 0||m.maze[newX][newY] == 2)) {

                // 如果新位置在迷宫内部且是通路（值为0）或者访问过（之前标记为2）

                Node next = {newX, newY};

                s.push(next);

                m.maze[newX][newY] = 2;  // 标记为已访问



            }

          

              



        }

      

        for (int i = 0; i < 4; ++i)

        {

            int newX = cur.x + dir[i][0];

            int newY = cur.y + dir[i][1];

            if (newX >= 1 && newX < m.size - 1 && newY >= 1 && newY < m.size - 1 && m.maze[newX][newY] ==1)

            {

                // 如果新位置在迷宫内部且是墙或者为已探索过路径（值为1）

                int tempX = newX + dir[i][0];

                int tempY = newY + dir[i][1];

                if (tempX >= 1 && tempX < m.size - 1 && tempY >= 1 && tempY < m.size - 1 && m.maze[tempX][tempY] == 1)

                {

                    // 如果新位置的相邻位置也是墙，则打通一面墙

                    m.maze[newX][newY] = 0;

                    Node next = {newX, newY};

                    s.push(next);

                }

            }

            else if (newX >= 1 && newX < m.size - 1 && newY >= 1 && newY < m.size - 1 && (m.maze[newX][newY] == 0||m.maze[newX][newY] == 2))

            {

                // 如果新位置在迷宫内部且是通路（值为0）或者访问过（值为2）

                Node next = {newX, newY};

                s.push(next);

                m.maze[newX][newY] = 2; // 标记为已访问

            }

        }

    }

}

主函数部分，利用伪随机数函数对迷宫进行初始化：

int main()

{

srand((unsigned int)time(NULL)); //以时间来设置伪随机函数的种子数

    maze m;

    m.size = 13;

   

    for(int i = 0; i < m.size; i++)//迷宫初始化（全为1）

    {

        for(int j = 0; j < m.size; j++)

        {

            m.maze[i][j] = 1;

        }

    }



    for(int i = 1; i < m.size - 1; i++)//随机打通迷宫内部

    {

        for(int j = 1; j < m.size - 1; j++)

        {

            if(rand() % 2 == 0)

                m.maze[i][j] = 0;

            else m.maze[i][j] = 1;

        }

    }

    

m.maze[1][1]=0;

m.maze[m.size-2][m.size-2]=0;//保证迷宫的起点与出口为通路

m.maze[1][2]=0;

m.maze[2][1]=0;

m.maze[m.size-3][m.size-2]=0;

m.maze[m.size-2][m.size-3]=0;//保证起点和出口右边和下边为通路，防止出现随机数导致出口或起点堵死

    

     

    // 调用深度优先搜索函数，从 (1, 1) 开始确保有到右下角的通路

    DFS(m, 1, 1);



for(int i=0; i<m.size; i++)//打印迷宫

{

for(int j=0; j<m.size; j++)

{

   printf("%d ",m.maze[i][j]);

   if(j==m.size-1)

{

printf("\n");

}

}

}

    return 0;

}

运行结果：

其中1是墙壁，2是已搜索过的通路或者被打通后再探索的墙壁 。

不足部分：

代码中打通墙壁的规则是基于当前格子和要探索的相邻可通行格子之间进行判断和操作的。然而，这种简单规则可能无法生成一些更复杂、更具趣味性的迷宫结构。

例如，对于一些需要生成含有 “岔路”“环岛” 等特殊结构的迷宫时，仅依靠当前相邻格子的简单打通方式可能无法实现，限制了迷宫生成的丰富度和多样性，生成的迷宫可能大多都是相对比较规整、简单的结构，缺乏复杂多变的路径形态。

实际上这段代码还存在一定逻辑错误，

尽管代码的初衷是通过深度优先搜索来生成一个不含有回路的连通迷宫，但在一些边界情况或者特定随机种子下，可能会出现生成的迷宫并非完全连通的问题。

比如，在迷宫规模较大且随机探索过程不太 “均匀” 时，有可能会出现孤立的区域，这些区域与起点通过正常的通路无法到达，导致迷宫实际上存在多个互不连通的部分，不符合正常迷宫应该整体连通的预期要求。这可能是由于深度优先搜索过程中某些方向的探索不够充分，或者在打通墙壁的操作中没能保证各个区域能有效连接起来。

目前博主还没有解决这些问题，如果博友们有更好的解决办法可以打在评论区哦。

说实话博主自己目前还是一个编程小白，对这次课设不是很有信心，也是第一次尝试写博客，如有谬误还请指出。