C语言实现一个走迷宫小游戏（深度优先算法）（c语言走出迷宫）

　　本篇文章为你整理了C语言实现一个走迷宫小游戏（深度优先算法）（c语言走出迷宫）的详细内容，包含有c语言走迷宫程序源代码 c语言走出迷宫 c语言实现迷宫问题 c语言实现迷宫求解问题(详细思路+附源代码) C语言实现一个走迷宫小游戏（深度优先算法），希望能帮助你了解 C语言实现一个走迷宫小游戏（深度优先算法）。

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

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

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

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

　　随机迷宫生成算法——深度优先算法

　　随机迷宫生成算法——prime算法

　　随机迷宫生成算法——递归分割算法

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

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

　　 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;

　　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++;

　　38 //count大于1表明墙体会被挖穿，停止

　　39 if (count 1)

　　40 break;

　　41 //确保不会挖穿时，前进

　　42 range -= 1;

　　43 maze[dx][dy] = ROUTE;

　　45 //没有挖穿危险，以此为节点递归

　　46 if (range = 0) {

　　47 CreateMaze(maze, dx, dy);

　　50 }

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

 1 int init(int** Maze) {//初始化迷宫

　　 2 //最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿

　　 3 for (int i = 0; i i++) {

　　 4 Maze[i][0] = ROUTE;

　　 5 Maze[0][i] = ROUTE;

　　 6 Maze[i][L - 1] = ROUTE;

　　 7 Maze[L - 1][i] = ROUTE;

　　 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;

　　21 }

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

 1 void print(int** Maze) {//画迷宫

　　 2 for (int i = 0; i i++) {

　　 3 for (int j = 0; j j++) {

　　 4 if (Maze[i][j] == ROUTE)

　　 5 printf(" ");//表示道路

　　 6 else if(Maze[i][j] == WALL)

　　 7 printf("回");//表示墙体

　　 8 else

　　 9 printf("十");//表示玩家

　　11 printf("\n");

　　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 i++) {

　　10 Maze[i] = (int*)calloc(L, sizeof(int));

　　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;

　　33 //一局游戏结束，释放内存

　　34 for (int i = 0; i i++) free(Maze[i]);

　　35 free(Maze);

　　36 }

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

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

　　说明界面：

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

　　编译器：TDM-GCC4.9.264-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

　　 7 //地图边长L，包括迷宫主体20，外侧的包围的墙体2，最外侧包围路径2（之后会解释）

　　 8 //可根据需要修改，有上限

　　 9 #define L 24

　　 11 #define WALL 0 //墙

　　 12 #define ROUTE 1 //路径

　　 13 #define PLAYER 2//玩家

　　 15 //控制迷宫的复杂度，数值越大复杂度越低，最小值为0

　　 16 //默认为简单难度，可根据需要在degree函数里调整不同难度的复杂度

　　 17 int Rank = 6;

　　 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);//移动角色

　　 28 int main() {

　　 29 menu();

　　 30 return 0;

　　 31 }

　　 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 }

　　 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 }

　　118 int init(int** Maze) {//初始化迷宫

　　119 int i;

　　120 //最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿

　　121 for (i = 0; i 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 }

　　141 void print(int** Maze) {//画迷宫

　　142 int i, j;

　　143 for (i = 0; i i++) {

　　144 for (j = 0; j 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 }

　　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 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 i++) free(Maze[i]);

　　220 free(Maze);

　　221 }

　　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 }

　　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 }

　　View Code

　　非常感谢您的观看，如果对你有所帮助的话实在是再好不过了。

　　—————————————我———是———分———割———线————————————

　　看了我公告的小伙伴可能会好奇，“哎博主你不是要准备期末考了吗？怎么跟打鸡血了一样疯狂更新啊？”原因很简单——期末复习的时候，除了复习以外的所有事都比复习有趣多了

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读