迷宫自动寻路问题求解

By Guanghao Zuo | July 28, 2019 | 4 minutes

迷宫寻路是一个很有趣的问题，这篇文章是对我思考过程的重述。完整流程图和代码请直接翻到文章最后。我的算法比较简单，在我的印象中，“算法”都是那种很“高大上”的东西，不敢相信我写出来的东西也能被叫做算法。所以我在标题里用了“问题”两个字?。有时间了真得系统地学学算法。

问题：已知一迷宫图，B,E两点分别为起始点及终止点，图中红色线为不可穿越路径，蓝色线为可穿越路径。某人从B点出发，当到达某一位置时，其周围的路径通行情况才被探索，未到达的位置，其周围路径该人无法得到。求：从B点到E点的一条路径

Matlab Ctrl+R 多行注释；Ctrl+T 取消多行注释。 axis on/off 坐标区线条和背景的可见性，指定为 on 或 off。 maze是最常见的一个表示“迷宫”的词。labyrinth是专指古希腊Crete（克里特）岛上的迷宫，由Crete国王，Zeus与Europe之子，Minos建造，里面关着Minos之妻与Poseidon的牛的后代——Minotaur，一个半牛半人的怪物，凶残而暴虐。

分三步进行

迷宫的数字化及迷宫的MATLAB绘制

为了绘制迷宫框线，我们可以这样考虑：我们把二维迷宫想象为铺在一个X-Y坐标系上；迷宫由一条条长度为1的短线拼接而成。我们分别绘制横向的迷宫框线和纵向的迷宫框线。对于横向短线，它的颜色由左端点的值决定；对于纵向短线，它的颜色由下端点处的值决定。我们也可以说，坐标系中的某迷宫结点，向上延伸出一条竖向的短线、向右延伸出一条横向的短线。例如，对于点(2,1)来讲，它向上延伸出一条蓝色的线，向右延伸出一条红色的线。我们约定，如果某点延伸出的线的颜色为红色，则该点处的值为“0”，否则为“1”（蓝色）。例如，我们想绘制横向的线，则点(1,1)处的值为0，点(1,2)处的值为1，……，(2,1)=0, (3,1)=0, (4,1)=0, (5,1)=0, (1,2)=1, (2,2)=1, …… 那么，我们可以得到一个0-1矩阵如下：

hori=[
0 1 1 1 0 0;
0 1 1 1 1 0;
0 1 1 1 1 0;
0 1 0 1 0 0;
0 0 0 1 1 0;
];

同理，对于纵向的线，则有(1,1)=0, (2,1)=1, (3,1)=0, (4,1)=1, (5,1)=1, (6,1)=0, (1,2)=0, …… 那么我们也可以再得到一个0-1矩阵如下：

这样我们便把一个二维迷宫数字化为了两个0-1矩阵。接下来我们使用Matlab的plot函数绘制迷宫框线。plot函数的实质其实就是“描点连线”，所以，如果我们想绘制横框线，我们只需要把两个点用带颜色的线连结起来就可以了。如点(1,1)处横向框线是红色的，那么我们只需要用plot在点(1,1)和点(2,1)间绘制一条红色的线，用代码来表示就是：

plot([1,2],[1,1],'r')

接下来，我们使用两层嵌套的for循环，绘制出该二维迷宫中所有的横向框线，代码如下：

hold on
axis square
axis([0,7,0,7])
for i=1:5
    for j=1:6
        if hori(i,j)==1
            plot([i,i+1],[j,j],'b')
        else
            plot([i,i+1],[j,j],'r')
        end
    end
end

效果如图：接下来我们再在此基础上绘制出所有的纵向框线，迷宫绘制完成。完整代码如下：

hori=[
0 1 1 1 0 0;
0 1 1 1 1 0;
0 1 1 1 1 0;
0 1 0 1 0 0;
0 0 0 1 1 0;
];

vert=[
0 0 0 0 0;
1 0 0 0 1;
0 1 0 0 0;
1 0 1 0 0;
1 1 1 0 1;
0 0 0 0 0;
];

