第1章 迷宫算法

《第1章 迷宫算法》由会员分享，可在线阅读，更多相关《第1章 迷宫算法（15页珍藏版）》请在装配图网上搜索。

1、第1章 迷宫算法1.1.1 迷宫坐标和绝对方向的建立迷宫是由 16*16 大小的方格组成的,其行列各有 16 个方格.为了让电脑鼠记 住所走过的各个迷宫的信息,我们就要对这 256 个迷宫格进行编号.很明显,用坐 标是非常方便的.那么,我们规定,以电脑鼠放到起点时的方向为参照,此时电脑鼠的正前方为 Y 轴正方向, 后方为 Y 轴负方向,左方为 X 轴负方向 ,右方为 X 轴正方向.迷宫格与 坐标的对应关系如图 3- 1所示.图 3- 1 迷宫格与坐标对应关系根据坐标的定义和比赛规则可以知道,电脑鼠的起点可能在(0,0)点,也可能 在(F,0)点.即终点可能在电脑鼠的右前方,也可能在电脑鼠的左前

2、方这个可以 根据电脑鼠第一次检测到的转弯口是在左方还是右方判断出来.如图 3-2 所示, 如果电脑鼠是从(0,0)点出发,那么它第一个检测到的拐弯口是在它的右边,如果 电脑鼠是从(0,F)出发的，那么它第一个检测到的拐弯口在它的左边.图 3-2 迷宫的方向值定义为了把上下左右这四个方向参数转换为微控制器能够识别的符号,我们将向 上方向定义为 0,向右方向定义为1向左定义为 3.如图3-2所示.1.1.2相对方向与绝对方向的转换有了坐标和方向后,电脑鼠在迷宫中行走就可以随时知道自己所处的位置和 方位了,然而,对于电脑鼠来说,红外线传感器的位置和方向是固定不变的 ,而对 于迷宫来说,红外线传感器的

3、位置和方向是随着电脑鼠前进方向的变化而一起变 化的,这就是由于选择参照物的不同而出现的差异,由此引出了两个方向的问题: 相对方向和绝对方向.相对方向:以电脑鼠当前行走方向为参照的方向,称为相对方向. 绝对方向:以迷宫绝对坐标平面为参照的方向,称为绝对方向. 那么传感器所检测到的资料如何存储才能更利于处理呢 ?很明显,若以相对 方向存储的资料将会是混乱一团的 ,不仅要存储麻烦,而且要记录起检测该资料 时电脑鼠所处的方向,存储量也比较大,处理起来也非常麻烦,而以绝对方向存储 的资料将不必考虑电脑鼠当时的方向即可进行处理,非常方便.这样,就会经常遇到相对方向与绝对方向的互换,我们以变量 Dir 记录

4、电脑 鼠前进方向上的绝对方向值，即电脑鼠前言的绝对方向值始终为Dir，这样电脑 鼠的相对方向转换为绝对方向如表3-1 所示.表 3-1 相对方向转换为绝对方向相对方向绝对方向电脑鼠前方Dir电脑鼠右方(Dir+1)%4电脑鼠后方(Dir+2)%4电脑鼠左方(Dir+3)%4例如，若电脑鼠当前的前进方向为迷宫的上方，即当时Dir=O,由表3-1可以 计算出其相对方向的右、后、左三方向的绝对方向值为:1、2、3.这三个值分别 代表迷宫绝对方向的右方、下方和左方.可以看出，此时电脑鼠的相对方向与绝对 方向相同.再假如当前电脑鼠前进方向为迷宫绝对方向的左方，即当时Dir=3,由表3-1 可以计算出其相

5、对方向右、后、左三个方向的绝对方向值为:0 、1、2.可知，这三 个值分别代表迷宫绝对方向的上方、右方、下方.可以看出，此时电脑鼠的前方为 迷宫的左方，电脑鼠的右方为迷宫的上方，电脑鼠的后方为迷宫的右方.有时系统的还需要根据绝对方向求出相对方向，比如要控制电脑鼠转向某一 个绝对方向，这时就需要计算出该绝对方向处于电脑鼠的哪个相对方向上 ，电脑 鼠根据相对方向来决定转向 .首先,根据目标的绝对方向(Dir_dst)和当前的绝对方向(Dir)求出方向偏差 值(Dir),如式6-1所示.Dir = Dir_ds t - Dir(6-1)为了使ADir的值落在0-3的范围内，计算式改进为：Dir =

