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

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

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

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

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

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

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

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

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

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

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