基于A*算法的電子地圖系統的設計

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

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

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

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

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

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

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

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

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

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