路径查找
广度优先（Breadth First）: 这种算法就像洪水（Flood fill）一样向外扩张
Dijkstra 算法：需要计算每一个节点距离起点的总移动代价。同时，还需要一个优先队列结构。对于所有待遍历的节点，放入优先队列中会按照代价进行排序。
最佳优先搜索（Best First）：以每个节点到达终点的距离作为优先级，每次始终选取到终点移动代价最小（离终点最近）的节点作为下一个遍历的节点
A* 算法：f(n)=g(n)+h(n) // 不一样的场景不同的优先级计算方法会有区别，给出一个近似解而不是保证最佳解
- f(n) 是节点 n 的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。
- g(n) 是节点 n 距离起点的代价。
- h(n) 是节点 n 距离终点的预计代价，这也就是A*算法的启发函数。
A* 算法在运算过程中，每次从优先队列中选取 f(n) 值最小（优先级最高）的节点作为下一个待遍历的节点。另外，A* 算法使用两个集合来表示待遍历（有优先级）的节点，与已经遍历过的节点，这通常称之为 open_set 和close_set。
完整的A*算法描述如下：
* 初始化open_set和close_set；
* 将起点加入open_set中，并设置优先级为0（优先级最高）；
* 如果open_set不为空，则从open_set中选取优先级最高的节点n：
* 如果节点n为终点，则：
* 从终点开始逐步追踪parent节点，一直达到起点；
* 返回找到的结果路径，算法结束；
* 如果节点n不是终点，则：
* 将节点n从open_set中删除，并加入close_set中；
* 遍历节点n所有的邻近节点：
* 如果邻近节点m在close_set中，则：
* 跳过，选取下一个邻近节点
* 如果邻近节点m也不在open_set中，则：
* 设置节点m的parent为节点n // 最终生成最短路径
* 计算节点m的优先级
* 将节点m加入open_set中
启发函数会影响 A* 算法的行为。
- 在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
- 如果 h(n) 始终小于等于节点 n 到终点的代价，则 A* 算法保证一定能够找到最短路径。但是当 h(n) 的值越小，算法将遍历越多的节点，也就导致算法越慢。
- 如果 h(n) 完全等于节点 n 到终点的代价，则 A* 算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
- 如果 h(n) 的值比节点 n 到终点的代价要大，则 A* 算法不能保证找到最短路径，不过此时会很快。
- 在另外一个极端情况下，如果 h(n) 相较于 g(n) 大很多，则此时只有 h(n) 产生效果，这也就变成了最佳优先搜索。
网格形式的图，有以下这些启发函数可以使用：
- 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）。
- 如果图形中允许朝八个方向移动，则可以使用对角距离。
- 如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。
