我的MATLAB®程序，使吃惊通过和老朋友一起创造迷宫，numgrid和delsq，有了一个新朋友图对象。让我们看看如何制作这个迷宫。

内容

开始

选择一个迷宫大小。我们的例子是15 × 15。

N = 15;

我们要画两个图，屏障和细胞。的障碍,B，是n × n方形网格上经典的五点离散拉普拉斯函数的图形。内部的每个节点都连接到它最近的四个邻居，边界上的每个节点有两个或三个邻居。的函数delsq和numgrid一直在sparfun目录自1992年引入稀疏矩阵以来。的图对象在R2015b中引入。我们要在这个网格上挖出一条路。

Db = delsq(numgrid)“年代”、n + 2));B =图(逻辑(Db)，“omitselfloops”）;

细胞,C，也是基于五点离散拉普拉斯，但在(n-1) × (n-1)网格上。最初C只有节点，没有边。当我们绘图时B和C的节点C的正方形居中B。

M = n-1;Dc = delsq(numgrid)“年代”, m + 2));C =图(逻辑(Dc)，“omitselfloops”）;

随机漫步

可用= 1:m^2;%我们尚未访问的节点。分支= [];分支=“中间”;树= 0 (0,2);%深度优先搜索。P = 1;

现在我们做一系列的随机漫步C。

而真正的%当available为空时中断

Available (p) = 0;如果~任何(可用)打破结束

每一步都是从一个节点到随机选择一个尚未访问过的邻居节点。

[~，~，ngh] = find(available(neighbors(C,p)));如果~ isempty(已)

Idx = randi(length(ngh));%随机选择。Q = ngh(idx);%下一个单元格。Tree (end+1，:) = [p q];

同时，在屏障的边缘B即将阻塞的步骤移除。

[i,j] = wall(p,q);B = rmedge(B,i,j);

我们保留一个节点列表，其中在两个或三个邻居之间进行随机选择。

如果长度(ngh) > 1分支(end+1) = p;结束P = q;

最后，步行到达了一个死胡同，一个节点的邻居都被访问过了。下面是我们的示例中的第一个这样的遍历。

回溯

当我们到达一个死胡同时，我们回溯到节点列表中的一个节点，在那里我们可以选择可用的邻居。这里有另一种选择。我们可以回到第一个列表中的节点，转到列表中的节点中间的名单，还是给的最后的列表中的节点。

其他的开关分支情况下“第一”Idx = 1;情况下“最后一次”Idx =长度(分支);否则Idx = round(length(branches))/2);结束P = branches(idx);分支(idx) = [];结束

这是退回到中间，然后走到第二个死胡同的结果。

这是几次返程后的结果。

结束C = graph(tree(:，1)，tree(:，2));

接近这一过程的尾声时，通往死胡同和回头路的路径长度会变得越来越短。一条路径可能包含一个点。最终所有的节点C被覆盖。这是最终结果。

当整个路径用Linestyle = 'none'我们有迷宫。

最短路径

我们可以通过寻找从一个角落到另一个角落的最短路径来轻松地“解决”迷宫。

path = short testpath(C,1,m^2);

（锻炼:这个怎么样?分支参数影响其平均长度路径?）

动画

软件

我有一个程序叫做令人惊异的这可以让你进行调查使吃惊。我已经提交给MATLAB中心文件交换然后把链接在这里。我还要加上令人惊异的的4.40版本克里夫的实验室。

谢谢

感谢Pat Quillen提供的宝贵帮助。

获取MATLAB代码

使用MATLAB®R2018b发布