我的MATLAB®程序，使吃惊，通过结合老朋友来生成迷宫，numgrid而且delsq，与一个新朋友，the图对象。让我们看看如何制作这个迷宫。

内容

开始

选择迷宫的大小。我们的例子是15乘15。

N = 15;

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

Db = delsq(numgrid(“年代”、n + 2));B = graph(logical(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．

而真正的% Break when available为空

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

每一步都是从一个节点到它还没有被访问过的一个邻居的随机选择。

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

Idx = randi(长度(ngh));%随机选择。Q = ngh(idx);下一个单元格。树(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 =圆(长度(分支)/2);结束P =分支(idx);分支(idx) = [];结束

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

这是经过几次反悔后的结果。

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

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

当整个路径被绘制时linstyle = 'none'我们有迷宫。

最短路径

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

path =最短路径(C,1,m^2);

（锻炼:这是怎么回事?分支参数影响此的平均长度路径？)

动画

软件

我有一个程序叫令人惊异的这样你就可以进行调查使吃惊．我已经提交给MATLAB中央文件交换然后把链接在这里．我还要补充一点令人惊异的的4.40版本克里夫的实验室．

谢谢

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

获取MATLAB代码

发布与MATLAB®R2018b