智能鼠原理與制作（高級篇）（中英雙語版）課件 項(xiàng)目三 掌握經(jīng)典迷宮搜索算法

項(xiàng)目三掌握經(jīng)典迷宮搜索算法1學(xué)習(xí)目標(biāo)（1）學(xué)習(xí)等高圖的制作及優(yōu)化。（2）學(xué)習(xí)智能鼠的左手、右手、中心法則。（3）學(xué)習(xí)多種智能鼠的程序設(shè)計(jì)算法。等高圖就是等高線地圖的簡稱，有如一般地圖可以標(biāo)出同一高度的地區(qū)范圍，或有如氣象報(bào)告時的等氣壓圖，可以標(biāo)出相等氣壓的范圍及大小。那么等高圖運(yùn)用在迷宮地圖上，可以標(biāo)出每個迷宮格到起點(diǎn)相等（對等）步數(shù)的關(guān)系。許多封閉路徑的逃脫與沖刺的關(guān)卡都可在制作出等高圖后迎刃而解，使智能鼠更容易逃脫，少走一些彎路。2任務(wù)一掌握等高圖的制作及優(yōu)化任務(wù)二掌握智能鼠的右手法則任務(wù)三掌握智能鼠的左手法則任務(wù)四掌握智能鼠的優(yōu)化算法——中心法則及優(yōu)化任務(wù)五了解Flood擴(kuò)散算法任務(wù)六了解幾種重要的智能鼠邏輯算法3任務(wù)一掌握等高圖的制作及優(yōu)化一、墻壁資料當(dāng)智能鼠達(dá)到一方格坐標(biāo)時，應(yīng)根據(jù)傳感器檢測結(jié)果記錄下當(dāng)前方格的墻壁資料。為了方便管理和節(jié)省存儲空間，每一個字節(jié)變量的低四位分別用來存儲一個方格四周的墻壁資料，見右表，迷宮共有16×16個方格，所以可以定義一個16×16的二維數(shù)組變量來保存整個迷宮墻壁資料。迷宮墻壁資料全部初始化為0，凡是走過的迷宮格至少有一方?jīng)]有墻壁，即墻壁資料不為0，這樣就可以通過單元格存儲的墻壁資料是否為0來確定該單元格是否曾搜索過。變量位絕對方向相對方向bit0上方01：有路，0：有墻壁bit1右方11：有路，0：有墻壁bit2下方21：有路，0：有墻壁bit3左方31：有路，0：有墻壁Bit4～bit7

