路径规划是运动规划中的一个主要问题，在很多领域中都有应用，高新领域有如机器人运动、无人机飞行、巡航导弹运动等；日常生活有如出行导航、路网规划等。在不同的场景中有不同的目标和约束，规划的方案会有所不同，也可能不止一个。比如说我们使用百度地图/高德地图等软件的导航功能时，软件返回的方案会包括时间最短、距离最短、红绿灯最少等方案，根据骑行、步行、自驾小汽车、公交等出行方式的不同又会有不同的方案（如下图），有时我们可能还要求所规划的路线必须经过某些指定地点。所以说路径规划本身的问题可以是非常复杂的，因为现实就是很复杂。

本项目以练手和规划算法学习为目标，以日常生活场景中的出行导航路径规划为例，搭建一个基本的路径规划框架，这个框架满足：

总体上分为四大模块：数据读取、路网模型构建、路径规划器构建与数据渲染。

包含如下文件：

main.cpp控制着程序的流程，完成四个主要任务：

将OSM数据读取到内存/程序中

将OSM数据组织成一个便于使用的数据结构：RouteModel

基于RouteModel创建一个路径规划器RoutePlanner，本项目中该规划器会对模型数据进行A*搜索，并将搜索结果存储在RouteModel中。也可以实现其他的规划器，实现不同的规划算法。

基于IO2D库渲染RouteModel中数据

model.h和model.cpp文件来自于IO2D的示例代码。其定义的是地图模型中地理要素的基本数据结构（Node、Way、Polygon、RoadWay及其他OSM对象中更抽象的基类）。

这些文件包含的类用于使用派生类RouteModel和RouteModel::Node来扩展model.h和model.cpp中的Model和Node数据结构。派生的RouteModel和RouteModel::Node类使用Model类和Node结构的所有公共方法和属性。

之所以要扩展现有的Model类和Node结构，是为了包含便于具体的路径搜索算法（如A*搜索）执行的有用的辅助方法和变量。以A*搜索算法为例，其派生路网模型现在允许节点类RouteModel::Node存储以下属性：

以下方法：

RouteModel类存储以下方法：

定义RoutePlanner类和A*搜索的方法。

render.h 和 render.cpp文件接收存储在RouteModel对象中的地图数据和规划好的路径数据，并将这些数据渲染成地图。

包括项目所引用的第三方代码：如用于测试的googletest框架、用于解析xml文件的pugixml。

测试用例。

A*算法执行流程：

基于GoogleTest实现单元测试。

OpenStreetMap项目是一个开源、合作的项目，其目的是创建免费的、以用户众源的方式生成的世界地图。这些地图类似于你可能在谷歌地图或手机上的苹果地图应用中使用的地图，但其数据完全是由自愿对当地环境进行调查的用户/志愿者所上传的。

OpenStreetMap数据可以有几种不同的格式。这个项目使用的数据是以OSM XML文件（.osm文件）的形式出现的，可以在OSM官网下载，这里给出示例如下：

主要有三种类型的要素：Node、Way、Relation

节点是OpenStreetMap数据模型中最基本的元素之一。每个节点表示一个单点，有一个标识符id、纬度lat和经度lon。节点元素中还有其他的XML属性，比如用户ID和节点被添加到数据集的时间戳。一个节点可以有多个标签（tag），用于提供额外的信息。

路径是一个有序的节点列表，代表地图中的一个线状地理要素，如道路、公园边界等。每条路至少有一个标签，表示该路的一些信息，每条路也至少属于一个Relation（关系）。路可能是开放的（首节点与末节点不同）也可能是闭合成环的（首节点与末节点为同一节点）。

关系是一种数据结构，它记录了数据元素之间的关系，由一个或多个标签和一个由一个或多个节点、路径或关系作为成员的有序列表组成，用于定义地理元素之间的逻辑或地理关系。OpenStreetMap wiki中的「关系」例子包括：

参考OSM wiki的一个例子: 如何绘制/记录一条河的地图？

河的两边有不同的河岸。在下面的图片中，节点被用来提供沿河两岸的控制点的坐标。然后使用路径将多个节点连接起来；一些路径构成了河流的封闭部分，在下图中被标记为 “Area”。另一种方式是用来表示河流中间的岛屿。然后用一个关系将这些方式分组，代表整个河流。

可想而知，如果要构建公交路线规划系统，那么可以使用Node模型表示公交站，以Way模型表示由一些（代表性）控制点形成的道路，由Relation模型表示由一系列道路/路径所形成的路线。

