前几天给大家介绍了“一行matlab代码可以做哪些匪夷所思的事情”，今天小编带给大家一款酷炫的私人订制版迷宫游戏。这款迷宫游戏包含以下功能：随机生成迷宫地图通过键盘手动求解生成的迷宫MATLAB自动求解生成的迷宫目前主流的生成迷宫的算法有：深度优先搜索算法(也称递归回溯算法)、Prim算法、递归分割算法，和Wilson算法(Loop-erased random walk)。今天只给大家介绍递归回溯算法生成迷宫。首先，我们来看一下深度优先算法的基本内容。
一、深度优先搜索算法
首先来看一下维基百科上对深度优先搜索算法的介绍：深度优先搜索算法(Depth-First-Search，DFS)[1]是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。通俗的说，深度优先搜索算法的基本思想就是：从起点开始随机走，走不通了就返回上一步，然后从下一个能走的地方再开始随机走。深度优先搜索算法的算法框架如下：Step 1.设置一个起点。将起点作为当前迷宫单元，并标记为已访问Step 2.当还存在未标记的迷宫单元时，进行循环(1)如果当前迷宫单元有未被访问过的相邻的迷宫单元①随机选择一个未访问的相邻迷宫单元②将当前迷宫单元入栈③移除当前迷宫单元与相邻迷宫单元的墙④标记相邻迷宫单元已访问，并用它作为当前迷宫单元(2)如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空①栈顶的迷宫单元出栈②令其成为当前迷宫单元下面我们通过一个简单的栗子，来理解一下深度优先搜索算法。如下图所示，从图中的V0(顶点)出发，是否存在一条路径长度为4的搜索路径。显然，可以直观地看出来，所求的搜索路径即：V0->V3->V5->V6。下面我们使用深度优先搜索算法来求解该问题。(1)从顶点V0开始，此时路径长度为1<4，继续搜索。由图可知V0的相邻节点中有V1和V3两个可选节点，这里不妨取V1作为下一个搜索节点。(2)从V0的相邻节点V1开始，此时路径长度为2<4，继续搜索。由图可知V1只有V2一个相邻的节点可供选择。(3)从V1的相邻节点V2开始，此时路径长度为3<4，继续搜索。由图可知V2已经没有未访问的节点了(V0为起始节点，已经访问过)，因此退回上一节点V1继续搜索。(4)由图可知 V1的相邻节点中，除V2外已经没有未访问的节点，因此退回上一节点V0继续搜索。(5)从顶点V0重新开始，选择V0的相邻节点V3作为下一个搜索节点。(6)从V0的相邻节点V3开始，此时路径长度为2<4，继续搜索。这里不妨去V3的相邻节点V4作为下一个搜索节点。(7)从V3的相邻节点V4开始，此时路径长度为3<4，继续搜索。由图可知V4已经没有未访问的节点了，因此退回上一节点V3继续搜索。(8)从节点V3重新开始，选择V3的相邻节点V5作为下一个搜索点。(9)从V3的相邻节点V5开始，此时路径长度为3<4，继续搜索。由图可知V5只有V6一个未访问的相邻节点，因此选择V6作为一下搜索点。此时，路径长度为4，且V6已经没有未访问的节点，因此已找到解，结束搜索。以上即为深度优先搜索算法求解该简单图的详细步骤，相信大家通过这个简单的栗子对深度优先搜索算法有了一定的认识，下面我们就进入正题——使用MATLAB制作迷宫游戏。二、生成迷宫游戏的地图
借助前面介绍的深度优先搜索算法可以生成迷宫游戏的地图。深度优先搜索算法构建迷宫的思想就是，每次把新找到的未访问迷宫单元作为起始点，寻找与其相邻的未访问过的迷宫单元，直到所有的单元都被访问到。也就是从起点开始随机走，走不通了就返回上一步，从下一个能走的地方再开始随机走。首先，我们生成迷宫游戏的地图的数据矩阵，MATLAB代码如下：function map=maze(a,b)
map=zeros(a,b);
map(2,1)=1;
map(a-1,b)=1;
p=zeros(1,4);
q=zeros(1,a*b);
i=2;j=2;
x=0;
while ~isempty(find(map(2:2:a,2:2:b)==0,1))
t=0;
map(i,j)=1;
if i>2
if map(i-2,j)==0
t=t+1;p(t)=1;
end
end
if i
if map(i+2,j)==0
t=t+1;p(t)=4;
end
end
if j>2
if map(i,j-2)==0
t=t+1;p(t)=2;
end
end
if j
if map(i,j+2)==0
t=t+1;p(t)=3;
end
end
if t==0
q(x)=5-q(x);
else
x=x+1;
q(x)=p(randi(t));
end
switch q(x)
case 1
i=i-2;map(i+1,j)=1;
case 4
i=i+2;map(i-1,j)=1;
case 2
j=j-2;map(i,j+1)=1;
case 3
j=j+2;map(i,j-1)=1;
end
if t==0
x=x-1;
end
后台回复关键词【迷宫】获得完整代码说明：map矩阵中的0元素代表未打通的墙壁，其余元素代表可行域(即通道)。通过运行上述代码，可以生成迷宫游戏的地图数据矩阵，下面我们来看一下如何进行数据可视化，即绘制迷宫游戏的地图。MATLAB绘制迷宫游戏主要借助line函数，因此，先来看一下line函数的主要功能，在MATLAB的命令窗口中输入help line可以看到如下说明：由帮助文件可以看出来line函数适用于绘制线条的。看到这可能有很多小伙伴有疑问，plot也是用来画图的，为什么不用plot函数呢？为了回答这个问题，同样的，在MATLAB的命令窗口中输入help plot可以看到如下说明：通过帮助文件还是可以看到这两个函数是有一些区别的，下面我们详细对比一下这两个函数：line函数与plot函数绘图对比图大家还可以根据帮助文件仔细对比一下两个函数的区别。下面回归正题，使用MATLAB绘制迷宫地图，MATLAB代码如下：function time=map_draw(map,str)global nar FIGURE;[e,f]=size(map);set(FIGURE,'position',get(0,'ScreenSize'));axis offset(gca,'YDir','reverse')if nar<1map(map==2)=3;endfor i=1:efor j=1:fif map(i,j)==0if nar<1if(mod(i,2)>mod(j,2))line([max(j-1,1),min(j+1,f)],[i,i]);elseif(mod(i,2)line([j,j],[max(i-1,1),min(i+1,e)]);endelseif map(i,max(j-1,1))==0&&j>1line([max(j-1,1),j],[i,i]);endif map(i,min(j+1,f))==0&&jline([j,min(j+1,f)],[i,i]);endif map(max(i-1,1),j)==0&&i>1line([j,j],[max(i-1,1),i]);endif map(min(i+1,e),j)==0&&iline([j,j],[i,min(i+1,e)]);endendelseif map(i,j)==2 || map(i,j)==3imagesc(map)colormap([0,0,0;1,1,1;0,1,0;1,0,0])axis offendendendg=gcf;set(g.Children,'position',[0.1 0.1 0.8 0.8])set(g,'position',get(0,'ScreenSize'));text(0.4*f,-1,str);后台回复关键词【迷宫】获得完整代码下面使用上述函数绘制10×10的迷宫地图，来看一下效果如何，并对生成的迷宫图做一些说明。随机生成的10×10的迷宫地图如上图所示，这款迷宫游戏中有如下默认设置：左上角为迷宫入口，右下角为迷宫出口，黑色实线为迷宫的墙壁，白色空白区域为迷宫通道。
三、求解迷宫游戏
这里我们使用普通的搜索路径方法求解迷宫游戏，大概思路如下：从起点开始随机走，如果走不通了，则保存当前路径；然后逐步后退，直到能继续随机走；最终走完所有格点，则停止程序。MATLAB代码如下：function [map,dist]=maze_sove(map)
[a,b]=size(map);model=map;h=zeros(3);h([2,4,6,8])=1;t=0;while 1sample=conv2(model,h,'same');sample(sample==1)=0;sample([2,a*b-1])=1;sample=sample>0;model(sample~=model)=0;if t==length(find(model>0))break;elset=length(find(model>0));endendmap=model+map;dist=length(find(map==2))-1;后台回复关键词【迷宫】获得完整代码到这里我们已经完成了迷宫游戏地图的生成、MATLAB自动求解所生成的迷宫游戏地图，一款豪华的私人定制迷宫游戏基本就完成了。Matlab自动求解迷宫游戏效果图下面一部分我们来给这款游戏提升一下“逼格”，通过gui设置实现手动求解迷宫游戏，即能够通过键盘在迷宫地图上移动棋子，完全实现单机版迷宫游戏。四、手动求解迷宫游戏
话不多说，直接上代码。function move(map)clf;map_draw(map, '迷宫游戏');[e,f]=size(map);curpos=[2,1];H=text(curpos(2),curpos(1),'\bullet','HorizontalAlignment','Center','FontSize',45,'color','r');tic;while ~all(curpos == [e-1,f])waitfor(gcf,'CurrentCharacter');set(gcf,'CurrentCharacter','~');switch double(key(1))case 117if map(max(curpos(1)-1,1),curpos(2))>0&&curpos(1)>1set(H,'string',[]);curpos(1)=curpos(1)-1;H=text(curpos(2),curpos(1),'\bullet','HorizontalAlignment','Center','FontSize',45,'color','r');endcase 100if map(min(curpos(1)+1,e),curpos(2))>0&&curpos(1)set(H,'string',[]);curpos(1)=curpos(1)+1;H=text(curpos(2),curpos(1),'\bullet','HorizontalAlignment','Center','FontSize',45,'color','r');endcase 108if map(curpos(1),max(curpos(2)-1,1))>0&&curpos(2)>1set(H,'string',[]);curpos(2)=curpos(2)-1;H=text(curpos(2),curpos(1),'\bullet','HorizontalAlignment','Center','FontSize',45,'color','r');endcase 114if map(curpos(1),min(curpos(2)+1,f))>0&&curpos(2)set(H,'string',[]);curpos(2)=curpos(2)+1;H=text(curpos(2),curpos(1),'\bullet','HorizontalAlignment','Center','FontSize',45,'color','r');endotherwiseendendtime=toc;str=num2str(['Your Last Time is: ' num2str(time) '秒']);text(0.8*f,-1,str);
后台回复关键词【迷宫】获得完整代码接下来一起看一下游戏效果。手动求解迷宫游戏效果图
五、迷宫游戏封装
通过前几部分，我们实现了实现了这款豪华私人订制版“迷宫游戏的”三大功能，即：随机生成迷宫地图、手动求解生成的迷宫、MATLAB自动求解生成的迷宫，下面我们将以上功能封装起来，完成这款迷宫游戏。function maze_mainglobal nar FIGURE;close all;clc;nar=nargin;if nar<1a=input('请输入迷宫的行数:');b=input('请输入迷宫的列数:');a=2*a+1;b=2*b+1;map=maze(a,b);str='迷宫游戏';endFIGURE=figure('KeyPressFcn',@move_spot);map_draw(map,str);num=3;while num==3||num==1num=input('请在以下操作中选择一项:\n1,运行迷宫游戏\n2,求解该迷宫\n3,重新选择迷宫\n4,退出\n');switch numcase 1figure(FIGURE);move(map);case 2clf;figure(FIGURE);tic;[map,~]=maze_sove(map);map_draw(map,str);case 3maze_main;case 4return;endendnum=input('是否继续:\n1,继续\n2,退出\n');switch numcase 1maze_main;case 2return;endfunction move_spot(~,evnt)assignin('caller','key',evnt.Key)return
后台回复关键词【迷宫】获得完整代码至此，我们彻底完成了这款迷宫游戏的制作，在命名窗口输入maze_main即可畅玩这款迷宫游戏。私人定制版迷宫游戏整体运行效果图MATLAB迷宫游戏的完整代码大家可以关注微信公众号【数学建模andMATLAB】，后台回复关键词【迷宫】就可以得到啦~参考来源[1] 维基百科_深度优先搜索/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2[2] 利用matlab创建与解决迷宫[深度优先、Prim、递归分割、Wilson]/weixin_42943114/article/details/104172146
