https://www.redblobgames.com/pathfinding/a-star/introduction.html
  
总结:
   通过这篇章你需要理解广度优先搜索算法、迪科斯彻算法、A*算法的区别和演进过程。  

https://www.gamedev.net/reference/articles/article2003.asp

总结：
1.你需要彻底掌握A*过程，大致如下：
    * 1. F = G + H:
         G:从起点到指定格子的代价，注意是以起点为参照目标。
           所以当前的格子的G代价 = 父节点G值 + 父节点移动到当前的G值
         H: 从当前点到最终点的代价。
            启发式算法值，本例采用曼哈顿算法： 忽略对角线运动，并忽略可能的任何障碍物，计算水平和垂直移动的方块的总数。
           
      A*算法在极罕见的情况下，寻找的路径不一定是最短，就是因为H值是一个启发式
      搜索算法，如果H不那么准高估了，那么就会导致路径不是最短的，但这种情况极少见。

    * 2. 把起点加入 open list 。
    * 3. 重复如下过程：
    * 		a.  遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
    * 		b.  把这个节点移到 close list 。
    * 		c.  对当前方格的 8 个相邻方格的每一个方格？
                ◆     本例中约定，不能斜对角直接穿过靠着墙下方的格子，因为会穿过墙壁的角落(认为整个格子都是不可走的)。
    * 			◆     如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
    * 			◆     如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
    * 			◆     如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。
    * 		 	       如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
                ◆     如果遍历完周围所有节点，发现从当前走到周围的节点，G值都没有变的更好，则停止当前节点所有操作（已经被加到关闭列表了）。
                       重新遍历开放列表理的节点，继续找F值最小的节点，重复上面操作。
    * 		d.  停止，当你：
    * 			◆     把终点加入到了 close list 中，此时路径已经找到了，或者
    * 			       查找终点失败，并且 open list 是空的，此时没有路径。
    * 4. 回溯，从终点遍历父节点直至最后的起点，即形成的路径。

考虑对地图进行预处理，以找出地图其余部分无法访问的区域。我称这些地区为“岛屿”。
实际上，它们可以是岛屿或任何其他被围起来且无法进入的区域。
A* 的一个缺点是，如果你告诉它寻找到这些区域的路径，它会搜索整个地图，只有在每个可访问的正方形/节点都已通过打开和关闭列表处理后才停止。
这会浪费大量的 CPU 时间。可以通过预先确定哪些区域不可访问（通过洪水填充或类似例程）、将该信息记录在某种数组中，
然后在开始路径搜索之前对其进行检查来防止它。

维护开放列表：这实际上是 A* 寻路算法中最耗时的元素之一。每次访问开放列表时，都需要找到 F 成本最低的方格。
有几种方法可以做到这一点。您可以根据需要保存路径项，并在每次需要找到最低 F 成本平方时简单地遍历整个列表。
这很简单，但对于长路径来说真的很慢。
这可以通过维护一个排序列表，并在每次需要最低 F 成本平方时简单地从列表中抓取第一项来改进。
A* 寻路中使用二叉堆，这种方法在大多数情况下至少快 2-3 倍，在更长的路径上速度快几何级数（快 10 倍以上）。

Dijkstra 算法：虽然 A* 通常被认为是最好的寻路算法，但至少还有一种其他算法有其用途——Dijkstra 算法。
Dijkstra 与 A* 基本相同，只是没有启发式（H 始终为 0）。因为它没有启发式，所以它通过在各个方向上均等地扩展来进行搜索。
正如您可能想象的那样，因此，Dijkstra 通常会在找到目标之前探索更大的区域。这通常使其比 A* 慢。

那么为什么要使用它呢？有时我们不知道我们的目标目的地在哪里。假设你有一个资源收集单位需要去获取某种资源。
它可能知道几个资源区域在哪里，但它想去最近的一个。在这里，Dijkstra 比 A* 好，因为我们不知道哪个最接近。
我们唯一的选择是重复使用 A* 来找到每个人的距离，然后选择那条路径。可能有无数类似的情况，我们知道我们可
能正在搜索的位置类型，想要找到最近的位置，但不知道它在哪里或哪个位置可能最近。

上面的链接文章都是英文，不要觉得是英文就看不下去，一定要多读英文文档。
现在越来越发现，很多优秀的文章都是英文，国内找不到。

是的，A*寻路算法在极限情况下确实会导致开放列表（Open List）中的节点过多。
开放列表存储了所有待处理的节点，随着搜索范围的扩大或地图的复杂性增加，开放列表中的节点数可能大幅增加，
影响算法的性能，增加内存使用，甚至导致系统崩溃。

1. 改进启发函数：
A*算法依赖启发函数（Heuristic Function）来估计当前节点到目标节点的最小代价。如果启发函数不够准确，可能导致搜索区域过大，开放列表膨胀。
可以通过优化启发函数来减少开放列表中的节点数量。
  • 曼哈顿距离（适合网格地图）：仅使用水平和垂直距离。
  • 欧几里得距离（适合连续空间）：使用直线距离的平方。
  • 对角距离（适合允许对角线移动的地图）：结合水平、垂直和对角线的距离。
  • 一致性启发：确保启发函数保持一致性（即满足三角不等式），避免开放列表过度膨胀。
2. 双向A*寻路:
双向A*通过同时从起点和终点向中间进行搜索，显著减少了搜索范围，从而减小了开放列表中的节点数量。
原理：同时执行两个A*算法，一个从起点开始，一个从终点开始，直到两个搜索区域相遇。这样可以有效减少搜索空间，尤其是在较大的地图中。
4. 平滑地图或简化搜索空间:
通过对地图或搜索空间进行平滑处理，可以减少搜索过程中生成的冗余节点，进而优化开放列表的大小。
  • 减少节点密度：在某些情况下，可以通过将节点之间的间隔加大来减少节点数量。
  • 层次化路径规划：将地图分为多个层次，首先在较粗略的层次上搜索路径，再在更细粒度的层次上进行局部优化。
5. 动态跳点搜索（Jump Point Search, JPS）
JPS 是对A*的优化，主要用于网格地图，它通过跳跃规则跳过不必要的节点，减少了开放列表中的节点数量。
  • 原理：JPS通过预先定义规则，跳过冗余的节点，只在关键的"跳跃点"处进行搜索，极大减少了节点数。