综合实验报告——迷宫（maze）

迷宫（maze）"/>

综合实验报告——迷宫（maze）

综合实验报告——迷宫（maze）

项目简介：

• 代码量小，注释详细
• 具有图形化页面，可以自定义色彩
• 实现了搜索过程的可视化
• 可以随机生成一定有通路的迷宫，并且可以进行相应的操作，比如移动等
• 添加了一些额外的操作，比如重新生成迷宫，寻找最短距离的通路
  
  ……

代码讲解：

注意：这里导进了第三方库easyx图形库，所以必须得先导进去才有效果

  步骤：请下载最新版 EasyX 安装程序，直接运行，并跟随提示安装即可。

  在生成迷宫过程中采用了bfs（广度优先），生成通路时也是采用了bfs，利用bfs的特性就一定可以找到最短距离的通路。

   生成： 利用比较简单的bfs生成简易迷宫，迷宫里面分成了许多的单元格，每个单元格里面记录了五个数据，分别是当前单元格的状态，上下左右单元格的状态（是否能走向这四个方向），利用随机法，每一次只打通一面，且打通的面肯定是联通的，这也保证了一定有路。在生成迷宫中比较精华的是设置了带访问点，且随机去访问这些待访问点且只打通一面，从而产生了迷宫效果。

  **生成通路：**同样也是利用bfs进行搜索，上述已经说过了一定有解，所利用bfs就一定可以生成一条最短的通路。

效果展示：

码源：

由于代码量不多就直接发出来了！