hold on
axis square
axis([0,7,0,7])
for i=1:5
    for j=1:6
        if hori(i,j)==1
            plot([i,i+1],[j,j],'b')
        else
            plot([i,i+1],[j,j],'r')
        end
    end
end

for i=1:6
    for j=1:5
        if vert(i,j)==1
            plot([i,i],[j,j+1],'b')
        else
            plot([i,i],[j,j+1],'r')
        end
    end
end

hold off

效果如图：为了分析问题的方便，我们把红色线条的宽度设置为2，让迷宫图形更加直观：

plot([i,i+1],[j,j],'r','LineWidth',2)
plot([i,i],[j,j+1],'r','LineWidth',2)

效果如图：

路径求解

在迷宫绘制完成后，我们从正常的人的角度看这个迷宫。迷宫是由一个个小方格构成的，“走迷宫”时“走一步，再走一步”之中的“一步”，指的是在这些小方格之间的一次移动。在求解时我们把这一个个小方格抽象为一个个的点，那么“走一步”就变成了点的坐标的变换。在该迷宫问题中，有这样一个限制：当到达某一位置时，其周围的路径通行情况才被探索；未到达的位置，其周围路径该人无法得到。也就是说，我们走到某一个点（某一个方格）处时，才可以判断“上下左右”四个方向的哪条路可以走。如果只有一个方向可以走，那么我们接着往下走就可以了；如果有两个以上方向可以走，就面临选择“走哪条路”的问题；如果除了来时的路，无路可走，那么我们就需要原路返回，在上一个点处重新选择路径。我们把思考过程用流程图（不是标准流程图，但能说明问题）表示如下： Created with Raphaël @@VERSIONStart输入数据，定义各种变量查找所有可以走的路径查找所有未走过的路径未走过的路径数量是否为0?原路回退随机选取一条到下一结点是否终点?Endyesnoyesno 接下来我们要做的就是用严谨的编程语言把流程图给叙述出来。

定义变量

在这个迷宫中，起点的坐标为(1,5)，终点的坐标为(5,5)，要判断迷宫是否已到终点，我们只需要比较“位置变量中的值”和“终点坐标”是否相同，如果相同，说明我们到达了终点，程序结束；如果不相同，说明我们还要继续往前走。很显然，我们需要用到“循环”来实现“走一步，再走一步”的过程，条件为“坐标变量表示的点不是终点”，Matlab中的while循环很合适。该怎样将坐标保存到变量中呢？对于一个点，我用一个1×2的矩阵保存横纵坐标；对于点的列表，我用n×2的矩阵保存坐标，随着循环的进行，不断把新的点的坐标追加到矩阵中。我定义的变量有：

BegP=[1,5];%初始点坐标
EndP=[5,5];%终点坐标
PosP=BegP;%当前位置点坐标，走一步变换一次，初值BegP
PosHis=[];%已走过位置坐标列表，初值空
PosB=[];%所有可走路径
PosBB=[];%所有未走过的路径
PTime=0;%尝试次数 %前进次数
BTime=0;%后退次数

接下来的所有路径求解代码都是在循环中的，先把框架搭好：

while ~isequal(PosP,EndP)

end

循环条件是“PosP和EndP两个变量中的值是否相等”，如果不相等，循环就继续进行下去。函数isequal()用来判断两个数组是否相等；前面的“~”表示“取反”。每一次循环时，我们都要把当前位置点追加到PosHis中，尝试次数也要增加1次，代码如下：

while ~isequal(PosP,EndP)
    PosHis=[PosHis;PosP(1),PosP(2)];
    PTime=PTime+1;
end

查找所有可走的路径

判断路径是否可以通过，即判断横向点矩阵中”当前点“和”上方紧邻点“对应位置处的值是”1或0“、判断纵向点矩阵中”当前点“和”右方紧邻点“对应位置处的值是”1或0“，代码表示如下：

