鄧 輝，詹 杰，何家偉，李先春

(湖南科技大學物理與電子科學學院，湖南湘潭411201)

電腦鼠［1］(Micromouse)是一個由微控制器、探測器、驅(qū)動電機組成的一種集感知、判斷、行走功能于一體，能夠在迷宮中自動尋找到達終點最佳路徑的微型機器人。電腦鼠走迷宮比賽集競賽和趣味性于一體，吸引了大量青年科技人員參加，文獻［1］給出了有關(guān)迷宮電腦鼠的比賽規(guī)則和要求。

在迷宮電腦鼠的設(shè)計中，迷宮搜索算法的設(shè)計和調(diào)試最困難［3－7］。主要因為迷宮搜索算法的設(shè)計和調(diào)試過程容易受到周圍環(huán)境以及電腦鼠底層軟硬件的影響而出現(xiàn)運行錯誤，從而使得調(diào)試經(jīng)常被打斷，完成一次完整的調(diào)試非常麻煩［8］，需耗費大量時間。本文針對電腦鼠設(shè)計者在迷宮搜索算法設(shè)計和調(diào)試上所面臨的問題，設(shè)計了迷宮搜索算法仿真程序，提高迷宮搜索算法設(shè)計和調(diào)試的效率，減輕設(shè)計者的負擔。該算法仿真程序及其實現(xiàn)思路不僅可以推廣到電腦鼠走迷宮競賽中，而且還可以作為電腦鼠迷宮搜索算法研究者的一個理想研究平臺。

1 仿真模塊設(shè)計

迷宮搜索算法仿真程序的主要功能模塊包含動態(tài)仿真器、迷宮搜索算法接口、人機交互界面和迷宮地圖編輯器。動態(tài)仿真器是整個程序的核心，迷宮搜索算法接口用于連接動態(tài)仿真器和迷宮搜索算法，人機交互界面和迷宮地圖編輯器，分別負責響應(yīng)用戶的鼠標動作和迷宮地圖的設(shè)置。地圖編輯器需要接受用戶的動作來完成地圖的編輯工作，所以將迷宮地圖編輯器作為人機交互界面的一個子功能來實現(xiàn)。圖1是迷宮搜索算法仿真程序的系統(tǒng)模塊框圖。

圖1 迷宮搜索算法仿真程序的總框圖

動態(tài)仿真器實現(xiàn)了三個功能，為迷宮搜索算法獲取迷宮信息，根據(jù)迷宮搜索算法的指令控制模擬電腦鼠運動，顯示運行中產(chǎn)生的過程數(shù)據(jù)。迷宮搜索算法接口定義了該算法的函數(shù)格式及通信協(xié)議。人機交互界面是人機交互平臺，內(nèi)部實現(xiàn)了與用戶交互的按鈕控件和控制程序工作狀態(tài)的狀態(tài)機，按鈕控件獲取用戶的鼠標事件，并將其作為狀態(tài)機的輸入信號，狀態(tài)機用于控制迷宮搜索算法仿真程序工作狀態(tài)的轉(zhuǎn)移。迷宮地圖編輯器用于編輯二維迷宮地圖，完成地圖設(shè)置后，將該地圖以圖片形式保存。這里采用多線程設(shè)計方法，將動態(tài)仿真器和人機交互界面分別設(shè)計于兩個不同的線程中。

2 迷宮搜索算法仿真程序的設(shè)計

2.1 人機交互界面的設(shè)計

圖2為迷宮搜索算法仿真程序的界面。迷宮地圖根據(jù)IEEE標準迷宮場地的大小進行等比例的縮小。迷宮地圖中每個像素代表0.4 cm，和實際迷宮相比，邊長等效為723個像素，迷宮單元的柵欄長度、厚度分別為45個像素和3個像素。整個顯示界面分為三部分，左方正方形部分顯示迷宮地圖，右方上半部分顯示按鈕控件，右方下半部分顯示運行信息。按鈕控件有6個，分別是載入地圖按鈕、設(shè)置地圖按鈕、保存地圖按鈕、迷宮算法按鈕、設(shè)置起點按鈕和開始仿真按鈕。

2.2 用戶事件檢測與狀態(tài)轉(zhuǎn)移

用戶在人機交互界面的動作信息通過鼠標事件獲取函數(shù)GetMouseMsg()進行檢測，通過事件檢測函數(shù)User-EventDetect()獲取;用戶事件檢測函數(shù)所返回的數(shù)據(jù)作為參數(shù)傳遞給狀態(tài)機，由狀態(tài)機控制相應(yīng)的動作和效果。

圖2 迷宮搜索算法仿真程序的界面

圖3 用戶事件檢測函數(shù)的流程圖

