一.前言
迷宫问题是数据结构中最值得实践的大项目之一，本文主要讲解思路，提供的代码大部分都有注释（没有的就是太多了懒得写了QAQ）。为了更好的表现效果，该程序使用了easyx可视化，easyx简单易学（大概一天到两天就可以学会），上手简单。该程序由c语言实现，本人水平有限程序可优化空间很大。本文我会简明的讲解该项目。
二.效果展示
<iframe allowfullscreen="true" data-mediaembed="csdn" frameborder="0" id="2etiJFcU-1728298246466" src="https://live.csdn.net/v/embed/428203"></iframe>随机prim算法生成迷宫
<iframe allowfullscreen="true" data-mediaembed="csdn" frameborder="0" id="brHWzQFa-1728292919710" src="https://live.csdn.net/v/embed/428201"></iframe>寻路效果演示
三.程序思路讲解
1.数据结构的表达：
我们程序主要需要用到的数据结构有：邻接矩阵，集合，路径存储
邻接矩阵：使用邻接矩阵时我们会发现，我们需要用到的最少只需要当前格子的旁边4个格子的关系就行了，如果使用整个迷宫太浪费空间，于是贪心一下，把邻接矩阵节省为4个格子的邻接矩阵。节点中的内容根据需求自行添加即可，我的节点中设有格子的x,y坐标，遍历标记值val,集合标记值repeat,打开墙方位m,豆子food（）。
集合：我们要用到集合，可以通过一个数组来存储，一个记录长度的元素即可，从集合中随机取元素时我们可以使用随机数种子来实现（关键字srand自行学习）。
路径存储： 为了存储路径设置的结构体,不使用节点结构体是为了节省内存空间
enum direction{TOP,BOTTOM,LEFT,RIGHT};//为了程序可读性和节省内存空间而做的枚举型变量
struct vnode{
int x,y;//记录当前在矩阵中的位置
int val;//标记值，初始值为0，经过后为1(为多个函数提供标记功能,为可视化做准备)
int repeat;//集合放入0为未放入，1为以放入(是否放入集合内的标记判断,避免重复进集合)
direction m;//消除方向判断(在passwall函数中判断当前矩阵方格打开的墙是哪一个方向)
bool food;//0为豆子，1为无豆子(豆子在地图上的显示做准备)
};//地图节点
struct mazegraph{
int maze[50][50][4];//顺序为TOP,BOTTOM,LEFT,RIGHT,0为墙，1为无墙(简化的邻接矩阵,节省内存空间)
vnode graph[50][50];//存储节点(矩阵中的节点,数组使用50高于30以防止数组的溢出导致程序崩溃)
int width,hight;
};//简化版本的邻接矩阵
struct gather{
vnode gather[MAXV];//合中存储的主要元素
int length;//当前集合的元素个数
};//集合,实现原理采用随机数在0到length-1中随机一个数,可以在数组中之间取出该元素,取出元素后后面元素整体前移，加入元素在数组的当前元素个数位置添加
struct D{
int x;
int y;
};//为了存储路径设置的结构体,不使用节点结构体是为了节省内存空间2.随机prim算法生成迷宫思路：
priim算法是选择权值最小的路径，而在迷宫中相邻两个格子的距离是相同的，所有可以使用随机抽取的方式在迷宫中抽取路径，这便是随机prim。那怎么使用随机prim来打开
最开始的迷宫可以看作是所有墙都是关闭的，我们要做的就是在使用prim遍历整个迷宫的过程中把墙打开。这个过程比较抽象，具体看下面的操作走一遍就明了了。
具体操作如下：
生成过程可以分为两步遍历和打开墙。二者都用到了集合的概率，但不是同一个集合，为了区分，我命名了集合1和集合2。
遍历 ：选择一个初始点开始，将初始点放入集合1中，把加入进集合1中的点上已遍历的标记，再从集合1中随机抽取出格子(因为目前集合中的格子只有一个，所以取出的也就是初始点)，将取出的格子“打开墙”(先忽略不看这一步，看完“打开墙”后再回来理解这一步)，并将取出的格子的四个方向中没有被上过遍历标记的格子放入集合1中，并将加入集合1的格子上遍历标记。再从集合1中随机抽取出格子重复以上操作。这便是遍历过程。
打开墙：把当前格子(即遍历过程中取出的那个格子)四周中有遍历标记的格子加入集合2中，如果集合2为空则不操作，如果有就从集合2中随机选择一个将其与当前格子打通，完成后清空集合。
流程图如下：
遍历
打开墙
打开墙的过程，是从该格子四个方向中符合条件的方向中，随机选择一个打开那个方向墙。
代码如下：
void passwall(mazegraph &G,int x,int y){
gather random; //创建随机选择方向的集合
random.length = 0; //初始化随机数组
int d=0;
random.gather[4];
if (G.graph[x][y - 1].val == 1){ //top
random.gather[random.length] = G.graph[x][y - 1];
random.gather[random.length].m=TOP;
random.length++;
}
if (G.graph[x][y + 1].val == 1){
random.gather[random.length] = G.graph[x][y + 1];
random.gather[random.length].m=BOTTOM;
random.length++;
}
if (G.graph[x - 1][y].val == 1){
random.gather[random.length] = G.graph[x - 1][y];
random.gather[random.length].m=LEFT;
random.length++;
}
if (G.graph[x + 1][y].val == 1){
random.gather[random.length] = G.graph[x + 1][y];
random.gather[random.length].m=RIGHT;
random.length++;
}
printf("有 %d个选择 ",random.length);
if(random.length!=0){
d=rand()%random.length;
}
printf("随机数为：%d ",d);
direction m=random.gather[d].m;
printf("方向是：%d",m);
if(m==TOP){
G.maze[x][y][0]=1;
G.maze[x][y-1][1]=1;
}
if(m==BOTTOM){
G.maze[x][y][1]=1;
G.maze[x][y+1][0]=1;
}
if(m==LEFT){
G.maze[x][y][2]=1;
G.maze[x-1][y][3]=1;
}
if(m==RIGHT){
G.maze[x][y][3]=1;
G.maze[x+1][y][2]=1;
}
}
void prim(mazegraph &G,gather & adj){
int random = rand() % adj.length; //random为0到数组长度之间的随机一个数，以此来实现随机
int x=adj.gather[random].x,y=adj.gather[random].y; //记录存入元素的x,y
printf("随机数=%d x=%d,y=%d", random, x, y);
G.graph[x][y].val = 1;//标记以访问 //标记已经访问
passwall(G,x,y);//随机消除与之相邻遍历过方格的墙*/
printf("执行前数组长度为 %d",adj.length);
for (int i = 0; i < 4; i++){
switch (i){
case TOP:
if (y != 0 && G.graph[x][y - 1].val == 0 && G.graph[x][y-1].repeat==0){
adj.gather[adj.length] = G.graph[x][y - 1];
G.graph[x][y-1].repeat=1;
adj.length++;
printf("上 %d ", adj.length);
}
break;
case BOTTOM:
if (y!= G.hight-1 && G.graph[x][y + 1].val == 0 && G.graph[x][y+1].repeat==0){
adj.gather[adj.length] = G.graph[x][y + 1];
G.graph[x][y+1].repeat=1;
adj.length++;
printf("下 %d ", adj.length);
}
break;
case LEFT:
if (x != 0 && G.graph[x - 1][y].val == 0 && G.graph[x-1][y].repeat==0){
adj.gather[adj.length] = G.graph[x - 1][y];
G.graph[x-1][y].repeat=1;
adj.length++;
printf("左 %d ", adj.length);
}
break;
case RIGHT:
if (x != G.width-1 && G.graph[x + 1][y].val == 0 && G.graph[x+1][y].repeat==0){
adj.gather[adj.length] = G.graph[x + 1][y];
G.graph[x+1][y].repeat=1;
adj.length++;
printf("右 %d ", adj.length);
}
break;
}//载入邻近方格中未遍历元素
}
int p = random + 1;
while (p < adj.length){
adj.gather[p - 1] = adj.gather[p];
p++;
}
adj.gather[adj.length - 1] = {0};//将结构体初始化
adj.length--;
//以上将元素从集合中踢出
printf("执行完后数组长度 %d\n", adj.length);//在当前集合中随机取出一个元素，并将该元素周围满足条件的元素加入集合中
}3.BFS寻路和DFS寻路和路径回溯
因为prim算法生成的迷宫是完美迷宫没有回路，所以由一个点到另外点的之间有且仅有一条路径，就像视频中的那个迷宫那样。所以寻路的话只有一条路径，那么想找到这一条路径，只需要把遍历过程中的路径记录下来，即一个点的前一个点是哪个的，由终点向前推就可以找出这条路径了（即路径回溯）。
路径的记录：当前元素在路径记录的位置为一维数组（x+y*宽度）数组中记录的为当前元素的前一个元素。
BFS：利用队列的先进先出的特点来实现遍历就是BFS遍历，因为队列是先进先出的，先加入的元素会先执行，后加入的元素会后执行，所以遍历的图像就是辐射状向外扩张。遍历过程：将初始点（目标当前点）加入队列中，入列时上标记，再出列，出列时把四周没有标记且是通路的格子加入队列中，并在进列格子在一维数组的位置中记录前一个格子(即出列的那一个格子)。循环以上进队列出队列的过程直至队列为空。这便是BFS遍历过程。
代码如下：
void bfs(mazegraph &G){
int x=q.front().x,y=q.front().y;//取出队首元素
q.pop();//出队列
if(G.maze[x][y][3]==1 && G.graph[x+1][y].val==0 ){
G.graph[x+1][y].val=1;
q.push(G.graph[x+1][y]);
data[(x+1)+y*G.width].x=x;
data[(x+1)+y*G.width].y=y;
}//向右
if(G.maze[x][y][1]==1 && G.graph[x][y+1].val==0 ){
G.graph[x][y+1].val=1;
q.push(G.graph[x][y+1]);
data[x+(y+1)*G.width].x=x;
data[x+(y+1)*G.width].y=y;
}//向下
if(G.maze[x][y][2]==1 && G.graph[x-1][y].val==0 ){
G.graph[x-1][y].val=1;
q.push(G.graph[x-1][y]);
data[(x-1)+y*G.width].x=x;
data[(x-1)+y*G.width].y=y;
}//向左
if(G.maze[x][y][0]==1 && G.graph[x][y-1].val==0 ){
G.graph[x][y-1].val=1;
q.push(G.graph[x][y-1]);
data[x+(y-1)*G.width].x=x;
data[x+(y-1)*G.width].y=y;
}//向上*/
}//bfs遍历地图并存储路径DFS:利用栈的先进后出的特点来实现，只需要把队列换成栈即可。路径的记录也是一样的。
代码如下：
void dfs(mazegraph& G){
int x=Q.top().x;int y=Q.top().y;//取出栈顶元素
Q.pop();
if(G.maze[x][y][3]==1 && G.graph[x+1][y].val==0 ){
G.graph[x+1][y].val=1;
Q.push(G.graph[x+1][y]);
data[(x+1)+y*G.width].x=x;
data[(x+1)+y*G.width].y=y;
}//向右
if(G.maze[x][y][1]==1 && G.graph[x][y+1].val==0 ){
G.graph[x][y+1].val=1;
Q.push(G.graph[x][y+1]);
data[x+(y+1)*G.width].x=x;
data[x+(y+1)*G.width].y=y;
}//向下
if(G.maze[x][y][2]==1 && G.graph[x-1][y].val==0 ){
G.graph[x-1][y].val=1;
Q.push(G.graph[x-1][y]);
data[(x-1)+y*G.width].x=x;
data[(x-1)+y*G.width].y=y;
}//向左
if(G.maze[x][y][0]==1 && G.graph[x][y-1].val==0 ){
G.graph[x][y-1].val=1;
Q.push(G.graph[x][y-1]);
data[x+(y-1)*G.width].x=x;
data[x+(y-1)*G.width].y=y;
}//向上*/
}路径回溯：
通过以上步骤已经将路径记录下来了，那么怎么通过记录的路径找到终点呢？
因为我们记录时记录的是当前格子的前一个格子，那么我们就从终点往前推，推到当前格子为止。
下图中：第一行是我们所需要的路径，而第二行为我们记录的路径。
只需要从终点位置开始向前找即可，图像中终点位置为(3,3)，x+y*宽度就是过来的路径。
那么第3+3*4=15。数组的第15号位置（即第二行的第16个，因为数组从0开始）就是它的前一个路径即(3,2).以此往前推直到当前位置(1,1)。以上即为路径回溯的过程。
代码如下：
void find(int x0,int y0,int X,int Y,mazegraph &G){
int x=X;
int y=Y;
int t=y*G.width+x;//t为记录数组位置
while(x!=x0 || y!=y0){
printf("(%d,%d)",x,y);
G.graph[x][y].val=1;
x=data[t].x;
y=data[t].y;
t=y*G.width+x;
if(x==0 && y==0){
break;
}
}
printf("\n");
for(int t=0;t<G.width*G.hight;t++){
printf("(%d,%d)",data[t].x,data[t].y);
}
}//输出路径存储数组元素
//从终点开始往前标记路径
四.源码：
可以根据以s做一个跟迷宫的项目，我的项目为吃豆人（本来为小鼠迷宫，后续更改的）。
源码我分为两部分，一个主程序，一个头文件
主程序：
#include"mouse_maze.h"
void button(region reg,char *arr);//创建按钮图标
bool prss_down(region reg, ExMessage &msg);//配合按钮图标判断是否按下指定区域
void key_cs(int &x,int &y,IMAGE *&mouse ,mazegraph &G);//
bool mouse_position(region reg,ExMessage &msg);//判断鼠标是否在该区域
int creatmaze(mazegraph & G);//创建迷宫图像
void initmaze( mazegraph & G,int width,int hight);//初始化迷宫
void passwall(mazegraph &G,int x,int y);//随机拆掉一个目前区域相邻的以访问过区域之间的墙
void prim(mazegraph &G,gather & adj);//在当前集合中随机取出一个元素,标记访问,并将周围符合条件的墙拆除，并将该元素周围满足条件的元素加入集合中
void bfs(mazegraph &G);//bfs函数
void find(int x0,int y0,int X,int Y,mazegraph &G);//输出路径
int main() {
void srand(unsigned int seed);
initgraph(1200, 900,SHOWCONSOLE | NOMINIMIZE | NOCLOSE);//创建窗口,show显示，console控制台，flog为窗口格式初始为0，SHOWCONSOLE控制台与窗口同时显示
HWND hnd = GetHWnd();
SetWindowText(hnd, "吃豆人");
int x = 0, y = 0;//老鼠的坐标（实际地图坐标）
int x0 = 0, y0 = 0;//老鼠的坐标
int tx=0,ty=0;//老鼠的地图坐标
int width = 0, length = 0;
scene = 1;//调整展示界面,值1为主界面,2为地图创建后界面,3为开始游戏后界面,4为游戏胜利界面
mazegraph G; //存储地图
gather adj; //存储集合
ExMessage key; //游戏操作//消息结构体，内包含多个消息，有鼠标，字符，键盘，窗口多种消息
setbkcolor(BLUE);//设置背景颜色
setbkmode(TRANSPARENT);//设置背景样式，transparent透明，可以避免字体遮盖住背景
cleardevice();//刷新页面
loadimage(&img1, "C:\\Users\\awa\\DesKtop\\gallery\\graph.jpg", 900, 900);//载入地图背景
loadimage(&img2, "C:\\Users\\awa\\DesKtop\\gallery\\bj.jpg", 300, 900);//载入控制台背景
loadimage(&beans_bottom, "C:\\Users\\awa\\DesKtop\\gallery\\beans_bottom.jpg", rode - 2 * wall, rode - 2 * wall);
loadimage(&beans_left, "C:\\Users\\awa\\DesKtop\\gallery\\beans_left.jpg", rode - 2 * wall, rode - 2 * wall);
loadimage(&beans_right, "C:\\Users\\awa\\DesKtop\\gallery\\beans_right.jpg", rode - 2 * wall, rode - 2 * wall);
loadimage(&beans_top, "C:\\Users\\awa\\DesKtop\\gallery\\beans_top.jpg", rode - 2 * wall,rode - 2 * wall);//以上四个载入老鼠图片
loadimage(&End, "C:\\Users\\awa\\DesKtop\\gallery\\EXIT.jpg", rode - 2 * wall, rode - 2 * wall);//载入奶酪
loadimage(&WALL1, "C:\\Users\\awa\\Desktop\\gallery\\blue.jpg", rode, wall);
loadimage(&WALL2, "C:\\Users\\awa\\Desktop\\gallery\\blue.jpg", wall, rode);
loadimage(&WALL3, "C:\\Users\\awa\\Desktop\\gallery\\blue-rode.jpg", 2 * wall, 2 * wall);
loadimage(&RODE1, "C:\\Users\\awa\\Desktop\\gallery\\R-1.jpg", rode, rode);
loadimage(&RODE2, "C:\\Users\\awa\\Desktop\\gallery\\R-1.jpg", rode, wall);
loadimage(&RODE3, "C:\\Users\\awa\\Desktop\\gallery\\R-1.jpg", wall, rode);//墙与路
loadimage(&b, "C:\\Users\\awa\\Desktop\\gallery\\b.jpg", rode, rode);
loadimage(&FOOD,"C:\\Users\\awa\\Desktop\\gallery\\food.jpg",rode,rode);
settextstyle(30, 20, "正楷");//字体高度（0为默认），字体宽度（可以使用0，即是默认），字体样式（只要系统中有即可用）
settextcolor(RGB(48, 48, 48)); //设置文本字体,可以使用RGB颜色
settextcolor(BLACK);//改字体为黑色
while (1) {
BeginBatchDraw();//存储
cleardevice();//重置//
/* PlaySound("music/eat.wav",NULL,SND_FILENAME|SND_ASYNC|SND_LOOP);*/
/*MCIERROR RET=mciSendString("open music/eat",NULL,0,NULL);
mciSendString("setaudio music1 volume to 50",NULL,0,NULL);
if(RET!=0){
printf("执行");
char err[100]={0};
mciGetErrorString(RET,err,sizeof(err));
puts(err);
}
RET=mciSendString("play music/eat" ,NULL,0,NULL);
if(RET!=0){
printf("执行");
char err[100]={0};
mciGetErrorString(RET,err,sizeof(err));
puts(err);
}
getchar();*/
switch (scene) {
case 1:
putimage(0, 0, &img1);//输出迷宫背景
putimage(900, 0, &img2);//输出控制台背景
button(gen, gen.arr);//开始游戏
button(game_win, "欢迎游玩欢乐吃豆人");
if (peekmessage(&key, EM_MOUSE)) {
/*printf("(key.%d,key.%d)",key.x,key.y); */ //测试
if (prss_down(gen, key)) {
int ok = MessageBox(hnd, "请输入迷宫的长和宽(长和宽最大为30)", "操作提示", MB_OKCANCEL);
if (ok == IDOK) {
cout << "请输入长度：";
cin >> length;
while (length > 30 || length < 0) {
printf("错误，请点击确定后重新输入\n");
MessageBox(hnd, "错误，请重新输入正确的长度", "警告", MB_OK);
cout << "请输入长度：";
cin >> length;
}
cout << "请输入宽度：";
cin >> width;
while (width > 30 || width < 0) {
printf("错误，请点击确定后重新输入\n");
MessageBox(hnd, "错误，请重新输入正确的宽度", "警告", MB_OK);
cout << "请输入宽度：";
cin >> width;
}
X = rode / 2 + ((30 - length) / 2) * rode - rode / 2;
Y = rode / 2 + ((30 - width) / 2) * rode - rode / 2;//X,Y为实际的初始坐标
x0 = rand() % (length - (length * 3) / 4) + length * 3 / 4;
y0 = rand() % (width - (width * 3) / 4) + width * 3 / 4;
} else continue;
scene = 2;
MessageBox(hnd, "开始生成", "地图生成", MB_OK);
printf("奶酪再(%d,%d)位置", x0, y0);
initmaze(G, length, width);
creatmaze(G);
adj.length = 0;
adj.gather[adj.length] = G.graph[0][0];
G.graph[0][0].repeat = 1;
adj.length++;
}
}
break;
case 2:
if (adj.length != 0){
printf("执行");
prim(G, adj);
}//存放遍历的集合中有元素则循环执行prim算法进行遍历
putimage(0, 0, &img1);
creatmaze(G);
putimage(900, 0, &img2);
button(game_begin, game_begin.arr);
if (peekmessage(&key, EM_MOUSE)){
/*printf("(key.%d,key.%d)", key.x, key.y);*/
if (prss_down(game_begin, key)){
if(adj.length==0){
G.maze[0][0][0]=0;//莫名奇妙的bug
/*G.maze[0][0][1]=1;
G.maze[0][0][3]=1;
G.maze[0][1][0]=1;
G.maze[0][1][3]=1;
G.maze[1][0][1]=1;
G.maze[1][0][2]=1;
G.maze[1][1][0]=1;
G.maze[1][1][2]=1;*///避免寻路时因为零点而出现死循环，将初始点扩大为2X2
h=G.width*G.hight;
for (int i = 0; i < G.width; i++){
for (int j = 0; j < G.hight; j++){
G.graph[i][j].val = 0;
}
}//为寻路做准备把标记初始化
start = clock();
printf("现在是开始游戏后界面");
scene = 3;//跳转开始游戏界面
}else{
MessageBox(hnd, "地图还未创建完", "警告", MB_OK);
}
MessageBox(hnd,"吃完一半豆子后出现出口","提示",MB_OK);
}
}
break;
case 3:
BeginBatchDraw();//存储
cleardevice();//重置
putimage(0, 0, &img1);//输出迷宫背景
s=creatmaze(G);//记录地图中的豆子数
if(eatfood==true){
putimage(X + x0 * rode + wall, Y + y0 * rode + wall, &End);//显示出口
}
putimage(900, 0, &img2);//输出控制太背景
putimage(X + x + wall, Y + y + wall, &*beans);//吃豆人的图像
sprintf(coordinate, "%s (%d,%d)", "当前坐标", (x / rode) + 1, (y / rode) + 1);
if(eatfood==false)
sprintf(arr, "%s %d", "还需吃豆数", s - h/2);//输出还需吃豆数
else
sprintf(arr, "%s %d", "还需吃豆数",s);//完成显示任务为0
button(BFS, BFS.arr);//按钮bfs
button(DFS, DFS.arr);//按钮dfs
button(data_graph, coordinate);//区域显示当前位置
button(operate, "操作说明:上W，左A，右D，下S");//操作说明
button(muice,muice.arr);
button(eat,arr);
FlushBatchDraw();//释放
if(s==G.width*G.hight/2) {
eatfood = true;
MessageBox(hnd,"出口以出现","提示",MB_OK);
for(int i=0;i<G.width;i++){
for(int j=0;j<=G.hight;j++){
G.graph[i][j].food=1;
}
}
s=0;
}
if (peekmessage(&key, EM_MOUSE)) {
/*printf("(%d,%d)",key.x,key.y);*/
if(prss_down(BFS,key)) {
if (eatfood == true) {
for (int i = 0; i < G.width; i++) {
for (int j = 0; j < G.hight; j++) {
G.graph[i][j].val = 0;
}
}//为寻路做准备把标记初始化
q.push(G.graph[x / 30][y / 30]);
G.graph[x / 30][y / 30].val = 1;//在结束前将初始点入栈
bfs_ok = true;
}
else MessageBox(hnd,"请先完成吃豆数","提示",MB_OK);
}
if(prss_down(DFS,key)) {
/* printf("执行");*/
if (eatfood == true) {
for (int i = 0; i < G.width; i++) {
for (int j = 0; j < G.hight; j++) {
G.graph[i][j].val = 0;
}
}//为寻路做准备把标记初始化
Q.push(G.graph[x / 30][y / 30]);
G.graph[x / 30][y / 30].val = 1;//在结束前将初始点入栈
dfs_ok = true;
}
else MessageBox(hnd,"请先完成吃豆数","提示",MB_OK);
}
}
if(bfs_ok){
if(q.empty()==false)
bfs(G);
if(q.empty()){
for (int i = 0; i < G.width; i++){
for (int j = 0; j < G.hight; j++){
G.graph[i][j].val = 0;
}
}//为寻路做准备把标记初始化
find(tx,ty,x0,y0,G);
bfs_ok = false;
}
}
if(dfs_ok){
if(Q.empty()==false)
dfs(G);
if(Q.empty()){
for (int i = 0; i < G.width; i++){
for (int j = 0; j < G.hight; j++){
G.graph[i][j].val = 0;
}
}//为寻路做准备把标记初始化
FIND(tx,ty,x0,y0,G);
dfs_ok = false;
}
}
if(kbhit()){
if(bfs_ok==false && dfs_ok==false){
key_cs(x, y, beans, G);//键盘操作处理函数
tx=x/30,ty=y/30;
}
}//避免键盘操作阻塞鼠标操作
if(eatfood==true) {
if (tx == x0 && ty == y0) {
printf("执行");
END = clock();
eatfood=false;
time_1 = (int) ((END - start) / CLOCKS_PER_SEC);//计算经过时间
scene = 4;
}
}
break;
case 4:
putimage(0, 0, &img1);//输出迷宫背景
creatmaze(G);
putimage(900, 0, &img2);//输出控制太背景
button(game_win, "恭喜你游戏胜利");
button(NewGame, "返回主菜单");//返回主菜单
button(BFS, "退出游戏");//退出游戏
sprintf_s(str, "%s %d s", "使用时间为：", time_1);//合成文字与时间
button(data_graph, str);//输出计时
if (peekmessage(&key, EM_MOUSE)){
/*printf("(%d,%d)",key.x,key.y);*/
if (prss_down(NewGame, key)){
scene = 1;
x = 0, y = 0;
printf("现在是游戏初始界面");
}//开始新游戏
if (prss_down(BFS, key)) {
return 0;
}//退出
}
break;
}
FlushBatchDraw();//释放
}
}
头文件：
#ifndef MAZE_MOUSE_MAZE_H
#define MAZE_MOUSE_MAZE_H
#include<iostream>
#include<cstdio>
#include<graphics.h>
#include<string>
#include<queue>
#include<stack>
#include<easyx.h>
#include<stack>
#include<conio.h>
#include<windows.h>
#include<mmsystem.h>
#pragma comment(lib,"WinMM.Lib")//音乐静态库
using namespace std;
#define rode 30//路长
#define wall 4//墙宽度,通过直接覆盖图片来表现
#define MAXV 200
enum direction{TOP,BOTTOM,LEFT,RIGHT};
struct vnode{
int x,y;//当前矩阵位置
int val;//标记值，初始值为0，经过后为1
int repeat;//集合放入0为未放入，1为以放入
direction m;//消除方向判断
int food;//0为豆子，1为无豆子
};//地图节点
struct mazegraph{
int maze[50][50][4];//顺序为TOP,BOTTOM,LEFT,RIGHT,0为墙，1为无墙//存储墙
vnode graph[50][50];//存储节点//存储路
int width,hight;
};
struct gather{
vnode gather[MAXV];//合中存储的主要元素
int length;//当前集合的元素个数
};//集合
struct D{
int x;
int y;
};
struct region{
int x;
int y;
int w;//width
int h;//eight
char *arr;//区域作用名
}muice={1050,60 ,100,60,"BGM"},//音乐模块
NewGame={1050,200,100,60,"新游戏"}, //新游戏
game_win{450,450,400,400,},//游戏胜利
eat={1050,435,300,130},//当前豆子剩余显示
operate={1050,600,300,200},//操作说明
data_graph={1050,800,300,200},//当前坐标 //计时器
game_begin={1050,60,100,60,"开始游戏"},//开始游戏按钮
gen={1050,200,100,60,"生成地图"},//生成迷宫按钮
BFS={1050,340,100,60,"BFS寻路"},//BFS按钮//退出游戏
DFS={1050,200,100,60,"DFS寻路"};//DFS按钮 //退出游戏
IMAGE img1;//定义迷宫背景图
IMAGE img2;//定义控制台背景图
IMAGE beans_bottom;
IMAGE beans_left;
IMAGE beans_right;
IMAGE beans_top;
IMAGE *beans=&beans_right;//以上吃豆人图像
IMAGE RODE1;//迷宫格
IMAGE RODE2;//迷宫格横立
IMAGE RODE3;//迷宫格竖立
IMAGE WALL1;//横立
IMAGE WALL2;//竖立
IMAGE WALL3;//补充缺口
IMAGE End;
IMAGE FOOD;
IMAGE b;//提示路
clock_t start,END,time_1;
int CLOCK;
int X,Y;//初始实际位置
int scene;
int s=0;
int h=0;
char str[100],coordinate[15];
char arr[20];
D data[900];//遍历路径的存储
char MUICE;
queue<vnode>q;
stack<vnode>Q;
bool bfs_ok=false;//是否开始bfs寻路
bool dfs_ok=false;//是否开始dfs寻路
bool eatfood=false;//判断是否吃完豆子
void button(region reg,char *arr){
setfillcolor(BLACK);//填充颜色
setlinecolor(YELLOW);
settextcolor(WHITE);
settextstyle(0,0,"宋体");
fillroundrect(reg.x-reg.w/2, reg.y-reg.h/2,reg.x+reg.w/2,reg.y+reg.h/2, 10, 10);//创建一个圆角矩阵，前面四个为左上角和右下角坐标，而后面两个为椭圆的宽度和高度
int x1 = textwidth(arr)/2, y1 =textheight(arr)/2;
if(arr!=NULL) {
outtextxy(reg.x- x1, reg.y - y1, arr);
}
}//创建按钮图标
bool prss_down(region reg, ExMessage &msg){
int left=reg.x-reg.w/2,top=reg.y-reg.h/2,right=reg.x+reg.w/2,bottom=reg.y+reg.h/2;
if(msg.message==WM_LBUTTONDOWN && msg.x>=left && msg.x<=right && msg.y>=top && msg.y<=bottom){
return true;
}
return false;
}//判断是否左键该区域
bool mouse_position(region reg,ExMessage &msg){
int left=reg.x-reg.w/2,top=reg.y-reg.h/2,right=reg.x+reg.w/2,bottom=reg.y+reg.h/2;
if(msg.x>=left && msg.x<=right && msg.y>=top && msg.y<=bottom){
return true;
}
return false;
}//鼠标停到按钮区域
void key_cs(int &x,int &y,IMAGE *&beans ,mazegraph &G){
char key=getch();
int X=x/30;
int Y=y/30;
printf("(%d,%d)",X,Y);
G.graph[X][Y].food=1;
switch(key){
case 72:
case 'w':
case 'W':
printf("往上到达");
if(G.maze[X][Y][TOP]==1){
y -= 30;
beans=&beans_top;
}
break;
case 80:
case 's':
case 'S':
printf("往下到达");
if(G.maze[X][Y][BOTTOM]==1){
y += 30;
beans=&beans_bottom;
}
break;
case 75:
case 'a':
case 'A':
printf("往左到达");
if(G.maze[X][Y][LEFT]==1) {
x -= 30;
beans=&beans_left;
}
break;
case 77:
case 'd':
case 'D':
printf("往右到达");
if(G.maze[X][Y][RIGHT]==1){
x += 30;
beans=&beans_right;
}
break;
}
X=x/30,Y=y/30;
printf("(%d,%d)\n",X,Y);
}//键盘操作处理
int creatmaze(mazegraph & G ){
int X,Y;
int num=0;//当前食物数
X=rode/2+((30-G.width)/2)*rode;
Y=rode/2+((30-G.hight)/2)*rode;
for(int i=0;i<G.width;i++){
for(int j=0;j<G.hight;j++){
putimage(X + (G.graph[i][j].x) * rode - rode / 2, Y + (G.graph[i][j].y) * rode - rode / 2,&RODE1);//创建迷宫方格
if(scene==1 || scene==2){
}else if(scene!=1||scene!=2){
if(G.graph[i][j].val==0){
if(G.graph[i][j].food==1)
putimage(X + (G.graph[i][j].x) * rode - rode / 2, Y + (G.graph[i][j].y) * rode - rode / 2,&RODE1);//创建迷宫方格
else if(G.graph[i][j].food==0){
num++;
putimage(X + (G.graph[i][j].x) * rode - rode / 2, Y + (G.graph[i][j].y) * rode - rode / 2,&FOOD);//创建迷宫方格
}
}
if(G.graph[i][j].val==1){
putimage(X + (G.graph[i][j].x) * rode - rode / 2, Y + (G.graph[i][j].y) * rode - rode / 2,&b);//创建迷宫方格
}
}
for(int d=0;d<4;d++){
switch(d){
case TOP:
if(G.maze[i][j][d] == 0){
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode - rode/2, &WALL1);
}else{
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode - rode/2, &RODE2);
}
break;//上
case BOTTOM:
if(G.maze[i][j][d] == 0){
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode + rode/2-wall, &WALL1);
}else{
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode + rode/2-wall, &RODE2);
}
break;//下
case LEFT:
if(G.maze[i][j][d] == 0){
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode - rode/2, &WALL2);
}else{
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode - rode/2, &RODE3);
}
break;//左
case RIGHT:
if(G.maze[i][j][d] == 0){
putimage(X+(G.graph[i][j].x)*rode + rode/2-wall, Y+(G.graph[i][j].y)*rode - rode/2, &WALL2);
}else{
putimage(X+(G.graph[i][j].x)*rode + rode/2-wall, Y+(G.graph[i][j].y)*rode - rode/2, &RODE3);
}
break;//右
}
}
}
}
for(int i=0;i<=G.width;i++){
for (int j = 0; j <= G.hight; j++){
putimage(X+i*rode-wall-rode/2,Y+j*rode-wall-rode/2,&WALL3);
}
}
for(int i=0;i<G.width;i++){
int j=0;
putimage(X+(G.graph[i][j].x)*rode-rode/2 , Y+(G.graph[i][j].y)*rode-rode/2-wall , &WALL1);
j=G.hight-1;
putimage(X+(G.graph[i][j].x)*rode - rode/2, Y+(G.graph[i][j].y)*rode + rode/2, &WALL1);
}
for(int j=0;j<G.hight;j++){
int i=0;
putimage(X+(G.graph[i][j].x)*rode - rode/2-wall, Y+(G.graph[i][j].y)*rode - rode/2, &WALL2);
i=G.width-1;
putimage(X+(G.graph[i][j].x)*rode + rode/2, Y+(G.graph[i][j].y)*rode - rode/2, &WALL2);
}
//以上三个for图像修补瑕疵
return num;
}//根据邻接矩阵创建图像
void initmaze( mazegraph & G,int width,int hight){
G.width=width;
G.hight=hight;
int X,Y;//迷宫左上角的地图实际坐标
X=rode/2+((30-width)/2)*rode;
Y=rode/2+((30-hight)/2)*rode;
for(int i=0;i<width;i++){
for(int j=0;j<hight;j++){
G.graph[i][j].x=i;
G.graph[i][j].y=j;
G.graph[i][j].val=0;
G.graph[i][j].repeat=0;
G.graph[i][j].m=TOP;
G.graph[i][j].food=0;
for(int t=0;t<4;t++){
G.maze[i][j][t]=0;
}
}
}
}//初始化邻接矩阵,将地图宽度和高度设定,将节点初始话，将
void passwall(mazegraph &G,int x,int y){
gather random;
random.length = 0;
int d=0;
random.gather[4];
if (G.graph[x][y - 1].val == 1){ //top
random.gather[random.length] = G.graph[x][y - 1];
random.gather[random.length].m=TOP;
random.length++;
}
if (G.graph[x][y + 1].val == 1){
random.gather[random.length] = G.graph[x][y + 1];
random.gather[random.length].m=BOTTOM;
random.length++;
}
if (G.graph[x - 1][y].val == 1){
random.gather[random.length] = G.graph[x - 1][y];
random.gather[random.length].m=LEFT;
random.length++;
}
if (G.graph[x + 1][y].val == 1){
random.gather[random.length] = G.graph[x + 1][y];
random.gather[random.length].m=RIGHT;
random.length++;
}
printf("有 %d个选择 ",random.length);
if(random.length!=0){
d=rand()%random.length;
}
printf("随机数为：%d ",d);
direction m=random.gather[d].m;
printf("方向是：%d",m);
if(m==TOP){
G.maze[x][y][0]=1;
G.maze[x][y-1][1]=1;
}
if(m==BOTTOM){
G.maze[x][y][1]=1;
G.maze[x][y+1][0]=1;
}
if(m==LEFT){
G.maze[x][y][2]=1;
G.maze[x-1][y][3]=1;
}
if(m==RIGHT){
G.maze[x][y][3]=1;
G.maze[x+1][y][2]=1;
}
}
void prim(mazegraph &G,gather & adj){
int random = rand() % adj.length; //random为0到数组长度之间的随机一个数，以此来实现随机
int x=adj.gather[random].x,y=adj.gather[random].y; //记录存入元素的x,y
printf("随机数=%d x=%d,y=%d", random, x, y);
G.graph[x][y].val = 1;//标记以访问 //标记已经访问
passwall(G,x,y);//随机消除与之相邻遍历过方格的墙*/
printf("执行前数组长度为 %d",adj.length);
for (int i = 0; i < 4; i++){
switch (i){
case TOP:
if (y != 0 && G.graph[x][y - 1].val == 0 && G.graph[x][y-1].repeat==0){
adj.gather[adj.length] = G.graph[x][y - 1];
G.graph[x][y-1].repeat=1;
adj.length++;
printf("上 %d ", adj.length);
}
break;
case BOTTOM:
if (y!= G.hight-1 && G.graph[x][y + 1].val == 0 && G.graph[x][y+1].repeat==0){
adj.gather[adj.length] = G.graph[x][y + 1];
G.graph[x][y+1].repeat=1;
adj.length++;
printf("下 %d ", adj.length);
}
break;
case LEFT:
if (x != 0 && G.graph[x - 1][y].val == 0 && G.graph[x-1][y].repeat==0){
adj.gather[adj.length] = G.graph[x - 1][y];
G.graph[x-1][y].repeat=1;
adj.length++;
printf("左 %d ", adj.length);
}
break;
case RIGHT:
if (x != G.width-1 && G.graph[x + 1][y].val == 0 && G.graph[x+1][y].repeat==0){
adj.gather[adj.length] = G.graph[x + 1][y];
G.graph[x+1][y].repeat=1;
adj.length++;
printf("右 %d ", adj.length);
}
break;
}//载入邻近方格中未遍历元素
}
int p = random + 1;
while (p < adj.length){
adj.gather[p - 1] = adj.gather[p];
p++;
}
adj.gather[adj.length - 1] = {0};//将结构体初始化
adj.length--;
//以上将元素从集合中踢出
printf("执行完后数组长度 %d\n", adj.length);//在当前集合中随机取出一个元素，并将该元素周围满足条件的元素加入集合中
}
void bfs(mazegraph &G){
int x=q.front().x,y=q.front().y;//取出队首元素
q.pop();//出队列
if(G.maze[x][y][3]==1 && G.graph[x+1][y].val==0 ){
G.graph[x+1][y].val=1;
q.push(G.graph[x+1][y]);
data[(x+1)+y*G.width].x=x;
data[(x+1)+y*G.width].y=y;
}//向右
if(G.maze[x][y][1]==1 && G.graph[x][y+1].val==0 ){
G.graph[x][y+1].val=1;
q.push(G.graph[x][y+1]);
data[x+(y+1)*G.width].x=x;
data[x+(y+1)*G.width].y=y;
}//向下
if(G.maze[x][y][2]==1 && G.graph[x-1][y].val==0 ){
G.graph[x-1][y].val=1;
q.push(G.graph[x-1][y]);
data[(x-1)+y*G.width].x=x;
data[(x-1)+y*G.width].y=y;
}//向左
if(G.maze[x][y][0]==1 && G.graph[x][y-1].val==0 ){
G.graph[x][y-1].val=1;
q.push(G.graph[x][y-1]);
data[x+(y-1)*G.width].x=x;
data[x+(y-1)*G.width].y=y;
}//向上*/
}//bfs遍历地图并存储路径
void find(int x0,int y0,int X,int Y,mazegraph &G){
int x=X;
int y=Y;
int t=y*G.width+x;//t为记录数组位置
while(x!=x0 || y!=y0){
printf("(%d,%d)",x,y);
G.graph[x][y].val=1;
x=data[t].x;
y=data[t].y;
t=y*G.width+x;
if(x==0 && y==0){
break;
}
}
printf("\n");
for(int t=0;t<G.width*G.hight;t++){
printf("(%d,%d)",data[t].x,data[t].y);
}
}//输出路径存储数组元素
//从终点开始往前标记路径
void dfs(mazegraph& G){
int x=Q.top().x;int y=Q.top().y;//取出栈顶元素
Q.pop();
if(G.maze[x][y][3]==1 && G.graph[x+1][y].val==0 ){
G.graph[x+1][y].val=1;
Q.push(G.graph[x+1][y]);
data[(x+1)+y*G.width].x=x;
data[(x+1)+y*G.width].y=y;
}//向右
if(G.maze[x][y][1]==1 && G.graph[x][y+1].val==0 ){
G.graph[x][y+1].val=1;
Q.push(G.graph[x][y+1]);
data[x+(y+1)*G.width].x=x;
data[x+(y+1)*G.width].y=y;
}//向下
if(G.maze[x][y][2]==1 && G.graph[x-1][y].val==0 ){
G.graph[x-1][y].val=1;
Q.push(G.graph[x-1][y]);
data[(x-1)+y*G.width].x=x;
data[(x-1)+y*G.width].y=y;
}//向左
if(G.maze[x][y][0]==1 && G.graph[x][y-1].val==0 ){
G.graph[x][y-1].val=1;
Q.push(G.graph[x][y-1]);
data[x+(y-1)*G.width].x=x;
data[x+(y-1)*G.width].y=y;
}//向上*/
}
void FIND(int x0,int y0,int X,int Y,mazegraph &G) {
printf("\n");
int x=X;
int y=Y;
int t=y*G.width+x;//t为记录数组位置
printf("\n");
while(x!=x0 || y!=y0){
printf("(%d,%d)",x,y);
G.graph[x][y].val=1;
x=data[t].x;
y=data[t].y;
t=y*G.width+x;
if(x==0 && y==0){
break;
}
}
printf("\n");
for(int t=0;t<G.width*G.hight;t++) {
printf("(%d,%d)", data[t].x, data[t].y);
}
}
#endif //MAZE_MOUSE_MAZE_H素材图片：如果要使用的话记得更改程序中图片的路径
通过百度网盘分享的文件：gallery
链接：https://pan.baidu.com/s/1aNXTD-FDLMXFcwuEFqm3Sw?pwd=6666
提取码：6666