苗雨

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）14-0186-02

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

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

1 問題提出的背景

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

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

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

1）等待狀態(tài)

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

2）啟動(dòng)狀態(tài)

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

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

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

4）沖刺狀態(tài)

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

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

5）方向的定義

為了讓電腦鼠記住所走過的各個(gè)迷宮格的信息，我們就要對(duì)這256個(gè)迷宮格進(jìn)行編號(hào)。很明顯，用坐標(biāo)是非常方便的。

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

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

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

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

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

3 算法的實(shí)現(xiàn)

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

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

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

4 編程實(shí)現(xiàn)

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

測(cè)試用例：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}；

運(yùn)行結(jié)果：

5 總結(jié)

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