自动走迷宫小游戏
第一章课程设计目的和要求1.1 课程设计的目的
根据课堂讲授内容，做相应的自主练习，消化课堂所讲解的内容；通过调试典型例题或习题积累调试C++程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。
同时在设计的过程中发现自己的不足之处，对以前所学过的知识理解的更加深刻，掌握得更加牢固。
1.2课程设计的要求
迷宫生成。
迷宫有起点和终点，生成的迷宫需要满足从起点到终点有通路，不需要唯一；
尝试走迷宫。
迷宫中每个位置有8个方向，每个方向都有可能有障碍。
从起点出发，行进过程中遇到岔路口需要记录，选择一条路继续，如果此路不通，能够回溯到刚才的岔路口继续，直到走到终点；
记录走迷宫成功的路线到文本文件。
第二章课程设计任务内容
选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。
假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。
如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。
输出迷宫原型图、迷宫路线图以及迷宫行走路径。
如果迷宫为死迷宫，则只输出迷宫原型图。
第三章详细设计说明
3.1模块描述
整个实验将实现迷宫路径的查找，并图形化输出其中最短的路径，迷宫使用二维数组存放。
机器通过穷举法解出迷宫的路径，最后输出。
整个实验分为以下几个模块：
创建模块。
本实验的创建包含两方面，迷宫的定义和脚步的初始化。
迷宫的定义通过修改二维数组实现，最终创建一个确定的迷宫。
脚步的初始化由程序自行完成.
路径查找模块。
路径查找核心分为两个部分：路径查找、更优解替换。
路径查找包括可通性检查、脚步前进、脚步后退三个模块。
可通性检查会检查当前脚步的四个方向是否有通路。
脚步前进可以在有通路的情况下抵达下一个点，并记录在脚步双向链表中。
脚步后退使在当前脚步无路的情况下后退一步，并转向其他方向，同时删除最后一个脚步。
可通性检查。
可通性检查用来判断指定的方向是否可以通过。
需要判断两方面内容，即下一点是否有障碍和下一点是否已包含在了已有路径之中。
若同时满足无障碍和无包含条件，则可以通过。
否则不能通过。
脚步前进。
下一点若经过检查可以通过，则通过move()函数完成前进。
“前进”的实现有两方面，第一方面，将新脚步纳入双向链表中，另一方面，在迷宫数组中将本步坐标所指标记为“已走”。
脚步后退。
若本步四个方向都不能行走，则通过back()函数退后。
退后包括两方面，一方面把链表中最后一个节点抛弃，当前脚步指向倒数第二个节点。
另一方面，将迷宫数组中已抛弃节点指向的元素重新标记为“未走”，以便进行其他路径的寻路操作时可以顺利通过。
输出模块。
实现迷宫解的图形化显示。
其他模块。
格式化模块，用于迷宫求解后的处理。
迷宫数组改写模块，按照求解的结果改写迷宫二维数组，以满足最终输出需要。
功能模块图如下图所示
图3—1功能模块图
3.2函数说明
1.data（）
函数原型void data(int m,int n)
data（）函数用于当用户输入的不是规整的m行n列的迷宫，用来生成规则的数字迷宫
2.print_maze（）
函数原型void print_maze(int m,int n)
print_maze（）函数用于打印迷宫外壳
3.result_maze（）
函数原型void result_maze(int m,int n)
result_maze（）函数用于打印输出迷宫的星号路径
4.visit（）
函数原型void visit(int row,int col,int maze[51][51])
visit()函数用于访问迷宫矩阵中的节点
5.)
) 这个是打印输出迷宫的星号路径
{
int i,j;
cout<<"迷宫通路(用☆表示)如下所示：\n\t";
for(i=0;i<m;i++)
{
cout<<"\n";
for(j=0;j<n;j++)
{
if(maze[i][j]==0||maze[i][j]==2) 2是队列中访问过的点
cout<<"□";
if(maze[i][j]==1)
cout<<"■";
if(maze[i][j]==3) 3是标记的可以走通的路径
cout<<"☆";
}
}
}
void enqueue(struct point p) 迷宫中队列入队操作
{
queue[tail]=p;
tail++; 先用再加，队列尾部加1
}
struct point dequeue() 迷宫中队列出队操作，不需要形参，因此用结构体定义
{
queue[ ) 路径求解
{
X=1; 初始值定为1
struct point p={0,0,-1}; 定义入口节点
if(maze[p.row][p.col]==1) 入口为1时，迷宫不可解
{
cout<<"\n============================================ ===\n";
cout<<"此迷宫无解\n\n";
X=0;
return 0;
}
maze[p.row][p.col]=2; 标记为已访问
enqueue(p); 将p 入队列
while(!is_empty())
{
p=dequeue();
if((p.row==m-1)&&(p.col==n-1)) 当行和列为出口时跳出
3.5 限制条件
在输入值时必须按照程序所规定的输入，否则将运行错误或无法运行。
第四章软件使用说明
4.1软件使用说明及出现的问题
运行环境为 Microsoft Visual C++6.0
输出界面有三个选项，1为手动生成迷宫，2为自动生成迷宫，3为推出程序。
当程序运行时，设cycle为0，当选择3退出程序时，cycle为-1。
选择自动生成迷宫时，只需输入想要迷宫的行数.列数。
在输出界面上，起初，仅仅是将最终结果展示，而无矩阵的规范输出，即如果使用者手输出迷宫时，并未整齐的输入迷宫，如果此时显示迷宫最后的路径，使使用者不易清晰的看出路径而难以理解。
基于站在使用者的角度，加入了data函数，实现了数组、符号、数位路径、字符路径共同出现的最终界面，并在输出时添加相应的箭头指
示，在输出的迷宫图时将最外层加入的围墙用“▢”表示，经多次修改，使得输出界面整洁大方。
4.2运行结果
图4—1欢迎界面
图4—1测试结果—迷宫有解
图4—1测试结果—迷宫有解
第五章课程设计心得与体会在程序编写的过程中，发现了很多问题及错误。
例如，程序刚形成雏形时，经测试，程序只能实现8*8的迷宫矩阵寻路，并且会出现寻路时跳出迷宫的情况。
因此，程序员在此基础上，将迷宫矩阵数组
由原来的maze[10][10]改为maze[N+2][M+2]，并在相应函数上加以大
量改动，最终使本程序实现了程序本身范围内的任意N*M迷宫矩阵组合的寻路求解。
在输出界面上，起初，仅仅是将最终结果展示，而无矩阵的规范输出，即如果使用者手输出迷宫时，并未整齐的输入迷宫，如果此时显示迷宫最后的路径，使使用者不易清晰的看出路径而难以理解。
基于站在使用者的角度，加入了data函数，实现了数组、符号、数位路径、字符路径共同出现的最终界面，并在输出时添加相应的箭头指示，在输出的迷宫图时将最外层加入的围墙用“▢”表示，经多次修改，使得输出界面整洁大方。
在最开始判断搜索方向的时候，我们列出的八个方向并未按照一定顺序搜索，此时就会出现错误，后来采用一定顺序来完成迷宫的搜索，因为设定迷宫的入口在左上方，出口在右下方，所以采用顺时针方向比采用逆时针方向能最先找出最短路径。
所以最后采用了顺时针的搜索方向，即沿北、东北、东、东南、南、西南、西、西北八个方向搜索。
在测试输出结果方面，出了一个困扰我们一阵时间的问题，在以5*7自动生成迷宫矩阵的测试过程中，几乎每隔几次都会出现一次这样类似的问题（见下图），在下图的输出界面
图5—1
以及字符展示界面中，经过简单的分析，便可以得出最后通往出口的道路，但在程序判断并输出路径后，在图中可以看到：五角星所标记的走过的路，在出口处出现了错误。
但是此程序手动输入的时候不会出现任何错误，所以问题锁定在自动生成迷宫函数中。
在此，我们列出当时的自动生成迷宫函数：
void automatic_maze(int m,int n)
{
int i,j;
cout<<"\n迷宫生成中……\n\n";
system("pause");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=rand()%2;
maze[0][0]=0;
maze[i-1][j-1]=0;
}
在修改过程中，反复分析了各个函数后将问题锁定在自动生成函数处。
观察此函数，发现“maze[i-1][j-1]=0；”是导致问题的最终所在。
该语句的初衷是将迷宫矩阵中最初一个数判定为0，防止出现迷宫出口不通的情况。
在这儿以5*7迷宫为例，经过分析，当跳出for循环时，i=5，j=6，而要改变的数是maze[5][7]，而非maze[5][6]，这也就是导致上图所示结果的原因，将该语句改为maze[m-1][n-1]，问题解决。
附录一：参考文献
[1]、谭浩强，C++程序设计，北京：清华大学出版社出版，2004年6月
[2]、谭浩强，C++程序设计题解与上机指导，北京：清华大学出版社
出版，2005年3月
[3]、姜灵芝、余健，C语言课程设计案例精编，北京：清华大学出版
社，2008年1月
[4]、严华峰，Visual C++课程设计案例精编，北京：中国水利水电出
版社出版，2002年
附录二：源代码
#include<stdlib.) 手动生成迷宫
{
int i,j;
cout<<endl;
cout<<"请按行输入迷宫，0表示通路，1表示障碍:"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>maze[i][j];
}
}
void automatic_maze(int m,int n) 自动生成迷宫
{
int i,j;
cout<<"\n迷宫生成中……\n\n";
system("pause");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=rand()%2; 随机生成0、1
maze[0][0]=0; 将开始和结束位置强制为0，保证有可能出来迷宫
maze[m-1][n-1]=0;
}
void data(int m,int n)
{ 当用户输入的不是规整的m行n列的迷宫，用来生成规则的数字迷宫
int i,j;
cout<<endl;
cout<<"根据您先前设定的迷宫范围"<<endl;
cout<<endl;
cout<<" 我们将取所输入的前"<<m*n<<"个数生成迷宫"<<endl;
cout<<"\n数字迷宫生成结果如下:\n\n";
cout<<"迷宫入口\n";
cout<<"↓";
for(i=0;i<m;i++)
{
cout<<"\n";
for(j=0;j<n;j++)
{
if(maze[i][j]==0)
cout<<" 0";
if(maze[i][j]==1)
cout<<" 1";
}
}
cout<<"→迷宫出口\n";
}
void print_maze(int m,int n)
{ 打印迷宫外壳int i,j,k;
cout<<"\n字符迷宫生成结果如下:\n\n";
cout<<"迷宫入口\n";
cout<<" ↓";
cout<<endl;
cout<<"▲ ";生成上外壳
for(k=0;k<n;k++)
{
cout<<"▲";这两个黑三角用来生成顶部外壳
}
for(i=0;i<m;i++)
{
cout<<"\n"; 生成左外壳
cout<<"▲";
for(j=0;j<n;j++)
{
if(maze[i][j]==0) printf("□");
if(maze[i][j]==1) printf("■");
}
cout<<"▲";生成右外壳}
cout<<endl;
for(k=0;k<n;k++)
{
cout<<"▲";
}
cout<<" ▲\n"; 生成底部外壳
for(i=0;i<n;i++)
{ cout<<" ";}
cout<<"↓\n";
for(i=0;i<n;i++)
{ cout<<" ";}
cout<<"迷宫出口\n";
}
void result_maze(int m,int n) 这个是打印输出迷宫的星号路径
{
int i,j;
cout<<"迷宫通路(用☆表示)如下所示：\n\t";
for(i=0;i<m;i++)
{
cout<<"\n";
for(j=0;j<n;j++)
{
if(maze[i][j]==0||maze[i][j]==2) 2是队列中访问过的点
cout<<"□";
if(maze[i][j]==1)
cout<<"■";
if(maze[i][j]==3) 3是标记的可以走通的路径cout<<"☆";
}
}
}
void enqueue(struct point p) 迷宫中队列入队操作
{
queue[tail]=p;
tail++; 先用再加，队列尾部加1 }
struct point dequeue() 迷宫中队列出队操作，不需要形参，因此用结构体定义
{
queue[ ) 路径求解
{
X=1; 初始值定为1
struct point p={0,0,-1}; 定义入口节点
if(maze[p.row][p.col]==1) 入口为1时，迷宫不可解{
cout<<"\n===============================================\n";
cout<<"此迷宫无解\n\n";
X=0;
return 0;
}
maze[p.row][p.col]=2; 标记为已访问
enqueue(p); 将p入队列while(!is_empty())
{
p=dequeue();
if((p.row==m-1)&&(p.col==n-1)) 当行和列为出口时跳出
break;
定义8个走位方向
if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+0)<n))&&(maze[p.row-1][p.col+0]==0))
visit(p.row-1,p.col+0,maze); 北
if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+1)<n))&&(maze[p.row-1][p.col+1]==0))
visit(p.row-1,p.col+1,maze); 东北
if((((p.row+0)<m)&&((p.col+1)<n))&&(maze[p.row+0][p.col+1]==0))
visit(p.row+0,p.col+1,maze); 东
if((((p.row+1)<m)&&((p.col+1)<n))&&(maze[p.row+1][p.col+1]==0))
visit(p.row+1,p.col+1,maze); 东南
if((((p.row+1)<m)&&((p.col+0)<n))&&(maze[p.row+1][p.col+0]==0))
visit(p.row+1,p.col+0,maze); 南
if((((p.row+1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+1][p.col-1]==0))
visit(p.row+1,p.col-1,maze); 西南
if((((p.row+0)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+0][p.col-1]==0))
visit(p.row+0,p.col-1,maze); 西
if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row-1][p. col-1]==0))
visit(p.row-1,p.col-1,maze); 西北
}
if(p.row==m-1&&p.col==n-1) 如果当前矩阵点是出口点，输出路径
{
cout<<"\n========================================================= =========\n";
cout<<"迷宫路径为：\n";
cout<<"出口"<<endl;
cout<<" "<<"↑"<<endl;
printf("(%d,%d)\n",p.row+1,p.col+1);
cout<<" "<<"↑"<<endl;
maze[p.row][p.col]=3; 逆序将路径标记为3
while(p.predecessor!=-1)
{
p=queue[p.predecessor];
printf("(%d,%d)\n",p.row+1,p.col+1);
cout<<" "<<"↑"<<endl;
maze[p.row][p.col]=3;
}
cout<<"入口"<<endl;
}
else
{
cout<<"\n=============================================================\ n";
cout<<"此迷宫无解！\n\n";
X=0;
}
return 0;
}
{
int i,m,n,cycle=0;
while(cycle!=(-1))
{
cout<<"************************************************************************ ********\n";
cout<<" 欢迎进入迷宫求解系统\n";
cout<<endl;
cout<<" 设计者:杨晓辉（计算机092202H班）\n";
cout<<"************************************************************************ ********\n";
cout<<" ☆手动生成迷宫请按：1\n";
cout<<" ☆自动生成迷宫请按：2\n";
cout<<" ☆退出请按：3\n\n";
cout<<"************************************************************************ ********\n";
cout<<"\n";
cout<<"请选择你的操作：\n";
cin>>i;
switch(i)
case 1:
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
while((m<0||m>49)||(n<0||n>49))
{
cout<<"\n抱歉，你输入的行列数超出预设范围(),请重新输入：\n\n";
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
}
);
data(m,n);
print_maze(m,n);
path(maze,m,n);
if(X!=0) result_maze(m,n); 当X不为0时，有解，调用输出路径函数
cout<<"\n\nPress Enter Contiue!\n";
getchar();
while(getchar()!='\n'); 接受一个输入，当为回车时执行break跳出，否则一直执行接受数据
break;
case 2:
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
while((m<0||m>49)||(n<0||n>49))
{
cout<<"\n抱歉，你输入的行列数超出预设范围(),请重新输入：\n\n";
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
}
automatic_maze(m,n);
data(m,n);
print_maze(m,n);
path(maze,m,n);
if(X!=0) result_maze(m,n);
cout<<"\n\nPress Enter Contiue!\n";
getchar();
while(getchar()!='\n');
break;
case 3:
cycle=(-1);break;
default:
cout<<"\n";cout<<"你的输入有误!\n";
cout<<"\nPress Enter Contiue!\n";
getchar();
while(getchar()!='\n');
break;
}
}
}。
