A*算法在路径查找中的应用原理是怎样的？

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

应用A*路径搜索算法在画板上查找连接起始点和终止点之间的最短最直折线。环境：Visual Studio 2017 + .Net Framework 4.5，应用场景：在画板上查找起始点和目标点之间的最短最直路径。

应用A*路径搜索算法在画板上查找连接起始节点和终止节点之间的最短最直的折线。

环境：Visual Studio 2017 + .Net Framework 4.5

应用场景：在画板上查找起始点和目标点之间的最短最直路径，最后画出连接两个点之间的折线。

算法简介：A*算法是一种性能较高的最优路径搜索算法，由Stanford Research Institute(now SRI International)的Peter Hart，Nils Nilsson和Bertram Raphael于1968年发表。A*算法可看做是对Dijkstra算法的扩展和优化，其性能一般情况下比Dijkstra算法快得多。在本文的应用场景中，（根据测试）通常比Dijkstra算法快三倍以上，甚至可能比Dijkstra算法快十几倍甚至几十倍。

A*算法的应用范围也比较广泛，如机器人行走路径规划，游戏中的NPC移动计算等。

更详细的算法说明请参考维基百科A* search algorithm

实现思想：

1，通过Locator把起始点坐标和目标点坐标对齐到步长（step，默认为20,）的整数倍。这样，起始点和目标点就成了原来的起始点目标点的近似点。

2，把包含起始点和目标点的障碍物（如图中所示，为矩形框）排除掉，不然折线遇到障碍物无法通过。

下图中的矩形框的虚边为避障区域，为了防止折线和障碍物碰撞。