智能鼠原理与制作（高级篇）（中英双语版）课件 项目三 掌握经典迷宫搜索算法

项目三掌握经典迷宫搜索算法1学习目标（1）学习等高图的制作及优化。（2）学习智能鼠的左手、右手、中心法则。（3）学习多种智能鼠的程序设计算法。等高图就是等高线地图的简称，有如一般地图可以标出同一高度的地区范围，或有如气象报告时的等气压图，可以标出相等气压的范围及大小。那么等高图运用在迷宫地图上，可以标出每个迷宫格到起点相等（对等）步数的关系。许多封闭路径的逃脱与冲刺的关卡都可在制作出等高图后迎刃而解，使智能鼠更容易逃脱，少走一些弯路。2任务一掌握等高图的制作及优化任务二掌握智能鼠的右手法则任务三掌握智能鼠的左手法则任务四掌握智能鼠的优化算法——中心法则及优化任务五了解Flood扩散算法任务六了解几种重要的智能鼠逻辑算法3任务一掌握等高图的制作及优化一、墙壁资料当智能鼠达到一方格坐标时，应根据传感器检测结果记录下当前方格的墙壁资料。为了方便管理和节省存储空间，每一个字节变量的低四位分别用来存储一个方格四周的墙壁资料，见右表，迷宫共有16×16个方格，所以可以定义一个16×16的二维数组变量来保存整个迷宫墙壁资料。迷宫墙壁资料全部初始化为0，凡是走过的迷宫格至少有一方没有墙壁，即墙壁资料不为0，这样就可以通过单元格存储的墙壁资料是否为0来确定该单元格是否曾搜索过。变量位绝对方向相对方向bit0上方01：有路，0：有墙壁bit1右方11：有路，0：有墙壁bit2下方21：有路，0：有墙壁bit3左方31：有路，0：有墙壁Bit4～bit7

