转载于我的博客园：https://www.cnblogs.com/xiao-qi-w/p/13031637.html
接上一篇万年历博文，还是那位朋友的练习题。这次是使用C语言做一个小游戏程序，三选一（2048、8皇后和迷宫游戏），我选择的是迷宫（文章末尾有源码下载链接以及演示视频链接）。个人认为这个程序的难点在于迷宫地图的绘制，也就是怎么建立一个迷宫。如果迷宫地图是在程序里写死的，那可玩性就大大降低了。那么能不能像正常游戏一样生成一个随机地图呢？当然有！在网上查到的结果不外乎这三种：深度优先算法、prim算法和递归分割算法。这三种算法的优劣比较可前往这篇博文一探究竟：
三大迷宫生成算法 (Maze generation algorithm) -- 深度优先，随机Prim，递归分割
至于代码实现我参考的是CSDN博主 jjwwwww 的三篇迷宫算法文章的第一篇，全部文章的链接如下：
下面来看一下思路和代码：
维基百科中给出的深度优先（递归回溯）算法思路如下：
1.将起点作为当前迷宫单元并标记为已访问
2.当还存在未标记的迷宫单元，进行循环
1.如果当前迷宫单元有未被访问过的的相邻的迷宫单元
1.随机选择一个未访问的相邻迷宫单元
2.将当前迷宫单元入栈
3.移除当前迷宫单元与相邻迷宫单元的墙
4.标记相邻迷宫单元并用它作为当前迷宫单元
2.如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空
1.栈顶的迷宫单元出栈
2.令其成为当前迷宫单元
如果你觉得上面这个表述不太容易理解，那么来看看下面这个思路（还是上面那个博主的，也是我的代码采用的）：
- 首先假设迷宫只有一条正确的道路。
- 假设自己是一只地鼠，要在这个区域不停的挖，直到任何一块区域再挖就会挖穿了为止。
- 我们挖的道路就像树结构，树上有很多的分支，分支也有子分支，每个子分支都不能相交，相交了就说明墙被挖穿了，那么此时的迷宫就可能存在多条正确道路，这不是我想看到的。
- 那么基于唯一道路的原则，我们向某个方向挖一块新的区域时，要先判断新区域是否有挖穿的可能，如果可能挖穿要立即停止并换个方向再挖。如图：
有了思路，就有了下面的代码，创建迷宫：
-
void CreateMaze(int **maze, int x, int y) {
//构建迷宫
-
maze[x][y] = ROUTE;
-
//确保四个方向随机，而不再是固定的上下左右这种排列
-
int direction[
4][
2] = { {
1,
0 },{
-1,
0 },{
0,
-1 },{
0,
1 } };
-
for (
int i =
0; i <
4; i++) {
-
int r = rand() %
4;
-
int temp = direction[
0][
0];
-
direction[
0][
0] = direction[r][
0];
-
direction[r][
0] = temp;
-
temp = direction[
0][
1];
-
direction[
0][
1] = direction[r][
1];
-
direction[r][
1] = temp;
-
}
-
//向四个方向开挖
-
for (
int i =
0; i <
4; i++) {
-
int dx = x;
-
int dy = y;
-
//控制挖的距离，由Rank来调整大小
-
int range =
1 + (Rank ==
0 ?
0 : rand() % Rank);
-
while (range >
0) {
-
//计算出将要访问到的坐标
-
dx += direction[i][
0];
-
dy += direction[i][
1];
-
//排除掉回头路
-
if (maze[dx][dy] == ROUTE) {
-
break;
-
}
-
//判断是否挖穿路径
-
int count =
0;
-
for (
int j = dx -
1; j < dx +
2; j++) {
-
for (
int k = dy -
1; k < dy +
2; k++) {
-
//abs(j - dx) + abs(k - dy) == 1 确保只判断九宫格的四个特定位置
-
if (
abs(j - dx) +
abs(k - dy) ==
1 && maze[j][k] == ROUTE) {
-
count++;
-
}
-
}
-
}
-
//count大于1表明墙体会被挖穿，停止
-
if (count >
1)
-
break;
-
//确保不会挖穿时，前进
-
range -=
1;
-
maze[dx][dy] = ROUTE;
-
}
-
//没有挖穿危险，以此为节点递归
-
if (range <=
0) {
-
CreateMaze(maze, dx, dy);
-
}
-
}
-
}
当然这样还不够，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿，我们把最外层全部设为路径。此外还需要设置入口以及寻找出口，如下：
-
int init(int** Maze) {
//初始化迷宫
-
//最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿
-
for (
int i =
0; i < L; i++) {
-
Maze[i][
0] = ROUTE;
-
Maze[
0][i] = ROUTE;
-
Maze[i][L -
1] = ROUTE;
-
Maze[L -
1][i] = ROUTE;
-
}
-
//创造迷宫，（2，2）为起点
-
CreateMaze(Maze,
2,
2);
-
//画迷宫的入口和出口，给出玩家初始位置
-
Maze[
2][
1] = PLAYER;
-
//由于算法随机性，出口有一定概率不在（L-3,L-2）处，此时需要寻找出口
-
for (
int i = L -
3; i >=
0; i--) {
-
if (Maze[i][L -
3] == ROUTE) {
-
Maze[i][L -
2] = ROUTE;
-
//返回出口所在的纵坐标
-
return i;
-
}
-
}
-
}
至此，我们已经能够生成一幅迷宫地图了，下面用函数把它展示出来：
-
void print(int** Maze) {
//画迷宫
-
for (
int i =
0; i < L; i++) {
-
for (
int j =
0; j < L; j++) {
-
if (Maze[i][j] == ROUTE)
-
printf(
" ");
//表示道路
-
else
if(Maze[i][j] == WALL)
-
printf(
"回");
//表示墙体
-
else
-
printf(
"十");
//表示玩家
-
}
-
printf(
"\n");
-
}
-
}
实际绘制效果如下：
至此我们已经完成80%的工作了，如何互动起来就看我们的输入了。我的想法是利用w,s,a,d四个键作为控制键控制角色 “十” 上下左右移动，当移动到出口处游戏结束。把这个想法转换为代码如下：
-
void start() {
//开始一局游戏
-
char t;
-
//y,x表示角色横纵坐标, out表示出口的纵坐标
-
int x =
2, y =
1, out =
0;
-
//随机数发生器初始化函数
-
srand((
unsigned)time(
NULL));
-
//申请数组空间
-
int **Maze = (
int**)
malloc(L *
sizeof(
int *));
-
for (
int i =
0; i < L; i++) {
-
Maze[i] = (
int*)
calloc(L,
sizeof(
int));
-
}
-
//得到出口纵坐标
-
out = init(Maze);
-
//游戏开始
-
system(
"cls");
-
print(Maze);
-
while(t = getch()) {
-
if(t ==
27)
//如果输入为ESC键，结束游戏回到主菜单
-
break;
-
system(
"cls");
//清屏
-
move(Maze, t, x, y);
//根据输入t进行移动
-
print(Maze);
//重新绘制迷宫
-
if(x == out && y == L
-2) {
//已经到出口，游戏结束
-
system(
"cls");
-
printf(
"=============\n");
-
printf(
"游 戏 胜 利！\n");
-
printf(
"=============\n");
-
printf(
"即将后返回主菜单……");
-
Sleep(
1500);
//执行挂起一段时间，暂停1.5秒后打印
-
break;
-
}
-
}
-
//一局游戏结束，释放内存
-
for (
int i =
0; i < L; i++)
free(Maze[i]);
-
free(Maze);
-
}
为了游戏体验我使用了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/
非常感谢您的观看，如果对你有所帮助的话实在是再好不过了。
转载：https://blog.csdn.net/qq_43464624/article/details/106501467