while ~isequal(PosP,EndP)
    PosHis=[PosHis;PosP(1),PosP(2)];
    PTime=PTime+1;
    % 查找所有可走的路径
    if hori(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1),PosP(2)-1];
    end
    if vert(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1)-1,PosP(2)];
    end
    if hori(PosP(1),PosP(2)+1)==1
        PosB=[PosB;PosP(1),PosP(2)+1];
    end
    if vert(PosP(1)+1,PosP(2))==1
        PosB=[PosB;PosP(1)+1,PosP(2)];
    end
end

查找所有未走过的路径

找到哪条路径没有走过，我们只需要判断PosB中的各点是否在PosHis中，在PosHis中的点就是已走过的点，我们可以使用ismember()函数实现。请查阅官方帮助文档获取详细信息。代码如下：

    %查找所有未走过的路径
    LiaP=ismember(PosB,PosHis,'rows');%判断PosB中的行能否在PosHis中找到
    PosBB=PosB(LiaP==0,:);%逻辑索引

选择路径

如果PosBB非空，那么就说明在当前位置周围，还有我们没走过的路，我们可以从中选择一条来走；如果PosBB为空，说明当前位置周围所有的路我们都走过了，只好原路回退了。如果走未走过的路，我本来想的是随机选择一条，但后来又想了想，直接走PosBB中第一行元素对应的点就好，我们走错了路还可以回来，而且，PosBB是每走一步都要重新计算的。如果原路返回，直接从PosHis读取上一个点的坐标就行。代码如下：

    if isempty(PosBB)
        %原路返回
        PosP=PosHis(PTime-1,:);
    else
        %走到下一结点. 走PosBB中的第一行坐标, 没问题
        PosP=PosBB(1,:);
        PosB=[];
        PosBB=[];
    end

现在代码初具规模，我们走一走看看能走到哪里，while中代码如下：

while ~isequal(PosP,EndP)
    PosHis=[PosHis;PosP(1),PosP(2)];
    PTime=PTime+1;
    % 查找所有可走的路径
    if hori(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1),PosP(2)-1];
    end
    if vert(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1)-1,PosP(2)];
    end
    if hori(PosP(1),PosP(2)+1)==1
        PosB=[PosB;PosP(1),PosP(2)+1];
    end
    if vert(PosP(1)+1,PosP(2))==1
        PosB=[PosB;PosP(1)+1,PosP(2)];
    end
    %查找所有未走过的路径
    LiaP=ismember(PosB,PosHis,'rows');%判断PosB中的行能否在PosHis中找到
    PosBB=PosB(LiaP==0,:);%逻辑索引
    %路径选择
    if isempty(PosBB)
        %原路返回
        PosP=PosHis(PTime-1,:);
    else
        %走到下一结点. 走PosBB中的第一行坐标, 没问题
        PosP=PosBB(1,:);
        PosB=[];
        PosBB=[];
    end
end

可以发现，走到点(1,4)处就要出问题了，因为前面已无路可走，要原路返回，但原路返回的代码有问题，导致我们只能来回地在点(1,4)和点(1,3)之间移动。能原路返回的关键是能根据PTime和BTime在PosHis中找到正确的坐标，经计算，我把相关代码修改为：

    %路径选择    
    if isempty(PosBB)
        %原路返回
        BTime=BTime+1;
        PosP=PosHis(PTime-2*BTime+1,:);
        PosB=[];
        PosBB=[];
    else
        %走到下一结点. 走PosBB中的第一行坐标, 没问题
        BTime=0;%把后退次数清零
        PosP=PosBB(1,:);
        PosB=[];
        PosBB=[];
    end

