最近做课设时,有一个部分需要用到迷宫的生成算法. 在这里介绍一种使用深度优先搜索生成迷宫的算法.

年少有为-李荣浩

目录

  1. 最终的效果
  2. 如何描述迷宫
    1. 迷宫的特点
    2. 思路
  3. 迷宫的生成过程
    1. 1 初始状态
    2. 2 迷宫的生成
    3. 3 设定起点和终点
  4. 核心算法–深度优先

最终的效果

先上几张效果图，图中绿色的表示障碍，灰色表示道路(我的世界既视感).




如何描述迷宫

迷宫其实就是一个复杂的地形图,在这个地形中有基本的障碍和通道,当然也可以有其他元素。

我们这里用最简单的方式描述迷宫——矩阵。迷宫中的地形也只有障碍和通道两种元素。可以用0和1表示这两种元素。

因此我们用一个存储着0和1,M*N大小的矩阵就可以描述迷宫啦!

迷宫的特点

  1. 从设定的起点到终点必须是连通的(否则,还能不能好好玩耍了)
  2. 从起点到终点只有一条通路.(其实也可以有多条,根据实际需要设定)

思路

从迷宫特点的描述有没有想到什么?

迷宫就是一个图,要求任意设定的起点和终点之间是连通的,就是一个 全连通图.但是如果这个图的连通度太高,迷宫就没有难度了,所以我们要求图中任意顶点之间只有一条路.

什么样的图只有一条路, 无环图.

所以我们需要的是无环的连通图,这是什么? 树

我们的迷宫就是一个树,因此迷宫的生成算法就是树的生成算法,树的生成算法有深度优先遍历和广度优先遍历, 在这里使用深度优先.

迷宫的生成过程

1 初始状态

图中绿色的表示障碍，灰色表示道路(空白)

由于迷宫四周都是障碍, 图的宽和高都必须是奇数.

2 迷宫的生成

1 任意选择一个空白块, 将该空白块作为树的根结点.

2 从根节点出发隔一个元素块查找四周(上,下,左,右,四个方向,不包括对角线方向)其他的空白块.

从该结点出发,四周只有两个空白块

从该结点出发,四周有四个空白块

3 随机选取其中一个空白块, 将道路沿该方向拓展, 即把夹在这两个空白块之间的障碍块去掉, 改成空白块.

把夹在这两个空白块之间的障碍块去掉

4 更新当前结点, 然后从当前结点出发,重复步骤2,3.

5 当遇到一个结点周围没有空白块时, 即没有可拓展道路的方向时, 回退并更新当前结点, 直至当前结点四周有空白块, 重复步骤2,3.

该结点周围没有空白块

6 当回退到根节点没有任何可以拓展的道路时, 算法结束, 迷宫也就生成了.

3 设定起点和终点

选取迷宫中的两个空白块作为迷宫的起点和终点,一个完整的迷宫就诞生了.

核心算法–深度优先

由于这部分算法是程序的一部分,不能完整运行,仅供参考.

在程序中用到了Qt中的容器QVector,可以用STL中的std::vector代替; 用到的qsrand()和qrand()生成随机数,可以使用C标准库中的srand()和rand()函数代替.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/*
@ 生成迷宫
*/
void GenerateMaze::Maze(int width, int height)
{
    //初始化矩阵, 申请内存
    maze_matrix_ = new int*[height];
    for(int i=0; i<height; i++)
    {
        maze_matrix_[i] = new int[width];
    }

    for(int i=0; i<height; i++)
    {
        for(int j=0; j<width;j++)
        {
            if(i % 2 == 0 || j % 2==0)
            {
                maze_matrix_[i][j] = 1;  //障碍
            }
            else
            {
                maze_matrix_[i][j] = 0;  //道路(空白)
            }
        }
    }

    qsrand(QTime(0,0,0).secsTo(QTime::currentTime())); //设置随机数种子

    maze_matrix_[1][1] = 2; //选取(1,1)作为根节点, 并将根节点的状态设置成2

    this->generateMaze(1, 1);   //深度优先遍历

    for(int i=0; i<height; i++)
    {
        for(int j=0; j<width;j++)
        {
            if(maze_matrix_[i][j] == 2)
            {
                maze_matrix_[i][j] = 0; //将状态为2的结点重新设置为0, 表示可通行道路
            }
        }
    }
}


/*
@ brief:深度优先生成迷宫(递归实现)
*/
void Maze::generateMaze(int pos_i, int pos_j)
{
    //到达边界, 返回
    if(pos_j < 0 || pos_j >= width || pos_i < 0 || pos_i >= height)
    {
        return;
    }

    QVector<int> vec = existedRoad((const int**)maze_matrix_, pos_i, pos_j); //查找当前结点四周空白块

    //四周没有空白块, 返回
    if(vec.size() == 0)
    {
        return;
    }

    for(int i=0; i < vec.size();)
    {
        int index = qrand()%vec.size(); //随机选择其中一个空白块

        switch(vec[index])
        {
        case D_LEFT:    //左
            if(maze_matrix_[pos_i][pos_j-2] != 2)
            {
                maze_matrix_[pos_i][pos_j-1] = 2;    //将走过的路径设为2, 防止重复经过
                maze_matrix_[pos_i][pos_j-2] = 2;
                this->generateMaze(pos_i, pos_j-2); //更新结点, 递归
            }
            break;
        case D_RIGHT:   //右
            if(maze_matrix_[pos_i][pos_j+2] != 2)
            {
                maze_matrix_[pos_i][pos_j+1] = 2;
                maze_matrix_[pos_i][pos_j+2] = 2;
                this->generateMaze(pos_i, pos_j+2); //更新结点, 递归
            }
            break;  
        case D_UP:  //上
            if(maze_matrix_[pos_i-2][pos_j] != 2)
            {
                maze_matrix_[pos_i-1][pos_j] = 2;
                maze_matrix_[pos_i-2][pos_j] = 2;
                this->generateMaze(pos_i-2, pos_j); //更新结点, 递归
            }
            break;
        case D_DOWN:    //下
            if(maze_matrix_[pos_i+2][pos_j] != 2)
            {
                maze_matrix_[pos_i+1][pos_j] = 2;
                maze_matrix_[pos_i+2][pos_j] = 2;
                this->generateMaze(pos_i+2, pos_j); //更新结点, 递归
            }
            break;
        }

        vec.remove(index);  //清空vec
    }
}

/*
@brief: 查找结点周围的空白块
*/

const QVector<int> Maze::existedRoad(const int **mat, int i, int j)
{
    QVector<int> vec;

    if(j-2 >= 0 && mat[i][j-2] == 0)
    {
        vec.push_back(D_LEFT);  //左边有空白块
    }

    if(j+2 < width && mat[i][j+2] == 0)
    {
        vec.push_back(D_RIGHT); //右边有空白块
    }

    if(i-2 >= 0 && mat[i-2][j] == 0)
    {
        vec.push_back(D_UP);    //上边有空白块
    }

    if(i+2 < height && mat[i+2][j] == 0)
    {
        vec.push_back(D_DOWN);  //下边有空白块
    }

    return vec;
}