“電腦鼠”斜向45度沖刺算法實現(xiàn)

苗雨

摘要 天津中德職業(yè)技術(shù)學院在2015年天津市高職院校技能大賽的“電腦鼠”走迷宮大賽中成功實現(xiàn)斜向45度沖刺，實現(xiàn)電腦鼠可以斜向沖刺的算法突破，本文介紹這一算法的設(shè)計思想和算法實現(xiàn)過程，采用有限狀態(tài)自動機的設(shè)計思想，算法實現(xiàn)通過自動機轉(zhuǎn)換成狀態(tài)轉(zhuǎn)換矩陣來實現(xiàn)。

關(guān)鍵詞 有限狀態(tài)自動機；狀態(tài)轉(zhuǎn)化矩陣；電腦鼠；斜向45度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）14-0186-02

“電腦鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、傳感器和機電運動部件構(gòu)成的一種智能行走裝置，電腦鼠可以在不同“迷宮”中自動記憶和選擇路徑，采用相應(yīng)的算法，快速地達到所設(shè)定目的地。

這項競技賽事風靡全球，從1979 年國際電工和電子工程學會（IEEE）每年都舉辦一次國際性的電腦鼠走迷宮競賽，至今已有30年的歷史，在歐洲東南亞日本、韓國等地區(qū)頗為盛行。

1 問題提出的背景

嵌入式微型機器人（電腦鼠）走迷宮競賽具有一定難度，是一項富有挑戰(zhàn)性和趣味性的比賽。此外，它還是一個很好的教學工具。電腦鼠可看作是一個集多項工程學科知識于一體的小型系統(tǒng)。成功的設(shè)計者通常都是合作團體，他們必須考慮電子、電氣、機械以及計算機軟件設(shè)計，算法各方面的問題。重量、速度、功耗、傳感技術(shù)、重心以及程序各方面都是設(shè)計中需要決定和綜合考慮的因素。

本論文從軟件算法角度提出了斜向45度沖刺的算法創(chuàng)新，并在2015年天津電腦鼠相關(guān)賽項中成功應(yīng)用。

電腦鼠在運行中可以劃分為四個狀態(tài)，等待狀態(tài)、啟動狀態(tài)、搜索迷宮狀態(tài)和沖刺狀態(tài)。

1）等待狀態(tài)

在該狀態(tài)中，電腦鼠靜止在起點，等待開始命令。同時實時顯示傳感器檢測結(jié)果和電池的電壓，這樣方便調(diào)試傳感器的靈敏度和更換電池。當控制啟動的按鍵按下后，電腦鼠進入啟動狀態(tài)。

2）啟動狀態(tài)

迷宮是由18cm*18cm 大小的方格組成的，其行列各有16個方格。以左下角的點為（0，0）點，右上角的點為（15，15）點。在該狀態(tài)中，電腦鼠根據(jù)第一次轉(zhuǎn)彎的方向判斷起點是在坐標的（0，0）點還是（15，0）點。

3）搜索迷宮狀態(tài)

在該狀態(tài)中，電腦鼠的任務(wù)就是探索并記憶迷宮地圖。這里采用右手搜索法則，并搜索全迷宮。其程序流程圖見圖1所示：

4）沖刺狀態(tài)

迷宮搜索完畢后，根據(jù)算法找出一條最優(yōu)路徑?jīng)_刺到終點。沖刺結(jié)束后返回到起點。

本論文研究的是，在沖刺狀態(tài)下以最優(yōu)路徑為基礎(chǔ)，通過類似自動機原理的算法找到最優(yōu)路徑下可以45度斜向跑的起始位置和終止位置。

5）方向的定義

為了讓電腦鼠記住所走過的各個迷宮格的信息，我們就要對這256個迷宮格進行編號。很明顯，用坐標是非常方便的。

在本文中，將向上的方向定義為0，向右為1、向下的方向定義為2、向左為3，如圖所示。

2 沖刺路徑絕對方向數(shù)組的獲取

絕對方向數(shù)組的獲取，通過讀取GucMapBlock（根據(jù)當前格修改過周邊4格的地圖），獲取沖刺地圖，并變換成沖刺路徑絕對方向的數(shù)組，在此基礎(chǔ)上分析斜向45度路線的起始坐標和終止坐標。

算法分析：斜向包括4個方向，8種情況，每種情況至少連續(xù)兩組以上即可選擇。4個方向，8種情況，以絕對方向1010的情況為例如圖3所示：

這種情況可以選擇斜向跑，101010以及更多的重復循環(huán)情況也可以選擇斜向跑，除此之外還有0101，1212，2121，2323，3232，0303，3030以及更多循環(huán)的情況。本論文就是通過有限狀態(tài)自動機原理，把符合條件的所有情況篩選出來。

3 算法的實現(xiàn)

首先，搭建有限狀態(tài)自動機，初始狀態(tài)為“0”狀態(tài)，輸入值只有0，1，2，3四種情況，每一個輸入之后，有限狀態(tài)自動機會有狀態(tài)跳轉(zhuǎn)，如：在“0”狀態(tài)下輸入0時調(diào)整到“1”狀態(tài)，輸入1時調(diào)整到“2”狀態(tài)，輸入2時調(diào)整到“3”狀態(tài)，輸入3時調(diào)整到“4”狀態(tài)；在“1”狀態(tài)下輸入0時調(diào)整到“1”狀態(tài)，輸入1時調(diào)整到“5”狀態(tài)，輸入2時調(diào)整到“3”狀態(tài)，輸入3時調(diào)整到“6”狀態(tài)。有的輸入會跳轉(zhuǎn)到新狀態(tài)，有的輸入會跳轉(zhuǎn)到已經(jīng)存在的狀態(tài)。其中，14，16，18，20，22，24，26，28為終止狀態(tài)，分別是8種情況，首次達到終止狀態(tài)，即滿足兩組斜向45度最低條件，再通過連續(xù)一組循環(huán)可以連續(xù)達到同一個終止狀態(tài)，再次基礎(chǔ)上可以計算出所有滿足條件的斜向45度的起始坐標和終止坐標等信息。

有限狀態(tài)自動機會轉(zhuǎn)換成一個所有狀態(tài)跳轉(zhuǎn)關(guān)系都包含在28*4的狀態(tài)轉(zhuǎn)換矩陣中。

狀態(tài)轉(zhuǎn)換矩陣如下：

4 編程實現(xiàn)

在VC++6.0環(huán)境模擬斜向45度算法，根據(jù)緩沖區(qū)讀取的實際數(shù)據(jù)在VC環(huán)境下，測試算法，通過算法運算出所有符合條件的序列段，并運算出起始步數(shù)，起始點絕對方向，起點坐標，終止坐標，步數(shù)等信息。

測試用例：test[N]={0，0，0，0，0，0，0，0，0，0，0，1，0，1，0，0，1，0，1，0，0，0，0，0，0，1，1，2，2，1，2，1，2，1，2，1，2，2}；

運行結(jié)果：

5 總結(jié)

這是利用編譯原理課程中，詞法分析的有限狀態(tài)自動機原理的一次實際應(yīng)用，解決了有限狀態(tài)并且有限輸入的情況下一類問題的分析和解決方法。在實際測試中達到預(yù)期效果，為“電腦鼠走迷宮”賽項的技術(shù)發(fā)展起到了推動作用。