保留位4任務(wù)一掌握等高圖的制作及優(yōu)化核心函數(shù)：__wallCheck/************************************************************************************Functionname:__wallCheck**Descriptions:根據(jù)傳感器檢測結(jié)果判斷是否存在墻壁**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任務(wù)一掌握等高圖的制作及優(yōu)化二、等高圖制作及優(yōu)化1.等高圖制作首先開辟一塊16×16的二維數(shù)組空間（MapStep[16][16]），其中每一個元素代表迷宮中的一個方格，用以計(jì)算后儲存各方格至起點(diǎn)的最短路徑步數(shù)（所謂步數(shù)即為路徑中經(jīng)過的方格數(shù)）。當(dāng)起點(diǎn)坐標(biāo)處標(biāo)識為1時，可以直接達(dá)到的相鄰方格均為2，再遠(yuǎn)的方格的等高值依次遞增。這樣距離越遠(yuǎn)的地方等高值越大。2.等高圖轉(zhuǎn)彎優(yōu)化由于智能鼠轉(zhuǎn)彎要浪費(fèi)一定時間，雖然(0，2)點(diǎn)和(1，1)點(diǎn)的等高值都為3，但肯定會認(rèn)為等高圖從(0，2)點(diǎn)到起點(diǎn)比從(1，1)點(diǎn)到起點(diǎn)要快。因此，為了尋找一條最優(yōu)的路徑(也就是能最快達(dá)到路徑)，可以給轉(zhuǎn)彎點(diǎn)加權(quán)。假設(shè)權(quán)值為1，即經(jīng)過轉(zhuǎn)變前進(jìn)的坐標(biāo)的等高值是由當(dāng)前等高值加2得到的。轉(zhuǎn)彎加權(quán)后的等高圖如圖2-3-1所示，加權(quán)值可以根據(jù)自己智能鼠轉(zhuǎn)彎性能來決定，這里設(shè)置為1。6任務(wù)一掌握等高圖的制作及優(yōu)化核心函數(shù)：mapStepEdit/********************************************************************************Functionname:mapStepEdit**Descriptions:制作等高圖**uiX:目的地橫坐標(biāo)**uiY:目的地縱坐標(biāo)**outputparameters:GucMapStep[][]:各坐標(biāo)上的等高值******************************************************************************/voidmapStepEdit(int8cX,int8cY){uint8n=0;/*GmcStack[]下標(biāo)*/uint8ucStep=1;/*等高值*/uint8ucStat=0;/*統(tǒng)計(jì)可前進(jìn)的方向數(shù)*/uint8i,j;GmcStack[n].cX=cX;/*起點(diǎn)x值入棧*/GmcStack[n].cY=cY;/*起點(diǎn)y值入棧*/n++;for(i=0;i<MAZETYPE;i++){//初始化各坐標(biāo)等高值for(j=0;j<MAZETYPE;j++){GucMapStep[i][j]=0xff;}}while(n){//制作等高圖，直到堆棧中數(shù)據(jù)處理完畢GucMapStep[cX][cY]=ucStep++;/*填入等高值*/ucStat=0;if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))//如果前方有路且前方等高值大于計(jì)劃設(shè)定值{ucStat++;//可前進(jìn)方向數(shù)+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){/*有多個可前進(jìn)方向，保存坐標(biāo)*/GmcStack[n].cX=cX;GmcStack[n].cY=cY;n++;}//選一條可前進(jìn)方向if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))//上方有路且等高值大于計(jì)劃設(shè)定值{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任務(wù)二掌握智能鼠的右手法則當(dāng)智能鼠在前進(jìn)時，如果在前進(jìn)的方向上存在兩條和兩條以上的支路時，它需要選擇向哪個方向轉(zhuǎn)彎，轉(zhuǎn)彎的方向不同導(dǎo)致智能鼠的運(yùn)動路徑也不同?？梢允怪悄苁髢?yōu)先考慮向右轉(zhuǎn)彎，其次向前直行，最后才考慮向左轉(zhuǎn)彎，這種策略方法稱為右手法則。如右圖所示，圖中坐標(biāo)（0，0）為智能鼠出發(fā)點(diǎn)，虛線為智能鼠運(yùn)動路徑，可以很清楚的看到，每當(dāng)智能鼠遇到分支路口時，它都會選擇優(yōu)先向右轉(zhuǎn)彎，不能右轉(zhuǎn)彎時智能鼠會選擇向前直行，當(dāng)它既不能右轉(zhuǎn)彎也不能直行時才會向左轉(zhuǎn)彎。以右手法則示意圖中的幾個關(guān)鍵點(diǎn)為例進(jìn)行解釋，決策對應(yīng)如右表所示。在坐標(biāo)（0，4）處，智能鼠可以選擇前進(jìn)或右轉(zhuǎn)，那么依據(jù)右手法則最終會選擇右轉(zhuǎn)；在坐標(biāo)（2，0）處，智能鼠可以選擇左轉(zhuǎn)或右轉(zhuǎn)，依據(jù)右手法則最終會選擇右轉(zhuǎn)；在坐標(biāo)（4，0）處，智能鼠可以選擇左轉(zhuǎn)或前進(jìn)，依據(jù)右手法則最終會選擇前進(jìn)。坐標(biāo)點(diǎn)方向選擇項(xiàng)最終策略選擇（0，4）前進(jìn)、右轉(zhuǎn)右轉(zhuǎn)（2，0）左轉(zhuǎn)、右轉(zhuǎn)右轉(zhuǎn)（4，0）左轉(zhuǎn)、前進(jìn)前進(jìn)8任務(wù)三掌握智能鼠的左手法則與右手法則相似，在迷宮搜索方法策略上，智能鼠優(yōu)先考慮向左轉(zhuǎn)彎，其次是向前直行，最后考慮向右轉(zhuǎn)彎，這種策略稱為左手法則。示意圖如右圖所示，圖中智能鼠出發(fā)點(diǎn)依然是坐標(biāo)（0，0），虛線依然為智能鼠運(yùn)動路徑，不同的是，每當(dāng)智能鼠遇到分支路口時，它都會選擇優(yōu)先向左轉(zhuǎn)彎；不能左轉(zhuǎn)彎時，智能鼠會選擇向前直行；當(dāng)它既不能左轉(zhuǎn)彎也不能直行時才會向右轉(zhuǎn)彎。以左手法則示意圖中的幾個關(guān)鍵點(diǎn)為例進(jìn)行解釋，決策對應(yīng)如右表所示。在坐標(biāo)（2，6）處，智能鼠可以選擇左轉(zhuǎn)或右轉(zhuǎn)，那么依據(jù)左手法則最終會選擇左轉(zhuǎn)；在坐標(biāo)（1，8）處，智能鼠可以選擇前進(jìn)或右轉(zhuǎn)，依據(jù)左手法則最終會選擇前進(jìn)；在坐標(biāo)（2，F(xiàn)）處，智能鼠可以選擇右轉(zhuǎn)或前進(jìn)，依據(jù)左手法則最終會選擇右轉(zhuǎn)。坐標(biāo)點(diǎn)方向選擇項(xiàng)最終策略選擇（2，6）左轉(zhuǎn)、右轉(zhuǎn)左轉(zhuǎn)（1，8）前進(jìn)、右轉(zhuǎn)前進(jìn)（2，F(xiàn)）右轉(zhuǎn)、前進(jìn)右轉(zhuǎn)9任務(wù)四掌握智能鼠的優(yōu)化算法——中心法則及優(yōu)化一、中心法則中心法則是指：當(dāng)智能鼠在前進(jìn)的方向上遇到兩條或兩條以上的支路時，優(yōu)先選離中心點(diǎn)最近的方向行進(jìn)。同時有兩個離中心最近的方向供選擇時，選擇直線方向。把迷宮分為四個對等的區(qū)域(1、2、3、4)，通過觀察可得到，各個區(qū)域中智能鼠向哪個方向上運(yùn)動更能接近中心，如右圖所示中箭頭所指。如果智能鼠前進(jìn)的方向上遇到兩系支路方向都是離迷宮中心最近的方向，優(yōu)先選擇可以直線前進(jìn)的方向，其次選擇只用轉(zhuǎn)彎90°的方向。如果可前進(jìn)的支路方向都是遠(yuǎn)離中心的方向時，優(yōu)先選擇直線運(yùn)行方向，其次選擇轉(zhuǎn)彎90°的方向，其搜索示意圖如右圖所示。10任務(wù)四掌握智能鼠的優(yōu)化算法——中心法則及優(yōu)化二、中心分割法則中心分割法則是中心算法的優(yōu)化，是指將迷宮分為幾個部分，根據(jù)每個部分相對于目標(biāo)區(qū)域的位置和當(dāng)前智能鼠行進(jìn)的絕對方向，采用不同的法則來控制智能鼠運(yùn)行。如圖2-3-6所示中右上角區(qū)域，當(dāng)智能鼠向上行進(jìn)時，采用左手法則；當(dāng)智能鼠向右行進(jìn)時，采用右手法則；當(dāng)智能鼠向下行進(jìn)時，采用中右法則：當(dāng)智能鼠向左行進(jìn)時，采用中左法則。11任務(wù)五了解Flood擴(kuò)散算法一、Flood-Fill算法概述Flood-Fill算法又稱為洪水?dāng)U散算法，是當(dāng)前智能鼠中使用最為廣泛的一種算法，其思路來源于水往低處流的自然現(xiàn)象。洪水?dāng)U散算法的基本思想是將迷宮終點(diǎn)看成是數(shù)值為1的低洼，并且從終點(diǎn)開始，相鄰的單元格的數(shù)值依次遞增1。單元格數(shù)值一方面表明了其距離終點(diǎn)的距離，另一方面說明了該單元格的高度，最終起點(diǎn)處的智能鼠按照拱水填充的方法，沿著逐漸變低的地勢〈單元格數(shù)值）流動就可以到達(dá)迷宮終點(diǎn)。Flood擴(kuò)散算法可以在搜索迷宮中使用，也可以在迷宮沖剌階段中使用。在搜索中使用時，由于迷宮信息并不全，此時可以將未知的迷宮單元格全部看成是無擋板通路，即最優(yōu)狀況，通過迷宮信息的不斷擴(kuò)充，單元格中的數(shù)字也將發(fā)生變化，直到智能鼠找到出口為止。如圖2-3-7所示，結(jié)合直行優(yōu)先對Flood擴(kuò)散算法進(jìn)行闡述。12任務(wù)五了解Flood擴(kuò)散算法Flood擴(kuò)散算法是一個不斷對行進(jìn)單元格進(jìn)行重新賦值的過程。在以上的算法詳述中，使用了直行優(yōu)先法則。但是如果使用右手法則進(jìn)行Flood擴(kuò)散算法，則找到的終點(diǎn)通道并不是迷宮最佳通道，因此，如果系統(tǒng)使用Flood擴(kuò)散算法得到最優(yōu)路徑，則需要對迷宮進(jìn)行完全搜索。13任務(wù)五了解Flood擴(kuò)散算法二、基于Flood擴(kuò)散算法的等高圖制作三、Flood擴(kuò)散算法優(yōu)化—迷宮補(bǔ)全迷宮補(bǔ)全是利用獲得的信息，對某些只有一個入口的死路迷宮通道進(jìn)行預(yù)測，并將這些處于死路的通道區(qū)域進(jìn)行“封鎖”，從而避免智能鼠進(jìn)入這些無關(guān)緊要的死區(qū)進(jìn)行搜索，在某些地圖中大大節(jié)省了搜索時間。該補(bǔ)全算法要求智能鼠在對當(dāng)前單元格進(jìn)行坐標(biāo)擋板更新的同時，也將該單元格相鄰的單元格信息進(jìn)行更新，比如對于坐標(biāo)（3，3）的擋板信息為右側(cè)有擋飯，則可以同時對左邊坐標(biāo)（3，4）的信息添加為左側(cè)有擋板，并對確定的死區(qū)區(qū)城添加虛擬墻壁，以阻止算法的擴(kuò)散，減少算法的運(yùn)算量。迷宮補(bǔ)全和Flood擴(kuò)散相結(jié)合可以減少對死區(qū)的搜索。這對于需要進(jìn)行完全搜索的Flood擴(kuò)散算法是非常有利的。如圖所示，圖中陰影部分為在右手法則下，通過迷宮補(bǔ)全算法對“死區(qū)”的判斷，從中可以看出大量減少了智能鼠的搜索時間（圖中灰色底紋部分不會再行走了）。14任務(wù)六了解幾種重要的智能鼠邏輯算法一、搜索算法智能鼠采用基于曼哈頓距離的A-Star搜索方法。智能鼠在每一步都會計(jì)算下一格到終點(diǎn)的曼哈頓距離，然后選擇距離終點(diǎn)最近的方向前進(jìn)，當(dāng)兩個方向與終點(diǎn)距離相同時，智能鼠優(yōu)先直行。路徑選擇程序如下：核心算法：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);//計(jì)算曼哈頓距離}if((!(BlockNow&0x02))&&(!(GucMapBlock[XX+1][YY]&0x10)))//判斷右方是否可行{Dis[1]=abs(YY-DEST_Y)+abs(XX+1-DEST_X);//計(jì)算曼哈頓距離}if((!(BlockNow&0x04))&&(!(GucMapBlock[XX][YY-1]&0x10)))//判斷后方是否可行{Dis[2]=abs(YY-1-DEST_Y)+abs(XX-DEST_X);//計(jì)算曼哈頓距離}if((!(BlockNow&0x08))&&(!(GucMapBlock[XX-1][YY]&0x10)))//判斷左方是否可行{Dis[3]=abs(YY-DEST_Y)+abs(XX-1-DEST_X);//計(jì)算曼哈頓距離}

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任務(wù)六了解幾種重要的智能鼠邏輯算法二、洪水算法智能鼠采用洪水算法制作等高圖。程序如下：核心算法：mapStepEditvoidmapStepEdit(intcX,intcY){intn=0;/*GmcStack[]下標(biāo)*/intucStep=1;/*等高值*/charucStat=0;/*統(tǒng)計(jì)可前進(jìn)的方向數(shù)*/chari,j;

GmcStack[n].cX=cX;/*起點(diǎn)X值入棧*/GmcStack[n].cY=cY;/*起點(diǎn)Y值入棧*/n++;/*初始化各坐標(biāo)等高值*/for(i=0;i<MAZETYPE_X;i++){for(j=0;j<MAZETYPE_Y;j++){GucMapStep[i][j]=9999;}}/*制作等高圖，直到堆棧中所有數(shù)據(jù)處理完畢*/while(n){if(er==1)break;GucMapStep[cX][cY]=ucStep++;/*填入等高值*//*對當(dāng)前坐標(biāo)格里可前進(jìn)的方向統(tǒng)計(jì)*/ucStat=0;if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*前方有路*/{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于計(jì)劃設(shè)定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x02){}else/*右方有路*/{if(GucMapStep[cX+1][cY]>ucStep){/*右方等高值大于計(jì)劃設(shè)定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x04){}else/*后方有路*/{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于計(jì)劃設(shè)定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(GucMapStep[cX-1][cY]>ucStep){/*左方等高值大于計(jì)劃設(shè)定值*/ucStat++;}}}/**沒有可前進(jìn)的方向，則跳轉(zhuǎn)到最近保存的分支點(diǎn)*否則任選一可前進(jìn)方向前進(jìn)*/if(ucStat==0){n--;cX=GmcStack[n].cX;cY=GmcStack[n].cY;ucStep=GucMapStep[cX][cY];}else{if(ucStat>1){/*有多個可前進(jìn)方向，保存坐標(biāo)*/GmcStack[n].cX=cX;/*橫坐標(biāo)X值入棧*/GmcStack[n].cY=cY;/*縱坐標(biāo)Y值入棧*/n++;}/*任意選擇一條可前進(jìn)的方向前進(jìn)*/if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于計(jì)劃設(shè)定值*/cY++;/*修改坐標(biāo)*/continue;}}if(GucMapBlock[cX][cY]&0x02){}else{if(GucMapStep[cX+1][cY]>ucStep){/*右等高值大于計(jì)劃設(shè)定值*/cX++;/*修改坐標(biāo)*/continue;}}if(GucMapBlock[cX][cY]&0x04){}else{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于計(jì)劃設(shè)定值*/cY--;/*修改坐標(biāo)*/continue;}}if(GucMapBlock[cX][cY]&0x08){}else{if(GucMapStep[cX-1][cY]>ucStep){/*左方等高值大于計(jì)劃設(shè)定值*/cX--;/*修改坐標(biāo)*/continue;}}}}}}16任務(wù)六了解幾種重要的智能鼠邏輯算法三、直接到指定坐標(biāo)程序設(shè)計(jì)該程序塊的目的是實(shí)現(xiàn)控制智能鼠能夠以最短路徑前進(jìn)到指定坐標(biāo)點(diǎn)。當(dāng)然該功能實(shí)現(xiàn)的前提是目的地是智能鼠已經(jīng)走過且記錄下來的方格。設(shè)計(jì)該程序的步驟如下：（1）制作以目的地為起點(diǎn)的等高圖。（2）檢查算法是否已搜索到目的地，如果是則跳到第（6）步，否則繼續(xù)順序執(zhí)行。（3）獲取當(dāng)前坐標(biāo)的等高值。（4）尋找比當(dāng)前坐標(biāo)等高值小的支路方向，且優(yōu)先選擇不需要轉(zhuǎn)彎的方向前進(jìn)。如果選擇的方向就是正前方，則前進(jìn)步數(shù)cNBlock加1并返回第（2）步，否則繼續(xù)執(zhí)行。（5）根據(jù)目標(biāo)方向記錄智能鼠轉(zhuǎn)彎，完成后返回第（2）步。（6）智能鼠依次執(zhí)行記錄記錄的操作。（7）按搜索法則選擇下一步動作。核心函數(shù)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);/*制作等高圖*//**根據(jù)等高值向目標(biāo)點(diǎn)運(yùn)動，直到達(dá)到目的地*/while(er==0){ucStep=GucMapStep[cX][cY];

if((cX==cXdst)&&(cY==cYdst)){SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;break;}/**任選一個等高值比當(dāng)前自身等高值小的方向前進(jìn)*/if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*上方有路*/{if(GucMapStep[cX][cY+1]<ucStep){/*上方等高值較小*/cDirTemp=UP;/*記錄方向*/if(cDirTemp==MouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一個方格*/cY++;continue;/*跳過本次循環(huán)*/}}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(GucMapStep[cX-1][cY]<ucStep){/*左方等高值較小*/cDirTemp=LEFT;/*記錄方向*/if(cDirTemp==MouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一個方格*/cX--;continue;/*跳過本次循環(huán)*/}}}if(GucMapBlock[cX][cY]&0x02){}else{/*右方有路*/if(GucMapStep[cX+1][cY]<ucStep){/*右方等高值較小*/cDirTemp=RIGHT;/*記錄方向*/if(cDirTemp==MouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一個方格*/cX++;continue;/*跳過本次循環(huán)*/}}}if(GucMapBlock[cX][cY]&0x04){}else{/*下方有路*/if(GucMapStep[cX][cY-1]<ucStep){/*下方等高值較小*/cDirTemp=DOWN;/*記錄方向*/if(cDirTemp==MouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一個方格*/cY--;continue;/*跳過本次循環(huán)*/}}}}SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;MouseDir=cDirTemp;cNBlock=0;}for(inti=0;i<Step;i++)//依次執(zhí)行動作{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);//繼續(xù)搜索}returnNEXTS;}17任務(wù)六了解幾種重要的智能鼠邏輯算法核心函數(shù)2：objectGoTovoidobjectGoTo(int8cXdst,int8cYdst){uint8ucStep=1;int8cNBlock=0,cDirTemp;int8cX,cY;GucCrossroad=0;cX=GmcMouse.cX;cY=GmcMouse.cY;mapStepEdit(cXdst,cYdst);/*首先制作等高圖*//*根據(jù)等高值向目標(biāo)點(diǎn)運(yùn)動*/while((cX!=cXdst)||(cY!=cYdst)){ucStep=GucMapStep[cX][cY];/*選一個等高值比自身小的方向前進(jìn)*/if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]<ucStep))//上方有路且等高值較小{cDirTemp=UP;//記錄方向

if(cDirTemp==GucMouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一格*/

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