基于A*算法的電子地圖系統(tǒng)的設(shè)計(jì)

摘要：為降低成本、合理利用軟硬件資源而設(shè)計(jì)的基于A*算法與STM32微控制器的電子地圖系統(tǒng)，運(yùn)用于公共信息服務(wù)。系統(tǒng)以STM32F103ZE T6微控制器為核心，配合少量的外圍電路，在其上運(yùn)行以高效、緊湊的程序以及算法。利用STM32芯片的FSMC總線驅(qū)動(dòng)IS62WV51216 SRAM存儲(chǔ)芯片，以擴(kuò)展主控處理地圖數(shù)據(jù)所需要的內(nèi)存空間。同時(shí)使用FSMC總線驅(qū)動(dòng)7．0寸LCD模塊，大大提高了LCD的刷屏速度。使用SD卡存放可更換的地圖數(shù)據(jù)，系統(tǒng)初始化時(shí)先將SD卡中的地圖數(shù)據(jù)讀取到外擴(kuò)的SRAM中待處理，以加快主控時(shí)數(shù)據(jù)的處理速度。軟件上，在STM32上移植了UCOSII嵌入式操作系統(tǒng)以及UCGUI圖形庫(kù)，實(shí)現(xiàn)對(duì)各個(gè)任務(wù)的處理以及整個(gè)系統(tǒng)界面的設(shè)計(jì)。通過(guò)移植A*算法，實(shí)現(xiàn)了兩點(diǎn)間最短路徑查找的功能。試驗(yàn)表明，系統(tǒng)運(yùn)行界面流暢美觀，路徑查找準(zhǔn)確，可作為一般小范圍場(chǎng)所的導(dǎo)航電子地圖系統(tǒng)，取代傳統(tǒng)的路標(biāo)或靜態(tài)地圖。
關(guān)鍵詞：STM32微控制器；FSMC總線；嵌入式操作系統(tǒng)；UCGUI；A*算法

當(dāng)前電子地圖的使用已經(jīng)越來(lái)越得到推廣，從專(zhuān)用的GPS電子導(dǎo)航設(shè)備，到智能手機(jī)等移動(dòng)設(shè)備都能夠?yàn)g覽到的網(wǎng)絡(luò)電子地圖，都體現(xiàn)著這一應(yīng)用的廣泛性，具有更新速度慢、使用壽命短等諸多缺點(diǎn)的紙質(zhì)地圖已經(jīng)漸漸地被電子地圖取代。嵌入式電子地圖設(shè)備通常都含有嵌入式微處理器，附帶著許多復(fù)雜的外圍電路，制作與生產(chǎn)成本高，開(kāi)發(fā)周期長(zhǎng)，常常被用于精度要求較高的車(chē)載導(dǎo)航系統(tǒng)。嵌入式電子地圖通常需要有軟件平臺(tái)的支持，當(dāng)前主流的電子地圖都是在桌面地理信息系統(tǒng)工具M(jìn)apInfo中制作完成，在不同系統(tǒng)平臺(tái)下有專(zhuān)用的軟件與插件支持，但這類(lèi)軟件或插件的購(gòu)買(mǎi)費(fèi)用較昂貴，而另一種方法是在嵌入式Linux環(huán)境下使用開(kāi)源的MITAB工具，實(shí)現(xiàn)對(duì)MapInfo格式的電子地圖的操作。這兩種方法實(shí)現(xiàn)的系統(tǒng)成本均較高，實(shí)現(xiàn)難度較大。文中介紹了一種基于STM32微控制器以及A*路徑算法的嵌入式電子地圖系統(tǒng)的設(shè)計(jì)，設(shè)計(jì)并實(shí)現(xiàn)了相應(yīng)功能。

1 系統(tǒng)結(jié)構(gòu)及硬件電路設(shè)計(jì)
系統(tǒng)以Cortex—M3系列ARMv7架構(gòu)芯片STM32F103微控制器為核心，包括SRAM存儲(chǔ)器、SD卡存儲(chǔ)器、LCD驅(qū)動(dòng)等電路，系統(tǒng)總體方案如圖1所示。

1．1 液晶模塊驅(qū)動(dòng)電路
主控通過(guò)配置內(nèi)部FSMC功能寄存器，開(kāi)啟FSMC總線并產(chǎn)生LCD的讀寫(xiě)時(shí)序，驅(qū)動(dòng)7寸LCD模塊。電路如圖2所示。其中，RS引腳接到了主控的FSMC_A16引腳，作為數(shù)據(jù)命令選擇端，F(xiàn)SMC_NE1接到了LCD模塊的使能端CS。