人機交互界面定義了7個工作狀態(tài)，分別為初始狀態(tài)、地圖編輯狀態(tài)、地圖保存狀態(tài)、地圖載入狀態(tài)、算法載入狀態(tài)、起點設(shè)置狀態(tài)，這7種狀態(tài)反映了狀態(tài)機在用戶事件驅(qū)動下的狀態(tài)跳轉(zhuǎn)。

2.3 動態(tài)仿真器的設(shè)計

2.3.1 電腦鼠屬性定義

動態(tài)仿真器首先定義了電腦鼠的絕對方向和相對方向，絕對方向以迷宮地圖為參照系，相對方向以電腦鼠自身作為參考的方向，如前后左右。為電腦鼠創(chuàng)建了一個結(jié)構(gòu)體MICROMOUSE.mouse用于存儲電腦鼠的相關(guān)信息，其原型如下:

結(jié)構(gòu)體中，dir用于存儲電腦鼠的絕對方向，x和y用于電腦鼠的當前坐標、start_x和start_y用于存儲電腦鼠的起點坐標，而state用于存儲電腦鼠的當前狀態(tài)。

2.3.2 電腦鼠的運動控制

電腦鼠的基本動作分為直行、右轉(zhuǎn)、左轉(zhuǎn)、原地后轉(zhuǎn)和停止，動態(tài)仿真器收到動作指令后，首先根據(jù)動作指令action更新電腦鼠的絕對方向mouse.dir，然后根據(jù)新的絕對方向調(diào)取相應(yīng)的圖像，用于動畫繪制。當執(zhí)行動畫動作時，仿真器會根據(jù)電腦鼠的絕對方向?qū)﹄娔X鼠的坐標進行更新。

為了使仿真程序更具一般性，將模擬電腦鼠的移動速度設(shè)置為可調(diào)，兩個控制參數(shù)分別是flame和delay_time。flame代表模擬電腦鼠每次移動的像素個數(shù)，delay_time為每次移動后需要延時等待的時間(等待指令)。默認為每移動一個基本單元所用的時間為450 ms。delay_time的值為0到2 000 ms之間的任意整數(shù)值。

2.3.3 迷宮信息的獲取

迷宮柵欄信息的獲取根據(jù)電腦鼠當前所在迷宮單元的坐標mouse.x和mouse.y完成。絕對方向的信息分別對應(yīng)變量的 bit3、bit2、bit1和bit0中，對應(yīng)關(guān)系如表1所示。相對方向的對應(yīng)關(guān)系如表2所示。絕對方向的柵欄信息反應(yīng)迷宮地圖信息，相對方向的柵欄信息反映電腦鼠可能運動的方向。

表1 絕對方向下的柵欄信息存儲格式

表2 柵欄信息的存儲格式

2.3.4 仿真數(shù)據(jù)統(tǒng)計

動態(tài)仿真器的仿真過程產(chǎn)生兩種數(shù)據(jù)，分別是模擬電腦鼠運動的軌跡圖和行走步數(shù)統(tǒng)計數(shù)據(jù)。在仿真過程中，動態(tài)仿真器會一直記錄電腦鼠的坐標，當發(fā)現(xiàn)電腦鼠從迷宮起點到達了迷宮終點或者從迷宮終點到達了迷宮起點，則使用圖像輸出函數(shù)putimage()將模擬電腦鼠的行走軌跡繪制出來，如圖4所示。繪制模擬電腦鼠的行走軌跡之后，動態(tài)仿真器使用圖像獲取函數(shù)getimage()對電腦鼠的行走軌跡進行截取，截取后的軌跡圖像保存在程序當前目錄下的Result文件夾中。

圖4 模擬電腦鼠的軌跡圖

圖5 步數(shù)統(tǒng)計

3 算法測試

為了驗證迷宮搜索算法仿真程序的方案是否可行以及該方案是否能夠減少迷宮搜索算法設(shè)計和調(diào)試的時間，本文對迷宮搜索算法仿真程序進行了一系列的測試。本測試基于兩套迷宮搜索算法和3個難度各異的迷宮地圖開展，最短路徑生成采用洪水填充算法，測試的內(nèi)容包括迷宮搜索算法的仿真情況以及仿真所用時間。測試結(jié)束后，通過分析對比迷宮搜索算法的仿真情況以及仿真所用時間，判斷是否達到設(shè)計目的。

為了便于對比測試結(jié)果，對實際電腦鼠的運行速度和模擬電腦鼠的運行速度作統(tǒng)一的假設(shè)。假設(shè)在實際環(huán)境中，電腦鼠每個基本動作用時為0.36 s(由電腦鼠0.5 m/s的運動速度計算而來，0.5米/秒的運動速度參考了比賽中電腦鼠的常用速度)。同時也假設(shè)在模擬環(huán)境中，模擬電腦鼠的基本動作用時為0.03 s(由模擬電腦鼠在模擬迷宮中1.5像素/ms的速度計算而來)。