保留位4任务一掌握等高图的制作及优化核心函数：__wallCheck/************************************************************************************Functionname:__wallCheck**Descriptions:根据传感器检测结果判断是否存在墙壁**Returnedvalue:低三位从左到右依次表示左、前、右是否有墙壁，1有墙，0无墙。**********************************************************************************/void__wallCheck(void){uint8ucMap=0;uint8uctemp=0;ucMap|=MOUSEWAY_B;if(__GucDistance[__LEFT]&0x01){ucMap&=~MOUSEWAY_L;uctemp|=0x06;}else{ucMap|=MOUSEWAY_L;}if(__GucDistance[__FRONT]&0x01){ucMap&=~MOUSEWAY_F;uctemp|=0x40;}else{ucMap|=MOUSEWAY_F;}if(__GucDistance[__RIGHT]&0x01){ucMap&=~MOUSEWAY_R;uctemp|=0x30;}else{ucMap|=MOUSEWAY_R;}GucMapBlock0[GmcMouse.cX][GmcMouse.cY]=ucMap;GucMapBlock[GmcMouse.cX][GmcMouse.cY]=ucMap;GucMapBlock1[GmcMouse.cX][GmcMouse.cY]=ucMap;if(GmcMouse.cY<(MAZETYPE-1)){GucMapBlock1[GmcMouse.cX][GmcMouse.cY+1]&=~(((~ucMap)&0x01)*4);}if(GmcMouse.cX<(MAZETYPE-1)){GucMapBlock1[GmcMouse.cX+1][GmcMouse.cY]&=~(((~ucMap)&0x02)*4);}if(GmcMouse.cY>0){GucMapBlock1[GmcMouse.cX][GmcMouse.cY-1]&=~(((~ucMap)&0x04)/4);}if(GmcMouse.cX>0){GucMapBlock1[GmcMouse.cX-1][GmcMouse.cY]&=~(((~ucMap)&0x08)/4);}

if(GmcMouse.cY<(MAZETYPE-1)){GucMapBlock[GmcMouse.cX][GmcMouse.cY+1]|=((ucMap&0x01)*4);}if(GmcMouse.cX<(MAZETYPE-1)){GucMapBlock[GmcMouse.cX+1][GmcMouse.cY]|=((ucMap&0x02)*4);}if(GmcMouse.cY>0){GucMapBlock[GmcMouse.cX][GmcMouse.cY-1]|=((ucMap&0x04)/4);}if(GmcMouse.cX>0){GucMapBlock[GmcMouse.cX-1][GmcMouse.cY]|=((ucMap&0x08)/4);}zlg7289Download(2,2,0,uctemp);}5任务一掌握等高图的制作及优化二、等高图制作及优化1.等高图制作首先开辟一块16×16的二维数组空间（MapStep[16][16]），其中每一个元素代表迷宫中的一个方格，用以计算后储存各方格至起点的最短路径步数（所谓步数即为路径中经过的方格数）。当起点坐标处标识为1时，可以直接达到的相邻方格均为2，再远的方格的等高值依次递增。这样距离越远的地方等高值越大。2.等高图转弯优化由于智能鼠转弯要浪费一定时间，虽然(0，2)点和(1，1)点的等高值都为3，但肯定会认为等高图从(0，2)点到起点比从(1，1)点到起点要快。因此，为了寻找一条最优的路径(也就是能最快达到路径)，可以给转弯点加权。假设权值为1，即经过转变前进的坐标的等高值是由当前等高值加2得到的。转弯加权后的等高图如图2-3-1所示，加权值可以根据自己智能鼠转弯性能来决定，这里设置为1。6任务一掌握等高图的制作及优化核心函数：mapStepEdit/********************************************************************************Functionname:mapStepEdit**Descriptions:制作等高图**uiX:目的地横坐标**uiY:目的地纵坐标**outputparameters:GucMapStep[][]:各坐标上的等高值******************************************************************************/voidmapStepEdit(int8cX,int8cY){uint8n=0;/*GmcStack[]下标*/uint8ucStep=1;/*等高值*/uint8ucStat=0;/*统计可前进的方向数*/uint8i,j;GmcStack[n].cX=cX;/*起点x值入栈*/GmcStack[n].cY=cY;/*起点y值入栈*/n++;for(i=0;i<MAZETYPE;i++){//初始化各坐标等高值for(j=0;j<MAZETYPE;j++){GucMapStep[i][j]=0xff;}}while(n){//制作等高图，直到堆栈中数据处理完毕GucMapStep[cX][cY]=ucStep++;/*填入等高值*/ucStat=0;if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))//如果前方有路且前方等高值大于计划设定值{ucStat++;//可前进方向数+1}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep))){ucStat++;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep))){ucStat++;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep))){ucStat++;}if(ucStat==0){n--;cX=GmcStack[n].cX;cY=GmcStack[n].cY;ucStep=GucMapStep[cX][cY];}else{if(ucStat>1){/*有多个可前进方向，保存坐标*/GmcStack[n].cX=cX;GmcStack[n].cY=cY;n++;}//选一条可前进方向if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))//上方有路且等高值大于计划设定值{cY++;continue;}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep))){cX++;continue;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep))){cY--;continue;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep))){cX--;continue;}}}}7任务二掌握智能鼠的右手法则当智能鼠在前进时，如果在前进的方向上存在两条和两条以上的支路时，它需要选择向哪个方向转弯，转弯的方向不同导致智能鼠的运动路径也不同。可以使智能鼠优先考虑向右转弯，其次向前直行，最后才考虑向左转弯，这种策略方法称为右手法则。如右图所示，图中坐标（0，0）为智能鼠出发点，虚线为智能鼠运动路径，可以很清楚的看到，每当智能鼠遇到分支路口时，它都会选择优先向右转弯，不能右转弯时智能鼠会选择向前直行，当它既不能右转弯也不能直行时才会向左转弯。以右手法则示意图中的几个关键点为例进行解释，决策对应如右表所示。在坐标（0，4）处，智能鼠可以选择前进或右转，那么依据右手法则最终会选择右转；在坐标（2，0）处，智能鼠可以选择左转或右转，依据右手法则最终会选择右转；在坐标（4，0）处，智能鼠可以选择左转或前进，依据右手法则最终会选择前进。坐标点方向选择项最终策略选择（0，4）前进、右转右转（2，0）左转、右转右转（4，0）左转、前进前进8任务三掌握智能鼠的左手法则与右手法则相似，在迷宫搜索方法策略上，智能鼠优先考虑向左转弯，其次是向前直行，最后考虑向右转弯，这种策略称为左手法则。示意图如右图所示，图中智能鼠出发点依然是坐标（0，0），虚线依然为智能鼠运动路径，不同的是，每当智能鼠遇到分支路口时，它都会选择优先向左转弯；不能左转弯时，智能鼠会选择向前直行；当它既不能左转弯也不能直行时才会向右转弯。以左手法则示意图中的几个关键点为例进行解释，决策对应如右表所示。在坐标（2，6）处，智能鼠可以选择左转或右转，那么依据左手法则最终会选择左转；在坐标（1，8）处，智能鼠可以选择前进或右转，依据左手法则最终会选择前进；在坐标（2，F）处，智能鼠可以选择右转或前进，依据左手法则最终会选择右转。坐标点方向选择项最终策略选择（2，6）左转、右转左转（1，8）前进、右转前进（2，F）右转、前进右转9任务四掌握智能鼠的优化算法——中心法则及优化一、中心法则中心法则是指：当智能鼠在前进的方向上遇到两条或两条以上的支路时，优先选离中心点最近的方向行进。同时有两个离中心最近的方向供选择时，选择直线方向。把迷宫分为四个对等的区域(1、2、3、4)，通过观察可得到，各个区域中智能鼠向哪个方向上运动更能接近中心，如右图所示中箭头所指。如果智能鼠前进的方向上遇到两系支路方向都是离迷宫中心最近的方向，优先选择可以直线前进的方向，其次选择只用转弯90°的方向。如果可前进的支路方向都是远离中心的方向时，优先选择直线运行方向，其次选择转弯90°的方向，其搜索示意图如右图所示。10任务四掌握智能鼠的优化算法——中心法则及优化二、中心分割法则中心分割法则是中心算法的优化，是指将迷宫分为几个部分，根据每个部分相对于目标区域的位置和当前智能鼠行进的绝对方向，采用不同的法则来控制智能鼠运行。如图2-3-6所示中右上角区域，当智能鼠向上行进时，采用左手法则；当智能鼠向右行进时，采用右手法则；当智能鼠向下行进时，采用中右法则：当智能鼠向左行进时，采用中左法则。11任务五了解Flood扩散算法一、Flood-Fill算法概述Flood-Fill算法又称为洪水扩散算法，是当前智能鼠中使用最为广泛的一种算法，其思路来源于水往低处流的自然现象。洪水扩散算法的基本思想是将迷宫终点看成是数值为1的低洼，并且从终点开始，相邻的单元格的数值依次递增1。单元格数值一方面表明了其距离终点的距离，另一方面说明了该单元格的高度，最终起点处的智能鼠按照拱水填充的方法，沿着逐渐变低的地势〈单元格数值）流动就可以到达迷宫终点。Flood扩散算法可以在搜索迷宫中使用，也可以在迷宫冲剌阶段中使用。在搜索中使用时，由于迷宫信息并不全，此时可以将未知的迷宫单元格全部看成是无挡板通路，即最优状况，通过迷宫信息的不断扩充，单元格中的数字也将发生变化，直到智能鼠找到出口为止。如图2-3-7所示，结合直行优先对Flood扩散算法进行阐述。12任务五了解Flood扩散算法Flood扩散算法是一个不断对行进单元格进行重新赋值的过程。在以上的算法详述中，使用了直行优先法则。但是如果使用右手法则进行Flood扩散算法，则找到的终点通道并不是迷宫最佳通道，因此，如果系统使用Flood扩散算法得到最优路径，则需要对迷宫进行完全搜索。13任务五了解Flood扩散算法二、基于Flood扩散算法的等高图制作三、Flood扩散算法优化—迷宫补全迷宫补全是利用获得的信息，对某些只有一个入口的死路迷宫通道进行预测，并将这些处于死路的通道区域进行“封锁”，从而避免智能鼠进入这些无关紧要的死区进行搜索，在某些地图中大大节省了搜索时间。该补全算法要求智能鼠在对当前单元格进行坐标挡板更新的同时，也将该单元格相邻的单元格信息进行更新，比如对于坐标（3，3）的挡板信息为右侧有挡饭，则可以同时对左边坐标（3，4）的信息添加为左侧有挡板，并对确定的死区区城添加虚拟墙壁，以阻止算法的扩散，减少算法的运算量。迷宫补全和Flood扩散相结合可以减少对死区的搜索。这对于需要进行完全搜索的Flood扩散算法是非常有利的。如图所示，图中阴影部分为在右手法则下，通过迷宫补全算法对“死区”的判断，从中可以看出大量减少了智能鼠的搜索时间（图中灰色底纹部分不会再行走了）。14任务六了解几种重要的智能鼠逻辑算法一、搜索算法智能鼠采用基于曼哈顿距离的A-Star搜索方法。智能鼠在每一步都会计算下一格到终点的曼哈顿距离，然后选择距离终点最近的方向前进，当两个方向与终点距离相同时，智能鼠优先直行。路径选择程序如下：核心算法：RightPathcharRightPath(intXX,intYY){charBlockNow;BlockNow=GucMapBlock[XX][YY];intDis[4]={99,99,99,99};charGoDer=GOAHEAD;intMinDis=99;if((!(BlockNow&0x01))&&(!(GucMapBlock[XX][YY+1]&0x10)))//判断前方是否可行{Dis[0]=abs(YY+1-DEST_Y)+abs(XX-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x02))&&(!(GucMapBlock[XX+1][YY]&0x10)))//判断右方是否可行{Dis[1]=abs(YY-DEST_Y)+abs(XX+1-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x04))&&(!(GucMapBlock[XX][YY-1]&0x10)))//判断后方是否可行{Dis[2]=abs(YY-1-DEST_Y)+abs(XX-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x08))&&(!(GucMapBlock[XX-1][YY]&0x10)))//判断左方是否可行{Dis[3]=abs(YY-DEST_Y)+abs(XX-1-DEST_X);//计算曼哈顿距离}

intDire=GucMouseDir/2;MinDis=Dis[Dire];

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNRIGHT;}

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNBACK;}

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNLEFT;}returnGoDer;}15任务六了解几种重要的智能鼠逻辑算法二、洪水算法智能鼠采用洪水算法制作等高图。程序如下：核心算法：mapStepEditvoidmapStepEdit(intcX,intcY){intn=0;/*GmcStack[]下标*/intucStep=1;/*等高值*/charucStat=0;/*统计可前进的方向数*/chari,j;

GmcStack[n].cX=cX;/*起点X值入栈*/GmcStack[n].cY=cY;/*起点Y值入栈*/n++;/*初始化各坐标等高值*/for(i=0;i<MAZETYPE_X;i++){for(j=0;j<MAZETYPE_Y;j++){GucMapStep[i][j]=9999;}}/*制作等高图，直到堆栈中所有数据处理完毕*/while(n){if(er==1)break;GucMapStep[cX][cY]=ucStep++;/*填入等高值*//*对当前坐标格里可前进的方向统计*/ucStat=0;if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*前方有路*/{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x02){}else/*右方有路*/{if(GucMapStep[cX+1][cY]>ucStep){/*右方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x04){}else/*后方有路*/{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(GucMapStep[cX-1][cY]>ucStep){/*左方等高值大于计划设定值*/ucStat++;}}}/**没有可前进的方向，则跳转到最近保存的分支点*否则任选一可前进方向前进*/if(ucStat==0){n--;cX=GmcStack[n].cX;cY=GmcStack[n].cY;ucStep=GucMapStep[cX][cY];}else{if(ucStat>1){/*有多个可前进方向，保存坐标*/GmcStack[n].cX=cX;/*横坐标X值入栈*/GmcStack[n].cY=cY;/*纵坐标Y值入栈*/n++;}/*任意选择一条可前进的方向前进*/if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于计划设定值*/cY++;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x02){}else{if(GucMapStep[cX+1][cY]>ucStep){/*右等高值大于计划设定值*/cX++;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x04){}else{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于计划设定值*/cY--;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x08){}else{if(GucMapStep[cX-1][cY]>ucStep){/*左方等高值大于计划设定值*/cX--;/*修改坐标*/continue;}}}}}}16任务六了解几种重要的智能鼠逻辑算法三、直接到指定坐标程序设计该程序块的目的是实现控制智能鼠能够以最短路径前进到指定坐标点。当然该功能实现的前提是目的地是智能鼠已经走过且记录下来的方格。设计该程序的步骤如下：（1）制作以目的地为起点的等高图。（2）检查算法是否已搜索到目的地，如果是则跳到第（6）步，否则继续顺序执行。（3）获取当前坐标的等高值。（4）寻找比当前坐标等高值小的支路方向，且优先选择不需要转弯的方向前进。如果选择的方向就是正前方，则前进步数cNBlock加1并返回第（2）步，否则继续执行。（5）根据目标方向记录智能鼠转弯，完成后返回第（2）步。（6）智能鼠依次执行记录记录的操作。（7）按搜索法则选择下一步动作。核心函数1：objectGoTocharobjectGoTo(intcXdst,intcYdst,charOK){intucStep=1;charNEXTS=0xFF;charcNBlock=0,cDirTemp;charMouseDir=GucMouseDir;intcX,cY;Step=0;cX=GmcMouseCoor.cX;cY=GmcMouseCoor.cY;mapStepEdit(cXdst,cYdst);/*制作等高图*//**根据等高值向目标点运动，直到达到目的地*/while(er==0){ucStep=GucMapStep[cX][cY];

if((cX==cXdst)&&(cY==cYdst)){SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;break;}/**任选一个等高值比当前自身等高值小的方向前进*/if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*上方有路*/{if(GucMapStep[cX][cY+1]<ucStep){/*上方等高值较小*/cDirTemp=UP;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cY++;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(GucMapStep[cX-1][cY]<ucStep){/*左方等高值较小*/cDirTemp=LEFT;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cX--;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x02){}else{/*右方有路*/if(GucMapStep[cX+1][cY]<ucStep){/*右方等高值较小*/cDirTemp=RIGHT;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cX++;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x04){}else{/*下方有路*/if(GucMapStep[cX][cY-1]<ucStep){/*下方等高值较小*/cDirTemp=DOWN;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cY--;continue;/*跳过本次循环*/}}}}SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;MouseDir=cDirTemp;cNBlock=0;}for(inti=0;i<Step;i++)//依次执行动作{Micromouse_SearchGoAhead(i);if(SpurtStep[i].nextrad==2){Turn_Right90();}elseif(SpurtStep[i].nextrad==4){Turn_Back();GmLeft.ucState=MOTORRUN;GmRight.ucState=MOTORRUN;GucMouseState=GOAHEAD;}elseif(SpurtStep[i].nextrad==6){Turn_Left90();}}GmcMouseCoor.cX=cX;GmcMouseCoor.cY=cY;if(OK==0){NEXTS=RightPath(GmcMouseCoor.cX,GmcMouseCoor.cY);//继续搜索}returnNEXTS;}17任务六了解几种重要的智能鼠逻辑算法核心函数2：objectGoTovoidobjectGoTo(int8cXdst,int8cYdst){uint8ucStep=1;int8cNBlock=0,cDirTemp;int8cX,cY;GucCrossroad=0;cX=GmcMouse.cX;cY=GmcMouse.cY;mapStepEdit(cXdst,cYdst);/*首先制作等高图*//*根据等高值向目标点运动*/while((cX!=cXdst)||(cY!=cYdst)){ucStep=GucMapStep[cX][cY];/*选一个等高值比自身小的方向前进*/if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]<ucStep))//上方有路且等高值较小{cDirTemp=UP;//记录方向

if(cDirTemp==GucMouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一格*/

cY++;if((GucMapBlock[cX][cY]&0x0f)==0x0f)GucCrossroad++;continue;}}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]<ucStep)){cDirTemp=RIGHT;if(cDirTemp==GucMouseDir){cNBlock++;cX++;if((GucMapBlock[cX][cY]&0x0f)==0x0f)GucCrossroad++;continue;}}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]<ucStep)){cDirTemp=DOWN;if(cDirTemp==GucMouseDir){cNBlock++;cY--;if((GucMapBlock[cX][cY]&0x0f)==0x0f)GucCrossroad++;continu