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

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

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

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

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

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

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

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

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

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

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