<span>C语言实现一个走迷宫小游戏（深度优先算法）</span>

　　补充一下，先前文章末尾给出的下载链接的完整代码含有部分C++的语法（使用Dev-C++并且文件扩展名为.cpp的没有影响），如果有的朋友使用的语言标准是VC6的话可能不支持，所以在修改过后再上传一版，这次直接放在文章末尾了，复制粘贴就行，希望对您有所帮助。

　　接上一篇万年历博文，还是那位朋友的练习题。这次是使用C语言做一个小游戏程序，三选一（2048、8皇后和迷宫游戏），我选择的是迷宫（文章末尾有源码下载链接以及演示视频链接）。个人认为这个程序的难点在于迷宫地图的绘制，也就是怎么建立一个迷宫。如果迷宫地图是在程序里写死的，那可玩性就大大降低了。那么能不能像正常游戏一样生成一个随机地图呢？当然有！在网上查到的结果不外乎这三种：深度优先算法、prim算法和递归分割算法。这三种算法的优劣比较可前往这篇博文一探究竟：

　　三大迷宫生成算法 (Maze generation algorithm) -- 深度优先，随机Prim，递归分割

　　至于代码实现我参考的是CSDN博主 jjwwwww 的三篇迷宫算法文章的第一篇，全部文章的链接如下：

　　下面来看一下思路和代码：

　　维基百科中给出的深度优先（递归回溯）算法思路如下：

　　1.将起点作为当前迷宫单元并标记为已访问
　　2.当还存在未标记的迷宫单元，进行循环
　　　　1.如果当前迷宫单元有未被访问过的的相邻的迷宫单元
　　　　　　1.随机选择一个未访问的相邻迷宫单元
　　　　　　2.将当前迷宫单元入栈
　　　　　　3.移除当前迷宫单元与相邻迷宫单元的墙
　　　　　　4.标记相邻迷宫单元并用它作为当前迷宫单元
　　　　2.如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空
　　　　　　1.栈顶的迷宫单元出栈
　　　　　　2.令其成为当前迷宫单元

　　如果你觉得上面这个表述不太容易理解，那么来看看下面这个思路（还是上面那个博主的，也是我的代码采用的）：

首先假设迷宫只有一条正确的道路。
假设自己是一只地鼠，要在这个区域不停的挖，直到任何一块区域再挖就会挖穿了为止。
我们挖的道路就像树结构，树上有很多的分支，分支也有子分支，每个子分支都不能相交，相交了就说明墙被挖穿了，那么此时的迷宫就可能存在多条正确道路，这不是我想看到的。
那么基于唯一道路的原则，我们向某个方向挖一块新的区域时，要先判断新区域是否有挖穿的可能，如果可能挖穿要立即停止并换个方向再挖。如图：

　　有了思路，就有了下面的代码，创建迷宫：

 1 void CreateMaze(int **maze, int x, int y) {//构建迷宫
 2     maze[x][y] = ROUTE;
 3     //确保四个方向随机，而不再是固定的上下左右这种排列 
 4     int direction[4][2] = { { 1,0 },{ -1,0 },{ 0,-1 },{ 0,1 } };
 5     for (int i = 0; i < 4; i++) {
 6         int r = rand() % 4;
 7         int temp = direction[0][0];
 8         direction[0][0] = direction[r][0];
 9         direction[r][0] = temp;
10         temp = direction[0][1];
11         direction[0][1] = direction[r][1];
12         direction[r][1] = temp;
13     } 
14     //向四个方向开挖
15     for (int i = 0; i < 4; i++) {
16         int dx = x;
17         int dy = y;
18         //控制挖的距离，由Rank来调整大小
19         int range = 1 + (Rank == 0 ? 0 : rand() % Rank);
20         while (range > 0) {
21             //计算出将要访问到的坐标 
22             dx += direction[i][0];
23             dy += direction[i][1];
24             //排除掉回头路
25             if (maze[dx][dy] == ROUTE) {
26                 break;
27             }
28             //判断是否挖穿路径
29             int count = 0;
30             for (int j = dx - 1; j < dx + 2; j++) {
31                 for (int k = dy - 1; k < dy + 2; k++) {
32                     //abs(j - dx) + abs(k - dy) == 1 确保只判断九宫格的四个特定位置
33                     if (abs(j - dx) + abs(k - dy) == 1 && maze[j][k] == ROUTE) {
34                         count++;
35                     }
36                 }
37             }
38             //count大于1表明墙体会被挖穿，停止 
39             if (count > 1)
40                 break;
41             //确保不会挖穿时，前进
42             range -= 1;
43             maze[dx][dy] = ROUTE;
44         }
45         //没有挖穿危险，以此为节点递归
46         if (range <= 0) {
47             CreateMaze(maze, dx, dy);
48         }
49     }
50 }

