基于A(yíng)*算法的電子地圖系統的設計

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

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

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

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

1．2 外擴SRAM電路
使用FSMC總線(xiàn)訪(fǎng)問(wèn)外部SRAM存儲器，其中FSMC_A0-FSMC_A15為主控FSMC總線(xiàn)地址引腳，對應接到SRAM地址線(xiàn)引腳，FSMC_D0-FSMC_D15為數據引腳，電路如圖3所示。

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

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

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

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

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