#include<easyx.h>
#include<vector>//可以访问的边
#include<stdlib.h>
#include<time.h>
#include<conio.h>
#include<graphics.h>
#include <stdio.h>#define MAP_ROW 20	/*25*/
#define MAP_COL 25	/*45*/#define OUT_ROW MAP_ROW - 1
#define OUT_COL MAP_COL - 1struct Node
{int flag;			//表示关键结点是否访问过 0:未访问 1:已访问 2:待访问// 3:人物 4:目的地bool left, right, top, buttom;	//表示这个节点周围的四堵墙 0:不可通过的墙 1:可通过的空地
};
//搜索中所用来保存节点的
struct node{int x ; int y; int pre;
}query[MAP_ROW*MAP_COL*4];int map_v[MAP_ROW][MAP_COL] = { 0 };//0-没访问过，1-已经访问过，2-最短路int index_Row, index_Col;			//人所在行，列void init(Node map[][MAP_COL]);int bfs(int x, int y);void drawMap(Node map[][MAP_COL]);void play(Node map[][MAP_COL]);void borderThrough(Node map[][MAP_COL], const COORD node);int judg(Node map[][MAP_COL])//判断是否到达了终点
{if (map[OUT_ROW][OUT_COL].flag == 3)return 1;elsereturn 0;
}
int main()
{srand((unsigned)time(NULL));initgraph(MAP_COL * 45, MAP_ROW * 30);      //设置了整张地图的规格Node map[MAP_ROW][MAP_COL] = { 0 };			//每个墙 都没打通的  每个结点 都是没有访问过int map_v[MAP_ROW][MAP_COL] = { 0 };init(map);							/*初始化地图*/drawMap(map);while (1){play(map);drawMap(map);if (judg(map)){MessageBox(GetHWnd(), L"恭喜你赢了", L"Vectory", MB_OK);memset(map, 0, sizeof(Node) * MAP_ROW * MAP_COL);init(map);drawMap(map);}}getchar();closegraph();return 0;
}
int bfs(int x, int y,const Node map[][MAP_COL])//**存在bug
{int first = 1, second = 1;//模拟队列map_v[x][y] = 1;query[second].pre = -1;query[second].x = x;query[second].y = y;second++;while (second > first) {int xx = query[first].x, yy = query[first].y;//行，列map_v[xx][yy] = 1;if (map[xx][yy].top == 1) {//上面可走if (xx >= 1 && xx <= MAP_ROW - 1 && yy >= 0 && yy <= MAP_COL-1&&map_v[xx-1][yy]==0) {query[second].pre = first;query[second].x = xx - 1;query[second++].y = yy;}}if (map[xx][yy].buttom == 1){//下面可以走if (xx >=0 && xx <= MAP_ROW - 2 && yy >= 0 && yy <= MAP_COL - 1&&map_v[xx + 1][yy] == 0) {query[second].pre = first;query[second].x = xx+1;query[second++].y = yy;if (xx == MAP_ROW - 2 && yy == MAP_COL - 1) { return second-1; }//走到了终点,并且返回头指针}}if (map[xx][yy].left == 1){//左面可以走if (xx >= 0 && xx <= MAP_ROW - 1 && yy >= 1 && yy <= MAP_COL - 1 && map_v[xx][yy-1] == 0) {query[second].pre = first;query[second].x = xx;query[second++].y = yy-1;}}if (map[xx][yy].right == 1){//右面可以走if (xx >= 0 && xx <= MAP_ROW - 1 && yy >= 0 && yy <= MAP_COL - 2 && map_v[xx][yy+1] == 0) {query[second].pre = first;query[second].x = xx;query[second++].y = yy+1;if (xx == MAP_ROW - 1 && yy == MAP_COL - 2) { return second-1; }//走到了终点,并且返回头指针}}first++;}return 1;//一般情况下是不会出现这个结果的
}
void ans(int start) //传入first头指针
{int x = query[start].x, y = query[start].y;map_v[x][y] = 2;if (query[start].pre != -1) {ans(query[start].pre);}return;
}
void play(Node map[][MAP_COL])
{/*******玩家操作*******/char dir;/******找到小人******/for (int Row = 0; Row < MAP_ROW; Row++){for (int Col = 0; Col < MAP_COL; Col++){if (map[Row][Col].flag == 3){index_Row = Row;index_Col = Col;}}}dir = _getch();//从键盘获取值switch (dir){case 'q':					//寻找通路的方法setfillcolor(RGB(255,165,0));//实现按钮闪变solidrectangle(25 * 40, 100, 25 * 45, 150);settextstyle(18, 0, _T("楷体"));settextcolor(RGB(255,106,106));outtextxy(25 * 40 + 8, 115, _T("寻找通路"));ans(bfs(0, 0,map));drawMap(map);break;case 'r':					// 重新生成迷宫setfillcolor(RGB(255, 165, 0));solidrectangle(25 * 40, 200, 25 * 45, 250);settextstyle(18, 0, _T("楷体"));settextcolor(RGB(255, 106, 106));outtextxy(25 * 40 + 8, 225, _T("重新生成"));Sleep(100);memset(map, 0, sizeof(Node) * MAP_ROW * MAP_COL);init(map);			/*初始化地图*/drawMap(map);break;case 'w':case 72://判断人物所在点上 top 是否可以通行if (map[index_Row][index_Col].top == 1 && index_Row >= 1){map[index_Row][index_Col].flag = 1;map[index_Row - 1][index_Col].flag = 3;}break;case 's':case 80://判断人物所在点 buttom 是否可以通行if (map[index_Row][index_Col].buttom == 1 && index_Row < MAP_ROW - 1){map[index_Row][index_Col].flag = 1;map[index_Row + 1][index_Col].flag = 3;}break;case 'a':case 75://判断人物所在点 left 是否可以通行if (map[index_Row][index_Col].left == 1 && index_Col >= 1){map[index_Row][index_Col].flag = 1;map[index_Row][index_Col - 1].flag = 3;}break;case 'd':case 77://判断人物所在点 right 是否可以通行if (map[index_Row][index_Col].right == 1){map[index_Row][index_Col].flag = 1;map[index_Row][index_Col + 1].flag = 3;}break;}
}void init(Node map[][MAP_COL])
{setfillcolor(WHITE);		//填充颜色 白色setlinecolor(BLACK);		//线条颜色  红色setlinestyle(PS_SOLID, 2);	//线条风格//对查询表进行重置for (int i = 0; i < MAP_ROW * MAP_COL * 4; i++) {query[i].pre = 0;query[i].x = 0;query[i].y = 0;}//先选中一个结点  最左上角  arr[0][0]map[0][0].flag = 1;			//这个节点已经访问过for (int i = 0; i < MAP_ROW; i++) {for (int j = 0; j < MAP_COL; j++) {map_v[i][j] = { 0 };//对查询访问数组进行初始化}}COORD waitForVisit[MAP_COL * MAP_ROW];	//存放待访问的结点int len = 0;					//map里面的坐标的个数waitForVisit[len++] = { 1, 0 };		//下方的结点 可以访问map[1][0].flag = 2;					//待访问waitForVisit[len++] = { 0, 1 };		//右边的结点 可以访问map[0][1].flag = 2;					//待访问int m;while (len > 0){//随机选取其中的一个结点  进行访问m = rand() % len;	//从可以访问的结点中随机取一个/*打通这个节点  把这个节点相邻的结点放到map里面*/borderThrough(map, waitForVisit[m]);	//borderThrough作用:打通waitForVisit[m]节点的任意一面（上下左右任意一面）map[waitForVisit[m].X][waitForVisit[m].Y].flag = 1;		/*已经访问过这个节点*//*周围的四个节点(如果有) 全部放到map里面*/if (waitForVisit[m].X - 1 >= 0 && map[waitForVisit[m].X - 1][waitForVisit[m].Y].flag == 0){//如果上方的结点没有访问过   设置为待访问 并且把这个位置放到map里面map[waitForVisit[m].X - 1][waitForVisit[m].Y].flag = 2;waitForVisit[len++] = { waitForVisit[m].X - 1, waitForVisit[m].Y };}if (waitForVisit[m].X + 1 < MAP_ROW && map[waitForVisit[m].X + 1][waitForVisit[m].Y].flag == 0){//下map[waitForVisit[m].X + 1][waitForVisit[m].Y].flag = 2;waitForVisit[len++] = { waitForVisit[m].X + 1, waitForVisit[m].Y };}if (waitForVisit[m].Y - 1 >= 0 && map[waitForVisit[m].X][waitForVisit[m].Y - 1].flag == 0){//左map[waitForVisit[m].X][waitForVisit[m].Y - 1].flag = 2;waitForVisit[len++] = { waitForVisit[m].X, waitForVisit[m].Y - 1 };}if (waitForVisit[m].Y + 1 < MAP_COL && map[waitForVisit[m].X][waitForVisit[m].Y + 1].flag == 0){//右map[waitForVisit[m].X][waitForVisit[m].Y + 1].flag = 2;waitForVisit[len++] = { waitForVisit[m].X, waitForVisit[m].Y + 1 };}//map[m]已经访问过  从map里面删掉就可以if (m == len - 1)//没有可以添加的待访问点len--;else{ //对已经访问过的节点进行更新waitForVisit[m] = waitForVisit[len - 1];len--;}drawMap(map);}map[0][0].flag = 3;							//初始化人物map[MAP_ROW - 1][MAP_COL - 1].flag = 4;		//初始目的地}void drawMap(Node map[][MAP_COL])
{BeginBatchDraw();cleardevice();									//清屏操作for (int i = 0; i < MAP_ROW; ++i){for (int j = 0; j < MAP_COL; ++j){if (map[i][j].flag == 0)				//没有访问过这个节点{setfillcolor(WHITE);if (map_v[i][j] == 2) {setfillcolor(RGB(255, 48, 48));}}else if (map[i][j].flag == 1)			//访问过{setfillcolor(RGB(255, 193, 193));if (map_v[i][j] == 2) {setfillcolor(RGB(255, 48, 48));}}else if (map[i][j].flag == 2)			//待访问{setfillcolor(BLUE);if (map_v[i][j] == 2) {setfillcolor(RGB(255, 48, 48));}}else if (map[i][j].flag == 3)			//人物                          {setfillcolor(RED);}else if (map[i][j].flag == 4)			//目的地{setfillcolor(GREEN);}solidrectangle(j * 40, i * 30, j * 40 + 39, i * 30 +29);	//绘制if (map[i][j].top == 0)				//没有打通{line(j * 40, i * 30, j * 40 + 39, i * 30);}if (map[i][j].buttom == 0){line(j * 40, i * 30 + 29, j * 40 + 39, i * 30 + 29);}if (map[i][j].left == 0){line(j * 40, i * 30, j * 40, i * 30 + 29);}if (map[i][j].right == 0){line(j * 40+39, i * 30, j * 40 + 39, i * 30 + 29);}}}setfillcolor(RGB(240,255,255));solidrectangle(25 * 40, 0, 25 * 45, 20 * 30-1);setbkmode(TRANSPARENT);//设置当前设备图案填充和文字输出时的背景模式rectangle(25 * 40, 100, 25 * 45, 150);rectangle(25 * 40, 200, 25 * 45, 250);RECT r = {25 * 40, 300, 25 * 45, 500};setfillcolor(RGB(238,238,209));solidrectangle(25 * 40, 100, 25 * 45, 150);solidrectangle(25 * 40, 200, 25 * 45, 250);settextstyle(18, 0, _T("楷体"));settextcolor(RGB(0,0,0));outtextxy(25 * 40 + 8, 115, _T("寻找通路(q)"));outtextxy(25 * 40 + 8, 225, _T("重新生成(r)"));drawtext(_T("* * * * *\n(要在英文输入状态下）\n按压方向箭头进行移动\n\n按压r,q可以进行相应操作"), &r, DT_WORDBREAK);EndBatchDraw();//结束绘画，并呈现出来
}void borderThrough(Node map[][MAP_COL], const COORD node)
{int flag = 0;int dir;do{//判断周围的结点 有哪些是可以打通的   可以打通就打通dir = rand() % 4;switch (dir){case 0:if ((node.X + 1 < MAP_ROW) && map[node.X + 1][node.Y].flag == 1)//下{map[node.X + 1][node.Y].top = 1;		//打通两堵墙map[node.X][node.Y].buttom = 1;flag = 1;break;}case 1:if ((node.Y - 1 >= 0) && map[node.X][node.Y - 1].flag == 1)//左{map[node.X][node.Y - 1].right = 1;		//打通两堵墙map[node.X][node.Y].left = 1;flag = 1;break;}case 2:if (node.Y + 1 < MAP_COL && map[node.X][node.Y + 1].flag == 1)//右{map[node.X][node.Y + 1].left = 1;		//打通两堵墙map[node.X][node.Y].right = 1;flag = 1;break;}case 3:if ((node.X - 1 >= 0) && map[node.X - 1][node.Y].flag == 1)//上{map[node.X - 1][node.Y].buttom = 1;map[node.X][node.Y].top = 1;flag = 1;break;}}} while (!flag);
}

欢迎大家访问我的个人博客

本文章到此结束！感谢阅读！