　　当然这样还不够，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿，我们把最外层全部设为路径。此外还需要设置入口以及寻找出口，如下：

 1 int init(int** Maze) {//初始化迷宫
 2     //最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿
 3     for (int i = 0; i < L; i++) {
 4         Maze[i][0] = ROUTE;
 5         Maze[0][i] = ROUTE;
 6         Maze[i][L - 1] = ROUTE;
 7         Maze[L - 1][i] = ROUTE;
 8     }
 9     //创造迷宫，（2，2）为起点
10     CreateMaze(Maze, 2, 2);
11     //画迷宫的入口和出口，给出玩家初始位置
12     Maze[2][1] = PLAYER;
13     //由于算法随机性，出口有一定概率不在（L-3,L-2）处，此时需要寻找出口
14     for (int i = L - 3; i >= 0; i--) {
15         if (Maze[i][L - 3] == ROUTE) {
16             Maze[i][L - 2] = ROUTE;
17             //返回出口所在的纵坐标 
18             return i;
19         }
20     }
21 }

　　至此，我们已经能够生成一幅迷宫地图了，下面用函数把它展示出来：

 1 void print(int** Maze) {//画迷宫
 2     for (int i = 0; i < L; i++) {
 3         for (int j = 0; j < L; j++) {
 4             if (Maze[i][j] == ROUTE)
 5                 printf("  ");//表示道路
 6             else if(Maze[i][j] == WALL)
 7                 printf("回");//表示墙体
 8             else
 9                 printf("十");//表示玩家
10         }
11         printf("\n");
12     }
13 }

　　实际绘制效果如下：

　　至此我们已经完成80%的工作了，如何互动起来就看我们的输入了。我的想法是利用w,s,a,d四个键作为控制键控制角色 “十” 上下左右移动，当移动到出口处游戏结束。把这个想法转换为代码如下：

 1 void start() { //开始一局游戏 
 2     char t;
 3     //y,x表示角色横纵坐标, out表示出口的纵坐标
 4     int x = 2, y = 1, out = 0;
 5     //随机数发生器初始化函数
 6     srand((unsigned)time(NULL));
 7     //申请数组空间
 8     int **Maze = (int**)malloc(L * sizeof(int *));
 9     for (int i = 0; i < L; i++) {
10         Maze[i] = (int*)calloc(L, sizeof(int));
11     }
12     //得到出口纵坐标
13     out = init(Maze);
14     //游戏开始
15     system("cls");
16     print(Maze);
17     while(t = getch()) {
18         if(t == 27)   //如果输入为ESC键，结束游戏回到主菜单
19             break;
20         system("cls");//清屏
21         move(Maze, t, x, y);//根据输入t进行移动
22         print(Maze);//重新绘制迷宫
23         if(x == out && y == L-2) {//已经到出口，游戏结束
24             system("cls");
25             printf("=============\n");
26             printf("游 戏 胜 利！\n");
27             printf("=============\n");
28             printf("即将后返回主菜单……");
29             Sleep(1500);//执行挂起一段时间，暂停1.5秒后打印
30             break;
31         }
32     }
33     //一局游戏结束，释放内存 
34     for (int i = 0; i < L; i++) free(Maze[i]);
35     free(Maze);
36 }

　　为了游戏体验我使用了getch()这个库函数代替getchar()，好处就是不回显。为了让这个游戏看起来还比较像样，我就把他做成了下面这个样子：

　　开始界面：　　　　　　　　　　　难度调整界面：

　　说明界面：

　　编辑工具：Dev-C++（版本：5.11.0.0）

　　编译器：TDM-GCC 4.9.2 64-bit Release

　　源码下载链接：https://download.csdn.net/download/qq_43464624/12489415

　　程序演示视频链接：https://www.bilibili.com/video/BV1pz411i7Nz/

