基于FLOOD Fill算法的迷宫路径求解方法研究王润民;刘占文;杨澜;惠飞【摘要】目前国际电脑鼠走迷宫竞赛中常采用的FLOOD Fill迷宫搜索算法存在硬件系统资源消耗较多和无法实现最短路径求解及判定等问题.根据FLOOD Fill算法和FLOOD Fill迷宫搜索算法的工作原理,提出修正的FLOOD Fill迷宫搜索算法及相应的最短路径求解算法.通过判断更新必要迷宫格编码值提高迷宫搜索算法的执行效率,建立“有墙迷宫”和“无墙迷宫”完成迷宫搜索后最短路径的最优性判定和迷宫搜索次数的决策.MATLAB平台的仿真分析和IEEE标准迷宫的实际测试结果表明,相对于FLOODFill迷宫搜索算法,该方法不仅减少了97％的冗余编码值更新,而且能够准确地求解出搜索后的迷宫最短路径.【期刊名称】《计算机应用与软件》【年(卷),期】2015(032)011【总页数】5页(P238-242)【关键词】电脑鼠;迷宫搜索算法;FLOOD Fill算法;最短路径求解;编码值【作者】王润民;刘占文;杨澜;惠飞【作者单位】长安大学现代工程训练中心陕西西安710018;长安大学信息工程学院陕西西安710064;长安大学信息工程学院陕西西安710064;长安大学信息工程学院陕西西安710064【正文语种】中文【中图分类】TP301.60 引言“电脑鼠”，英文名MicroMouse，是由嵌入式微处理器、传感器和电机组成的一种小型自动化轮式智能机器人。
根据国际电工和电子工程学会(IEEE)制定的电脑鼠迷宫竞赛规则，电脑鼠需要在由16×16个18 cm×18 cm大小的单元格组成的不同的未知迷宫中自行行走、搜索迷宫内部信息并寻找迷宫起点到终点的路径，以快速到达迷宫的终点［1］。
IEEE每年会举办一次国际性的电脑鼠走迷宫竞赛，在竞赛中电脑鼠需要完成迷宫路径的求解，具体包括未知迷宫的搜索和最短路径的求解两个任务，前者要求电脑鼠搜索并记忆迷宫的内部结构，寻找迷宫起点与终点之间存在的路径，后者要求电脑鼠根据搜索过程获得的迷宫墙壁资料信息寻找判断迷宫从起点到终点的最短路径。
在硬件条件确定的条件下，电脑鼠的性能优劣主要由电脑鼠的迷宫路径求解算法(包括迷宫搜索算法和最短路径求解算法)决定，其中前者反映了电脑鼠的智能性和记忆能力，后者反映了电脑鼠的运算处理能力。
迷宫路径求解问题是一个典型的组合优化问题，被广泛应用于解决管道铺设、设备安装、线路规划、智力训练等生产生活中的诸多方面［2］。
目前研究拓扑学和图论的工程师已经探讨研究了较多的迷宫路径求解算法，包括沿壁法、向心深度优先算法、Djikstra算法、FLOOD Fill 算法和遗传算法等［3］。
本文对目前电脑鼠迷宫竞赛中常用FLOOD Fill迷宫搜索算法进行分析研究，针对其应用在迷宫路径求解问题上的存在不足进行修正，然后在修正搜索算法的基础上构建了迷宫最短路径的求解方法，并通过建立MATLAB仿真平台和实物IEEE标准迷宫对改进前后的算法进行测试。
通过对算法的仿真、分析验证了修正算法的优越性。
1 FLOOD Fill算法FLOOD Fill算法又称泛洪算法，或贝尔曼算法，该算法属于一种特殊的深度优先遍历算法，利用了水流从水源近处流向远处的原理［4］。
假设洪水从迷宫中的某一个格子源源不断地流出，那么洪水就会向有路的地方流动，而且洪水会首先到达离洪水涌出点最近的迷宫格，最后到达离洪水涌出点最远的迷宫格。
利用此原理可以按照迷宫布局建立一个编码表，将洪水涌出迷宫格编码标记为0，洪水每流动到下一格就将该迷宫格编码标记为上一迷宫格的编码值加1。
以一个8×8大小迷宫为例，如图1(a)所示，假设该迷宫中洪水涌出点为F，将该格编码值标记为0，“洪水”从此点开始向相邻迷宫格流动，每流过一个迷宫单元格就标定该单元格的编码值为上一个迷宫单元格的编码值加1，以此类推，就可以计算出每一个迷宫格的编码值，如图1(b)所示。
实际上迷宫单元格的编码值代表了该单元格与洪水涌出迷宫格的距离值，因此依据每一个迷宫格与迷宫洪水涌出点的距离值(编码值)，再以由大到小的方式排列，即可找到已知迷宫中任意迷宫格与洪水涌出迷宫格间的最短路径。
图1(c)中灰色线条表示通过FLOOD Fill算法求解得到的迷宫右上角单元格与洪水涌出迷宫格间的最短路径。
通过将已知迷宫中的任意迷宫格定义为洪水涌出点，即可找到迷宫中任意两个迷宫格之间的最短路径。
图1 FLOOD Fill算法原理示意图2 迷宫搜索算法2.1 FLOOD Fill迷宫搜索算法FLOOD Fill迷宫搜索算法是一种以FLOOD Fill算法为核心实现对未知迷宫进行搜索的算法。
为了简化问题的说明，以一个5×5的迷宫为例，如图2(a)所示，以左下角的迷宫格为原点建立一个正向坐标系，每一组坐标(x，y)表示了该位置的迷宫格，其中(0，0)为迷宫的起点S，(2，2)为迷宫的终点G。
在电脑鼠开始搜索迷宫之前，FLOOD Fill迷宫搜索算法首先建立一个5×5的矩阵作为迷宫编码表，用于存储FLOOD Fill算法执行后各迷宫格的编码值。
然后假设迷宫内部没有墙壁并以迷宫终点为洪水涌出点执行FLOOD Fill算法，结果如图2(b)所示，其中迷宫内部的数据表示第一次执行FLOOD Fill算法后各迷宫格的编码值［5］。
图2 示例迷宫及初始编码表随后FLOOD Fill迷宫搜索算法驱动电脑鼠从起点开始运行并探索迷宫，直至搜索到终点。
在搜索过程中需要遵循以下规则。
规则1:a)电脑鼠每进入一个迷宫格就检测当前迷宫格的墙壁信息，然后在当前探索到的所有迷宫墙壁信息的基础上以迷宫终点为洪水涌出点执行一次FLOOD Fill算法，更新编码表;b)电脑鼠选择比当前迷宫格编码值小的相邻迷宫格前进，若比当前迷宫格编码值小的相邻迷宫格不止1个，则选择编码值最小的迷宫格前进;若编码值最小的迷宫格存在不止1个，则随机选择一个方向进入，并返回a执行。
具体搜索过程如图3所示，电脑从起点(0，0)开始运行，在此处检测到右边存在墙壁，然后执行一次FLOOD Fill算法，更新编码表，结果如图3(a)所示。
在(0，0)处仅存在一个可前进的迷宫格(0，1)，因此移动到该迷宫格，检测到上方有墙，并根据迷宫墙壁信息执行一次FLOOD Fill算法，结果如图3(b)所示。
在(0，1)处存在两个相邻的迷宫格(0，0)和(1，1)，但根据规则1.a，可前进的迷宫格为(1，1)，于是电脑鼠移动到该迷宫格，检测到右方有墙，并根据此时的迷宫墙壁信息执行一次FLOOD Fill算法，更新编码表，结果如图3(c)所示。
在(1，1)处仅存在一个可前进的方向(1，2)，于是电脑鼠移动到该迷宫格，此时检测到右方和上方有墙，然后根据此时的迷宫墙壁信息执行一次FLOOD Fill算法，更新编码表，结果如图3(d)所示，电脑鼠在(1，2)的左方和后方存在两个优先级相同的可前进方向，则随机选择一个方向前进。
图3 FLOOD Fill迷宫搜索算法执行过程按照上述方式，电脑鼠每进入一个新的迷宫格就检测迷宫墙壁信息，然后执行FLOOD Fill算法并更新编码表，判定前进方向并进入下一迷宫格继续进行上述过程，直至搜索到迷宫终点(2，2)。
电脑鼠在(1，2)处分别选择(0，2)和(1，1)两个方向前进时得到的最终搜索结果如图4所示，其中灰色线表示相应的搜索过程中电脑鼠走过的路径。
图4 FLOOD Fill迷宫搜索算法搜索结果电脑鼠采用FLOOD Fill迷宫搜索算法对图2(a)所示的迷宫进行搜索的过程中(以图4(a)所示的结果为例)，电脑鼠从起点到终点一共走过了11个迷宫格，进行了11次FLOOD Fill迷宫算法，更新了11×25=275个迷宫格编码值，若将FLOOD Fill 迷宫搜索算法应用到16×16大小的迷宫，电脑鼠进行一次搜索需要更新数十万个编码值［6］。
然而实际上相当多的编码值重算和更新过程并不是必需的，例如电脑鼠运行至(0，1)和(1，1)时更新的全部编码值与更新前相比没有任何变化，如图3(a)－(c)所示;再如电脑鼠运行至(1，2)时更新的全部的编码值仅部分发生了变化，如图3(c)和图3(d)所示。
大量冗余编码值的更新需要耗用较多的算法处理时间和电脑鼠系统资源，然而考虑到造价及开发难度等因素电脑鼠一般被设计为具有较小的运算处理能力，因此需要考虑仅在需要更新的时候才对需要更新的迷宫格的编码值进行重算赋值，减少电脑鼠的冗余计算，提高其运算处理效率［7］。
2.2 修正的FLOOD Fill迷宫搜索算法针对上述问题，提出修正的FLOOD Fill迷宫搜索算法。
该算法不仅需要在电脑鼠开始搜索迷宫之前建立一个5×5的矩阵作为迷宫编码表，还需要在电脑鼠正式运行之前在内存中建立一个堆栈。
然后电脑鼠在迷宫起点设定迷宫内无墙壁，并执行一次FLOOD Fill算法并填充编码表，填充完毕后开始正式运行。
电脑鼠每到达一个新的迷宫格时不再以迷宫终点为洪水涌出点执行FLOOD Fill算法，而是按照如下规则进行判断处理执行，直至运动至迷宫终点。
规则2:a)将当前迷宫格的坐标值(m，n)压入堆栈，并检测当前迷宫格的墙壁信息;b)将堆栈顶端的坐标值(x，y)弹出，判断与(x，y)相邻接连通且编码值最小的迷宫格的编码值MC是否等于(x，y)迷宫格的编码值减1，如果不相等，就将(x，y)迷宫格的编码值赋值为MC+1，并把上下左右四个相邻迷宫格(终点迷宫格除外)的位置坐标压入堆栈，否则直接转入c执行;c)判断堆栈是否为空，如果不为空则返回b执行。
如果为空则选择与当前迷宫格连通且比当前迷宫格编码值小的相邻迷宫格前进，若可供选择的迷宫格不止1个，则选择编码值最小的迷宫格进入(若存在多个，则随机选择一个进入)，然后返回a执行。
以图2(a)所示的迷宫为例说明:按照规则2，电脑鼠进入(0，0)、(0，1)、(1，1)迷宫格后，当前迷宫格的编码值减1均与其相邻连通且编码值最小的迷宫格的编码值相等，并且堆栈为空，因此电脑鼠不需要更新迷宫编码表，直至运行至迷宫格(1，2)。
在进入迷宫格(1，2)时，电脑鼠将坐标(1，2)压入栈顶，如图5(a)所示，其中灰色三角形表示电脑鼠。
与迷宫格(1，2)相邻接的编码值最小的连通迷宫格为(1，1)和(0，2)，其编码值MC为2，而(1，2)的编码值减1为0，二者不相等，因此需要将迷宫格(1，2)的编码值更新为MC+1=3，同时将迷宫格(1，2)上下左三个相邻迷宫格的坐标压入堆栈，结果如图5(b)所示，其中灰色圆代表当前坐标被压栈的迷宫格。
继续按规则2执行，直至堆栈再一次为空，执行结果如图5(c)所示，其中灰色区域表示电脑鼠在(1，2)处时编码值被更新的迷宫格，然后电脑鼠按规则2选择下一个迷宫格前进。