6、(Dir_dst + 4 - Dir)%4 (6-2) 这时就可以根据方向偏差值求出电脑鼠的相对方向 ,如表 3-2 绝对方向 转换为相对方向所示.表 3-2 绝对方向转换为相对方向绝对方向差值(ADir)相对方向0电脑鼠前方1电脑鼠右方2电脑鼠后方3电脑鼠左方1.1.3 坐标转换假设电脑鼠已知当前位置坐标(X,Y),那么就可以求出其某一绝对方向上(相 对方向也可按表 3-1 转换为绝对方向) 的相邻坐标值, 如所示.该表是可逆的, 即 可以根据坐标值的变化求出绝对方向.表 3-3 坐标转换绝对方向坐标当前位置(X,Y)上方(0)(X,Y+1)右方(1)(X+1,Y)下方(X,Y-1)左方 (

7、3)(X-1,Y)1.1.4 墙壁资料储存当电脑鼠达到一方格坐标时，应根据传感器检测结果记录下当前方格的墙壁 资料，为了方便管理和节省储存空间，每一个字节变量的低四位分别用来储存一 个方格四周的墙壁资料，如表 3-4 所示，迷宫共有 16 * 16 个方格，所以可以定 义一个 16 * 16 的二维数组变量来保存整个迷宫墙壁资料。迷宫墙壁资料全部初始化为 0，凡是走过的迷宫格至少有一方没有墙壁，即 墙壁资料不为 0。这样就可以通过单元格存储的墙壁资料是否为 0来确定该单元 格是否曾搜索过。表 3-4 墙壁资料存储方式变量位代表的绝对方向备注bit 0上方1 ：有路，0 :有墙壁bit 1右方1

8、 ：有路，0 :有墙壁bit 2下方1 :有路，0 :有墙壁bit 3左方1 :有路.0 :有墙壁bit 7- bit 4保留位1.2迷宫搜索方法在没有预知迷宫路径的情况下，电脑鼠必须要先探索迷宫中的所有迷宫格， 直到抵达终点为止。做这个处理的电脑鼠要随时知道自己的位置及姿势，同时要 记录下所有访问过的方块四周是否有墙壁。在搜索过程中，还要尽量避免重复搜 索已知搜索过的地方。因此,迷宫搜索有两种方式：1. 尽快到达目标地。2. 搜索整个迷宫。利用第一种方式虽然可以缩短搜索迷宫所需的时间，但不一定能够得到整个 迷宫的地图资料。若找到的路不是迷宫的最优路径，这将会影响电脑鼠最后冲刺 的时间。若采用

9、第二种方式，可以得到整个迷宫的地图资料，这样就可以求出最 优路径。不过采用这种方法所花费的搜索时间较长。1.3深度优先搜索算法（DFS）迷宫问题也可以看作典型的图搜索问题，常用的图搜索策略有:深度优先搜 索算法（DFS）、广度优先搜索算法（BFS）。深度优先搜索算法递归定义，先访问出 发顶点（并标记为已访问），然后以深度优先搜索算法依次访问他的尚未访问过的 各个邻接顶点，在访问过程中，表现出纵向深入的特点。深度优先搜索利用堆栈来实现，可以找到一条从起点到终点的路径，但不 一定是最短路径。广度优先搜索算法是一种按层遍历算法，先访问出发顶点（并 标记为己访问），然后依次访问它没有访问过的各个邻接顶

10、点，再按相同的规则， 访问各个邻接顶点的尚未访问过的各个邻接顶点，在访问的过程中，表现出横向 扩展的特点。利用列队的广度优先搜索算法，通常可以找到最短路径。深度优先搜索算法遵循的策略是尽可能深的搜索图。在此算法中，对于新发 现的节点，如果他还有以此为起点而尚未探测的边，就沿此边继续搜索下去，当 节点V的所有边都以搜索过，搜索将回溯到发现结点V的那条边的始结点。这一 过程一直持续到从原结点到所有可搜索的结点都被搜索过为止。如果还存在未被 发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程重复直到所 有结点都被发现为止。图3-3是一个简单的深度优先搜索策略算法示意图。图 3-3 深度优先

11、搜索示意图路径搜索的选择:按照八个方向来搜索迷宫，会有更好的效率，为了更方便的分析，我们简化问题，只采用四个方向来搜索迷宫，如下表 3- 5所示:表 3- 5 四方向搜索(i-1,j)(i,j-l)(i,j)(i,j+1)(i+1,j)图 3-4 简单迷宫深度优先搜索示实例从图3-4 示意图可以看出，在深度优先搜索策略中，我们首先扩展最新产生 的结点(也即最深的结点)，深度相同的结点可以任意排列。可以如下定义结点的深度:(1) 起始结点(根节点)深度定义为 0;(2) 其他任何结点的深度在其父结点的深度上加 1。首先，扩展最深的结点使得搜索沿着空间中某条单一路径从起始单元格到 达目标单元格进行