我还想过引入一个NTime变量来记录前进次数（不包含后退次数），后来发现没必要。我们再来测试程序，看能走到哪里。我们可以发现，当第3次走到点(4,1)的时候出问题了，本应回退到点(3,1)，但却回退到了(4,2)。这个问题是由我们”原路返回部分“的代码造成的，因为我们为回退到之前的点，采用的坐标计算方式是线性的，不能跳过一部分点。这个问题不能在现有的流程框架下解决，我们有必要对流程图进行修改。我的做法是：引入”标记点“。当某点可以前进的方向大于1条时，就把这个点储存起来作为”标记点“，如果某个标记点无路可走时，则直接跳到前一个标记点。如果在某点处未走过的路径为3条（更多条的情况在这种形式的迷宫下不会出现），则该点会被重复标记一次（是的，一次），程序有在该点处产生死循环的危险，当然，这个迷宫里没有这种情况出现，但我们要考虑到更一般的情况。有两种方式解决，一，在标记某点时先判断该点是否已经是标记点；二，在返回上一个标记点时，返回上一个紧邻的与当前点不同的标记点。~~我这里采用第二种方式，因为我觉得第二种方式可以把代码写得很巧妙。~~我这里不对这个问题进行修正。新的流程图如下： Created with Raphaël @@VERSIONStart输入数据，定义各种变量查找所有可以走的路径查找所有未走过的路径未走过的路径数量是否为0?当前点是否为标记结点？回退到上一非自身紧邻点原路回退未走过的路径数量是否为1？走第一条到下一结点是否终点?End标记该节点yesnoyesnoyesnoyesno ”路径选择“部分，新代码如下：

    %路径选择
    if isempty(PosBB)
        %判断该点是否为标记结点
        [LiaS,LocbS]=ismember(PosP,PosPS,'rows');
        if LiaS==1
            PosP=PosPS(LocbS-1,:);%返回到上一标记结点
            BTime=0;%把后退次数清零
            PosB=[];
            PosBB=[];
        else
            %原路返回
            BTime=BTime+1;
            PosP=PosHis(PTime-2*BTime+1,:);
            PosB=[];
            PosBB=[]; 
        end
    else
        if size(PosBB,1)==1
            BTime=0;%把后退次数清零
            PosP=PosBB(1,:);
            PosB=[];
            PosBB=[];
        else
            BTime=0;%把后退次数清零
            PosPS=[PosPS;PosP];%标记该点为特殊点%注意此时PosP还没被重新赋值
            PosP=PosBB(1,:);%PosP被重新赋值
            PosB=[];
            PosBB=[];
        end
    end

我又引入了一个变量PosPS用来保存特别标记点。我还想过引入一个变量PosPSH，用来保存两个相邻标记点之间的点，一步步退回去，后来觉得没必要，又去掉了。我还想过给变量PosPS一个初值，把BegP赋值给它。后来明白这是多此一举。因为即便是第一个点，后面的代码也会判断该点是否应该作为标记点。再来测试代码，程序顺利走到了终点。此时我们成功完成了路径求解部分的代码，代码如下：

BegP=[1,5];%初始点坐标
EndP=[5,5];%终点坐标
PosP=BegP;%当前位置点坐标，走一步变换一次，初值BegP
PosHis=[];%已走过位置坐标列表，初值空
PosB=[];%所有可走路径
PosBB=[];%所有未走过的路径
PTime=0;%尝试次数 %前进次数
BTime=0;%后退次数

PosPS=[];%特别标记点,前进方向多于1个的点,%del但无论怎样,初始点是特别标记点

