基于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路径算法的电子地图系统运行稳定，界面美观流畅，路径查找准确，成本低廉，可以运用于旅游场所、小区或者学校等。