地图路径规划的本质是遍历地图中的所有节点，然后找到最短路径的过程[8]。算法中的图是由大量节点和连接节点之间的线组成的。这里说的节点指的是现实生活中的每一个分叉路口，只要出现需要选择方向的时候，在地图上呈现的就是一个节点（vertices）[14]。而连接节点的线则是指现实生活中的道路，例如上海的南京西路，它在地图上的数据身份是一个边（edge）。每一条边都带有相对应的权重，即现实世界中的物理距离。图拥有两种类型，即有向图和无向图。有向图指的是带有方向的边，即a指向b的边和b指向a的边是两种不同的边。这两条边，在无向图中则是同一条边。

根据周小镜的描述，最短路径算法的基础是将图中的节点遍历[8]。由于实际路网的复杂性，节点的遍历有可能会出现从某一顶点选择一条边搜索后，该边又与带有该顶点的另一条边相交[8]。从而导致该顶点的重复遍历。因此在遍历地图的过程中，需要对已访问过的节点进行标记，以防重复遍历的出现[8]。

A*算法的关键在于启发函数，即F(n)=G(n)+H(n)。F(n)指代起始节点到目标节点的总代价。G(n)表示当前节点n到起始节点的当前代价。H(n)则表示当前节点n到目标节点的预估代价。依据这个函数，从而使得每一个被搜索的节点n都有一个总代价F(n)。然后选择其中最小的总代价节点作为下一步节点。接着继续计算新加入的节点的F(n)，如此，循环。

将实际路网信息变成节点和边的数据结构形式并存储。以上海市交通路网为例。首先，通过OpenStreetMap（OSM）提供的Overpass API Query Form获取XML格式的上海市交通路网的信息。

在该XML文件中，可以发现，地理数据的数据结构是带有拓扑性质的数据。地理信息系统的点，线，面以及它们之间的关系通过XML中node，way和relation进行分别描述。各自标签下的tag用于记录其标签的属性信息。

标签记录路网节点信息，它包含经度和纬度，是标签的组成部分。

标签记录路的信息，是一个包含大量的集合。其属性包含街道，高速公路等信息。 

标签将和结合在一起用于描述地理事物，例如公交路线和自行车道。

接着，使用ElementTree（元素树）方式对XML文件进行解析。该方式类似一种轻量级的DOM。相对于拥有大量函数的Simple API for XML（SAX）方法和需要将XML数据映射到内存中的树的Document Object Model（DOM）方法。ElementTree可以以更容易被理解的代码形式和更快的速度解析XML。通过ElementTree方法遍历获得搜索所有的和标签并定位。然后，导入Networkx库。下图展示的就是以实例化对象Map中的路网信息所绘制的SVG格式的上海市交通道路路网。 

OpenStreetMap提供的XML文件中包含了许多不同类型的道路信息，例如公共交通道路，机动车道路，自行车道路或人行道道路等等。

本段将基于OpenStreetMap提供的数据结构解析出公共交通路线数据。公共交通道路信息主要被存储与标签中，作为的子标签。图14中展示的是公共交通路网中某一个标签的数据结构。根据OSM的官方网站中提供的XML中标签的数据结构，图15展示的是其子标签的各类属性和值，图16展示的是其子标签的各类属性和值。标签中的“type”属性node和way分别表示节点和道路，“ref”表示对应的ID号，“role”表示对应的类型是站点或站台。标签中的“k”表示属性，“v”表示值。当k=“route”是，v中的值可以代表道路类型，即公交车，地铁，人行道，有轨电车，火车等等。通过定位不同的标签还可以解析获取线路的方向，站点名称等多样化的信息。

图14: 

图15: OpenStreetMap官网上中属性值内容解析

图16: OpenStreetMap官网上中属性值内容解析

解析公共交通路网数据的步骤如下。首先，需要确定当前标签记录的是道路信息，即。接着，确定道路的类型，公交，地铁，无轨电车和电车，即。然后，收集标签中属性为“name”的值，以得到该条公共线路的起始站和终点站的站点信息。其次，遍历该标签下的子标签中记录着way和node的ID信息并保存。最后，根据存储的ID信息获取对应的way和node的经度和纬度并存储。图17展示的是公共交通路网数据提取步骤的流程图。

TIP: 由于openstreetmap是一款国外的开源地图数据。因此国内路网数据上会存在一些缺失的现象，导致线路信息不完整。 例如，上海的公共交通线路数据，在openstreetmap中仅有少数线路。下图所示：

真实的交通路网地图区别于游戏中的栅格地图不同之处在于，真实的交通路网中的子节点扩展方式是找寻该父节点的最近直系节点，而不是节点的上下左右方位上的四个节点。它们之间的距离也不是固定为1，而是需要通过两节点的经度和纬度进行计算。

在寻找的过程中将使用韩忠民提供的两点的经纬度计算距离的近似公式[16]。假设有A, B两地，它们的纬度和经度分别是(lat1, lon1)和(lat2, lon2)。公式中S表示两地之间的距离（千米），a表示AB两地纬度之差(lat1-lat2)，b表示AB两地经度之差(lon1-lon2)，6378.137表示地球的半径（千米）。使用该公式计算出的距离精度和谷歌地图的距离精度误差在正负0.2米之内[16]。

然后，遍历地图中所有节点的经度和纬度。将其与起始地和目的地的经度和纬度进行距离计算，找出一定范围内的所有节点，并使用起始列表和目的列表分别保存被找到的节点的ID。接着，将起始列表中的所有节点于目的列表中的所有节点进行组合。两节点组合结果将作为Map对象中的起始节点和目的节点代入A*算法中。Map对象中的节点（node）间的地理距离也将使用韩忠民的距离近似函数进行计算，然后作为Map对象中边（edge）的权重。将节点组合代入A*算法中进行最优路径的寻找，如果不存在路径则会抛出异常。但如果两个节点列表中的所有节点组合的经度和纬度都不能通过A*算法找到它们之间的最优路径，则会扩大附近节点的搜索范围，每次增加10米。直到两个节点列表中出现可以找到最优路径的节点组合，搜索范围不再扩大，程序进入下一步运算。随后，将所有没有抛出异常的节点组合存放在字典中，并找到其中路径方案距离最小的节点组合。输出其节点组合中A*算法返回的字典回溯中的节点ID。将这些节点按照输出顺序进行连接，即可得到两节点之间的最短路径。

参考文献：

8. 周小镜. 基于改进A*算法的游戏地图寻径的研究[D].西南大学,2011.

14. 严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报,2000(02):210-215.

16. 韩忠民.知经纬度计算两点精确距离[J].科技传播,2011(11):196+174.