寻路算法
这部分相当不完整。
一般的图搜索算法可用于寻路。许多算法教科书描述了不使用启发式算法的图搜索算法（广度优先搜索、深度优先搜索、Dijkstra 算法）。阅读它们可能有助于理解 A*，它是 Dijkstra 的变体。许多 AI 教科书将介绍使用启发式算法的图搜索算法（最佳优先搜索，A*）。
对于非图搜索算法，请参阅John Lonningdal 的网页（通过 Wayback Machine，因为他的网站已停止运行）。
要查看 A* 是最优的证明，请参阅最小成本路径的启发式确定的正式基础。
要了解有关找到路径后的单位移动的更多信息，请参阅 Pottinger 关于单位移动和群组移动的文章。同样强烈推荐 Craig Reynold 的关于转向和植绒的页面。Geoff Howland 有一篇关于单位运动的很棒的文章。
基于网格的寻路竞赛结果论文（替代链接）描述了在未加权网格上运行的 A* 优化：收缩层次结构、子目标图、跳跃点搜索、可见性图、压缩路径数据库等。
Patrick Lester 有一个页面描述了一个两级探路者。分层规划 A* (HPA*) 可以将网格表示转换为简化图。
基于间隙的寻路用可以通过那里的对象的大小来注释图形。如果您希望小型单位能够通过一个区域而大型单位被阻挡，这将非常有用。
有一篇有趣的论文描述了如何找到最简单的路径而不是最短的路径。
这个 StackOverflow 问题包括 A* 的许多变体的摘要。
Triangulation A*使用三角形将多边形障碍物表示转换为导航网格，Triangulation Reduction A* 通过删除节点来简化生成的寻路图。
以下是我尚未归类的其他一些论文：
实时启发式搜索通过附加数据增强 A* 和其他算法，以加快寻路速度。
边缘搜索一次查看大量节点（边缘或边界）。它们大大降低了处理每个节点的成本。A* 一次对一个节点进行排序（从集合中插入和删除，或两者都进行），批量排序更快。但更快的根本不是排序。在边缘搜索正在处理的节点批次中，不需要对它们进行排序。缺点是必须处理更多节点，有时不止一次。但是，如果您可以使处理它们的成本非常低，那么处理大量节点就可以了。
收缩层次结构（长篇论文）可以通过添加快捷边来更快地找到路径。相关工作部分也是很好的读物，它总结了地标、弧形标志、交通节点、高速公路层次结构和其他方法的 A* 改进。
弧标志（自我注意：此处需要更好的链接）限制在主寻路循环中扩展的边集。首先将世界划分为多个区域，然后预先计算哪些边是通往每个区域的最短路径的一部分。与其查看邻居的所有边，不如只查看作为到达目标所在区域的最短路径的一部分的边。Steve Rabin 将这种方法称为“目标边界”。
偏置成本寻路改变了其他单位将要移动的区域的移动成本，以便后续路径避免与这些单位发生碰撞。
Parallel Ripple Search 专为多核寻路而设计，没有 A* 的排序瓶颈。
Corridor Maps是一种构建寻路图的方法，可以大大减少节点的数量，尤其是在有很多走廊的地图中。
学习实时 A*在探索地图时更新启发式。优先学习实时 A*优先搜索有利于学习更多的领域。
压缩路径数据库测试网格上所有对最短路径（Floyd-Warshall 或 Johnson 算法）的压缩效果。如果您使用网格并且地图没有变化，则适用；我怀疑您最好先减小图形大小。
概率路线图 (PRM)从多边形障碍图构建寻路图。