Python实现迷宫自动寻路实例

背景

起因源于手机QQ空间中的一条动态，有人言语轻狂。

对方神态得意，似乎久居家中，不知天高地厚。

预处理

设计迷宫自动寻路算法本身并不复杂，但当前任务的首要难点在于如何将迷宫图像转化为计算机可识别的数据结构，即实现迷宫图片的矩阵化。

原始图片尺寸为397×390。处理步骤包括：首先裁剪掉四周的白边，随后对图中每个像素进行二值化处理。根据颜色赋值规则，黑色像素记为0，白色像素记为1，从而构建一个0/1矩阵。鉴于迷宫边界均为封闭结构，为防止因图像质量瑕疵导致视觉上看似0的区域实际为1，进而引发列表越界等可预见的错误，我们将矩阵四条边界上的所有元素强制设置为0。至此，迷宫的预处理基本完成。若将1隐藏，仅打印所有0并经过缩放处理，即可得到如下可视化结果：

寻路算法

获得迷宫矩阵后，核心目标是寻找一条从左上角至右下角的通路。

关于走迷宫的方法，记忆中曾在一节算法选修课上听过老师讲解深度优先搜索（DFS）与广度优先搜索（BFS）。当时专注于抄写大物实验报告，对这两个概念仅剩下英文缩写首字母分别为D和B的模糊印象。

但这并不影响实现。正如电影台词所言，陈刀仔能用20块赢到3700万，我使用for循环解决这个小型迷宫问题，应当不在话下。

通常迷宫内部并非完全封闭，从任意点注入液体均可填满整个迷宫。据此假设，若有一只小老鼠置于起点，只要它能自动避开障碍、不重复踩踏已走过的路径，并在遇到死胡同时自动回退，则必然能找到终点。

因此，定义一个坐标点(x,y)，其初始位置设定为(1,1)，即边界内左上角的第一个有效点。

定义两个列表：path用于存储最终确定的路径（即成功到达终点的路径）中的每一个坐标点；footprint用于记录所有经过的坐标，包括那些走错的路径。两个列表的数据结构示例如[(1,1),(1,2),(2,2),......,(m,n)]所示。

此外，定义四种移动动作：向下移动一步(y=y+1)，向右移动一步(x=x+1)，向左移动一步(x=x-1)，以及向上移动一步(y=y-1)。算法每次尝试这四种动作，若可行则执行。判断不可行的条件是下一步的坐标指向墙壁或已记录的足迹。将新坐标加入path和footprint，作为新的足迹记录。

确定四种动作的执行优先级，顺序为下、右、左、上。即优先向下，若不可行则向右，再不可行则向左，最后尝试向上。这种优先级设定可避免点在空地无意义地乱转，使其具有方向性地探索。

接下来，赋予算法自动回退的能力。考虑如下简单情景：

此示意图虽不严格符合本文的优先级设定，但足以表达核心逻辑。

当遇到死胡同时，若进入时足迹已封锁出口，则该点无法继续前进。一旦发现点陷入绝境，四周均不可通行，必须原路返回。返回上一路口的方法简单，即从path列表中逐一弹出最后一个元素。由于footprint记录了所有足迹，确保任何点不再被第二次访问，因此只要错误路径未完全回溯至出口，退至任何中间点时，四周均不可通行（因为附近已被足迹覆盖）。这样，点会一直回溯至预期的路口，即误入歧途的那个节点。

测试

随后启动循环。只要当前坐标不等于终点坐标，算法便持续探索。运行结束后，得到一条迂回的曲线，如图（局部）所示。

程序成功找到通往终点的路径，但该路径过于冗杂。以上图为例，所有宽度不为1的区域均是由点的反复绕圈所致。因此，该路径仍有优化空间。

优化

考虑如下一种简单情况：

在此路线中，显然4至9属于无意义的兜圈行为，正确路线应是从3直接连接至10。

优化策略如下：若第n步位于(x,y)，从第n+2步（即下一步的下一步）开始，直至最后一步，检查中间是否有任何一步落在(x,y)一步可达的范围内。若是，则删除从第n+1步到该步的所有路径点。以上述例子为例，从第1步开始检查。当检查至第3步时，从第5步开始查看，直至第10步发现10落在3一步可达之处，此时将中间的4-9全部删除，直接将10连接至3之后。

然而，考虑到后续可能存在更优情况，例如从12开始继续绕圈，至20发现20恰好落在3的正上方，此时应直接将20连接至3，而12应被丢弃。前述方法存在缺陷。为避免此类情况，采用逆向循环策略：对于第3步，从第20步向前循环，直至第5步，检查是否有3步内可直接到达的点。如此可实现路线的最大化优化。

绘制路径

最终，我们得到了正确且简洁的路径，同时记录了曾经走过的错误路径及冗余路径。

根据矩阵与图像的对应关系，将图像中对应的像素颜色修改，其余点保持不变。

绘制路径效果如下：

优化前效果：

全部足迹展示：

结语

至此，问题已基本解决。整个程序在我的电脑上运行耗时约三五分钟，这主要是因为仅使用了for循环的暴力搜索方法。