基于FLOOD Fill算法的迷宫路径求解方法研究  

STUDY ON SOLUTION OF MAZE PATH BASED ON FLOOD FILL ALGORITHM

作　　者：王润民[1] 刘占文[2] 杨澜[2] 惠飞[2] 

机构地区：[1]长安大学现代工程训练中心,陕西西安710018 [2]长安大学信息工程学院,陕西西安710064

出　　处：《计算机应用与软件》2015年第11期238-242,共5页Computer Applications and Software

基　　金：国家自然科学基金项目(60902075);国家物联网重大示范工程专题研究项目(2012-364-812-105);中央高校基本科研业务费专项资金项目(2013G5240009)

摘　　要：目前国际电脑鼠走迷宫竞赛中常采用的FLOOD Fill迷宫搜索算法存在硬件系统资源消耗较多和无法实现最短路径求解及判定等问题。根据FLOOD Fill算法和FLOOD Fill迷宫搜索算法的工作原理,提出修正的FLOOD Fill迷宫搜索算法及相应的最短路径求解算法。通过判断更新必要迷宫格编码值提高迷宫搜索算法的执行效率,建立"有墙迷宫"和"无墙迷宫"完成迷宫搜索后最短路径的最优性判定和迷宫搜索次数的决策。MATLAB平台的仿真分析和IEEE标准迷宫的实际测试结果表明,相对于FLOOD Fill迷宫搜索算法,该方法不仅减少了97%的冗余编码值更新,而且能够准确地求解出搜索后的迷宫最短路径。As being commonly used in international Micromouse competitions, the FLOOD Fill maze search algorithm has the problems of more consumption in hardware system resource and unable to achieve the solution and discriminant of shortest path. According to the working principle of FLOOD Fill algorithm and FLOOD Fill maze search algorithm, the paper proposed a modified FLOOD Fill maze search algorithm and the corresponding shortest path solving algorithm. It improves the execution efficiency of maze search algorithm by estimating and updating the necessary coding values of maze grid. The optimality discriminant of the shortest path and the decision of maze search numbers after searching the maze were accomplished by establishing ＂maze with walls＂ and ＂ maze without walls＂. Simulation analysis on MATLAB platform and actual test results of IEEE standard maze show that the method reduces 97% update of redundant coding values and can solve accurately the shortest path of maze after search compared with the FLOOD Fill maze search algorithm.

关 键 词：电脑鼠 迷宫搜索算法 FLOOD Fill算法 最短路径求解 编码值 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]