A*算法在寻路中的应用原理及详细解析是怎样的？

本文共计2675个文字，预计阅读时间需要11分钟。

前言：在实际开发中，我们会经常用到的寻路算法，例如在MMOARPG游戏中，魔兽的行走模拟。为了模拟真实人的行走体验，会选择最近的路径到达目标地点，同时避开高山或水域，绕过障碍物。

前言

在实际开发中我们会经常用到寻路算法，例如MMOARPG游戏魔兽中，里面的人物行走为了模仿真实人物行走的体验，会选择最近路线达到目的地，期间会避开高山或者湖水，绕过箱子或者树林，直到走到你所选定的目的地。这种人类理所当然的行为，在计算机中却需要特殊的算法去实现，常用的寻路算法主要有宽度最优搜索^[1]、Dijkstra算法、贪心算法、A*搜索算法、B*搜索算法^[2]、导航网格算法、JPS算法^[3]等，学习这些算法的过程就是不断抽象人类寻路决策的过程。本文主要以一个简单空间寻路为例，对A*算法进行分析实现。

介绍

A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的常用启发式算法，算法中的距离估算值与实际值越接近，最终搜索速度越快。之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

问题

在包含很多凸多边形障碍的空间里，解决从起始点到终点的机器人导航问题。