while ~isequal(PosP,EndP)
    PosHis=[PosHis;PosP(1),PosP(2)];
    PTime=PTime+1;
    % 查找所有可走的路径
    if hori(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1),PosP(2)-1];
    end
    if vert(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1)-1,PosP(2)];
    end
    if hori(PosP(1),PosP(2)+1)==1
        PosB=[PosB;PosP(1),PosP(2)+1];
    end
    if vert(PosP(1)+1,PosP(2))==1
        PosB=[PosB;PosP(1)+1,PosP(2)];
    end
    %查找所有未走过的路径
    LiaP=ismember(PosB,PosHis,'rows');%判断PosB中的行能否在PosHis中找到
    PosBB=PosB(LiaP==0,:);%逻辑索引
    
    %路径选择
    if isempty(PosBB)
        %判断该点是否为标记结点
        [LiaS,LocbS]=ismember(PosP,PosPS,'rows');
        if LiaS==1
            PosP=PosPS(LocbS-1,:);%返回到上一标记结点
            BTime=0;%把后退次数清零
            PosB=[];
            PosBB=[];
        else
            %原路返回
            BTime=BTime+1;
            PosP=PosHis(PTime-2*BTime+1,:);
            PosB=[];
            PosBB=[]; 
        end
    else
        if size(PosBB,1)==1
            BTime=0;%把后退次数清零
            PosP=PosBB(1,:);
            PosB=[];
            PosBB=[];
        else
            BTime=0;%把后退次数清零
            PosPS=[PosPS;PosP];%标记该点为特殊点%注意此时PosP还没被重新赋值
            PosP=PosBB(1,:);%PosP被重新赋值
            PosB=[];
            PosBB=[];
        end
    end

end

路径绘制

接下来就是绘制指示正确路径的箭头的部分了。我根据PosHis中保存的点来绘制正确路径。我们走了很多弯路，现在要把这些”弯路“去掉。我是这样考虑的：如果一个点在PosHis中重复出现，那么出现的两次之间所夹的点就是无用的，这些点连起来所构成的路径就是”弯路“。我们用代码实现这一过程。代码如下：

i=1;
while i<=size(PosHis,1)
    [LiaPP,LocbPP]=ismember(PosHis(i,:),PosHis((i+1):end,:),'rows');
    if LiaPP==1
        i=i+LocbPP;
    end
    PlotPP=[PlotPP;PosHis(i,:)];
    i=i+1;
end
PlotPP=[PlotPP;EndP];

可从代码看出，我引入了一个新变量PlotPP，用来保存从PosHis中得到的构成”正确路径“的各点坐标。因为我们放置的位置的原因，PlotHis中没有包含终点坐标，我也给额外添加到了PlotPP中。我们用每个小方格左下角的点来代表这个小方格，但我们画箭头的时候肯定是要把箭头画在方格中心位置，所以需要对PlotPP中的坐标进行修正。我使用quiver()函数来画箭头。我将所有箭头起点的坐标保存在一个变量中，将所有箭头终点坐标保存在另一个变量中。我还计算得到每个箭头向量的坐标。代码如下：

%quiver(x,y,u,v) x,y为起点坐标,u,v为起点在原点的向量的坐标,也就是在x,y轴的分量
%得到每个方格的中心点坐标
PlotPPF=PlotPP+0.5;
%起点坐标和终点坐标
PlotPPA=PlotPPF(1:end-1,:);
PlotPPZ=PlotPPF(2:end,:);
%得到向量坐标u,v
PlotPPV=PlotPPZ-PlotPPA;

quiver(PlotPPA(:,1),PlotPPA(:,2),PlotPPV(:,1),PlotPPV(:,2),0.5,'LineWidth',2)

我还把箭头宽度变为了原来的2倍，看起来更美观。

这样，我们的程序就大功告成了，完整代码如下：

% 我的Matlab版本：2018b，运行通过。
clear
clc
hori=[
0 1 1 1 0 0;
0 1 1 1 1 0;
0 1 1 1 1 0;
0 1 0 1 0 0;
0 0 0 1 1 0;
];

vert=[
0 0 0 0 0;
1 0 0 0 1;
0 1 0 0 0;
1 0 1 0 0;
1 1 1 0 1;
0 0 0 0 0;
];

hold on
axis square
axis([0,7,0,7])
for i=1:5
    for j=1:6
        if hori(i,j)==1
            plot([i,i+1],[j,j],'b')
        else
            plot([i,i+1],[j,j],'r','LineWidth',2)
        end
    end
end

for i=1:6
    for j=1:5
        if vert(i,j)==1
            plot([i,i],[j,j+1],'b')
        else
            plot([i,i],[j,j+1],'r','LineWidth',2)
        end
    end
