電腦老鼠走迷宮競賽

1、電腦老鼠走迷宮競賽,算法簡介,08計算機（1）班 龔若皓,軟件算法所需要實現(xiàn)的功能,最基本的功能：1.正確記錄迷宮的信息2.正確記錄小車的狀態(tài)（當前的方向，四周的擋板情況等）3.確保小車的移動，停止和轉(zhuǎn)彎的可控性需要實現(xiàn)的核心功能1.實現(xiàn)基本的從起點到終點的尋路過程。2.實現(xiàn)等高表的生成算法。3.實現(xiàn)從當前的位置通過最有效的路徑移動到指定的任意位置。（通過建立等高表來實現(xiàn)）4.根據(jù)已經(jīng)得到的迷

2、宮地圖信息實現(xiàn)起點到終點的最短路徑分析。（通過建立等高表來實現(xiàn)）,軟件算法所需要實現(xiàn)的功能,可拓展的部分：1.適當修改步進電機的驅(qū)動函數(shù)，提高步進電機的加速和減速功能，提高整體的速度。2.改進尋路算法，最好不要使用傳統(tǒng)的右手法則和左手法則，使用向心法則等高效的尋路方法。3.進行數(shù)據(jù)補全，減少小車進入“死胡同”的次數(shù)。4.改進轉(zhuǎn)彎的方式，盡量實現(xiàn)前進中拐彎，同時確保穩(wěn)定性，提高整體的速度。消除不必要的停頓使小車行駛更

3、加流暢。5.改進傳統(tǒng)的等高表路徑分析算法，實現(xiàn)加權(quán)的等高表算法，將拐彎次數(shù)的信息也加入到最短路徑的分析過程中。,數(shù)據(jù)的存儲方式,1.迷宮信息的存儲 因為迷宮分為16*16=256個方格，所以很直觀地可以想到用一個二維矩陣來存儲一個迷宮的信息，矩陣中的每一個元素用于存儲地圖中一個方格的信息，矩陣每個元素可以定義成Byte型，只用其中的四位就可以存儲方格四面的擋板信息了，有擋板的方向?qū)?yīng)的位置位，沒有擋板

4、的將對應(yīng)位清零。要獲取某一個方格單個方向的擋板信息，只需要做一個簡單的與運算在看結(jié)果是否為零即可。剩下的四位用于其它的用途，例如在后期的加權(quán)等高表生成算法中存儲小車的方向信息。初始化的時候?qū)⒕仃囋氐臄?shù)值低四位初始化為0，標識改坐標是否被探測過。,數(shù)據(jù)的存儲方式,舉例： 假設(shè)Byte型的數(shù)據(jù)Data=0bxxxx1100存儲了某一個方格四個方向的擋板信息，高四位用于存儲其他信息，低四位用于存儲檔板的信息，從高位到低位

5、分別對應(yīng)方向為：上，右，下，左（絕對方向）。 上 右 下 左 0b x x x x 1 1 0 0& 0b 0 0 0 0 0 1 0 0 0b 0 0

6、 0 0 0 1 0 0 結(jié)果不為零，判斷為右邊有擋板,數(shù)據(jù)的存儲方式,2.方向信息的存儲方向 絕對方向：以小車剛剛開始運行的時候車頭面 向的方向作為“上”，

7、其他的方向 類推。 相對方向：顧名思義，相對于當前小車所朝向 的方向的方向。例如絕對方向的下 相對于絕對方向的右的相對方向是 右方,數(shù)據(jù)的存儲方式,方向的分類：小車的車頭朝向的方向： 需要分配空間來固定地存

8、儲下來，平并且在小車運行的過程中隨著轉(zhuǎn)彎而變化，是以絕對方向來表示的。小車轉(zhuǎn)彎的方向： 不需要分配單獨的空間的固定存儲，只需要給不同的轉(zhuǎn)彎方向編制不同的實現(xiàn)函數(shù)就行了，例如給向右轉(zhuǎn)彎編制一個函數(shù)TurnRight()，這里的右方是相對方向，亦即是相對于當前小車的車頭朝向的方向的方向，例如小車當前是朝著絕對方向的右方的，那么現(xiàn)在右轉(zhuǎn)函數(shù)要實現(xiàn)的就是將小車車頭轉(zhuǎn)到面向絕對方向的下方，而不是絕對方向的右方。那么