12、下去。只有当搜索到没有后续结点的状态时，才考虑用另一个 替代的路径。替代路径与前面刚搜索过的路径的不同之处在于后面的 n 步不同， 而这个 n 应保持尽可能的最小。1.4 迷宫搜寻法则设定搜寻法则和策略是为了电脑鼠可以以最快的方式找到终点，到达目标后 随即以所走过的路径中找出一路径返回起点，然后再做冲刺，直达目的；法则的 设定很重要，它可以使电脑鼠不多走冤枉路，可节省很多时间而制胜。每一只电脑鼠到达一方格时它最多有三个方向可前进，最少则因为三面都有 墙，没有可以前进的方向；当遇到二个以上的可选择方向时，由于不同场合需要 而有不同优先搜寻的方向顺序，常见的法则有以下几种：1. 右手法则：遇叉路时

13、，以右边为优先前进方向，然后直线方向，左边方 向；2. 左手法则：遇叉路时，以左边为优先前进方向，然后直线方向，右边方向；3. 中左法则：与右手法则相似，不过方向选择顺序改为直线优先，然后左 边，右边；4. 中右法则：遇叉路时，以直线为优先前进方向，然后右边方向，左边方 向；5. 求心法则：遇叉路时，以距中心最短的那个方向优先，然后依次选择。6. 乱数法则：以电脑的随即值作为下一前进方向。1.5 迷宫搜寻策略迷宫搜寻模式有全迷宫搜寻策略和部分迷宫搜寻策略两种：1. 全迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠会反 身继续前进，然后以原设定的搜寻法则，时时检查未走过的路，直到每 一

14、方格都搜寻过后，才回起点。2. 部分迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠将 沿原路线返回起点，不再进行其它搜寻。如果不计算搜寻时间，可采用全迷宫搜寻策略，待地毯式的搜寻过所有方格 后，再计算最佳路径，作最后的冲刺，冲刺成绩一定相当不错。由于考虑搜寻时 间，因此我们必须考虑部分迷宫搜寻策略，甚至还可能须考虑加入求心法则，截 路径功能等更智慧的法则来协助；此时找到的路径可能不是最佳路径，但保证花 的时间最短。1.6 寻找最优路径的方法及等高图的应用假设电脑鼠已经搜索完整个迷宫或者只搜索了包含起点和终点的部分迷宫， 且记录了已走过的每个迷宫格的墙壁资料，因此,引入等高图的概念和制

15、作方法。等高图就是等高线地图的简称，有如一般地图可以标出同一高度的地区范围 一样，等高图运用在迷宫地图上，可以标出每个迷宫格到起点相等步数的关系， 可不要小看它，许多封闭路径的逃脱与冲刺的关卡都可在我们制作出等高图后迎 刃而解，使电脑鼠更容易逃脱，少走一结弯路。1.6.1 等高图制作原理首先开辟一块16*16的二维数组空间(MapStep1616),其中每一个元素代表 迷宫中的一个方格,用以计算后储存各方格至起点的最短路径步数(所谓步数即为 路径中经过的方格数).当起点坐标处标识为 1 时,可以直接达到的相邻方格均为 2,再远的方格的等 高值依次递增.这样距离越远的地方等高值越大.1.6.2

16、等高图制作步骤用一个 4*4 的小迷宫作为范例,并以坐标(0,0)作为起点.步骤一:把所有迷宫格上的等高值填为Oxff.(Oxff是迷宫中等高值的上限) 起点坐标(0,0),其步数填入 1记录等高值的变量 Step 自加 1 变为 2 在堆栈中存入起点坐标(0,0)步骤二: 观察图3-5中(0,0)点四周仅有一个方向可前进(可前进的定义是说箭头 所指方向的步数值比当前坐标上的值大 2 以上,如坐标(0,1)的值为Oxff,则Oxff-ll,则坐标(0,1)为可前进的方向) 进入箭头所指方向的方格,此时坐标为(0,1)1.2.3.4.1.2.3.4.填入步数值 Step图 3-5 等高图步骤一f