数据结构与算法基础课程中经典的最短路径求解算法如Dijkstra算法，虽然能够保证一定能够找到最短路径，但具有复杂度过高的致命缺陷，在大型的路网中几乎无法进行规划工作。所以如何改进路径规划算法的现实应用价值，使之既有较高的运行效率优化又不失准确性，便成为了一个老大难的问题。

启发式算法在很多实际问题中都有不错的表现：在合理时间内求得效果良好的解。在路径规划问题中自然也有人尝试这种思路。 一种比较简单的思路便是：Greedy Best First Search（这里将其简称为GBFS）。

Dijkstra算法在从当前节点向外探索的过程中，尽量选择离起点最近的节点作为下一步探索的点，搜索最短路径的整个过程可以总结为：徐图渐进，稳中求胜。Dijkstra算法最后一定能找到最短路径。（除非是Dijkstra处理不了的图，如边具有负权重）

而GBFS算法则采用了相反的思路，每次都以所能达到的离目的地更近的节点作为下一步探索目标，搜索路径的整个过程可以总结为：凌厉欺近，不留余地。GBFS算法是不一定保证能够找到最短路径的。

什么情况下GBFS算法不能找到最短路径？什么时候能找到？

最理想的情况下，地图/路网是无障碍物，此时凌厉欺近对方无可抵挡，一击可期必中。但是现实情况下地图/路网是复杂的，即便是游戏世界的地图也有很多地形起伏、障碍约束，此时通过GBFS搜索，很可能会在快到达终点时遇上过不去的坎，如下图：

A*算法是Dijsktra和GBFS的一种折中，其通过启发式的方式提高算法效率，且保证能寻找到一条较优的路径。

既然Dijsktra太猥琐，GBFS太莽撞，那么干脆将当前节点到目的地与到起点的距离/所需代价都考虑上，设计一条既可以提高效率又不至于做无用功的搜索策略。

记g(n)为从起点到节点n所需代价；h(n)为从节点n到终点的所需代价。A*搜索算法在每次搜索时选择使得f(n)=h(n)+g(n)最小的节点。可见，极端情况下当h(n)为0，则只有g(n)对搜索过程起作用，此时A*算法退化成Dijsktra算法，并且保证能够找到一条最短路径；当g(n)为0时，只有h(n)起作用，A*退化成GBFS算法，不保证能找到最短路径。我们既然选择了A*，就意味着我们已经认同了一个观点：我们只需要一条“好”的路径，而不是一条“完美”的路径。所以设计A*算法中的一个关键问题是：如何设计启发式函数h(n)、权衡速度与精度以达到在合理时间内获得可接受的规划结果？

启发式函数度量的是代价：从某一节点到运动到另一节点所需要耗费的资源或经历的路程。 以距离度量为例，常见的距离度量包括：

A*算法和GBFS算法中有一个重要组件：度量当前节点到目的地的代价。这实际上是一个估计，而不是有一个上帝视角告诉你当前节点距离终点的真实代价。实际上也正是因为信息不完全我们才需要设计一系列的策略来搜索从起始点到目的地的最短路径。

既然从当前节点到终点的真实代价不清楚，那么谁（代价函数）的估计与真实情况更吻合，算法就会工作得更好。经典的GBFS算法正是因为采用的启发式函数（欧式距离或曼哈顿距离度量）没能把障碍物（物理约束）所造成的“绕路成本”考虑在内而效果不好，这就是“错误”的启发所带来的副作用。

A*算法会依据总的启发值选择下一个探索的节点：f(n)=h(n)+g(n)。需要保证h(n)和g(n)在同一尺度，否则A*将会高估或者低估g或h之一，导致你得不到好的路径或者以极长的运行时间得到接近完美的路径。

一个集合容器用于存储待搜索节点 如果当前节点不是终点，那么需要将该节点周围的一些还没搜索过且值得在日后搜索的节点加入到容器中

计算节点的启发式值 g值和h值

对待搜索节点按f值排序 用于确定下一步应该检查哪个节点。如何使排序过程更高效又是一个问题，可以考虑使用优先队列。

实现多种图数据源的融合

实现地图交互

集成更多路径规划算法

A*搜索算法 Wiki

Introduction to A*

Amit’s A* Pages

Don’t follow the shortest path!

Path planning with modified A star algorithm for a mobile robot

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

Yet another bidirectional algorithm for shortest paths

Empowering A ∗ Search Algorithms with Neural Networks for Personalized Route Recommendation

Map representations