9、轉(zhuǎn)彎后，記錄小車的車頭方向的變量應(yīng)該怎樣變化呢？,數(shù)據(jù)的存儲方式,絕對方向和相對方向的變換： 假設(shè)數(shù)值0，1，2，3分別表示絕對方向的上，右，下，左，那么就用0，1，2，3中的其中一個數(shù)值來表示當前小車車頭朝向的方向，當然這個數(shù)值是動態(tài)變化的，每轉(zhuǎn)彎一次該數(shù)值應(yīng)當變化一次，例如當前方向的數(shù)值為3（左方），那么經(jīng)過一次右轉(zhuǎn)操作后該數(shù)值就應(yīng)該變化為0了（上方）。其實轉(zhuǎn)化的規(guī)則相當簡單，只要右轉(zhuǎn)方向數(shù)值就加1，只要左轉(zhuǎn)

10、方向數(shù)值就加3，只要后轉(zhuǎn)方向數(shù)值就加2，當然可能有越界的情況，所以得出的方向數(shù)值再進行模運算對4取余數(shù)得出的結(jié)果就是轉(zhuǎn)彎后小車的車頭所面向的方向的數(shù)值了。,數(shù)據(jù)的存儲方式,綜上所述可以得出如下的表格：,數(shù)據(jù)的存儲方式,通過前面的表格可以找到當前的小車方向和轉(zhuǎn)彎后的小車方向的對應(yīng)關(guān)系，得出的相對方向和絕對方向的轉(zhuǎn)換公式如下所示：轉(zhuǎn)彎后的絕對方向=（轉(zhuǎn)彎前的絕對方向+轉(zhuǎn)彎數(shù)值）% 4 小車的車頭方向一般是用一個

11、全局變量來存儲的，方便在轉(zhuǎn)彎的函數(shù)中進行修改，避免C語言中一些作用域的問題。也可以通過傳指針的方式來完成，不過定義為全局變量比較方便。,小車的運行包括的子過程,1.初始探測 確定小車的起點坐標是（0，0）還是（15，0）。2.尋路 在找到迷宮終點的前提下盡量多地通過尋路算法獲取更多的迷宮信息并正確存儲起來。3.反向搜索（可以省略） 在找到迷宮的終點后不馬

12、上返回終點，而是繼續(xù)探索，獲取更多的迷宮信息，為最短路徑的算法提供更多的信息。4.沖刺 在保證穩(wěn)定的情況下，用最快的速度控制小車從起點移動到終點。,尋路算法簡介,尋路是小車在運行的整個過程中進行的第一個操作，目的是讓小車在迷宮中探索，同時記錄已經(jīng)走過的路徑的信息，直到小車找到終點就可以結(jié)束探索尋路的過程了，當然也可以在找到終點后繼續(xù)探索遍歷整個迷宮，使小車盡可能多地收集迷宮的地圖信息，以便后期進行最短路徑的分

13、析計算時能夠運用更多的信息，這樣就可能在分析數(shù)據(jù)后找到更好的最短路徑，得到更好的成績。,尋路算法簡介,尋路算法的兩個關(guān)鍵點：在岔路口的轉(zhuǎn)彎策略以及小車運行的穩(wěn)定性 轉(zhuǎn)彎的策略一定程度上決定了從小車開始運行到找到終點的時間長短。良好的轉(zhuǎn)彎尋路策略可以大量減少不必要的尋路時間，用較高的效率尋找到終點。小車運行的穩(wěn)定性對于尋路過程也十分重要，如果小車運行時姿態(tài)不穩(wěn)定很有可能撞到擋板，這時電機就會空轉(zhuǎn)一段時間，那么統(tǒng)計的數(shù)據(jù)

14、就整個亂掉了，很有可能造成算法崩潰，所以小車的行進和轉(zhuǎn)彎的過程一定要在機械和軟件方面都調(diào)節(jié)到最穩(wěn)定的狀態(tài)，然后再開始設(shè)計后續(xù)的算法。,尋路算法簡介,2. 正確使用堆棧，整個選路算法的運行過程中會大量地使用堆棧的入棧和出棧操作，如果對入棧和出棧的條件判斷不正確，有可能造成數(shù)據(jù)紊亂，整個算法就崩潰了，最好使用調(diào)試版上的數(shù)碼管實時顯示堆棧棧頂?shù)臄?shù)據(jù)，發(fā)現(xiàn)有錯誤就在程序中尋找錯誤，直到整個尋路算法穩(wěn)定為止。,轉(zhuǎn)彎策略簡介,在尋路過程中，如