17、fffffffffftfffTfffffffffffffTStep = Step + 1STACK（堆栈）1.2.3.4.5.6.1.2.3.4.5.步骤三:图 3-6 中(0,1) 点四周有两个可前进的方向 ,即此坐标点为一岔路 . 将该岔路坐标存入堆栈 进入箭头所指的一方向(可任选之,对结果无影响),此时坐标为(1,1) 填入 Step 值Step = Step + 1 得到下图3ffffffff2fffTffff3ffff20ffffff000,0STACK（堆栈）图 3-7 等高图步骤三步骤四:图 3-7 中仅有一个可前进的方向 进入箭头所指方向,此时坐标为( 1 , 0) 填入 St

18、ep 值Step = Step + 1得到下图图 3- 8 等高图步骤四0,10,0STACK（堆栈）步骤五:1.2.3.4.5.1.2.3.4.5.1.图 3- 8 中仅有一个可前进的方向 进入箭头所指方向,此时坐标为( 2 , 0) 填入 Step 值Step = Step + 1得到下图图 3-9 等高图步骤五0,10,0STACK（堆栈）步骤六:图 3-9 中四周无可前进的方向 取出堆栈中的内容,跳到其保存的坐标( 1 , 0)读出对应的坐标的Step值,Step = 2Step = Step + 1得到下图图 3-10 等高图步骤六fTfffffTffff3ffff45ff步骤七:图

19、 3-10 中坐标(0 , 1)点有一个前进方向( 坐标 (0,0) 处 Step 值为 1),不 比当前坐标的步数值大2以上,所以不是可前进的方向.2. 进入箭头所指方向,此时坐标为(0 , 2)3. 填入 Step 值4. Step = Step + 15. 得到下图图 3-11 等高图步骤七0,0STACK（堆栈）步骤八:1. 图 3-11 中坐标 (0 , 2)有两个可前进的方向2. 将该岔路坐标入栈3. 进入箭头所指的一个方向,此时坐标为(1 , 2)4. 填入 Step 值5.6.Step = Step + 1得到下图图 3-12 等高图步骤八ff耀0- fffT2、k 3fftf

20、1ff以此类推,直到当前坐标没有可前进方向 ,且堆栈中没有示处理完的分岔点 时结束.最终可以得到如下图所示的等高图.等高图的数字即为步数,也就是代表 其相对应的位置,距离起点的最少方格数,如坐标(2 , 2)距离起点的有 5 格,坐标(3 , 2)距离起点有 8 格.45673458236114580123图 3-13 等高图最终的示意图1.6.3 转弯加权的等高图制作由于电脑鼠转弯要浪费一定时间,如图 3-13 所示,虽然(0 , 2)点和(1 , 1) 点的等高值都为 3,但肯定我们会认为电脑鼠从( 0 , 2)点到起点比从( 1 , 1) 点到起点要快.因此,为了寻找一条最优的路径 (也

21、就是能最快达到路径),可以给转弯点加 权.假设权值为1,即经过转变前进的坐标的等高值是由当前等高值加 2得到的.加权后的等高图如下图所示,加权值可以根据自己电脑鼠转弯性能来决定. 这里我们设置为 1.4635241678610s108120123图 3-14 转弯加权后的等高图1.7 软件结构框架电脑鼠在运行中可以划分为四个状态 : 等待状态、启动状态、搜索迷宫状 态和冲刺状态.1. 等待状态 在该状态中,电脑鼠静止在起点,等待开始按键的按下,同时实时显示传感器 检测结果,这样方便调试传感器的灵敏度 . 当控制启动的按键按下后 ,电脑鼠进 入启动状态.2. 启动状态 在该状态中,电脑鼠根据第一

22、次转弯的方向判断起点是在坐标的(0 , 0)点还 是( 15 , 0)点,其程序流程图见下图所示.3. 搜索迷宫状态N.心边仃路？右边育路标数组屮储心 绘点坐标宫地图的 状态7 修改起点餡 横座标为15前进一格墳壁检测修改愉的 横地标为1,XZ标数红叩储血 起点坐林修改己碼存 的墙壁坐杯 资料疋入搜寻迷 宫地图的 状态图 3-15 判断起点坐标程序流程图在该状态中,电脑鼠的任务就是探索并记忆迷宫地图 .这里采用右手搜索法则,并搜索全迷宫.其程序流程图见下图.出未送过的跑点坐股用彳于袪划前进一棉图 3-16 迷宫搜索流程图4. 冲刺状态迷宫搜索完毕后,根据算法找出一条最优路径冲刺到终点 .冲刺结束后返回 到起点.