1．2 外擴(kuò)SRAM電路
使用FSMC總線訪問(wèn)外部SRAM存儲(chǔ)器，其中FSMC_A0-FSMC_A15為主控FSMC總線地址引腳，對(duì)應(yīng)接到SRAM地址線引腳，F(xiàn)SMC_D0-FSMC_D15為數(shù)據(jù)引腳，電路如圖3所示。

2 主要軟件設(shè)計(jì)
系統(tǒng)初始化主控先讀取MicroSD卡里的地圖數(shù)據(jù)，并將其寫(xiě)入外部SRAM存儲(chǔ)器中，并把地圖顯示在LCD上，當(dāng)使用系統(tǒng)查詢最短路徑時(shí)，調(diào)用A*算法，賦予特定的地點(diǎn)參數(shù)以及相應(yīng)的權(quán)值，在兩點(diǎn)之間可行的路線中尋找到最近的路徑，再調(diào)用UCGUI API函數(shù)實(shí)現(xiàn)在地圖上的路徑的顯示以及導(dǎo)航，程序是在UCOSII嵌入式實(shí)時(shí)操作系統(tǒng)的框架下以任務(wù)的形式編寫(xiě)的，以下是A*算法的實(shí)現(xiàn)思想。
A*算法在人工智能中是基于A算法的一種典型的啟發(fā)式搜索，主要是對(duì)估價(jià)函數(shù)加以特別的定義和描述，從而得到一種具有較強(qiáng)的啟發(fā)能力的有序搜索法。事先對(duì)所要安裝的地圖數(shù)據(jù)進(jìn)行處理，為地圖圖片規(guī)劃一個(gè)坐標(biāo)平面，并標(biāo)出足夠多的路徑節(jié)點(diǎn)坐標(biāo)值，在程序中以一個(gè)結(jié)構(gòu)體變量記錄，結(jié)構(gòu)體類(lèi)型名為MapPoint，結(jié)構(gòu)體元素包含節(jié)點(diǎn)本身的坐標(biāo)值，以及周?chē)?、下、左、右可?jīng)過(guò)的節(jié)點(diǎn)號(hào)，根據(jù)A*算法，A*搜索的評(píng)價(jià)函數(shù)為f(n)=g(h)+h(n)，其中g(shù)(n)是從初始節(jié)點(diǎn)到該節(jié)點(diǎn)n的路徑耗散，即從初始節(jié)點(diǎn)沿最短路徑到達(dá)該節(jié)點(diǎn)走過(guò)的路程，h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的估計(jì)耗散值，h(n)值可以用不同的方法估算，這里使用的方法被稱(chēng)為曼哈頓方法，它計(jì)算從當(dāng)前格到
目的格之間水平和垂直的方格的數(shù)量總和，被稱(chēng)為啟發(fā)式或啟發(fā)函數(shù)，而f(n)是g(n)與h(n)的和。定義另外一個(gè)結(jié)構(gòu)體類(lèi)型AstarPoint，用于記錄路徑中每個(gè)節(jié)點(diǎn)的x、y坐標(biāo)值、g(n)值、h(n)值、f(n)值，以及其他節(jié)點(diǎn)的AstarPoint結(jié)構(gòu)體指針類(lèi)型元素。示意性的算法流程如圖4所示。

使用A*算法獲取到最短路徑后，調(diào)用UCGUI庫(kù)函數(shù)在地圖上動(dòng)態(tài)的顯示出路徑。

3 應(yīng)用實(shí)踐
根據(jù)設(shè)計(jì)的原理圖繪制PCB電路板，完成后的PCB版圖如圖5所示。

焊接完元件后開(kāi)始調(diào)試程序，首先在PC機(jī)上用UCGUIBuilder軟件進(jìn)行界面的設(shè)計(jì)，利用拖取軟件中的控件設(shè)計(jì)好界面后，再把生成的代碼移植到STM32硬件平臺(tái)中去，并且移植好A-Star路徑算法，進(jìn)行仿真調(diào)試，最終系統(tǒng)的運(yùn)行效果圖如圖6所示。
路徑的動(dòng)態(tài)顯示較順暢，屏幕刷新速度較快，路徑查找準(zhǔn)確率達(dá)到100％。

4 結(jié)論
以STM32微控制器為核心，基于A-Star路徑算法的電子地圖系統(tǒng)運(yùn)行穩(wěn)定，界面美觀流暢，路徑查找準(zhǔn)確，成本低廉，可以運(yùn)用于旅游場(chǎng)所、小區(qū)或者學(xué)校等。