3.1 迷宮地圖的選擇

為使測試結(jié)果具有普遍的參考意義，本次測試使用的迷宮地圖為國內(nèi)外比賽中出現(xiàn)過的3個迷宮地圖。如圖6所示，其中圖6(a)為2009年中國電腦鼠走迷宮競賽的迷宮地圖。圖6(b)為2012年湖南省電腦鼠走迷宮競賽的迷宮地圖。圖6(c)為2011年日本電腦鼠走迷宮競賽的迷宮地圖。

圖6 測試所選用的迷宮地圖

3.2 測試結(jié)果

3.2.1 左手法則迷宮搜索算法的測試結(jié)果

圖7、圖8和圖9分別是模擬電腦鼠在左手法則迷宮搜索算法的控制下，分別在三個迷宮地圖中生成的軌跡圖。

圖7 左手法則在迷宮地圖一中的運行軌跡圖

圖8 左手法則在迷宮地圖二中的運行軌跡圖

圖9 左手法則在迷宮地圖三中的運行軌跡圖

除了軌跡圖之外，左手法則迷宮搜索算法的仿真結(jié)果還包括模擬電腦鼠在三個迷宮地圖中仿真時的步數(shù)統(tǒng)計數(shù)據(jù)。如圖10所示，圖10a)、b)、c)是左手法則迷宮搜索算法分別在迷宮地圖一、二、三中的仿真步數(shù)統(tǒng)計數(shù)據(jù)。

圖10 左手法則分別在三個迷宮地圖中運行的統(tǒng)計數(shù)據(jù)

3.2.2 右手法則迷宮搜索算法的測試結(jié)果

圖11、圖12和圖13分別為模擬電腦鼠在右手法則迷宮搜索算法的控制下，在三個迷宮地圖中運行生成的軌跡圖。圖11，圖12、圖13中，圖a)為模擬電腦鼠第一次搜索時的軌跡圖，圖b)為模擬電腦鼠第二次搜索時的軌跡圖，圖c)為模擬電腦鼠沖刺時的軌跡圖。

圖11 右手法則在迷宮地圖一中的運行軌跡圖

圖12 右手法則在迷宮地圖二中的運行軌跡圖

圖13 右手法則在迷宮地圖三中的運行軌跡圖

同樣，右手法則迷宮搜索算法的仿真結(jié)果也包含了步數(shù)統(tǒng)計數(shù)據(jù)。左手法則迷宮搜索算法的仿真統(tǒng)計數(shù)據(jù)，如圖14所示，圖a)、b)、c)是右手法則迷宮搜索算法分別在迷宮地圖一、二、三中的仿真統(tǒng)數(shù)據(jù)。

圖14 右手法則分別在三個迷宮地圖中運行的統(tǒng)計數(shù)據(jù)

4 結(jié)論

從兩套迷宮搜索算法生成的軌跡圖中可以看出，軌跡圖和電腦鼠真實的運動情況沒有區(qū)別，雖然兩套迷宮搜索算法的搜索軌跡都不一樣，但最終都能成功搜索到三個迷宮的最短路徑。經(jīng)過多次的測試檢驗，發(fā)現(xiàn)仿真程序均可穩(wěn)定工作，這說明兩套迷宮搜索算法在仿真程序中均能正常運行，設(shè)計的迷宮搜索算法仿真程序正確。

采用仿真的形式來研究迷宮搜索算法，可以直觀地看到整個仿真過程，還可以顯示電腦鼠的行走數(shù)據(jù)，對算法的性能分析可以起到很大的幫助。因此，本仿真程序可以廣泛推廣到電腦鼠走迷宮競賽中使用，幫助參賽隊伍有效地提高迷宮搜索算法和電腦鼠的整體設(shè)計進度。

［1］周立功.IEEE電腦鼠開發(fā)指南［M］.廣州:廣州致遠電子有限公司，2008.

［3］林國恩.電腦鼠的設(shè)計與實作［D］.臺灣:龍華科技大學，2010.

［4］陳 鋒.環(huán)境搜索與路徑規(guī)劃算法的研究［D］.長春:吉林大學，2012.

［5］張新誼.一種電腦鼠走迷宮的算法［J］.單片機與嵌入式系統(tǒng)應(yīng)用，2007(5):84－85.

［6］萬玉瓊，梁俊有.基于嵌入式微處理器的走迷宮機器人的設(shè)計［J］.洛陽理工學院學報(自然科學版)，2010(4):36－39.

［7］李亞洲，嚴 石.電腦鼠軟件系統(tǒng)關(guān)鍵技術(shù)研究［J］.單片機與嵌入式系統(tǒng)應(yīng)用，2011(5):72－73.

［8］付秀偉，張 驊.基于ARM－M3的電腦鼠硬件設(shè)計［J］.吉林化工學院學報，2012(1):47 －49.