15、果小車遇到迷宮中的岔路口時，應(yīng)該考慮的問題是在岔路口應(yīng)該選擇哪個方向繼續(xù)行進探索。比較常規(guī)的策略有右手法則，左手法則，優(yōu)先向前法則，向心法則等等，下面詳細介紹一下它們的概念： 右手法則：小車在搜過程中有兩個以上的搜索方向時，優(yōu)先選擇向右轉(zhuǎn)，其次是向前行進，最后才考慮向左轉(zhuǎn)彎。 左手法則：小車在搜過程中有兩個以上的搜索方向時，優(yōu)先選擇向左轉(zhuǎn)，其次是向前行進，最后才考慮向右轉(zhuǎn)彎。,轉(zhuǎn)彎

16、策略簡介,優(yōu)先向前法則：優(yōu)先向前行進不轉(zhuǎn)彎，然后考慮向左或向右轉(zhuǎn)彎，向左或向右的優(yōu)先級可以自行靈活設(shè)定。 隨即策略：在可前進的方向中隨機選擇一個前進，其選擇的結(jié)果是不定的，也沒有什么規(guī)律可循。 上述的所有策略都有一個共同的缺陷，就是在選擇轉(zhuǎn)彎方向時，沒有考慮小車當前在迷宮的那個位置，一味地調(diào)用一種尋路策略都是不科學的。因為迷宮的終點是在迷宮地圖的中心固定不變的，所以在選擇轉(zhuǎn)彎的方向時應(yīng)該把小車所處

17、的位置考慮在內(nèi)。,轉(zhuǎn)彎策略簡介,向心法則： 把整個16*16的迷宮地圖分解為左下，右下，左上，右上四個均等的區(qū)域，在不同的區(qū)域中選擇不同的轉(zhuǎn)彎策略，使得小車始終向著迷宮的中心靠近，這樣就可以以最快的速度接近終點，總體上說比單獨的右手或者左手法則要科學有效。下面介紹具體的在地圖的那個區(qū)域采用哪種轉(zhuǎn)彎策略。,轉(zhuǎn)彎策略簡介,向心法則需要根據(jù)小車車頭當前朝向的方向和小車處在迷宮中位置來綜合判斷需要采用哪一種轉(zhuǎn)彎的策略

18、，所以在判斷條件上比較繁復(fù)，但是實際的運行效果是比較好的。犧牲一些程序的效率來實現(xiàn)向心法則是比較劃算的。在向心法則中轉(zhuǎn)彎方向的選擇以靠近中心為原則，可以得出策略的選擇如下面的圖表所示。,向心法則轉(zhuǎn)彎選擇統(tǒng)計表,尋路算法流程圖,檢測擋板信息,開始,統(tǒng)計方格四周沒有探索過的路徑數(shù)目,是否還有沒探索過的方向,有兩個以上的未探索方向,坐標入棧,根據(jù)定好的策略轉(zhuǎn)彎,繼續(xù)前進,是,轉(zhuǎn)向剩下的一個方向,是,否,保存岔路口坐標的堆棧為空？,否,棧頂?shù)牟?/p>

19、路口坐標出棧,否,是否還有沒探索過的方向,否,控制小車到達該坐標,是,小車返回起點,是,后轉(zhuǎn),結(jié)束尋路過程,進入沖刺狀態(tài),等高表算法介紹,在電腦鼠的尋路過程中有一個比較特殊的過程，就是在小車遇到了死胡同時，應(yīng)該讓小車回到上一個岔路口，雖然可以利用堆棧的先入后出的特性來存儲尋路過程中經(jīng)過的岔路口坐標，但是具體地要怎么樣使得小車從當前的位置移動到岔路口呢？換言之，我們需要實現(xiàn)將小車從當前的位置移動到一個指定的任意位置，而且還要使得移動過程經(jīng)

20、歷的路徑盡可能地短。在后期的最短路徑的生成問題其實也是上面的問題的一個特例，只不過把當前的位置設(shè)置為了迷宮的起點，而要到達的位置設(shè)置成了迷宮的終點而已。,等高表算法介紹,綜上所述，我們只需要集中精力解決上面敘述的第一個問題就行了，即怎樣從當前的位置尋找一條最短的路徑到達一個指定的任意位置，要實現(xiàn)上面的功能，就需要用到等高表。 其實等高表的概念并不復(fù)雜，其實在電腦鼠這個比賽中，等高表就是以一個二維矩陣的形式表現(xiàn)出來的，