end

%hold off %注意这里的hold off被我移动到了最下面

BegP=[1,5];%初始点坐标
EndP=[5,5];%终点坐标
PosP=BegP;%当前位置点坐标，走一步变换一次，初值BegP
PosHis=[];%已走过位置坐标列表，初值空
PosB=[];%所有可走路径
PosBB=[];%所有未走过的路径
PTime=0;%尝试次数 %前进次数
BTime=0;%后退次数

PosPS=[];%特别标记点,前进方向多于1个的点,%del但无论怎样,初始点是特别标记点

PlotPP=[];%画图有效点

while ~isequal(PosP,EndP)
    PosHis=[PosHis;PosP(1),PosP(2)];
    PTime=PTime+1;
    % 查找所有可走的路径
    if hori(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1),PosP(2)-1];
    end
    if vert(PosP(1),PosP(2))==1
        PosB=[PosB;PosP(1)-1,PosP(2)];
    end
    if hori(PosP(1),PosP(2)+1)==1
        PosB=[PosB;PosP(1),PosP(2)+1];
    end
    if vert(PosP(1)+1,PosP(2))==1
        PosB=[PosB;PosP(1)+1,PosP(2)];
    end
    %查找所有未走过的路径
    LiaP=ismember(PosB,PosHis,'rows');%判断PosB中的行能否在PosHis中找到
    PosBB=PosB(LiaP==0,:);%逻辑索引
    
    %路径选择
    if isempty(PosBB)
        %判断该点是否为标记结点
        [LiaS,LocbS]=ismember(PosP,PosPS,'rows');
        if LiaS==1
            PosP=PosPS(LocbS-1,:);%返回到上一标记结点
            BTime=0;%把后退次数清零
            PosB=[];
            PosBB=[];
        else
            %原路返回
            BTime=BTime+1;
            PosP=PosHis(PTime-2*BTime+1,:);
            PosB=[];
            PosBB=[]; 
        end
    else
        if size(PosBB,1)==1
            BTime=0;%把后退次数清零
            PosP=PosBB(1,:);
            PosB=[];
            PosBB=[];
        else
            BTime=0;%把后退次数清零
            PosPS=[PosPS;PosP];%标记该点为特殊点%注意此时PosP还没被重新赋值
            PosP=PosBB(1,:);%PosP被重新赋值
            PosB=[];
            PosBB=[];
        end
    end
end

i=1;
while i<=size(PosHis,1)
    [LiaPP,LocbPP]=ismember(PosHis(i,:),PosHis((i+1):end,:),'rows');
    if LiaPP==1
        i=i+LocbPP;
    end
    PlotPP=[PlotPP;PosHis(i,:)];
    i=i+1;
end
PlotPP=[PlotPP;EndP];

%quiver(x,y,u,v) x,y为起点坐标,u,v为起点在原点的向量的坐标,也就是向量在x,y轴的分量
%得到每个方格的中心点坐标
PlotPPF=PlotPP+0.5;
%起点坐标和终点坐标
PlotPPA=PlotPPF(1:end-1,:);
PlotPPZ=PlotPPF(2:end,:);
%得到向量坐标u,v
PlotPPV=PlotPPZ-PlotPPA;

quiver(PlotPPA(:,1),PlotPPA(:,2),PlotPPV(:,1),PlotPPV(:,2),0.5,'LineWidth',2)
hold off %注意,上面的hold off被我移动到了这里

效果如图：

写在最后

我觉得这个问题最难的部分就是程序开头，定义变量那部分。定义什么变量都随意，没人规定好，要自行判断，简直纠结死个人。虽说万事开头难，也正是魅力所在。 C语言对我影响很大，再加上我对面向对象的语言特性理解得也不深刻，我会不由自主地以面向过程的思考方式或者说编程方式去思考问题。也许以后我能给出更完美的解答。程序可改进的部分我已写在文中，也许还有其他不妥之处我暂时没注意到，留待以后完善。