計算機迷宮搜索算法仿真研究①

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

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

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

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

1 仿真模塊設計

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

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

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

2 迷宮搜索算法仿真程序的設計

2.1 人機交互界面的設計

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

2.2 用戶事件檢測與狀態轉移

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

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

圖3 用戶事件檢測函數的流程圖

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

2.3 動態仿真器的設計

2.3.1 電腦鼠屬性定義

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

結構體中，dir用于存儲電腦鼠的絕對方向，x和y用于電腦鼠的當前坐標、start_x和start_y用于存儲電腦鼠的起點坐標，而state用于存儲電腦鼠的當前狀態。

2.3.2 電腦鼠的運動控制

電腦鼠的基本動作分為直行、右轉、左轉、原地后轉和停止，動態仿真器收到動作指令后，首先根據動作指令action更新電腦鼠的絕對方向mouse.dir，然后根據新的絕對方向調取相應的圖像，用于動畫繪制。當執行動畫動作時，仿真器會根據電腦鼠的絕對方向對電腦鼠的坐標進行更新。

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

2.3.3 迷宮信息的獲取

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

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

表2 柵欄信息的存儲格式

2.3.4 仿真數據統計

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

圖4 模擬電腦鼠的軌跡圖

圖5 步數統計

3 算法測試

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

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

3.1 迷宮地圖的選擇

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

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

3.2 測試結果

3.2.1 左手法則迷宮搜索算法的測試結果

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

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

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

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

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

圖10 左手法則分別在三個迷宮地圖中運行的統計數據

3.2.2 右手法則迷宮搜索算法的測試結果

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

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

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

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

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

圖14 右手法則分別在三個迷宮地圖中運行的統計數據

4 結論

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

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

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

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

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

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

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

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

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