21、對于16*16的迷宮地圖而言，我們可以開辟一個16*16的二維矩陣來表示等高表，數(shù)值類型選擇Byte型就夠用了，等高表中的每一項都對應(yīng)了迷宮地圖上的一個方格，用于存儲起點到該方格的最短路徑步數(shù)。,等高表算法介紹,我們可以形象地想象地圖中的每一個方格都有一個高度，起點的高度最高，而終點的高度最低，從起點到終點的過程其實就是沿著一條等高表的數(shù)值遞減的路徑行進的過程。終點相當于山腳，起點相當于山頂，從起點向終點沖刺就是從山頂向山腳沖刺。,等高

22、表算法流程圖,開始,開辟16*16的存儲空間用于存儲等高表,遍歷整個二維矩陣,該方格是否是搜索時曾經(jīng)過的,將方格對應(yīng)的等高表數(shù)值賦值為0xFE，表示該方格信息有效,將方格對應(yīng)的等高表數(shù)值賦值為0xFF，表示該方格信息無效,是,終點坐標等高值賦值為1，當前坐標設(shè)置為終點坐標,否,當前坐標旁邊還有有通路且等高表值比當前坐標等高值大二以上,當前坐標向旁邊移動，將對應(yīng)的等高值賦值為前一個坐標對應(yīng)等高值加1,是,當前的方格是不是有兩條以上岔路,將

23、當前坐標壓入堆棧,是,否,回到堆棧中保存的前一個岔路口坐標，如果該坐標的方格只有一條或是沒有岔路可行了，就將該坐標彈出堆棧,否,,求最短路徑——等高表生成算法演示:,,等高表生成算法,,,,,建立一個小型示意迷宮，假設(shè)老鼠已完成對迷宮的搜索，即掌握了迷宮地圖。,1,00,2,10,3,4,5,3,4,5,6,7,8,8,把走過的方格標記為0xfe，未走過的標記為0xff,起點標記為1,把起點坐標保存到堆棧,標記為2，表示第二步到達的方格

24、，后面的以此類推,此時迷宮的前方和右方都有路,這是第三步,此時沒有可前進的路，于是返回堆棧保存分支的地址繼續(xù)標記,地址出棧,20,22,13,,,繼續(xù)保存分叉路的坐標,9,10,11,12,此時前進方向的數(shù)比自己還小，所以無路可走，應(yīng)該返回到堆棧保存的分支地址,,6,32,7,,7,8,,4,5,,等高圖的最后的結(jié)果如左圖所示，圖中已經(jīng)標明各個坐標到起點需要的最少步數(shù)，也就是找出了所有點到起點的最短路徑。,,,,,,,,,,,,,于是保

25、存分叉路的坐標，并隨便選一個方向前進，這不影響結(jié)果,此時搜索已沒有可前進的方向，且堆棧中的分支地址僅有起點地址，所以可以判斷等高圖制作完畢。,普通等高表,對拐彎加權(quán)的等高表,最關(guān)鍵的功能：直接到指定的坐標,控制小車直接從當前的坐標達到一個指定的坐標是整個軟件設(shè)計中要實現(xiàn)的最為關(guān)鍵的一個功能，在尋路的過程中涉及到頻繁地回到以前所經(jīng)歷的岔路口的過程，這就是一個從當前坐標移動到指定的坐標的典型情況，還有從起點到終點的沖刺過程其實也是一句

26、代碼完成的，就是將迷宮的起點作為小車的運行起點，將迷宮的終點作為小車運行的終點來調(diào)用這個關(guān)鍵的功能。所以說這個從當前坐標移動到指定的坐標的功能是十分關(guān)鍵的。該功能的實現(xiàn)就要用到迷宮的等高表信息。,直接到指定的坐標實現(xiàn)流程圖,制作以目的地為起始點的等高表,小車是否達到目的地,獲取當前坐標的等高值,尋找四周等高值較小的方向,前方的等高值較??？,否,前進n個方格，n=0,否,前進的方格數(shù)n++,是,小車是否達到目的地,向等高表數(shù)值較小的方向轉(zhuǎn)

27、彎,否,前進n個方格，n=0,是,沖刺階段,沖刺階段沒有特殊的復(fù)雜算法問題，只需要調(diào)用前面已經(jīng)實現(xiàn)的從當前坐標到指定坐標的的功能就行了，該功能實現(xiàn)的兩個坐標之間的路徑的選擇已經(jīng)是最短的了。在沖刺的階段可以修改小車的速度參數(shù)，使小車在沖刺的階段跑得快一點，而在尋路的過程里可以跑得慢一點，力求平穩(wěn)完成尋路的過程才可能完成比賽。,推薦軟件工具,Notepad++source insightVisual Studio 2005/2008