　　修改过的VC6标准的完整代码：

  1 #include<stdio.h>
  2 #include<windows.h>
  3 #include<conio.h>
  4 #include<time.h>
  5 #include<math.h>
  6 
  7 //地图边长L，包括迷宫主体20，外侧的包围的墙体2，最外侧包围路径2（之后会解释）
  8 //可根据需要修改，有上限 
  9 #define L 24
 10 
 11 #define WALL  0 //墙 
 12 #define ROUTE 1 //路径 
 13 #define PLAYER 2//玩家 
 14 
 15 //控制迷宫的复杂度，数值越大复杂度越低，最小值为0
 16 //默认为简单难度，可根据需要在degree函数里调整不同难度的复杂度 
 17 int Rank = 6;
 18 
 19 void menu();   //主菜单界面
 20 void start();  //开始游戏
 21 void degree(); //游戏难度 
 22 void explain();//游戏说明
 23 int init(int** Maze);  //初始化迷宫
 24 void print(int** Maze);//画迷宫
 25 void CreateMaze(int **maze, int x, int y);    //创建迷宫
 26 void move(int** Maze, char t, int *x, int *y);//移动角色
 27 
 28 int main() {
 29     menu();
 30     return 0;
 31 }
 32 
 33 void menu() { //主菜单
 34     while(1) {
 35         system("cls"); //清屏
 36         char t;
 37         printf("*******(走迷宫)*******");
 38         printf("\n======================\n");
 39         printf("\n||   1. 开始 游戏   ||\n");
 40         printf("\n||   2. 游戏 说明   ||\n");
 41         printf("\n||   3. 游戏 难度   ||\n");
 42         printf("\n||   4. 关闭 游戏   ||\n");
 43         printf("======================\n");
 44         t=getch();    //不回显函数
 45         switch(t) {
 46             case '1':
 47                 start();
 48                 break;  //开始一局游戏
 49             case '2':
 50                 explain();
 51                 break;  //进入游戏说明界面
 52             case '3':
 53                 degree();
 54                 break;  //调整游戏难度 
 55             case '4':
 56                 printf("\n欢迎下次再玩，再见（￣︶￣）↗");
 57                 Sleep(1500);
 58                 exit(0);
 59                 break;  //结束程序
 60             default :
 61                 break;
 62         }
 63     }
 64 }
 65 
 66 void CreateMaze(int **maze, int x, int y) {//构建迷宫
 67     maze[x][y] = ROUTE;
 68     //确保四个方向随机，而不再是固定的上下左右这种排列 
 69     int direction[4][2] = { { 1,0 },{ -1,0 },{ 0,-1 },{ 0,1 } };
 70     int i, j;
 71     for (i = 0; i < 4; i++) {
 72         int r = rand() % 4;
 73         int temp = direction[0][0];
 74         direction[0][0] = direction[r][0];
 75         direction[r][0] = temp;
 76         temp = direction[0][1];
 77         direction[0][1] = direction[r][1];
 78         direction[r][1] = temp;
 79     } 
 80     //向四个方向开挖
 81     for (i = 0; i < 4; i++) {
 82         int dx = x;
 83         int dy = y;
 84         //控制挖的距离，由Rank来调整大小
 85         int range = 1 + (Rank == 0 ? 0 : rand() % Rank);
 86         while (range > 0) {
 87             //计算出将要访问到的坐标 
 88             dx += direction[i][0];
 89             dy += direction[i][1];
 90             //排除掉回头路
 91             if (maze[dx][dy] == ROUTE) {
 92                 break;
 93             }
 94             //判断是否挖穿路径
 95             int count = 0, k;
 96             for (j = dx - 1; j < dx + 2; j++) {
 97                 for (k = dy - 1; k < dy + 2; k++) {
 98                     //abs(j - dx) + abs(k - dy) == 1 确保只判断九宫格的四个特定位置
 99                     if (abs(j - dx) + abs(k - dy) == 1 && maze[j][k] == ROUTE) {
100                         count++;
101                     }
102                 }
103             }
104             //count大于1表明墙体会被挖穿，停止 
105             if (count > 1)
106                 break;
107             //确保不会挖穿时，前进
108             range -= 1;
109             maze[dx][dy] = ROUTE;
110         }
111         //没有挖穿危险，以此为节点递归
112         if (range <= 0) {
113             CreateMaze(maze, dx, dy);
114         }
115     }
116 }
117 
118 int init(int** Maze) {//初始化迷宫
119     int i;
120     //最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿
121     for (i = 0; i < L; i++) {
122         Maze[i][0] = ROUTE;
123         Maze[0][i] = ROUTE;
124         Maze[i][L - 1] = ROUTE;
125         Maze[L - 1][i] = ROUTE;
126     }
127     //创造迷宫，（2，2）为起点
128     CreateMaze(Maze, 2, 2);
129     //画迷宫的入口和出口，给出玩家初始位置
130     Maze[2][1] = PLAYER;
131     //由于算法随机性，出口有一定概率不在（L-3,L-2）处，此时需要寻找出口
132     for (i = L - 3; i >= 0; i--) {
133         if (Maze[i][L - 3] == ROUTE) {
134             Maze[i][L - 2] = ROUTE;
135             //返回出口所在的纵坐标 
136             return i;
137         }
138     }
139 }
140 
141 void print(int** Maze) {//画迷宫
142     int i, j;
143     for (i = 0; i < L; i++) {
144         for (j = 0; j < L; j++) {
145             if (Maze[i][j] == ROUTE)
146                 printf("  ");//表示道路
147             else if(Maze[i][j] == WALL)
148                 printf("回");//表示墙体
149             else
150                 printf("十");//表示玩家
151         }
152         printf("\n");
153     }
154 }
155 //将原先的引用int &x，更改为现在的指针指向int *x
156 void move(int** Maze, char t, int *x, int *y) {//移动角色
157     int i = *x, j = *y;//记录原始位置
158     switch(t) {
159         case 'w':    //向上移动
160             *x -= 1;
161             break;
162         case 's':    //向下移动
163             *x += 1;
164             break;
165         case 'a':    //向左移动
166             *y -= 1;
167             break;
168         case 'd':    //向右移动
169             *y += 1;
170             break;
171         default:
172             break;
173     }
174     if(*x>=0 && *x<L-1 && *y>=0 && *y<L-1 && Maze[*x][*y]!=WALL) {//符合条件，移动
175         Maze[i][j] = 1;
176         Maze[*x][*y] = 2;
177     } else {//保持位置不变
178         *x = i;
179         *y = j;
180     }
181 }
182 
183 void start() { //开始一局游戏 
184     char t;
185     //y,x表示角色横纵坐标, out表示出口的纵坐标
186     int *p, *q;
187     int x = 2, y = 1, out = 0, i = 0;
188     p = &x;
189     q = &y;
190     //随机数发生器初始化函数
191     srand((unsigned)time(NULL));
192     //申请数组空间
193     int **Maze = (int**)malloc(L * sizeof(int *));
194     for (i = 0; i < L; i++) {
195         Maze[i] = (int*)calloc(L, sizeof(int));
196     }
197     //得到出口纵坐标
198     out = init(Maze);
199     //游戏开始
200     system("cls");
201     print(Maze);
202     while(t = getch()) {
203         if(t == 27)   //如果输入为ESC键，结束游戏回到主菜单
204             break;
205         system("cls");//清屏
206         move(Maze, t, p, q);//根据输入t进行移动
207         print(Maze);//重新绘制迷宫
208         if(x == out && y == L-2) {//已经到出口，游戏结束
209             system("cls");
210             printf("=============\n");
211             printf("游 戏 胜 利！\n");
212             printf("=============\n");
213             printf("即将后返回主菜单……");
214             Sleep(1500);//执行挂起一段时间，暂停1.5秒后打印
215             break;
216         }
217     }
218     //一局游戏结束，释放内存 
219     for (i = 0; i < L; i++) free(Maze[i]);
220     free(Maze);
221 }
222 
223 void explain() { //操作说明 
224     while(1) {
225         char t;
226         system("cls");
227         printf("=================================================\n");
228         printf("感谢您体验本游戏，游戏的操作如下：\n");
229         printf("\n1.将输入法调整为英文（小写）\n");
230         printf("\n2.通过w,s,a,d四个键控制角色上下左右移动\n");
231         printf("\n3.在任意界面均可按“ESC”键返回到主菜单\n");
232         printf("\n胜利条件：移动角色到出口处，加油各位(￣▽￣)\"!\n");
233         printf("=================================================\n");
234         t=getch();  //不回显函数 
235         switch(t) {
236                 //ESC键的ASCII码值 
237             case 27:
238                 //返回主菜单
239                 menu();
240                 break;
241             default :
242                 break;
243         }
244     }
245 }
246 
247 void degree() { //调整游戏难度 
248     while(1) {
249         char t;
250         system("cls");
251         printf("=======================\n");
252         printf("输入1,2,3进行难度调整：\n");
253         printf("\n||    1.简  单    ||\n");
254         printf("\n||    2.中  等    ||\n");
255         printf("\n||    3.困  难    ||\n");
256         printf("=======================\n");
257         t=getch();  //不回显函数 
258         switch(t) {
259             case '1':
260                 Rank = 6;
261                 printf("\n当前难度：简单，即将返回主菜单……");
262                 Sleep(1500);
263                 menu();//返回主菜单
264                 break; 
265             case '2':
266                 Rank = 3;
267                 printf("\n当前难度：中等，即将返回主菜单……");
268                 Sleep(1500);
269                 menu();//返回主菜单
270                 break;
271             case '3':
272                 Rank = 0;
273                 printf("\n当前难度：困难，即将返回主菜单……");
274                 Sleep(1500);
275                 menu();//返回主菜单
276                 break;
277             case 27:
278                 menu();
279                 break; 
280             default :
281                 break;
282         }
283     }
284 }