28、,添加一個方便的插件Visual Assist,軟件中可改進的部分 1.消除不必要的停頓,在出廠代碼試跑中，小車每到一個岔路口就會停頓一下，即是在該岔路口不需要轉(zhuǎn)彎，小車也會先停頓在出路口，然后再重新加速開始前進，顯然是沒有必要的。根據(jù)上次比賽對代碼的分析，出現(xiàn)這種現(xiàn)象的原因在于出廠示例代碼的架構(gòu)安排不合理，出場的示例代碼中小車的前進和在岔路口是否轉(zhuǎn)彎的判斷是分離的，所以小車每到一個岔路口程序就會從控制

29、前進的函數(shù)跳回到主函數(shù)中進行是否需要轉(zhuǎn)彎的判斷，然后再轉(zhuǎn)彎后又跳回到控制前進的函數(shù)中運行程序。這樣就在某些不需要在岔路口轉(zhuǎn)彎的情況造成了不必要的停頓。其實在岔路口是否需要轉(zhuǎn)彎應(yīng)該在控制前進的函數(shù)結(jié)束前久判斷，如果不需要轉(zhuǎn)彎，就繼續(xù)進行前進的過程，不需要跳回主函數(shù)進行是否需要轉(zhuǎn)彎的判斷，所以修正以上缺陷的方法就是增加控制前進的子過程的返回條件，在不需要轉(zhuǎn)彎的岔路口不跳出前進的子過程就行了。,軟件中可改進的部分 2.去除“傻瓜式

30、”尋路過程,在出廠實例代碼的試跑過程中，可以發(fā)現(xiàn)其尋路過程效率非常低，經(jīng)常在一些三面都有擋板的單個方格間打轉(zhuǎn)，其低效的原因其實是因為沒有進行數(shù)據(jù)補全，其實迷宮里面方格的信息并不是只有探測過此能夠得到，通過推斷的方法也是可以得到的，利用某個方格四周的方格的信息，就有可能推斷出這個方格的信息。而不需要每一個方格都探索。,軟件中可改進的部分 3.防止小車在終點浪費時間,普通的代碼中并沒有在小車到達終點之后進行特殊的處理，造成小車在

31、終點的四個方格中轉(zhuǎn)一圈然后才返回終點，這顯然是應(yīng)該改進的地方，需要對終點的判定增加特殊的處理。,軟件中可改進的部分 4.限制探索迷宮的深度,在小車找到終點后，可以繼續(xù)探索迷宮，但是比賽的迷宮有256個方格，要全部探索完是相當耗時間的，所以需要控制遍歷迷宮的深度，可以通過已經(jīng)探測的方格個數(shù)來衡量迷宮的探測程度，給探測的迷宮方格數(shù)設(shè)置一個上限，在到達探索的上限后返回迷宮起點，結(jié)束尋路的過程，避免在尋路的過程中耗費了太多的時間，影

32、響到比賽的成績。,軟件中可改進的部分 5.改進轉(zhuǎn)彎的模式,提高比賽成績的比較直接的方式，傳統(tǒng)的左拐彎和右拐彎都是先讓電機停轉(zhuǎn)，然后一個電機正轉(zhuǎn)，另外一個電機反轉(zhuǎn)實現(xiàn)小車轉(zhuǎn)彎，電機的停轉(zhuǎn)過程會浪費很多時間，所以相對而言，沒有電機停轉(zhuǎn)過程的前進中拐彎方式是比較理想的轉(zhuǎn)彎方式，如果實現(xiàn)在小車上，可以比較大幅度地提高比賽的成績，但是創(chuàng)新的難度比較大。在改進的過程里會遇到大量的問題，如小車轉(zhuǎn)彎后的坐標應(yīng)該怎樣更新，小車轉(zhuǎn)彎后的位置，姿

33、態(tài)能不能穩(wěn)定地保持，傳感器的探測狀態(tài)應(yīng)該怎樣改進才能配合好新的拐彎方式呢，有可能造成坐標錯亂，探測丟失，累計誤差等等問題，要修正眾多的bug是一個十分困難的過程。,本組參加比賽的經(jīng)驗,1.先求穩(wěn)定，再追求速度。2.先把機械部分的傳感器，電機調(diào)整到比較理想的狀態(tài)，再開始試跑，盡量不要硬件上的誤差影響到程序的運行。3.調(diào)試的時候要好好利用裝有數(shù)碼管的調(diào)試板，實時顯示小車的狀態(tài)，以便發(fā)現(xiàn)軟件上的漏洞。4.多試跑，多思考，多討論，團